CODEWITHSUNDEEP
pythonpandasnetworkx
Rushabh Mehta
Rushabh Mehta

Reputation: 1559

Directed Graph Traversal with Networkx

I have a large directed graph (networkx.DiGraph()) that is composed of several directed trees, each with one root. I also have a function that takes in a certain graph and outputs some of its nodes. Here are the operations I would like to do.

  1. Given an arbitrary directed forest, and a level provided, cut the graph at that given level, and run each of the newly created subgraphs through the function.
  2. If the root of the newly created graph shows up in the output of the function, proceed to remove that subgraph from the graph. Else, remove all of its descendants from the graph.

I know that was complicated, so let's run through a sample run.

For the sake of simplicity, let our arbitrary graph be one tree, rather than several. I'll choose the nx.balanced_tree(2,4,create_using=nx.DiGraph()) as my graph. The edgelist for that graph is shown below

(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(3,8),(4,9),(4,10),(5,11),(5,12),(6,13),(6,14),
(7,15),(7,16),(8,17),(8,18),(9,19),(9,20),(10,21),(10,22),(11,23),(11,24),(12,25),(12,26),
(13,27),(13,28),(14,29),(14,30)

Note that 0 has level 0, 1-2 have level 1, 3-6 have level 2, 7-14 have level 3, and 15-30 have level 4.

Let's say I input 3 into my program. Then, I take each node in level 3 as a root of its own subgraph, and process each one in my program. So, the subgraphs represented as

Subgraph 1: (7,15),(7,16)
Subgraph 2: (8,17),(8,18)
etc

Will be inputted into my function. Let the function output 7 as a node, but not 8. Then, the nodes 7, 15, 16 should all be removed, and the nodes 17 and 18 should be removed, but not 8.

I apologize for this being complicated, but in reality, I think its a bunch of simple steps concatenated together. However, my looping approach is definitely un-optimal. What is the best approach?

Upvotes: 2

Views: 2642

Answers (1)

Gambit1614
Gambit1614

Reputation: 8801

Okay, the solution I am going to present is a little hacky but I am open to suggestions for more optimizations.

First we will create a dummy graph for testing

import networkx as nx
G = nx.balanced_tree(2,4,create_using=nx.DiGraph())

Next, we will dfs_tree API of networkx (use the latest version) and use the depth_limit attribute to extract tree upto depth n and n+1 where n+1 is the depth entered by the user (since it starts indexing depth at 1)

T1 = nx.dfs_tree(G, source=0,depth_limit=3)   #here n=3
T1_edges = list(T.edges())
#[(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6), (3, 8), (3, 7), (4, 9), (4, 10), (5, 11), (5, 12), (6, 13), (6, 14)]

Then do the same for depth n+1

T2 = nx.dfs_tree(G, source=0,depth_limit=4)
T2_edges =list(T2.edges())
#[(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6), (3, 8), (3, 7), (4, 9), (4, 10), (5, 11), (5, 12), (6, 13), (6, 14), (7, 16), (7, 15), (8, 17), (8, 18), (9, 19), (9, 20), (10, 21), (10, 22), (11, 24), (11, 23), (12, 25), (12, 26), (13, 27), (13, 28), (14, 29), (14, 30)]

Now take the XOR of these two lists

edges_left = list(set(T1_edges).symmetric_difference(T2_edges))
#[(14, 30), (11, 23), (10, 21), (7, 16), (11, 24), (7, 15), (10, 22), (9, 20), (12, 25), (13, 28), (8, 17), (14, 29), (12, 26), (13, 27), (8, 18), (9, 19)]

These are the edges at level 3. Now extract the nodes at these levels

nodes_at_level = set([x[0] for x in edges_left])
#{7, 8, 9, 10, 11, 12, 13, 14}

Then use bfs_tree to extract tree at these nodes

for n in nodes_at_level:
    tree = nx.bfs_tree(G, n)
    print tree.edges()              #Do whatever you want with those subgraphs

#[(7, 16), (7, 15)]
#[(8, 17), (8, 18)]
#[(9, 19), (9, 20)]
#[(10, 21), (10, 22)]
#[(11, 24), (11, 23)]
#[(12, 25), (12, 26)]
#[(13, 27), (13, 28)]
#[(14, 29), (14, 30)]

Upvotes: 2

Related Questions