Recursively populate a tree-graph

Question

I have a data structure where node can have multiple parents.
I have a list of nodes that i want to insert to a tree. Node in list contains the data and a sub list of it's parents.

I want to build a tree from this list.

private class Treenode {

        private List<Treenode> children;
        private List<Treenode> parents;

        public List<Treenode> getChildren() {
            return children;
        }

        public List<Treenode> getParents() {
            return parents;
        }

        private Info data;


        public Info getData() {
            return data;
        }

        public void setData(Info data) {
            this.data = data;
        }

        public Treenode() {
            children = new ArrayList<Treenode>();
            parents = new ArrayList<Treenode>();
        }

        public Treenode(Info data) {
            children = new ArrayList<Treenode>();
            parents = new ArrayList<Treenode>();
            this.data = data;
        }

        public boolean addChild(Treenode n) {
            return children.add(n);
        }

        public boolean removeChild(Treenode n) {
            return children.remove(n);
        }
        public boolean addParent(Treenode n) {
            return parents.add(n);
        }

        public boolean removeParent(Treenode n) {
            return parents.remove(n);
        }



    }


private void scanListAndAddToTree(final List list,Treenode parent){

        for (Iterator iter = list.iterator(); iter.hasNext();) {
            Info info = (Info) iter.next();
            String [] parents = info.getParents();
            if(parents==null){ //no parents
                Treenode newNode = new Treenode(info);
                parent.addChild(newNode);
                scanTree(list,newNode);
            } else

            for (int i = 0; i < parents.length; i++) {
                if (parents[i].getID.equals(parent.data.getID())){
                    Treenode newNode = new Treenode(info);
                    parent.addChild(newNode);
                    scanTree(list,newNode);
                }
            }           

}

But my code is wrong :(

The recursion never stops and re-adds same nodes

Answer 1

If you make your class bullet proof as follows, a list insertion, done by item is no problem.

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public class GraphNode<D> {

    private D data;
    private Set<GraphNode<D>> ins = new HashSet<>();
    private Set<GraphNode<D>> outs = new HashSet<>();

    public GraphNode(D data) {
        this.data = data;
    }

    public D getData() {
        return data;
    }

    public void setData(D data) {
        this.data = data;
    }

    public Set<GraphNode<D>> getIns() {
        return Collections.unmodifiableSet(ins);
    }

    public Set<GraphNode<D>> getOuts() {
        return Collections.unmodifiableSet(outs);
    }

    public void addIn(GraphNode<D> node) {
        if (node == null) {
            throw new NullPointerException(); // Never add null.
        }
        if (ins.add(node)) {
            node.outs.add(this);
        }
    }

    public void addOut(GraphNode<D> node) {
        if (node == null) {
            throw new NullPointerException(); // Never add null.
        }
        if (outs.add(node)) {
            node.ins.add(this);
        }
    }
}

Notes

• This is written in Java 7, for older Java change <> to <GraphNode<D>>.
• I have used the name Graph, as with multiple parents Tree is a misnomer.
• Parametrized the Info class as <D> so one can reuse the class.
• Getters for collections made unmodifiable.
• addIn and addOut garantuee a correct structure.
• removeIn/removeOut "left as excercise".
• I have used Sets relying on Object (pointer) equality.

---

public static class Info {
    private String id;
    private String[] parents;

    private String getID() {
        return id;
    }

    public String[] getParents() {
        return parents;
    }
}

public static class TreeNode extends GraphNode<Info> {
    public TreeNode(Info info) {
        super(info);
    }
}

private void insertGraph(Map<String, TreeNode> allNodes, List<Info> insertList) {
    for (Info info : insertList) {
        TreeNode newNode = new TreeNode(info);
        allNodes.put(info.getID(), newNode);
    }
    for (TreeNode node : allNodes.values()) {
        for (String parentID: node.getData().getParents()) {
            TreeNode parentNode = allNodes.get(parentID);
            parentNode.addOut(node);
        }
    }
}

private TreeNode scanTree(Info rootInfo, List<Info> insertList) {
    Map<String, TreeNode> allNodes = new HashMap<>();
    insertList.add(rootInfo);
    insertGraph(allNodes, insertList);
    return allNodes.get(rootInfo.getID());
}

As there is no guarantee to have a single tree with a parent of all, and the Info already contains the structure, recursion is not needed, but a collection of the nodes is needed. As an Info might refer to an ID for which no TreeNode is defined, one needs two phases/fors.