Переменная итерация для каждого узла | Подключение узла в Python Graph

Question

Я бы хотел найти связность узлов между узлом 1 и остальными узлами на графике. Формат входного текстового файла следующий:

1 2 1
1 35 1
8 37 1

и так далее для 167 строк. Первый столбец представляет узел источника, второй столбец представляет узел назначения, а последний столбец представляет вес ребра.

Я пытаюсь прочитать исходные, конечные узлы из входного файла и создать ребро между ними. Затем мне нужно выяснить, является ли это подключенной сетью (только один компонент графа и никаких подкомпонентов). Вот код

from numpy import*
import networkx as nx
G=nx.empty_graph()

for row in file('out40.txt'):
    row = row.split()
    src = row[0]
    dest = row[1]
    #print src
    G.add_edge(src, dest)
    print src, dest

for i in range(2, 41):
    if nx.bidirectional_dijkstra(G, 1, i): print "path exists from 1 to ", i

добавление граней вручную с помощью

G.add_edge(1, 2)

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

in neighbors_iter
raise NetworkXError("The node %s is not in the graph."%(n,))
networkx.exception.NetworkXError: The node 2 is not in the graph.

Любая помощь будет высоко ценится!

Answer 1

В вашем коде вы добавляете узлы "1" и "2" и так далее (поскольку чтение из файла даст вам строки, если вы не преобразуете их явно).

Однако вы пытаетесь сослаться на узлы 1 и 2. Я предполагаю, что networkx не думает, что 2 == "2".

Попробуйте изменить это ...

G.add_edge(src, dest)

к этому:

G.add_edge(int(src), int(dest))

Answer 2

Не уверен, что это вариант для вас, но знаете ли вы о встроенной поддержке networkx для нескольких форматов графического текста ?

Формат списка edge, похоже, очень хорошо подходит для вашего случая.В частности, следующий метод будет читать ваши входные файлы без необходимости в пользовательском коде:

G = nx.read_weighted_edgelist(filename)

Если вы хотите удалить веса (потому что они вам не нужны), вы можете впоследствии сделать следующее:

for e in G.edges_iter(data=True):
    e[2].clear()                   #[2] is the 3rd element of the tuple, which 
                                   #contains the dictionary with edge attributes

Answer 3

Вы также можете использовать "is_connected ()", чтобы сделать это немного проще. например,

$ cat disconnected.edgelist
1 2 1
2 3 1
4 5 1
$ cat connected.edgelist 
1 2 1
2 3 1
3 4 1
$ ipython

In [1]: import networkx as nx

In [2]: print(nx.is_connected(nx.read_weighted_edgelist('disconnected.edgelist')))
False

In [3]: print(nx.is_connected(nx.read_weighted_edgelist('connected.edgelist')))
True

Answer 4

Из Networkx документации :

for row in file('out40.txt'):
    row = row.split()
    src = row[0]
    dest = row[1]
    G.add_nodes_from([src, dest])
    #print src
    G.add_edge(src, dest)
    print src, dest

В сообщении об ошибке говорится, что на графике G нет узлов, между которыми вы хотите создать ребро.