如何使用networkx图根据中间节点的属性值来查找两个节点之间的路径？

Question

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

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

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

我有一个带节点的简单图

^{pr2}$

和边缘：

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='from'）开始构建递归，并搜索相邻的对象，但情况相同-缺少属性。在

for i in G.neighbors("from"):
    print(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))