Networkx: извлеките подключенный компонент, содержащий заданный node (направленный график)

Я пытаюсь извлечь из большого графика субграфит всех подключенных узлов, содержащих конкретный node.

Есть ли решение в библиотеке Networkx?

[EDIT]
Мой график - DiGraph

[EDIT]
Перефразировано просто:
Я хочу, чтобы часть моего графика содержала мой конкретный node N_i и все узлы, которые прямо или косвенно связаны (передаются другими узлами) с использованием любых входящих или исходящих ребер.
Пример:

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

Ответы

Ответ 1

Вы можете использовать shortest_path(), чтобы найти все узлы, доступные из заданного node. В вашем случае вам нужно сначала преобразовать граф в неориентированное представление, чтобы соблюдались как внутренние, так и внешние ребра.

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

Ответ 2

Просто проведите через подграфы, пока цель node не будет включена в подграф.

Для графиков направленных я предполагаю, что подграф представляет собой график, так что каждый node доступен из любого другого node. Это сильно связанный подграф, а функция 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()

enter image description here

Для ориентированного подграфа (орграф) измените соответствующие строки на:

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

enter image description here

Обратите внимание, что один из узлов находится в подключенном компоненте, но не в сильно подключенной компоненте!

Ответ 3

Используйте пример в конце страницы connected_component_subgraphs.

Просто убедитесь, что ссылались на последний элемент из списка, а не на первый

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

Ответ 4

Я нашел три решения для решения вашего требования, так же, как и мое. Размер моего Digraph составляет от 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)

Результат теста сводится к следующему:

timeit ms