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?

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.