时间戳

首页 > 解决方案 > 是否可以在 networkx 中获得路径中包含属性的唯一路径？

python - 是否可以在 networkx 中获得路径中包含属性的唯一路径？

问题描述

我有下面的图表，我希望能够发现我可以从“ip”到“name”的所有方式，在networkx中使用下面的图表它表明如果我遵循我可以从“ip”到“name”这条路径[['ip', 'address', 'name']]问题是我还定义了address可以name从两个不同的边缘开始，一个具有属性through=isptool，另一个通过属性through=phyonebook是否可以让 networkx 将这两个路径列为单独的路径，并且还包括 through 属性路径？就像是

ip -sometool-> address -isptool-> name

ip -sometool-> address -phonebook-> name

import networkx as nx
g = nx.DiGraph()
g.add_node('email')
g.add_node('ip')
g.add_node('address')
g.add_node('name')
g.add_edges_from([('address', 'name')], through='isptool')
g.add_edges_from([('address', 'name')], through='phonebook')
g.add_edge('email', 'address')
g.add_edge('ip', 'address', through='sometool')
list(nx.all_simple_paths(g, 'ip', 'name'))
>>>[['ip', 'address', 'name']] # should have 2 paths one using isptool and one using phonebook edge
list(nx.all_simple_paths(g, 'email', 'name'))
>>>[['email', 'address', 'name']] # same here, should have 2 paths

标签： pythonnetworkx

解决方案

问题是您正在尝试使用 a DiGraph，它只能处理从一个节点到另一个节点的一个有向边。如果我们切换到使用 a MultiDiGraph，nx.all_simple_paths()则返回预期结果：

>>> import networkx as nx
    g = nx.MultiDiGraph()
    g.add_nodes_from(['email', 'ip', 'address', 'name'])
    
    g.add_edges_from([('address', 'name')], through='isptool')
    g.add_edges_from([('address', 'name')], through='phonebook')
    g.add_edge('email', 'address')
    g.add_edge('ip', 'address', through='sometool')
>>> list(nx.all_simple_paths(g, 'ip', 'name'))
[['ip', 'address', 'name'], ['ip', 'address', 'name']]
>>> list(nx.all_simple_paths(g, 'email', 'name'))
[['email', 'address', 'name'], ['email', 'address', 'name']]

但是，虽然我们现在得到了两条路径，但我们看不到边缘属性。我们可以nx.all_simple_edge_paths()改用：

>>> list(nx.all_simple_edge_paths(g, 'email', 'name'))
[[('email', 'address', 0), ('address', 'name', 0)],
 [('email', 'address', 0), ('address', 'name', 1)]]

通过一些 f-string 魔法，我们可以使用边缘数据来产生你想要的输出：

>>> for path in nx.all_simple_edge_paths(g, 'email', 'name'):
        a, b, e = path[0]
        print(f'{a} -{g[a][b][e].get("through", "sometool")}-> {b}', end='')
        for a, b, e in path[1:]:
            print(f' -{g[a][b][e].get("through", "sometool")}-> {b}', end='')
        print('\n')
email -sometool-> address -isptool-> name

email -sometool-> address -phonebook-> name

推荐阅读