Java：添加節點到圖形錯誤

前言：我知道有高質量的圖形API可用。我有興趣寫自己的自我完善。Java：添加節點到圖形錯誤

這是我的函數添加節點：

public void addNode(Vertex v, Collection<Edge> neighbors) { 

     int originalSize = size(); 

     if (head == null) { 
      head = v; 
     } 
     else { 
      Collection<Edge> inEdges = new ArrayList<Edge>(); 
      inEdges.addAll(neighbors); 

      traverseGraphToAdd(head, inEdges, v); 
     } 

     assert originalSize + 1 == size() : 
         String.format("adding operation failed. original size: %d, current size: %d", originalSize, size()); 
    } 
private void traverseGraphToAdd(Vertex start, Collection<Edge> inEdges, Vertex toAdd) { 
     Iterator<Edge> iter = inEdges.iterator(); 
     Edge e; 
     while (iter.hasNext()) { 
      e = iter.next(); 
      if (e.getSource().equals(start)) { 
       start.addEdge(e); 
       iter.remove(); 
      } 
      else if (! directionalEdges && e.getSink().equals(start)) { 
       start.addEdge(e); 
       iter.remove(); 
      } 
     } 
     if (inEdges.size() > 0) { //otherwise there's no point in continuing to search 
      for (Edge arc : start.getOutEdges()) { 
       traverseGraphToAdd(arc.getSink(), inEdges, toAdd); 
      } 
     } 
    }

大小和它的依賴：

public int size() { 
    int count = 0; 
    if (head == null) { 
     return 0; 
    } 
    else { 
     count = countNodes(head); 
    } 
    clearVisited(); 
    return count; 
} 

private int countNodes(Vertex start) { 
    int result = 1; 
    start.setVisited(true); 
    for (Edge e: start.getOutEdges()) { 
     if (! e.getSink().isVisited()) { 
      result += countNodes(e.getSink()); 
     } 
    } 
    return result; 
} 

private void clearVisited() { 
    if (head != null) { 
     clearNode(head); 
    } 
} 

private void clearNode(Vertex start) { 
    start.setVisited(false); 
    for (Edge e: start.getOutEdges()) { 
     if (e.getSink().isVisited()) { 
      clearNode(e.getSink()); 
     } 
    } 
}

邊緣分類：

public Edge(Vertex source, Vertex sink, int weight) { 
    this.source = source; 
    this.sink = sink; 
    this.weight = weight; 
}

以下調用工作：

g.addNode(ftw, new HashSet<Edge>()); //first node - empty edges 
g.addNode(odp, Arrays.asList(new Edge(ftw, odp, 3))); //link new node to one already in the graph

這不：

g.addNode(tlt, Arrays.asList(new Edge(tlt, ftw, 2)));

在這其中，邊緣構造函數的第一個參數是不已經在圖中的節點。我嘗試用下面的（從上面重複），以糾正這種在ADDNODE：

if (e.getSource().equals(start)) { /*... */ } 
else if (! directionalEdges && e.getSink().equals(start)) { /*... */ }

directionalEdges是一類字段確定此圖形是否是定向的或不。

然而，這會導致的斷言錯誤：

Exception in thread "main" java.lang.AssertionError: adding operation failed. original size: 1, current size: 1

這到底是怎麼回事？

來源

2009-11-16 Nick Heiner

addNode（）中調用的size（）方法的外觀如何？我沒有在traverseGraphToAdd（）中看到任何你將對象放入集合的地方。 – uckelman 2009-11-16 23:14:27

你有調試器嗎？我強烈建議從那裏開始。 – StevenWilkins 2009-11-16 23:19:31

我一直在Eclipse中經歷它，似乎無法弄清楚。 – 2009-11-16 23:20:38

你想在你的例子要創建的圖表看起來是這樣的：

tlt -> ftw -> odp

創建ftw -> odp後，你應該（和做的，我相信）有head == ftw。在添加tlt後，如果您希望遍歷算法正常工作，則應該有head == tlt。但是在您向我們展示的代碼中，只有一個地方分配給head，並且僅在addNode（）的第五行中發生的情況下才會發生這種情況head == null。因此，當您添加tlt時，head不會更改，因此traverseGraphToAdd（）從ftw開始，而不是tlt，因爲您打算這樣做。

但是，這裏有一個更一般的問題，即您的代碼無法處理未定植的有向圖（即它們有多個源節點）。請考慮如果您發生了什麼情況想要一個這樣的圖表：

a -> b <- c

我想你會遇到問題，因爲你不再有一個頭。

來源

2009-11-17 10:25:43 uckelman

Java：添加節點到圖形錯誤

回答

相關問題