Networkx：提取包含在给定节点的连接的组件（有向图）(Networkx: extract th

我想从一个大的图形抽取包含特定节点的所有连接的节点的子图。

有没有在Networkx库的解决方案？

[编辑]
我的图是一个有向图

[编辑]
简单地转述：
我想包含我的特定节点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):

请注意，其中一个节点是在所连接的组件，但不是在强连通分量！

Answer 3:

在页面的最终用途例如connected_component_subgraphs 。

只要确保从列表，请参阅最后一个元素，而不是第一

>>> G=nx.path_graph(4)
>>> G.add_edge(5,6)
>>> H=nx.connected_component_subgraphs(G)[-1]

Answer 4:

我发现了三个解决方案来解决你的需求，只是和我一样。我有向图的尺寸是6000至12000点之间，并且最大尺寸子我将使用到3700三个功能是：

def create_subgraph_dfs(G, node):
    """ bidirection, O(1)"""
    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_shortpath(G, node):
    """ unidirection, O(1)"""
    nodes = nx.single_source_shortest_path(G,node).keys()
    return G.subgraph(nodes)

def create_subgraph_recursive(G, sub_G, start_node):
    """ bidirection, O(nlogn)"""
    for n in G.successors_iter(start_node):
        sub_G.add_path([start_node, n])
        create_subgraph_recursive(G, sub_G, n)

测试结果是总结如下：