Different ways to implement DAGs in java

Question

I am implementing DAG and wondering whether the following is the only way to represent it in Java:

class Node{
List<Node> parents;
List<Node> successors;
int value; }
class DAG{
Node root; // assuming only one root exists
}

I am looking for something simpler without two lists for parents and children.
is it possible? Also I have an issue with this representation that if I reached a particular node x and wanted the path from x to the root node, how I can find it without going through all the parents set?

• Doron Manor: Take a look at this thread stackoverflow.com/questions/144642/…

Answer 1

To simplify your directed graph structure, it is not necessary for nodes to have links back to their ancestors. I would also place the Node class inside your DAG class. Conceptually this representation makes more sense anyway since in a directed graph, if node A links to node B, there need not be a path from B to A. In fact there cannot be a path in both directions because that would be a cycle.

public class DAG {
 Node root; // assuming only one root exists
 public static class Node{
 List<Node> successors;
 int value; 
 }
}

To find the path from the root to a particular node, you would need to run an algorithm to search through the graph. That does mean possible visiting the other nodes in the graph, probably recursively, until you locate the given node. If you want to avoid repeating these sorts of calculations, you could also store the path from the root to a given node with something like this:

class PathMap {
 HashMap<DAG.Node, List<DAG.Node> > pathMap;
 public List<DAG.Node> getPathFromRoot(DAG.Node n) {
 List<DAG.Node> pathFromRoot = pathMap.get(n);
 return pathFromRoot;
 }
}

Now there may be several different paths from the root to a given node. In that case, you may want to implement a shortest-path-first algorithm to find and store the optimal path. See this dzone article for pseudocode.

• Frank Hopkins: Whether or not it is reasonable to drop the parents list depends on your typical use case. As Thorn pointed out, in principle you can drop the parents in a DAG as they are implicitly given by the children (or the parents). However, if in your applications you often need to find some ancestor(s) of a given node, the parent lists might help to implement a fast algorithm to do that (as you would not always need to start from the root and potentially traverse the whole graph, instead going backwards as far as needed from the given node).