Networkx - find all subgraphs with conditions

user_190791 0
Viewed 127

I have a directed graph and would like to get all subgraphs with conditions as follow:

For each subgraph:

  • all nodes have exactly 1 edge in
  • all nodes have exactly 1 edge out
  • sum of 'durations' (a given attribute) per subgraph is under (<=) a given value K

Here is a small example:

import networkx as nx

G = nx.DiGraph()

G.add_nodes_from([
    (1, {"name": "node 1", "duration": 30}),
    (2, {"name": "node 2", "duration": 40}),
    (3, {"name": "node 3", "duration": 20}),
    (4, {"name": "node 4", "duration": 10}),
    (5, {"name": "node 5", "duration": 30}),
    (6, {"name": "node 6", "duration": 20}),
    (7, {"name": "node 7", "duration": 50}),
    (8, {"name": "node 8", "duration": 40}),
])

links = ( (1,2), (2,3), (3,4), (4,5), (1,8), (8,7), (7,6), (6,5))

G.add_edges_from(links)

The expected solution is (for example, as there are multiple options):

( (2,3,4), (6,7), (8) )
networkx
2 Answers

I found a way to do this in two parts, with:

# create a subgraph with all nodes that have following condition:
# 1 in edge
# 1 out edge
sub = G.subgraph([node for node in G.nodes() if (len(G.in_edges(node)) == 1) & (len(G.out_edges(node)) == 1)])

# convert to undirected graph to use connected_components
ug_sub = sub.to_undirected()

# get list of subgraphs that have directed compenents from sub list of nodes
list_of_subgraphs = [c for c in sorted(nx.connected_components(ug_sub), key=len, reverse=True)]

I still need to split each subgraph into subgraphs that respect the condition on maximum duration, but this seems feasible without networkx.

user_1907910

Here is a possible way to do that:

  1. You can compute all the possible subgraphs of your graph G

  2. Next, for each subgraph in your list, you can check whether the subgraph verifies the degree condition by using the check_degree function below.

  3. Then, you can mask your array of subgraphs with the vector of boolean values you got from running the check_degree function over all the subgraphs. With the specific graph you provided in your question, there are no subgraphs that verify the degree condition.

  4. Assuming there are subgraphs that verify the degree condition, you can then check whether the sum of the durations is below your threshold and use np.argwhere to extract the full list of the subgraphs that verify all conditions.

See full code below:

import itertools 
import networkx as nx
import numpy as np  

def check_degree(G,list_nodes):
  subG=G.subgraph(list_nodes) #create subgraph
  in_deg=np.array(subG.in_degree)[:,1] #compute in degree
  out_deg=np.array(subG.out_degree)[:,1] #compute out degree
  cond=np.logical_and(in_deg==out_deg, in_deg==1)
  good_nodes_deg=np.argwhere(cond)[:,0]+1
  return len(good_nodes_deg)==subG.number_of_nodes() #check if all nodes in subgraph verify the degree condition

def find_subgraphs(G,thresh):

  all_comb=sum([list(itertools.combinations(G.nodes,i)) for i in range(1,len(G.nodes)+1)],[]) #find all possible subgrpahs
  all_comb_arr=np.array([list(li) for li in all_comb])

  good_subs_deg_bool=[check_degree(G,node_list) for node_list in all_comb_arr] # run the check_degree function over all subgraphs
  good_subs_deg=all_comb_arr[good_subs_deg_bool] #mask the array of subgraph with good_subs_deg_bool

  dur=np.array([G.nodes[i+1]['duration'] for i in range(G.number_of_nodes())]) 
  sums=np.array([np.sum(dur[np.array(good_subs_deg[j])-1]) for j in range(len(good_subs_deg))]) #sum duration over all subgraphs
  subs=good_subs_deg[np.argwhere(sums<=thresh)][:,0] #check that the sum of duration is below thresh
  return subs
user_68657870
Related