Java，在有向图中连接边以使图可遍历

Question

我正在生产（或尝试）一个由Node和Edge组成的java中的有向图。该图表示我称之为模块（模块在我的程序中扮演某种角色）的依赖关系树。某些模块需要在程序中的其他模块之前运行，并使用有向图表示。模块（和Node）知道哪些其他模块必须在它们之前。

目前我读取并读取一个目录，并获得一个模块的ArrayList，然后将其转换为Node的ArrayList。我的问题是连接这些node s与node类addEdge(..)函数。当我打电话给我的功能（代码如下）connectNodes(..)我想在node之间创建边缘对象，以便我可以遍历整个树，从node s到node s，使用edge s。这似乎是我的connectNodes(..)方法的工作方式，我不能这样做。

的问题是，从connectNodes返回的每个Node对象的outEdge和inEdgeHashSet正确地指向Node用正确的域名（代表其上下依赖性），但这些Node对象没有自己的inEdge和outEdge套充满指向树中上方和下方的Node。

所以它就好像每条边的每一端指向具有适当信息的另一个节点对象的副本，但是错误的（通过错误，我的意思是没有）边集。他们应该指向ArrayList中的其他节点对象。

Node.java

import java.util.ArrayList; 
import java.util.HashSet; 

public class Node 
{ 
    public String name; 
    public HashSet<Edge> inEdges; 
    public HashSet<Edge> outEdges; 
    public ArrayList<String> deps; 

    public Node(String name, ArrayList<String> deps) { 
     this.name = name; 
     inEdges = new HashSet<Edge>(); 
     outEdges = new HashSet<Edge>(); 

     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<Edge>)inNode.inEdges.clone(); 
     this.outEdges = (HashSet<Edge>)inNode.outEdges.clone(); 
     this.deps = inNode.deps; 
    } 
} 

Edge.java

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 && e.to == to; 
    } 
} 

问题函数

private ArrayList<Node> connectNodes(ArrayList<Node> modNodes) 
{ 
    //Final output, a directed graph 
    ArrayList<Node> dirGraph = new ArrayList<Node>(); 
    //For each moduleNode in the argument list 
    for(int i = 0; i < modNodes.size(); i++) 
    { 
     Node curNode = modNodes.get(i); 
     //Get the modules dependencies 
     ArrayList<String> curDepNames = curNode.deps; 
     //For each dependency of this module 
     for(int j = 0; j < 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 < 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; 
} 

编辑：我想我的问题就出在这个功能意味着克隆数组列表，它没有考虑指向旧节点而不是新节点的边缘。

public static ArrayList<Node> cloneList(ArrayList<Node> inList) 
{ 
    ArrayList<Node> clonedList = new ArrayList<Node>(inList.size()); 
    for(Node aNode : inList) 
    { 
     clonedList.add(new Node(aNode)); 
    } 
    return clonedList; 
} 

Answer 1

首先，当你有HashSet的，总是同时覆盖equals和hashCode。

除此之外，图似乎是正确构建的（请注意，您总是返回一个新列表，其中包含与您的参数相同的元素）。您可以使用一些Map来消除最内层的循环（k）。