Поиск пути в Networkx MultiDigraph

Question

У меня есть MultiDigraph, как это:

G=nx.MultiDiGraph()

G.add_edge(1,2,attr=0.5)
G.add_edge(3,2,attr=1.0)

Я пытаюсь найти путь от узла 1 к узлу 3, который даст результат примерно так:

1 to 2 (forward), 2 to 3 (reverse). 

Любой способ Networkx сделать это?Спасибо,

Answer 1

Вы можете найти путь неориентированного G, а затем получить все ребра, которые строят путь неориентированного G, и проверить, есть ли эти ребра в подграфе исходного графа, индуцированного узлами пути [(1, 2), (2, 3)] vs [(1, 2), (3, 2)]:

import networkx as nx

G=nx.MultiDiGraph()

G.add_edge(1,2,attr=0.5)
G.add_edge(3,2,attr=1.0)

path = nx.shortest_path(G.to_undirected(), source=1, target=3)
path_edges = zip(path, path[1:])
path_subgraph = G.subgraph(path)

for i in path_edges:
    if i in path_subgraph.edges():
        print(f'{i[0]} to {i[1]} (forward)')
    else:
        print(f'{i[0]} to {i[1]} (reverse)')

# 1 to 2 (forward)
# 2 to 3 (reverse)

Answer 2

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

Gu = G.to_undirected()
path = nx.shortest_path(Gu, source=1, target=3)

# Go through each edge in the path to check if it's "forward"
for x in range(len(path)-1):
    if G.has_edge(path[x], path[x+1]):
        print(f'{path[x]} to {path[x+1]} (forward)')
    elif G.has_edge(path[x+1], path[x]):
        print(f'{path[x]} to {path[x+1]} (reverse)')
    else:
        # This shouldn't happen but always good to check
        print(f'No path from {path[x]} to {path[x+1]}')