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：添加节点到图形错误

回答

相关问题