发现使用Python-networkx中的两个图中的共同路径

Question

我有两个digraphs，例如g和h，我想计算g的一部分

。发电机： g_gen = nx.all_simple_paths（g，src，dst） h_gen = nx.all_simple_paths（h，src，dst），

因为路径的数量相当高（图通常具有100个节点），我无法求助于构建列表等。是处理它的更聪明的方法。另外，我还想根据路径长度来区分。

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

事先感谢您对此的任何帮助。

蒂埃里

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

节点全部共享在示例中，因为节点ID只是简单的整数，因此它们遵循相同的一代索引。有了真实的数据，我想您的节点集可能不像这里那样等效，您可能也会看到那里的差异。

在路径长度上，我不太确定您将如何解决。交点只检查了两个图之间共享哪些节点和边缘，并返回那些都不知道的任何其他条件。通过将源代码与相交函数调整一些条件检查，可能有一种方法可以施加一些其他约束。

我想这不会检查路径的数量，而是 edges的数量，所以我想您正在寻找比这更具体的东西。 /strong>，但至少在交叉路口之外没有任何路径，因为所有共享路径都必须在两者中都包含相同的边缘（因为这两个路径丢失了边缘，因此它不能作为共享的路径存在解决方案）。

希望这以某种方式或形式有所帮助，尽管我觉得我已经过度简化了您的问题。

编辑：直观地，您问题的完整解决方案可能是简单地列举交叉路口中的所有可能路径。