不在简单网络中修剪路径X？

Question

我有一个DiGrraph，我想修剪我指定的两个节点之间的simple paths中没有包含的任何节点。（另一种方法是，任何节点都不能同时到达这两个点start和{}点，则应进行修剪）。在

我发现最好的方法是得到all_simple_paths，然后用它们重建一个新的图，但我希望得到一个更优雅、更不容易出错的解决方案。例如，有没有一种方法可以确定哪些节点不在简单路径上，然后删除这些节点？在

Answer 1

当@kikohs正在努力理解我的问题并给出他的答案时，我确实在这方面取得了一些进展，所以我将此作为问题的替代解决方案。不过，我确实认为他的回答很高明！在

def _trim_branches(self, g, start, end):
    """Find all the paths from start to finish, and nuke any nodes that
    aren't in those paths.
    """
    good_nodes = set()
    for path in networkx.all_simple_paths(
            g,
            source=start,
            target=end):
        [good_nodes.add(n) for n in path]

    for node in g.nodes:
        if node not in good_nodes:
            g.remove_node(node)

    return g

使用subgraph来执行第二个循环显然更好，正如他使用itertools.chain的一行程序一样。今天这些地方的东西很棒！在

Answer 2

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

编辑：要返回由所有简单路径引起的子图，只需将all_simple_paths返回的uniques节点连接起来。在

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))

输出：

^{pr2}$