Implementing a graph with multiple parents and children

Question

I need to implement a tree-like data structure where each node has multiple parents and children and therefore multiple roots.

New nodes will only be added to the tree with as either a root with no parents or a child of one or more parents.

Nodes will not start with children, but any existing node can gain another child node with any number of other parent nodes

It looks like you're on your way to implementing this yourself - good work! But if you need more information about what you can do with your tree-not-a-tree - consider reading about graph data structures, which is what this is. (There are multiple ways to implement a graph, they each have their pros and cons.) — davidbak
This is a graph, not a tree. If you want to preserve the distinction between "parent" and "child" then it is a directed graph. If you want to preserve the property that no node is an ancestor or descendant of itself, then it is a directed acyclic graph. It's better to use the proper terminology so that people will understand your question, but also so that you can search for existing solutions more easily. en.wikipedia.org/wiki/Directed_acyclic_graph — kaya3
Thanks for clarifying that my tree is a not a tree but a graph. A directed acyclic graph with multiple roots is exactly what I am trying to implement, and I didn't realize this was not a tree. — stzups
No problem. I added some tags which might help people find your question. — kaya3

stzups stzups · Accepted Answer · 2020-01-26T18:02:18

I was able to create a Node class and Graph class. I gave each Node a List<Node> of their parent and child nodes.

Each Node keeps track of its own direct children and parents.

Node implementation

public class Node<T>{
    private T data;
    private List<Node<T>> parents;
    private List<Node<T>> children = new ArrayList<>();//this can be initialized because a node will not start with children
    public Node(T data){//adding a node without parents
        this.data = data;
        parents = new ArrayList<>();//make parents an empty ArrayList so other methods won't break with a null value
    }
    public Node(T data, List<Node<T>> parents){//adding a node with parents
        this.data = data;
        this.parents = parents;
    }

    //search methods
    public List<Node<T>> getChildren(){return children;}//return only direct children
    public List<Node<T>> getChildren(int level){return getChildren(new ArrayList<>(Collections.singletonList(this)),new ArrayList<>(),level);}//convenience method to find only this node's children to a certain level
    public List<Node<T>> getChildren(List<Node<T>> find, List<Node<T>> found, int level){//level can be -1 to search through all children or a positive integer to only search the first n level of children.
        if(level!=0){//setting level to -1 will never stop the search until all children have been found because level only goes down, because the level will never reach zero
            for(Node<T> node:find){//can find the children of multiple nodes
                if(node.hasChild()) {
                    for (Node<T> child : node.getChildren()) {
                        if (!found.contains(child)) {//trees can intersect, so the child may have already been found, so only add if it hasn't
                            found.add(child);
                        }
                    }
                    getChildren(node.getChildren(),found,level--);//recursively find the remaining children of the current node
                }
            }
        }
        return found;
    }
    //a method that finds parents can be implemented by modifying the getChildren() methods

    //examples of other methods that can be added
    public T getData(){return data;}
    public boolean hasChild(){return children.size()>0;}
    void addChild(Node<T> node){children.add(node);}
    void addChildren(List<Node<T>> nodes){children.addAll(nodes);}
    public List<Node<T>> getParents(){return parents;}
    public boolean hasParent(){return parents.size()>0;}
    void addParent(Node<T> node){parents.add(node);}
    void addParent(List<Node<T>> nodes){parents.addAll(nodes);}
}

The Graph class is only used for keeping track of the graph's roots. A root is simply a Node with no parents. The scopes of each method can be adjusted for your specific use case. This class is meant to be extended by a more specific class that includes methods for dealing with your specific data type.

Graph implementation:

public class Graph<T> {
    private List<Node<T>> roots;
    protected Tree(List<Node<T>> roots){this.roots = roots;}//Graph class can be initialized with or without existing roots 
    protected Tree(){roots = new ArrayList<>();}
    public List<Node<T>> getRoots(){return roots;}
    public List<Node<T>> getAllNodes(){
        List<Node<T>> nodes = roots.get(0).getChildren(roots,new ArrayList<>(),-1);//loop through all roots with an empty list for nodes already found, because no nodes have been found yet
        nodes.addAll(roots);
        return nodes;
    }
    public void addNode(Node<T> node){
        for(Node<T> parent:node.getParents()){//for each parent node add this node as their child
            parent.addChild(node);
        }
        if(!node.hasParent())roots.add(node);
    }
    public void addNodes(List<Node<T>> nodes){
        for(Node<T> node:nodes){
            addNode(node);
        }
    }
}

When adding a new Node with parents, the Graph class gets the parents and adds the Node as a child of those parents so the parent nodes know they have child node.

Implementing a graph with multiple parents and children

1 Answers