Networkx: estrae il componente connesso che contiene un determinato nodo (grafico diretto)

Question

Sto provando ad estrarre da un grafico grande il sotto-grafico di tutti i nodi connessi che contengono un nodo specifico.

C'è una soluzione nella libreria Networkx?

[EDIT]
mio grafico è un digramma

[EDIT]
riformulato semplicemente:
voglio la parte del mio grafico che contiene il mio nodo specifico N_i e e tutti i nodi che sono collegati direttamente o indirettamente (passando da altri nodi) utilizzando i bordi in entrata o in uscita.
Esempio:

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

mio risultato desiderato sarebbe:

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

Answer 1

È possibile utilizzare shortest_path() per trovare tutti i nodi raggiungibili da un determinato nodo. Nel tuo caso devi prima convertire il grafico in una rappresentazione non orientata, in modo che vengano seguiti sia l'interno che l'esterno.

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

o in una linea di

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

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

Answer 2

utilizzare l'esempio alla fine della pagina connected_component_subgraphs.

Solo garantire di sottoporre l'ultimo elemento della lista anziché prima

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

Answer 3

semplicemente scorrere i sottografi fino al nodo di destinazione è contenuto all'interno del sottografo.

Per i grafici diretti a, presumo che un sottografo sia un grafico tale che ogni nodo sia accessibile da ogni altro nodo. Questo è un sottografo strongly connected e la funzione networkx è strongly_connected_component_subgraphs.

(MWE) Minimal esempio funzionante:

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() 

Per un sottografo diretto (digramma) esempio cambiate le linee corrispondenti:

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

Si noti che uno dei nodi è nel componente collegato ma non nel componente fortemente connesso!

Answer 4

ho trovato tre soluzione per risolvere la vostra esigenza, proprio uguale al mio. La dimensione del mio Digraph è compresa tra 6000 e 12000 nodi e la dimensione massima del sottografo è fino a 3700.A tre funzioni che ho usato sono:

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) 

Il risultato del test è riassunto come segue: