Draw graph using GraphML and yEd graph editor

Graph theory  http://algs4.cs.princeton.edu/41graph/

GraphML http://graphml.graphdrawing.org/
GraphML Primer http://graphml.graphdrawing.org/primer/graphml-primer.html

yEd graph editor
http://www.yworks.com/en/products/yfiles/yed/
http://docs.yworks.com/yfiles/doc/developers-guide/graphml.html


Graph stored in simple text format

user11 group1
user12 group1
user21 group2
user22 group2
user31 group3
user32 group3
user41 group4
user42 group4
group1 orgunit1
group2 orgunit1
group3 orgunit2
group4 orgunit2  

Java code to create GraphML file from graph stored in simple text format
( using algs4 libs - can beeasily rewritten to use  standard Java IO)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Out;
import edu.princeton.cs.algs4.StdOut;

public class TestDrawGraph {

    public static void main(String[] args) {

        Map<String, Integer> principals = new HashMap<>();
        Map<Integer, String> revert_principals = new HashMap<>();
        Map<Integer, List<Integer>> graph = new HashMap<>();

        In in = new In(args[0]);

        int V = 0;

        while (in.hasNextLine()) {
            String v = in.readString();
            String w = in.readString();

            // StdOut.println("v=" + v + " w=" + w);

            if (!principals.containsKey(v)) {
                principals.put(v, V++);
                revert_principals.put(principals.get(v), v);
                graph.put(principals.get(v), new ArrayList<Integer>());
            }
            if (!principals.containsKey(w)) {
                principals.put(w, V++);
                revert_principals.put(principals.get(w), w);
                graph.put(principals.get(w), new ArrayList<Integer>());
            }

            graph.get(principals.get(v)).add(principals.get(w));

        }

        Out out = new Out(args[0] + ".graphml");

        out.print("<graphml xmlns=\"http://graphml.graphdrawing.org/xmlns\" "
                + " xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" "
                + " xmlns:y=\"http://www.yworks.com/xml/graphml\" "
                + " xmlns:yed=\"http://www.yworks.com/xml/yed/3\" "
                + " xsi:schemaLocation=\"http://graphml.graphdrawing.org/xmlns"
                + "http://www.yworks.com/xml/schema/graphml/1.1/ygraphml.xsd\"> ");

        out.print(
                " <key for=\"node\" id=\"d6\" yfiles.type=\"nodegraphics\"/> ");

        out.print("  <graph id=\"G\" edgedefault=\"undirected\">\n");

        for (String node : principals.keySet()) {
            out.printf(
                    " <node id=\"%s\">\n" + "<data key=\"%s\">\n"
                            + "<y:GenericNode configuration=\"com.yworks.entityRelationship.small_entity\">\n"
                            + "\t<y:Geometry height=\"40.0\" width=\"80.0\" x=\"383.0\" y=\"227.0\"/>\n"
                            + "\t<y:Fill color=\"#E8EEF7\" transparent=\"false\"/>\n"
                            + "\t<y:BorderStyle color=\"#000000\" type=\"line\" width=\"1.0\"/>\n"
                            + "\t<y:NodeLabel>%s</y:NodeLabel>\n"
                            + "</y:GenericNode>\n" + "</data>\n </node>\n",
                    node, "d6", node);
        }

        for (Map.Entry<Integer, List<Integer>> me : graph.entrySet()) {
            for (Integer w : me.getValue()) {
                out.printf(" <edge source=\"%s\" target=\"%s\"/>\n",
                        revert_principals.get(me.getKey()),
                        revert_principals.get(w));

            }
        }

        out.print("  </graph>\n" + "</graphml>\n");

        out.close();

        StdOut.print("Created" + args[0] + ".graphml");

    }

}

Generated graph displayed in yEd

 http://www.summa-tech.com/blog/2011/04/12/a-visual-maven-dependency-tree-view
 In yEd modify the layout of the graph using menu
  Select Layout > Hierarchical > Orientation > Left to Right > OK 

Graph using Bottom -> Top

Graph using Tree -> Ballon

GraphML file created

<graphml xmlns="http://graphml.graphdrawing.org/xmlns"  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"  xmlns:y="http://www.yworks.com/xml/graphml"  xmlns:yed="http://www.yworks.com/xml/yed/3"  xsi:schemaLocation="http://graphml.graphdrawing.org/xmlnshttp://www.yworks.com/xml/schema/graphml/1.1/ygraphml.xsd">  <key for="node" id="d6" yfiles.type="nodegraphics"/>   <graph id="G" edgedefault="undirected">
 <node id="user11">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>user11</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="user22">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>user22</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="user21">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>user21</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="user32">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>user32</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="user31">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>user31</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="user42">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>user42</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="user41">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>user41</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="user12">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>user12</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="group4">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>group4</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="group3">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>group3</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="group2">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>group2</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="group1">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>group1</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="orgunit1">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>orgunit1</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <node id="orgunit2">
<data key="d6">
<y:GenericNode configuration="com.yworks.entityRelationship.small_entity">
    <y:Geometry height="40.0" width="80.0" x="383.0" y="227.0"/>
    <y:Fill color="#E8EEF7" transparent="false"/>
    <y:BorderStyle color="#000000" type="line" width="1.0"/>
    <y:NodeLabel>orgunit2</y:NodeLabel>
</y:GenericNode>
</data>
 </node>
 <edge source="user11" target="group1"/>
 <edge source="group1" target="orgunit1"/>
 <edge source="user12" target="group1"/>
 <edge source="user21" target="group2"/>
 <edge source="group2" target="orgunit1"/>
 <edge source="user22" target="group2"/>
 <edge source="user31" target="group3"/>
 <edge source="group3" target="orgunit2"/>
 <edge source="user32" target="group3"/>
 <edge source="user41" target="group4"/>
 <edge source="group4" target="orgunit2"/>
 <edge source="user42" target="group4"/>
  </graph>
</graphml>

Tree traversal

http://en.wikipedia.org/wiki/Tree_traversal
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search

Tree traversal in various languages
http://rosettacode.org/wiki/Tree_traversal#Java

Algorithms
http://algs4.cs.princeton.edu/home/
Graphs
http://algs4.cs.princeton.edu/40graphs/
Directed Graphs

http://algs4.cs.princeton.edu/42directed/

Java Data Structure: A Generic Tree

http://sujitpal.blogspot.com/2006/05/java-data-structure-generic-tree.html

Generic Node

public class Node<T> {
 
    public T data;
    public List<Node<T>> children;
    public List<Node<T>> parents;

Non-generic node

package dave;

/**
 * Non-generic subclass of Node<String>
 */
public class DaveNode extends Node<String> {
    public DaveNode() {
        super();
    }
}

Walk using stack

 /**
   *   
   * @param element
   * @return set of all nodes
   */
  public List<Node<T>> walk(Node<T> element){
      
      List<Node<T>> out = new ArrayList<Node<T>>();
      
      Queue<Node<T>> q = new LinkedList<Node<T>>();
      q.add(element);
      
      while(!q.isEmpty()){
          Node<T> x = q.poll();
          out.add(x);
          
          for(Node<T> child : x.getChildren()){
              q.add(child);
          }
      }
      
      return out;
      
  }

Walk from bottom up

  /**
   *   
   * @param element
   * @return set of all upper nodes
   */
  public Collection<Node<T>> pathBottomUp(Node<T> element){
      
      Set<Node<T>> out = new LinkedHashSet<Node<T>>();
      
      Queue<Node<T>> q = new LinkedList<Node<T>>();
      q.add(element);
      
      while(!q.isEmpty()){
          Node<T> x = q.poll();
          out.add(x);
          
          for(Node<T> parent : x.getParents()){
              q.add(parent);
          }
      }
      
      return out;
      
  }

Construct tree

package dave;


public class WalkTree {

    public static void main(String[] args) {
        
        DaveTree daveTree = new DaveTree();
        
        DaveNode daveNode = getDaveNode("1");
        
        DaveNode daveNode11 = getDaveNode("1.1");
        DaveNode daveNode12 = getDaveNode("1.2");
        DaveNode daveNode13 = getDaveNode("1.3");
        
        DaveNode daveNode131 = getDaveNode("1.3.1");
        DaveNode daveNode132 = getDaveNode("1.3.2");
        
        daveNode.addChild(daveNode11);
        daveNode.addChild(daveNode12);
        daveNode.addChild(daveNode13);
        
        daveNode12.addChild(daveNode131);
        
        daveNode13.addChild(daveNode131);
        daveNode13.addChild(daveNode132);
        
                
        daveTree.setRootElement(daveNode);
        
        System.out.println(daveTree.toList());
                
        Node<String> root = daveTree.getRootElement();
        
        System.out.println("walk:" + daveTree.walk(root));
        
        System.out.println("pathBottomUp:" +daveTree.pathBottomUp(daveNode131));

    }
    
    private static DaveNode getDaveNode(String profileName){
        
        DaveNode daveNode = new DaveNode();
        
        daveNode.setData(profileName);
        
        return daveNode;
        
    }

}

Program output

[{1,[1.1,1.2,1.3]}, {1.1,[]}, {1.2,[1.3.1]}, {1.3.1,[]}, {1.3,[1.3.1,1.3.2]}, {1.3.1,[]}, {1.3.2,[]}]
walk:[{1,[1.1,1.2,1.3]}, {1.1,[]}, {1.2,[1.3.1]}, {1.3,[1.3.1,1.3.2]}, {1.3.1,[]}, {1.3.1,[]}, {1.3.2,[]}]
pathBottomUp:[{1.3.1,[]}, {1.2,[1.3.1]}, {1.3,[1.3.1,1.3.2]}, {1,[1.1,1.2,1.3]}]