使用python-networkx发现两个图中的公共路径

Question

我有两个DiGraphs，比方说G和H，我想数一数G的多少条路径是H的一部分。

对于任何节点对(src，dst)，我可以使用“all_simple_paths”函数来生成它们之间的路径: G_gen = nx.all_simple_paths(G，src，dst) H_gen = nx.all_simple_paths(H，src，dst)

由于路径的数量相当高(图通常有100个节点)，所以我不能求助于构建列表等等。(例如，列表(G_gen))所以我想知道是否有更明智的方法来处理它。此外，我还想根据路径长度来区分。

。。或者用不同的模块可以找到更好的解决方案？

谢谢您在这方面的任何帮助。

蒂埃里

Answer 1

我想知道为什么nx.intersection (请看这里)不能在这里工作吗？我不确定它是否检查引擎盖下的方向，但它似乎也没有强制输出到标准的Graph输出。以下可能有效：

# Create a couple of random preferential attachment graphs
G = nx.barabasi_albert_graph(100, 5)
H = nx.barabasi_albert_graph(100, 5)

# Convert to directed
G = G.to_directed()
H = H.to_directed()

# Get intersection
intersection = nx.intersection(G, H)

# Print info for each
print(nx.info(G))
print(nx.info(H))
print(nx.info(intersection))

其中产出：

>>> DiGraph with 100 nodes and 950 edges
>>> DiGraph with 100 nodes and 950 edges
>>> DiGraph with 100 nodes and 176 edges

该示例中的节点都是共享的，因为节点in只是简单的整数，因此它们遵循相同的生成索引。对于实际数据，我认为您的节点集可能与这里不同，您可能也会看到那里的差异。

在这条路上，我不太确定你会怎么做。交集只检查两个图之间共享哪些节点和边，并返回两个图中的节点和边，而不知道我怀疑的任何其他条件。可能有一种方法可以通过使用带有条件检查的交集函数的源代码来施加一些额外的约束。

我想这不是检查edges，路径的数量，而是检查 path 的数量，所以我想您正在寻找比这更具体的东西。但是至少没有路径可以存在于交集之外，因为所有共享路径都必须包含两个路径中的相同边缘(因为如果在这两条路径中的路径中都缺少边缘，那么在共享解决方案中它就不能作为路径存在)。

希望这能在某种程度上对你的问题有所帮助，尽管我觉得我把你的问题简单化了很多。

编辑:直观地说，你的问题的全部解决方案可能是简单地列举出交叉口中所有可能的路径。