NetworkX DiGraph create subgraph (DiGraph) by node

Question

I would like to get a subgraph (red area) by node: The subgraph is composed of all the nodes reachable from the input node.

like G.subgraph(3) returns a new DiGraph from the red area.

For example I create a DiGraph as this:

import networkx as nx
G = nx.DiGraph()

G.add_path([1,2,3,4])
G.add_path([3,'a','b'])

A = nx.to_agraph(G)
A.layout()
A.draw('graph.png')

I looked into https://networkx.github.io/documentation/latest/reference/generated/networkx.Graph.subgraph.html and converting it to unidirectional. I tested out_egdes, strong/weak_connected_component, but its never worked. I also looked How to find subgraphs in a directed graph without converting to undirected graph? and Networkx: extract the connected component containing a given node (directed graph).

I know that Subgraph does not work in DiGraph.

Can someone please show me how to do this ? Would be nice if the resulting Graph is also a DiGraph

Answer 1

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.

Answer 2

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:

Answer 3

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