使用NetworkX高效地检查路径在图中是否有效？

Question

我想找到一种有效的方法来检查给定的“遍历”图是否有效。在

这样的函数应该接受一个图（节点、边）和一个节点名字符串，如果可以根据图按给定的顺序访问节点，则应该输出True；如果不能，则输出false。在

我最好使用NetworkX库，因为我已经用它来存储和表示图形。在

类似这样的东西：

""" G:
    Q1 -> Q1
    Q1 -> Q2
    Q2 -> Q2
"""
accepts(G, ["Q1", "Q1", "Q2"]) 
>> True
accepts(G, ["Q2", "Q2", "Q2"]) 
>> True
accepts(G, ["Q2", "Q2", "Q1"]) 
>> False
accepts(G, ["Q1", "Q2", "Q1"]) 
>> False
accepts(G, ["Q1", "Q1", "Q2", "Q1"]) 
>> False

这将用于automata类。基本上检查给定一种由图形表示的语言的字符串的成员资格。在

Answer 1

虽然@newbie的观点是“您只需要检查路径的所有边是否有效”是正确的，但是他给出的实现远没有效率；graph.edges()为路径中的每一条边从头开始重建一个图的所有边的列表。应该始终使用(u, v) in g.edges()，而不是(u, v) in g.edges()，这是一个常量时间操作。尽管目前看来您正在使用DiGraph，但后一种方法还有一个额外的好处，即既能为Graph和{}工作，而前面的方法只适用于DiGraph。（这是因为Graph的edges()方法只返回一个（随机）方向的边，因此只检查一个方向的边是不够的；g.has_edge()对Graph和DiGraph都是正确的）

长话短说，使用：

def accepts(g, path):
    return all([g.has_edge(path[i], path[i+1]) for i in range(len(path)-1)])

或者更简洁一点：

^{pr2}$

Answer 2

您只需要检查路径的所有边是否有效。在

def accepts(g, path):
    return all([(path[i],path[i+1]) in g.edges() for i in range(len(path)-1)])

示例：

^{pr2}$