NetworkX DiGraph create subgraph (DiGraph) by node

According to my understanding that the criteria of creation of the subgraph depends on the nodes reachable from the input node. Then the following recursive function should be sufficient to get the job done.

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)

I copied your code to create the graph, initialized an empty Directed graph and called the function as follows:

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)

The resulted Digraph is shown in the figure.enter image description here


Use build-in traversal algorithms may get better performance, support bi-direction option, and avoid recursive depth limitation.

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)

Or the concise version for uni-direction:

def create_subgraph(G, node):
    nodes = nx.single_source_shortest_path(G,node).keys()
    return G.subgraph(nodes)

The build-in version is 3 times fast than recursive one in my case. It subgraph 3000 from 5000 nodes :

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

The result of create_subgraph(G, 3) is shown in figure: enter image description here


To elaborate on @vaettchen's cryptic comment on How to extract a subgraph from a dot file

  1. grab a gvpr command file, reduce.g from https://gist.github.com/blabber/74b8d9ed59d0b2ad0d7a734113996424#file-reduce-g

  2. run gvpr on reduce.g:

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

where -a are the parameters to the reduce.g program, i.e. target node=3 and hops to follow. If you skip -a it'll tell you about it.

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

Now, as it stands reduce.g does seem to modify the graph quite a bit - I switched from horizontal to vertical orientation.

BTW, since feeding parameters into bash script stumped me quite a bit with the quotes, I am adding what does work.

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