在我的多向图中,我想找到 2 个节点之间可能的所有(简单)路径。我设法获得了所有路径,但无法区分源节点到达目标节点所需的边(假设它是一个多向图)。

例如,我有 A->B->C,其中 (A,B) 和 (B,C) 之间有多个平行边。如果我说 A->B 有 5 条平行边,B->C 有 2 条平行边,则 all_simple_path(graph, source='A', target='C') 将总共返回 7 条路径,都是类(class) A->B->C

使用 get_edge_data() 时,它返回每个节点之间的所有平行边。但我想要的是能够列出 路径中​​指定节点采用的所有组合 边。

谢谢 !

最佳答案

我认为 OP 不需要这个答案,但它对其他人有用。
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'}}))]]

关于Python 网络x : find all edges for a given path in a multiDiGraph,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/44648790/

10-10 18:03