title: Java, connected edges in a directed graph so that the graph is traversable
body: <p>I am producing (or trying to) a directed graph in java made up of <code>Node</code>s and <code>Edge</code>s. This graph represents a dependency tree of what I call Modules (Modules play some role in my program). Certain modules need to be ran before others within the program and I use a directed graph to represent this. Modules (and <code>Node</code>s) know which other modules must come before them. </p>
  
  <p>Currently I take and read a directory and get a ArrayList of Modules and in turn make that into an ArrayList of <code>Node</code>s. My problem is connecting these <code>node</code>s with the <code>node</code> classes <code>addEdge(..)</code> function. When I call my function (code below) <code>connectNodes(..)</code> I want to create edge objects between the <code>node</code>s so that I can traverse the entire tree, going from <code>node</code>s to <code>node</code>s using <code>edge</code>s. It seems the the way in which my <code>connectNodes(..)</code> method works I cannot do this. </p>
  
  <p>The problem is that the <code>outEdge</code> and <code>inEdge</code> <code>HashSet</code> of each <code>Node</code> object returned from <code>connectNodes</code> correctly points to <code>Node</code> with the proper name (representing their upper and lower dependencies), but those <code>Node</code> objects do not have their <code>inEdge</code> and <code>outEdge</code> sets filled to point to the <code>Node</code> above and below them in the tree. </p>
  
  <p>So it is as if, each end of every edge points to a copy of another Node object with the proper info but the wrong (by wrong I mean none) edge sets. They should point to the other Node objects in the ArrayList. </p>
  
  <p>Node.java</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.HashSet;
  
  public class Node
  {
      public String name;
      public HashSet&lt;Edge&gt; inEdges;
      public HashSet&lt;Edge&gt; outEdges;
      public ArrayList&lt;String&gt; deps;
  
      public Node(String name, ArrayList&lt;String&gt; deps) {
          this.name = name;
          inEdges = new HashSet&lt;Edge&gt;();
          outEdges = new HashSet&lt;Edge&gt;();
  
          this.deps = deps;
      }
      public Node addEdge(Node node){
          Edge e = new Edge(this, node);
          outEdges.add(e);
          node.inEdges.add(e);
          return this;
      }
      @Override
      public String toString() {
          return name;
      }
  
      //Used to copy a given node
      public Node(Node inNode)
      {
          this.name = inNode.name;
          this.inEdges = (HashSet&lt;Edge&gt;)inNode.inEdges.clone();
          this.outEdges = (HashSet&lt;Edge&gt;)inNode.outEdges.clone();
          this.deps = inNode.deps;
      }
  }
  </code></pre>
  
  <p>Edge.java</p>
  
  <pre><code>public class Edge
  {
      public Node from;
      public Node to;
      public Edge(Node from, Node to) {
          this.from = from;
          this.to = to;
      }
      @Override
      public boolean equals(Object obj) {
          Edge e = (Edge)obj;
          return e.from == from &amp;&amp; e.to == to;
      }
  }
  </code></pre>
  
  <p>The problem function</p>
  
  <pre><code>private ArrayList&lt;Node&gt; connectNodes(ArrayList&lt;Node&gt; modNodes)
  {
      //Final output, a directed graph
      ArrayList&lt;Node&gt; dirGraph = new ArrayList&lt;Node&gt;();
      //For each moduleNode in the argument list
      for(int i = 0; i &lt; modNodes.size(); i++)
      {
          Node curNode = modNodes.get(i);
          //Get the modules dependencies
          ArrayList&lt;String&gt; curDepNames = curNode.deps;
          //For each dependency of this module
          for(int j = 0; j &lt; curDepNames.size(); j++)
          {
              String curDep = curDepNames.get(j);
              Node depNode = null;
              //For each moduleNode in the argument list
              //Find the one that matches this dependency
              for(int k = 0; k &lt; modNodes.size(); k++)
              {
                  Node AmodNode = modNodes.get(k);
                  //If this modules name is the same as the dependency save it
                  //and break from the loop
                  if(AmodNode.toString().equals(curDep))
                  {
                      depNode = AmodNode;
                      break;
                  }
              }
              // If we didn't find the modules dependency then there is an error
              // We are missing a dependency
              if(depNode == null)
              {
                  // Throw missing dependency error! ? Do we stop what were doing?
                  modCheckStat = Messages.SetConfig.MODULE_MISSINGDEP;
                  return null;
              }
              //Otherwise connect an edge between the current ModuleNode and its dependency
              curNode = curNode.addEdge(depNode);
          }
          //Add this node and its dependency to the final array
          dirGraph.add(curNode);
      }
      return dirGraph;
  }
  </code></pre>
  
  <p>EDIT: I think my problem lies in this function meant to clone the array list, it does not take into account the edges pointing to the old Nodes and not the new nodes. </p>
  
  <pre><code>public static ArrayList&lt;Node&gt; cloneList(ArrayList&lt;Node&gt; inList)
  {
      ArrayList&lt;Node&gt; clonedList = new ArrayList&lt;Node&gt;(inList.size());
      for(Node aNode : inList)
      {
          clonedList.add(new Node(aNode));
      }
      return clonedList;
  }
  </code></pre>