Блог

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

 1 2 1
1 35 1
8 37 1
  

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

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

 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.
  

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

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

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

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

 G.add_edge(src, dest)
  

для этого:

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

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

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

 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
  

Из 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 нет узлов, которые вы хотите создать между ними.

Вы также можете использовать «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
  

Другой вариант — загрузить файл в виде фрейма данных pandas, а затем использовать iterrows для итерации:

 import pandas as pd
import networkx as nx

cols = ["src", "des", "wei"]
df = pd.read_csv('out40.txt', sep=" ", header=None, names=cols)
G = nx.empty_graph()

for index, row in df.iterrows():
    G.add_edge(row["src"], row["des"])