Networkx:提取包含给定节点的连通组件(有向图)

Question

我试图从一个大图中提取包含特定节点的所有连接节点的子图.

Networkx库中是否有解决方案？

[编辑]
我的图是DiGraph

[编辑]
简单地改写:
我想包含我的特定节点n_i个和与所有连接直接或间接地使用任何传入或outcoming边缘(由其它节点传递)的节点我的曲线图的一部分.
例:

>>> g = nx.DiGraph()
>>> g.add_path(['A','B','C',])
>>> g.add_path(['X','Y','Z',])
>>> g.edges()
[('A', 'B'), ('B', 'C'), ('Y', 'Z'), ('X', 'Y')]

我想要的结果是:

>>> g2 = getSubGraph(g, 'B')
>>> g2.nodes()
['A', 'B', 'C']
>>> g2.edges()
[('A', 'B'), ('B', 'C')]

Answer 1

您可以使用shortest_path()来查找从给定节点可到达的所有节点.在您的情况下,您需要首先将图形转换为无向表示,以便遵循入边和出边.

In [1]: import networkx as nx

In [2]: >>> g = nx.DiGraph()

In [3]: >>> g.add_path(['A','B','C',])

In [4]: >>> g.add_path(['X','Y','Z',])

In [5]: u = g.to_undirected()

In [6]: nodes = nx.shortest_path(u,'B').keys()

In [7]: nodes
Out[7]: ['A', 'C', 'B']

In [8]: s = g.subgraph(nodes)

In [9]: s.edges()
Out[9]: [('A', 'B'), ('B', 'C')]

或者在一行中

In [10]: s = g.subgraph(nx.shortest_path(g.to_undirected(),'B'))

In [11]: s.edges()
Out[11]: [('A', 'B'), ('B', 'C')]

Answer 2

只需遍历子图,直到目标节点包含在子图中.

对于有向图,我假设子图是一个图,这样每个节点都可以从每个其他节点访问.这是一个强连接的子图,其networkx功能是strongly_connected_component_subgraphs.

(MWE)最小工作示例:

import networkx as nx
import pylab as plt

G = nx.erdos_renyi_graph(30,.05)
target_node = 13

pos=nx.graphviz_layout(G,prog="neato")

for h in nx.connected_component_subgraphs(G):
    if target_node in h:
        nx.draw(h,pos,node_color='red')
    else:
        nx.draw(h,pos,node_color='white')

plt.show()

对于有向子图(有向图)示例,将相应的行更改为:

G = nx.erdos_renyi_graph(30,.05, directed=True)
...
for h in nx.strongly_connected_component_subgraphs(G):

请注意,其中一个节点位于连接组件中,但不在强连接组件中!