How can I get branch of a networkx graph from pandas dataframe in Python in the form of a new pandas dataframe?

user_12276279 0
Viewed 291

I have a pandas dataframe df which looks as follows:

From    To
0   Node1   Node2
1   Node1   Node3
2   Node2   Node4
3   Node2   Node5
4   Node3   Node6
5   Node3   Node7
6   Node4   Node8
7   Node5   Node9
8   Node6   Node10
9   Node7   Node11

df.to_dict() is:

{'From': {0: 'Node1',
  1: 'Node1',
  2: 'Node2',
  3: 'Node2',
  4: 'Node3',
  5: 'Node3',
  6: 'Node4',
  7: 'Node5',
  8: 'Node6',
  9: 'Node7'},
 'To': {0: 'Node2',
  1: 'Node3',
  2: 'Node4',
  3: 'Node5',
  4: 'Node6',
  5: 'Node7',
  6: 'Node8',
  7: 'Node9',
  8: 'Node10',
  9: 'Node11'}}

I have plotted this pandas dataframe as a network graph using networkx package which looks as follows: enter image description here

I want to get the unique scenarios/branches from this network graph in the form of a new pandas dataframe as follows:

  A B   C   D
0   Node1   Node2   Node4   Node8
1   Node1   Node2   Node5   Node9
2   Node1   Node3   Node6   Node10
3   Node1   Node3   Node7   Node11

How is it possible to get this?

pandas dataframe python-3.x function python
3 Answers

You are already using networkx, why not ask it to get the paths for you:

import networkx as nx

# create a digraph from your edges
G = nx.from_pandas_edgelist( df, 'From', 'To', create_using=nx.DiGraph())
root_node = 'Node1'
leaf_nodes = df.To[~(df.To.isin(df.From))]

# get all paths from leaf_nodes back to root_node
paths = []
for node in leaf_nodes:
    paths.append( nx.shortest_path(G, root_node, node) )
result = pd.DataFrame(paths)

result:

       0      1      2       3
0  Node1  Node2  Node4   Node8
1  Node1  Node2  Node5   Node9
2  Node1  Node3  Node6  Node10
3  Node1  Node3  Node7  Node11
user_20090470

You can iterate graph like DFS then save path on each iterate and return path and convert to DataFrame like below:

import pandas as pd

df = pd.DataFrame({
          'From':['Node1','Node1', 'Node2', 'Node2', 'Node3', 'Node3', 'Node4', 'Node5', 'Node6', 'Node7'],
          'TO'  :['Node2','Node3', 'Node4', 'Node5', 'Node6', 'Node7', 'Node8', 'Node9', 'Node10', 'Node11']
        })

fnl_result = []
def svPath(path, node, df, lst_vst, fnl_result):
    for val in df.values:
        if val[0] == node:
            path.append(val[1])
            svPath(path, val[1], df, lst_vst, fnl_result)
    
    if not path[-1] in lst_vst:
        fnl_result.append([p for p in path])
    for p in path: lst_vst.add(p)
    path.pop()
    return
    
lst_vst = set()
svPath(['Node1'],'Node1', df, lst_vst, fnl_result)
dfOut = pd.DataFrame(fnl_result, columns=['A','B','C','D'])

Output:

>>> dfOut
        A       B       C       D
0   Node1   Node2   Node4   Node8
1   Node1   Node2   Node5   Node9
2   Node1   Node3   Node6   Node10
3   Node1   Node3   Node7   Node11
user_17405770

An alternative approach to solve this using the networkx package.

import networkx as nx
G = nx.DiGraph()
G.add_edges_from((r.From, r.To) for r in df.itertuples())
roots = [n for (n, d) in G.in_degree if d == 0]
print(roots)
leafs = [n for (n, d) in G.out_degree if d == 0]
print(leafs)
pd.DataFrame(
    nx.algorithms.all_simple_paths(G, roots[0], leafs)
)

A directed graph is created and the edges are added to it from df. Node 1 is the only node in G, where the in_degree is equal to 0, i.e. it is the root of the entire graph. Therefore, roots is equal to Node 0.

leafs imply the nodes at the directed graph at which out_degree is equal to 0. i.e., ["Node8", "Node9", "Node10", "Node11"].

nx.algorithms.all_simple_paths(G, roots[0], leafs) provide the list of all the paths starting from Node 1 and ending at each of the nodes in leafs.

user_122762790
Related