通过节点创建 NetworkX DiGraph 子图（DiGraph）

Question

我希望能够通过节点获取子图（红色区域）：

所得到的子图由从输入节点可达的所有节点组成。

例如G.subgraph(3)返回一个新的有向图，其中包含红色区域中的所有节点。

例如我创建了这样一张有向图：

import networkx as nx
G = nx.DiGraph()

G.add_path([1,2,3,4])
G.add_path([3,'a','b'])

A = nx.to_agraph(G)
A.layout()
A.draw('graph.png')

我研究了 https://networkx.github.io/documentation/latest/reference/generated/networkx.Graph.subgraph.html 并将它转换为单向图。我测试了 _egdes、strong/weak_connected_component，但从未成功过。 我还看了 如何在有向图中查找子图而不转换为无向图？ 和 Networkx：提取包含给定节点的连通分量（有向图）。

我知道 Subgraph 在 DiGraph 中不起作用。

请问有人能告诉我如何做到这一点吗？结果图形最好也是一个 DiGraph。

- svenhornberg

---

您能否澄清一下，您希望如何生成子图？是从给定的输入节点开始，生成所有可到达的节点吗？ - Abdallah Sobehy

是的，这就是我想要的。抱歉我没有澄清。顺便说一下，它运行得很好。 - svenhornberg

Answer 1

根据我的理解，创建子图的标准取决于从输入节点可达的节点。那么下面的递归函数应该足以完成这项工作。

def create_subgraph(G,sub_G,start_node):
    for n in G.successors_iter(start_node):
        sub_G.add_path([start_node,n])
        create_subgraph(G,sub_G,n)

我将您的代码复制到创建图表中，初始化了一个空的有向图，并按以下方式调用了函数：

G = nx.DiGraph()
G.add_path([1,2,3,4])
G.add_path([3,'a','b'])
sub_G = nx.DiGraph()
create_subgraph(G, sub_G,3)

图中展示了生成的有向图。

- Abdallah Sobehy

Answer 2

为了解释 @vaettchen 对于 如何从dot文件中提取子图 的神秘评论，您需要：

1. 获取一个名为 reduce.g 的 gvpr 命令文件，可以在 https://gist.github.com/blabber/74b8d9ed59d0b2ad0d7a734113996424#file-reduce-g 找到

2. 运行 gvpr 并使用 reduce.g 文件：

gvpr -f reduce.g -a '"3" 10' mygraph.dot > myreduced.graph.dot

其中 -a 是传递给 reduce.g 程序的参数，即目标节点为3和要遵循的跳数。如果您跳过 -a 参数，它会提示您。

此脚本需要两个参数: 1. 节点名称，2. 跳数

目前来看，reduce.g 确实会对图形进行相当大的修改 - 我从水平方向切换到了垂直方向。

顺便说一下，由于将参数传递给 bash 脚本时引号的问题困扰了我很久，所以我正在添加可行的方法。

gvpr -f reduce.g -a " \"$node_to_select\" 10" mygraph.dot

- JL Peyret

Answer 3

使用内置遍历算法可能会获得更好的性能，支持双向选项，并避免递归深度限制。

def create_subgraph(G, node):
    edges = nx.dfs_successors(G, node)
    nodes = []
    for k,v in edges.items():
        nodes.extend([k])
        nodes.extend(v)
    return G.subgraph(nodes)

或者单向的简洁版本：

def create_subgraph(G, node):
    nodes = nx.single_source_shortest_path(G,node).keys()
    return G.subgraph(nodes)

内置版本在我的情况下比递归版本快3倍。它从5000个节点中提取了3000个子图：

In [1]: %timeit -n10 use_built_in('O_CONTRACT_PRODUCT') 
10 loops, best of 3: 102 ms per loop 

In [2]: %timeit -n10 use_recursive('O_CONTRACT_PRODUCT')
10 loops, best of 3: 341 ms per loop

create_subgraph(G, 3) 的结果如下图所示：

- Jesse