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

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

0 голосов
/ 11 октября 2011

Я бы хотел найти связность узлов между узлом 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.

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

Ответы [ 4 ]

2 голосов
/ 11 октября 2011

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

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

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

G.add_edge(src, dest)

к этому: 

G.add_edge(int(src), int(dest))
2 голосов
/ 11 октября 2011

Не уверен, что это вариант для вас, но знаете ли вы о встроенной поддержке 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
0 голосов
/ 11 октября 2011

Вы также можете использовать "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
0 голосов
/ 11 октября 2011

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

...