python - networkx 是否提供了一种方法来创建可以从一个节点获取的所有可能路径的子图？

Question

我有一个图表显示对象之间的关系，如果对象 A 与对象 B 交互，对象 B 与对象 C 交互，我必须假设对象 A 可以与对象 C 交互交互。

我可以使用nx.descendants.

我还想显示一个显示这些传递关系的图表 - 是否有类似的方法返回一个图表而不是一个集合？

Answer 1

您可以通过获取后代（加上源）并制作由这些节点诱导的子图的副本来轻松完成此操作：

In [1]: import networkx as nx

In [2]: G = nx.DiGraph()

In [3]: G.add_edges_from([("a", "b"), ("b", "c"), ("c", "d"), ("b", "e")])

In [4]: descendants = nx.descendants(G, "b")

In [5]: descendants
Out[5]: {'c', 'd', 'e'}

In [6]: descendants.add("b")

In [7]: H = G.subgraph(descendants).copy()

In [8]: H.adj
Out[8]: AdjacencyView({'b': {'c': {}, 'e': {}}, 'c': {'d': {}}, 'd': {}, 'e': {}})

In [9]: list(H.edges)
Out[9]: [('b', 'c'), ('b', 'e'), ('c', 'd')]

请注意，这将仅包括原始图中存在的边，例如('b', 'c')和('c', 'd')，但不包括('b', 'd')。这种关系隐含在图的结构中，但要添加填充这些隐含关系（可达性关系）的边，您可以采用传递闭包：

In [15]: list(nx.transitive_closure(H).edges)
Out[15]: [('b', 'c'), ('b', 'e'), ('b', 'd'), ('c', 'd')]

这些算法实际上适用于所有有向图，而不仅仅是 DAG。