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.
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:
To elaborate on @vaettchen's cryptic comment on How to extract a subgraph from a dot file
grab a
gvpr
command file,reduce.g
from https://gist.github.com/blabber/74b8d9ed59d0b2ad0d7a734113996424#file-reduce-grun
gvpr
onreduce.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