Пути NetworkX MultiDiGraph не различают параллельные ребра

Question

Если бы у меня был очень простой направленный мультиграф

G = nx.MultiDiGraph()

G.add_edge('A', 'B', key=1)
G.add_edge('B', 'C', key=2)
G.add_edge('B', 'C', key=3)

--

(A) -1- (B) -2- (C)
            \3/ 

, я бы ожидал, что nx.all_shortest_paths(G, source='A', target='C') возвратит два пути;

• A-1-B-2-C
• A-1-B-3-C

но (как это в настоящее время реализовано) all_shortest_paths просто возвращает узлы, а не узлы и ребра, поэтому мы получаем только один путь;

>>> list(nx.all_shortest_paths(G, source='A', target='C'))
[['A', 'B', 'C']]

Есть ли какие-либопростой / универсальный метод для возврата реальных путей, а не простых списков узлов?

Answer 1

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

nx.all_simple_paths() возвращает списки узлов, поэтому для MultiDiGraph будет много повторений.Итак, сначала мы удалим их, преобразовав вывод nx.all_simple_paths() в set, а затем повторим для него.Для каждого пути мы извлекаем пары узлов (например: [1,2,3,4] -> [[1,2],[2,3],[3,4]]), а для каждой пары мы получаем AtlasView всех ребер между ними.Вот код для этого алгоритма:

import networkx as nx
from pprint import pprint

# Create the graph with unique edges to check the algorithm correctness
G = nx.MultiDiGraph()
G.add_edges_from([
    [1,2],
    [1,2],
    [1,2],
    [2,3],
    [2,3],
    [2,3],
    [3,4],
    [3,4],
    [2,4]
])
G.add_edge(1,2,data='WAKA')
G.add_edge(2,3,data='WAKKA')
G.add_edge(2,4,data='WAKA-WAKA')

# Our source and destination nodes
source = 1
destination = 4

# All unique single paths, like in nx.DiGraph
unique_single_paths = set(
    tuple(path)  # Sets can't be used with lists because they are not hashable
    for path in nx.all_simple_paths(G, source, destination)
)

combined_single_paths = []
for path in unique_single_paths:
    # Get all node pairs in path:
    # [1,2,3,4] -> [[1,2],[2,3],[3,4]]
    pairs = [path[i: i + 2] for i in range(len(path)-1)]

    # Construct the combined list for path
    combined_single_paths.append([
        (pair, G[pair[0]][pair[1]])  # Pair and all node between these nodes
        for pair in pairs
    ])
pprint(combined_single_paths)

[[((1, 2), AtlasView({0: {}, 1: {}, 2: {}, 3: {'data': 'WAKA'}})),
  ((2, 3), AtlasView({0: {}, 1: {}, 2: {}, 3: {'data': 'WAKKA'}})),
  ((3, 4), AtlasView({0: {}, 1: {}}))],
 [((1, 2), AtlasView({0: {}, 1: {}, 2: {}, 3: {'data': 'WAKA'}})),
  ((2, 4), AtlasView({0: {}, 1: {'data': 'WAKA-WAKA'}}))]]