python - 如何使用networkx图根据中间节点的属性值找到2个节点之间的路径？

Question

我可以搜索树并使用简单的方法获得节点之间的最短路径:

nx.shortest_path(G, source=, target=)

但是我如何选择通过具有特定属性值的节点的路径？

我有带有节点的简单图表

G = nx.Graph()
for token in document:
    G.add_node(token.orth_, item = token.i, tag = token.tag_, dep = token.dep_)

和边缘:

for token in document:    
    for child in token.children:
        G.add_edge(token.orth_, child.orth_, pitem = token.i, citem = child.i,
                   ptag = token.tag_, pdep = token.dep_, ctag = child.tag_, cdep = child.dep_)

我可以找到简单的解决方案吗，因为现在我正在努力构建复杂的功能。

编辑

这个想法是有一个像这样的函数:(粗略)

def getPathByNode(betw_word, betw_attr, src_word, src_attr, trg_word, trg_attr):
    nx.shortest_path(G, source=src, source_attr=src_attr, target=trg, target_attr=trg_attr, through=betw_word, through_attr=betw_attr)
    ....

但是当然不是所有参数都必须传递。作为输入，我将采用以下示例:

source_attr = {'dep_': 'ROOT'}
target_attr = {'tag_': 'NN'}

through = "of" 或 through = "from" 或 through_attr = {'tag_': 'IN'}

等等。我目前正在尝试从中间开始构建递归(through='from')并搜索邻居，但情况相同 - 缺少属性。

for i in G.neighbors("from"):
    print(i)

i 只是一个字符串。

Answer 1

一个简单的解决方案是计算从源到目标的所有路径。然后就过滤掉所有没有满足条件的节点的路径，并在这组路径中选择最短的路径。假设您有一个无向且未加权的图，类似这样的东西应该可以工作:

import networkx as nx

# Generate a sample graph:
G = nx.barabasi_albert_graph(10, 3, seed=42)
print(G.edges())

def check_attribute(G, node):
    # Say the condition is node id is 3:
    return node == 3

valid_paths = []
for path in nx.all_simple_paths(G, source=0, target=7):
    cond = False
    for node in path:
        if check_attribute(G, node):
            cond = True
            valid_paths.append(path)
            break

lengths = [len(path) for path in valid_paths]
shortest_path = valid_paths[lengths.index(min(lengths))]
print('valid paths: {}'.format(valid_paths))
print('shortest_path: {}'.format(shortest_path))