Как узнать, существует ли вершина в моем графе?

Question

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

Это мой текущий код:

public static Graph<ElementoDecorado<Integer>, String> loadGraphFromFile(File f) {
        boolean v1_exists = false, v2_exists = false;
        Graph<ElementoDecorado<Integer>, String> g = new AdjacencyListGraph<ElementoDecorado<Integer>, String>();
        Vertex<ElementoDecorado<Integer>> v1, v2, aux = null;
        Scanner fr;

        try {
            fr = new Scanner(f);

            while(fr.hasNextLine()) {
                v1 = g.insertVertex(new ElementoDecorado<Integer>(fr.nextInt()));
                v2 = g.insertVertex(new ElementoDecorado<Integer>(fr.nextInt()));

                for(Vertex<ElementoDecorado<Integer>> v : g.vertices()) {
                    if(v.equals(v1)) {

                        /*aux = v;
                        v1_exists = true;*/
                    }
                    if(v.equals(v2)) {
                        /*aux = v;
                        v2_exists = true;*/
                    }
                }

                g.insertEdge(v1, v2, "edge");

                v1_exists = v2_exists = false;
            }
        } catch(FileNotFoundException e) {
            e.printStackTrace();
        }

        return g;
    }

Я не знаю, что написать в два if.Я попытался удалить вершину, если они равны, но, очевидно, это не работает, потому что в конце мой график будет пуст: S

Это страница руководства для вершиныинтерфейс.

Любая помощь приветствуется.Спасибо и счастливого Рождества!

Answer 1

Вы должны сначала проверить, что делает graph.insertVertex(V value).Если пакет был собран прилично (что я сомневаюсь из плохой документации), тогда этот метод создаст новую вершину, только если вершина с value еще не существует;в противном случае он возвращает существующую вершину со значением value.

Однако из недокументированной документации я не могу сказать, действительно ли пакет предполагает наличие единственной вершины для заданного значения и правильно ли ведет себя insertVertex.

Вот некоторый кодв случае, если insertVertex не проверяет на дублирование:

(я заменил ElementoDecorado<Integer> на Integer для удобства чтения)

while(fr.hasNextLine()) {
   int nodeId1 = fr.nextInt();
   int nodeId2 = fr.nextInt();
   Vertex<Integer> vert1 = null;
   Vertex<Integer> vert2 = null;

   for(Vertex<Integer> v : g.vertices()) {
      int nodeId = v.element();
      if(nodeId == nodeId1) 
         vert1 = v;
      else if (nodeId == nodeId2) // assumes can't have nodeId1 == nodeId2
         vert2 = v;
    }
    if (vert1 == null)
       vert1 = g.insertVertex(nodeId1);
    if (vert2 == null)
       vert2 = g.insertVertex(nodeId2);

    g.insertEdge(vert1, vert2, null);
 }

Answer 2

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

v1 = new ElementoDecorado<Integer>( fr.nextInt() );
v2 = new ElementoDecorado<Integer>( fr.nextInt() );

Затем в for вы проверяете, существует ли вершина, так же, как вы пытались.Ваши if могут выглядеть так:

if( !v1_exists && v.equals( v1 ) ) {
    v1 = v;
    v1_exists = true;
}

И аналогично для v2.В конце, если и только если v1_exists ложно, вы добавляете вершину:

// right anfter the for-each
if ( !v1_exists ) {
    g.addVertex( v1 );
}
if ( !v1_exists ) {
    g.addVertex( v2 );
}

g.insertEdge( v1, v2, "edge" );
// etc

Есть несколько оптимизаций, которые вы также можете сделать, например, остановка for, когда найдены обе вершины, но это должно сработать.

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

Answer 3

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

vertex = new ElementoDecorado<Integer>(fr.nextInt());
if(graph.get(key) != null) { 
    //it exists, don't insert it
} else { 
    g.insertVertex(vertex)
}

Знайте свои собственные структуры данных. Спросите себя, из чего сделан график? Это просто отображение:

ElementoDecorado<Integer> => String

Также не называйте ваши переменные такими вещами, как: g. Это не передает никакого смысла.