Java: добавление узлов в ошибку графика

Question

Предисловие: Я знаю, что существуют графические API высокого качества. Мне интересно писать свои собственные для самосовершенствования.

Это моя функция для добавления узлов:

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 

Что здесь происходит?

Answer 1

На графике вы пытаетесь создать в вашем примере выглядит следующим образом:

tlt -> ftw -> odp

После создания ftw -> odp, вы должны (и делать, я считаю) есть head == ftw. После добавления tlt вы должны иметь head == tlt, если вы хотите, чтобы ваш алгоритм обхода работал правильно. Но в коде, который вы нам показали, есть только одно место, где назначается head, и это происходит только в условии, когда head == null, в пятой строке addNode(). Поэтому head не изменяется, когда вы добавляете tlt, и поэтому traverseGraphToAdd() поэтому начинает формировать форму ftw вместо tlt, как вы намереваетесь для этого.

Однако у вас есть более общая проблема, а именно, что ваш код не способен обрабатывать ориентированные графы, которые не внедрены (то есть у них более одного узла-источника). Подумайте, что произойдет, если вы хотел граф, как этот:

a -> b <- c

Я думаю, что вы должны были бы проблемы с этим, так как вы больше не имеют одну головку.