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）。