Find all the pairs in a network diagram

Question

I'm tying to solve a problem. I've a pandas DataFrame with columns Source, Target and Freq.

Let's assume I'm interested in Node 1. Node 1 can be linked in below way.

Source Target
5 1
3 5
2 3
6 2

5 is the source when 1 is the Target and 3 is the source when 5 is the target and the link goes on. I'm essentially trying to create a network graph which would b 6-2-3-5-1.

Is there any way to programmatically find the all source-target combinations that would eventually end up in a Target of my choice?

Edit: Edited to provide more clarification.

Answer 1

Is there any way to programmatically find the all source-target combinations

Yes, this is known as the Shortest path problem, that is given a graph G constructed of nodes/vertices V connected by edges E find the shortest path between source and target nodes. What you specify is a list of edges where each edge connects some node v(i) to another node v(j).

There are several algorithms that implement a solution. You can use a library like NetworkX so you don't have to implement the algorithm yourself. For example,

# let's create the data frame as per your example
import pandas as pd
df = pd.DataFrame([
        (5, 1),
        (3, 5),
        (2, 3),
        (6, 2),
    ], columns=['source', 'target'])

# import networkx and build the graph
import networkx as nx
G = nx.Graph()
G.add_edges_from(df.values)

# import the shortest_paths generic algorithm
nx.shortest_path(G, source=6, target=1)
=> 
[6, 2, 3, 5, 1]

find the all source-target combinations

NetworkX provides many algorithms that you should match with the specific use-case you are trying to solve. To find all the possible paths given a source and a target node,

# assume we have added another edge source=6 target=1 
list(nx.all_simple_paths(G, source=6, target=1))
=> 
[[6, 1], [6, 2, 3, 5, 1]]

all source-target combinations (...) that would eventually end up in a target of my choice

We want to find all possible source nodes and paths that eventually end up at a target of our choice, without specifying the source node:

# find all start/end nodes
import networkx as nx
# -- we need a directed graph
dG = nx.DiGraph()
dG.add_edges_from(df.values)
# -- find possible source nodes
source_nodes = [x for x in G.nodes_iter() if dG.out_degree(x) >= 1]
# -- for every source node find the shortest path to target
paths = [nx.shortest_path(G, source=source, target=1) for source in source_nodes]
paths
=>
[[2, 3, 5, 1], [3, 5, 1], [5, 1], [6, 2, 3, 5, 1]]