python - 修剪不在networkx简单路径中的节点？

Question

我有一个 DiGraph，我想修剪任何未包含在 simple paths 之一中的节点。我指定的两个节点之间。 (另一种思考方式是，任何无法同时到达开始和结束点的节点都应该被修剪)。

我发现做到这一点的最好方法是获取all_simple_paths，然后使用它们重建一个新的图表，但我希望有一个更优雅且不易出错的解决方案。例如，有没有办法确定简单路径上不存在的内容，然后删除这些节点？

Answer 1

您可以使用返回生成器的方法all_simple_paths，但您只需要第一个路径。然后您可以使用G.subgraph(nbunch)从您的路径返回诱导图。

编辑:要返回由所有简单路径引起的子图，只需连接 all_simple_paths 返回的唯一节点即可。

import networkx as nx
import itertools

G = nx.complete_graph(10) # or DiGraph, MultiGraph, MultiDiGraph, etc
# Concatenate all the paths and keep unique nodes (in one line)
all_path_nodes = set(itertools.chain(*list(nx.all_simple_paths(G, source=0, target=3))))
# Extract the induced subgraph from a given list of nodes
H = G.subgraph(all_path_nodes)
print(nx.info(H))

输出:

Name: complete_graph(10)
Type: Graph
Number of nodes: 10
Number of edges: 45
Average degree:   9.0000