Использование NetworkX all_simple_paths дает AttributeError

У меня есть граф с матрицей смежности приведенной ниже формы (граф с 6 узлами, где собственные ребра равны 0, а no_connections помечены как Inf, а другие ребра - 1):

{1: {1: 0, 2: 1, 3: inf, 4: inf, 5: inf, 6: inf}, 2: {1: 1, 2: 0, 3: inf, 4: 1, 5: 1, 6: inf}, 3: {1: inf, 2: inf, 3: 0, 4: 1, 5: inf, 6: inf}, 4: {1: inf, 2: 1, 3: 1, 4: 0, 5: 1, 6: 1}, 5: {1: inf, 2: 1, 3: inf, 4: 1, 5: 0, 6: inf}, 6: {1: inf, 2: inf, 3: inf, 4: 1, 5: inf, 6: 0}}

Я хочу использовать пакет networkx для его функции all_simple_paths, чтобы найти все простые пути от источника к месту назначения, но когда я вызываю

nx.all_simple_paths(graph, src, dst)

он дает: AttributeError: объект 'dict' не имеет атрибута 'is_multigraph'

В настоящее время у меня нет графика в другом формате. Как мне решить эту проблему?

Спасибо.


python networkx adjacency-matrix
person Ezzat Zar    schedule 03.11.2015    source источник
comment
зачем вообще указывать вес inf, если нет связи? Почему бы просто не исключить их из словаря?   -  person Joel    schedule 03.11.2015

Ответы (1)


arrow_upward
1
arrow_downward

Ваш график в настоящее время хранится как словарь. Немного несправедливо ожидать, что networkx будет работать автоматически с любой структурой данных, которую вы выберете. Даже если бы он был настроен на обработку словаря так, как вы это сделали, как бы он узнал, как интерпретировать 0 или inf?

Чтобы использовать команды networkx, вам необходимо, чтобы ваш график был в формате networkx Graph.

import networkx as nx
D = {1: {1: 0, 2: 1, 3: float('inf'), 4: float('inf'), 5: float('inf'), 6: float('inf')}, 2: {1: 1, 2: 0, 3: float('inf'), 4: 1, 5: 1, 6: float('inf')}, 3: {1: float('inf'), 2: float('inf'), 3: 0, 4: 1, 5: float('inf'), 6: float('inf')}, 4: {1: float('inf'), 2: 1, 3: 1, 4: 0, 5: 1, 6: 1}, 5: {1: float('inf'), 2: 1, 3: float('inf'), 4: 1, 5: 0, 6: float('inf')}, 6: {1: float('inf'), 2: float('inf'), 3: float('inf'), 4: 1, 5: float('inf'), 6: 0}}

G=nx.Graph()
for node, neighbor_dict in D.items():
    G.add_node(node)
    for neighbor, val in neighbor_dict.items():
        if val !=0 and val <float('inf'):
            G.add_edge(node, neighbor, weight=val)

for path in nx.all_simple_paths(G,1,3):
    print path
>[1, 2, 4, 3]
>[1, 2, 5, 4, 3]
person Joel    schedule 03.11.2015