NetworkX DiGraph 按节点创建子图（DiGraph）

Question

我想按节点获取子图（红色区域）：子图由输入节点可达的所有节点组成。

like G.subgraph(3) returns a new DiGraph from the red area.

例如我创建一个有向图是这样的：

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 并将其转换为单向。我测试了 out_egdes、strong/weak_connected_component，但它从未奏效。我也看了How to find subgraphs in a directed graph without converting to undirected graph? and Networkx: extract the connected component containing a given node (directed graph)。

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

谁能告诉我怎么做？如果生成的 Graph 也是 DiGraph

就好了

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)

结果如图所示

Answer 2

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

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)的结果如图：

Answer 3

详细说明@vaettchen 对 How to extract a subgraph from a dot file

的神秘评论

从https://gist.github.com/blabber/74b8d9ed59d0b2ad0d7a734113996424#file-reduce-g

gvpr

reduce.g

运行 gvpr 在 reduce.g:

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

其中 -a 是 reduce.g 程序的参数，即目标节点=3 和要遵循的跃点。如果您跳过 -a，它会告诉您。

This script takes exactly two parameter. 1: name of node, 2: number of hops

现在，就目前的情况来看，reduce.g 似乎确实对图表进行了相当大的修改 - 我从水平方向切换到了垂直方向。

顺便说一句，因为将参数输入 bash 脚本让我对引号感到困惑，所以我添加了有效的内容。

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

NetworkX DiGraph 按节点创建子图（DiGraph）

NetworkX DiGraph create subgraph (DiGraph) by node

python

subgraph

networkx