Find all node predecessors in a directed graph

user_7781354 0
Viewed 768

I need to find all the connected elements in column ID.

for e.g. My main Element is 4120882840 in ID Column.

4120882840 is connected to 4120874920, 4120874720 (refer column ID2) likewise, 4120874920 is connected to 4121482000 which is further connected to 4121480930 and so on

finally, all the elements that are connected to 4120882840 are [4120882840, 4120874920, 4121482000, 4121480930, 4121480780, 4120874720, 4120871840, 4120871830] total 8 in the list

But I am only getting first 7 i.e. [4120882840, 4120874920, 4121482000, 4121480930, 4121480780, 4120874720, 4120871840]

file link https://drive.google.com/file/d/1E5_cbGjtKoB6RDSsC7ned-X2RFoF6Rad/view?usp=sharing

This is my Code

import pandas as pd
df = pd.read_csv("Test.csv")
ID = df.iloc[:,1] 
ID2 = df.iloc[:,2] 

x = [4120882840]
for i in range (len(ID)):
    for element in x:
        if element == ID2[i]:
            newID = ID[i]
            #print (newID)
            x.append (newID)
print (x)
pandas networkx graph-theory graph python
3 Answers

It looks like you want to find all predecessors of the node in question. This becomes clearer by inspecting the corresponding component subgraph:

G = nx.from_pandas_edgelist(df, source='ID', target='ID2',
                                create_using=nx.DiGraph)

comps = nx.weakly_connected_components(G)
comp = next(comp for comp in comps if 4120882840 in comp)
H = nx.subgraph(G, comp)
plt.figure(figsize=(10,4))
nx.draw(H, node_color='lightgreen', with_labels=True, node_size=500)

enter image description here

We can use to find the node's predecessors. NetworkX has nx.edge_dfs, where we can set orientation='reverse' to traverse every predecessor edge in reverse order (upstream). Then we can just flatten the returned list of tuples to obtain the corresponding nodes:

from itertools import chain 
source = 4120882840

*n, _ = zip(*(nx.edge_dfs(G, source, orientation='reverse')))
print(set(chain.from_iterable(n)))
{4120874720, 4120871840, 4121480930, 4120874920, 4121480780, 
 4121482000, 4120871830, 4120882840}
user_96986840

Is this what you're looking for?

import networkx as nx
graph = nx.from_pandas_edgelist(df, source='ID', target='ID2',
                                create_using=nx.DiGraph)
visited = set()
to_visit = [4120882840]
while to_visit:
    dst = to_visit.pop()
    visited.add(dst)
    for parent in graph.predecessors(dst):
        if parent in visited:
            continue
        to_visit.append(parent)
print(visited)

Output

{4120874720, 4120871840, 4121480930, 4120874920, 4121480780, 4121482000, 4120871830, 4120882840}
user_126114090

You can use mask to check if the element in ID2 and you can use list(set(x)) to remove duplicate

Here is an algorithm that work:

x = [4120882840]
lastLen = 0
while lastLen != len(x):
    lastLen = len(x)
    for i in x:
        x += list(df['ID'][df['ID2'] == i])
        x = list(set(x))
user_52141200
Related