我有两个有向图，假设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个节点)，我不能求助于构建列表等。(例如list(G_gen))，所以我想知道是否有更聪明的方法来处理它。另外，我还想根据路径长度来区分。
. .或者可以用不同的模块找到更好的解决方案?
提前感谢您的帮助。
蒂埃里
我想知道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
节点在示例中都是共享的，因为节点id只是简单的整数，所以它们遵循相同的生成索引。对于真实的数据，我想你的节点集可能不像这里一样等效，你可能也会看到那里的差异。
关于路径长度，我不太确定你会怎么做。交集只是检查两个图之间哪些节点和边是共享的，并返回两个图都共享的节点和边，而不知道我怀疑的任何其他条件。可能有一种方法可以通过使用一些条件检查来调整交集函数的源代码来施加一些额外的约束。
我猜这并没有检查路径的数量而是检查边的数量，所以我想你在寻找比这更具体的东西。但至少没有路径可以存在于交集之外，因为所有共享路径必须包含相同的边(因为如果一条边在任何一条路径中缺失，它就不能作为共享解决方案中的路径存在)。
希望这在某种程度上对你有所帮助，尽管我觉得我把你的问题简化了一点。
编辑:直观地说，你的问题的完整解决方案可能是简单地列举所有可能的路径在交集。