StrayChild01 StrayChild01 - 28 days ago 9
Java Question

Dynamically create a tree graph and walk around it

I have a graph which will be fed using an external source. So far, a rough structure is something like this:

TreeGraph, shown this way to fit
. In there, the red lines represent siblings of the node, which might be dependency but not a parenthood itself. It might or might not exist.

Currently, I have this code for each node:




public class TreeNode {
private int id;
private int container;
private int status;
private int value;
private boolean visited;
private String node_name;
private ArrayList children = new ArrayList();
private ArrayList siblings = new ArrayList();
private ArrayList parents = new ArrayList();

public TreeNode()
{
this.id = 0;
this.status = 0;
this.visited = false;
this.node_name="";
}
//Getters and setters below.
//parents/siblings/children are added through addParent(treeNode);
}




Then, I have this code to set the values:




public class TreeSetter {

public static void main(String[] args) {

TreeNode A = new TreeNode();
TreeNode B = new TreeNode();
TreeNode C = new TreeNode();
TreeNode D = new TreeNode();
TreeNode E = new TreeNode();
TreeNode F = new TreeNode();
TreeNode G = new TreeNode();
TreeNode H = new TreeNode();

A.setId(1);
A.setNode_name("A");
A.setStatus(1);
A.addParent(null);

B.setId(2);
B.setNode_name("B");
B.setStatus(1);
B.addParent(A);
A.addChildren(B);

C.setId(3);
C.setNode_name("C");
C.setStatus(1);
C.addParent(A);
A.addChildren(C);

D.setId(4);
D.setNode_name("D");
D.setStatus(1);
D.addParent(A);
A.addChildren(D);

E.setId(5);
E.setNode_name("E");
E.setStatus(1);
E.addParent(B);
E.addParent(C);
E.addParent(D);
B.addChildren(E);
C.addChildren(E);
D.addChildren(E);
E.addSiblings(F);
E.addSiblings(G);
E.addSiblings(H);

F.setId(6);
F.setNode_name("F");
F.setStatus(1);
F.addParent(B);
F.addParent(C);
F.addParent(D);
B.addChildren(F);
C.addChildren(F);
D.addChildren(F);
F.addSiblings(E);
F.addSiblings(G);
F.addSiblings(H);

G.setId(7);
G.setNode_name("G");
G.setStatus(1);
G.addParent(B);
G.addParent(C);
G.addParent(D);
B.addChildren(G);
C.addChildren(G);
D.addChildren(G);
G.addSiblings(E);
G.addSiblings(F);
G.addSiblings(H);

H.setId(8);
H.setNode_name("H");
H.setStatus(1);
H.addParent(B);
H.addParent(C);
H.addParent(D);
B.addChildren(H);
C.addChildren(H);
D.addChildren(H);
H.addSiblings(E);
H.addSiblings(F);
H.addSiblings(G);
//Set all other nodes

//Set all node values.
}
}




So, what I need is, let's say that given H, I need to know:


  • What is the value from H -> I -> L (H+I+L)

  • Who will be affected if H changes. H -> B,C,D -> A

  • What are the dependencies of H? F, G, E.



Given this, my troubles are:


  • How do I create the tree dynamically? For example, let's say that instead of 12 nodes, you have 1000. Using my code, I will need a lot of lines just to set the values and relations because I am creating every single object by hand. Should I use reflection, factory paradigm to create the 1000 objects?

  • How do I walk the tree? For example, given D, move D->H->I->L (and so on).
    I know recursion would be the easiest and cleanest way to do it, but I don't know how to implement it :(


Answer

How do I create the tree dynamically:

public class Tree {

    private class Node {
        public int value;
        public List<Node> = new children ArrayList<Node>();
        public List<Node> = new parents ArrayList<Node>();
        public static final INFINITY = Integer.MAX_VALUE;

        public void addChild(Node n) {
            children.add(n);
        }

        public void addParent(Node n) {
            parents.add(n);
        }

        public int getValue() {return value;}

        //What is the value from H -> I -> L (H+I+L):
        int getValueToNode(Node Destination, HashSet<Node> s) {
           int minValue = INFINITY;
           int value = 0;

           if(s.contains(this)) return INFINITY; //we already checked this
           s.add(this);
           if(this.equals(Destination)) return Destination.value();

           for(int i = 0; i < children.size(); i++) {
               Node c = children.get(i);
               int value = c.getValueToNode(Destination);
               if (value != Integer.MAX_VALUE && value < minValue) {
                   minValue = value + this.getValue();
               }
           }

           for(int i = 0; i < parents.size(); i++) {
               Node p = parents.get(i);
               value = p.getValueToNode(Destination);
               if (value != Integer.MAX_VALUE && value < minValue) {
                   minValue = value + this.getValue();
               }
           }
           return minValue;
        }

        //Who will be affected if H changes. H -> B,C,D -> A
        public int getDependency(ArrayList<Node> affected) {
          for(int i = 0; i < children.size(); i++) {
               Node c = children.get(i);
               affected.add(c);
           }

           for(int i = 0; i < parents.size(); i++) {
               Node p = parents.get(i);
               affected.add(p);
           }
        }

        //What are the dependencies of H? F, G, E.
        List<Node> getDependency() {
           List<Node> dependency = new ArrayList<Node>();
           for(int i = 0; i < parents.size(); i++) {
               Node p = parents.get(i);
               for(int j= 0 ; j < p.children.size(); j++) {
                   Node c = p.children.get(i);
                   if(!c.equals(this)) dependency.add(c);
               }
           }
           return dependency;
        }
    }

    //data here.
    private Map<String, Node> mapping = new HashMap<String, Node>();

    public connectParentToChild(String parent, String child) {
        Node p = getNode(parent);
        Node c = getNode(child);
        p.addChild(c);
        c.addParent(p);
    }

    public int getValue(String first, String second) {
        a = getNode(first);
        b = getNode(second);
        HashSet<Node> s = new HashSet<Node>();
        return a.getValueToNode(b, s);
    }

    private Node getNode(String s) {
        if(!mapping.containsKey(s)) {
           mapping.put(s, new Node(...));
        }
        return mapping.get(s);
    }

    //members here.
}

This is a simple way to dynamically add nodes.

public static void main(String[] args) {
    Tree t;
    t.connectParentToChild("A", "D");
    t.connectParentToChild("A", "B");
    t.connectParentToChild("A", "C");
    t.connectParentToChild("B", "C");
    t.connectParentToChild("B", "H");
    t.connectParentToChild("B", "F");
    t.connectParentToChild("B", "E");
    //Set all other nodes
    t.getValue("H", "L");
}