CODEWITHSUNDEEP
pandasalgorithmnetworkxshortest-path
Guy Barash
Guy Barash

Reputation: 490

most probable path in networkx

I had a adjacency matrix (as a pandas dataframe) with each cell is a probability of going from A to B

The row is the "from" and the column is "to". The sum of each row is 1.0.

I've built a networkx graph and now the probabilities are the "weights" of the graph.

I'm trying to find the most probable path - i.e the product of the weights is the lowest, not the sum. I know that networkx shortest path find the optimal path i terms of the sum of the weights. How do i find the optimal path in terms of the optimal product?

Edit: The inputs are graph G, node "SOURCE" and node "TARGET", which for simplicity are indeed connected by multiple paths. I want to find the most probable path between them in G

Thx

Upvotes: 1

Views: 964

Answers (1)

yatu
yatu

Reputation: 88236

One way to do this, could be to look for all paths from a given source an target, using nx.all_simple_paths, and while iterating over all intermediate edges, multiply their respective edge weights, to keep track of the one that gives the smallest resulting weight.

Following this logic, we could do something like:

def shortest_path_w_prod(G, source, target):
    paths = list(nx.all_simple_paths(G, source, target))
    w_path = []
    for path in paths:
        w = 1
        for edge in zip(path[:-1],  path[1:]):
            w *= G.get_edge_data(*edge)['weight']
        w_path.append(w)
    min_path_ix = w_path.index(min(w_path))
    return paths[min_path_ix]

Let's see with an example:

l = [('a', 'f', 2), ('f', 'c', .1), ('r', 'e', 3), ('d', 'e', .4), ('e', 'a', 5), ('a', 'b', 2), ('c', 'a', 1.5), ('d', 'a', 2.), ('c', 'e', 0.2)]
G = nx.Graph()
G.add_weighted_edges_from(l)

Which looks like:

pos = nx.spring_layout(G, scale=20, k=3/np.sqrt(G.order()))
nx.draw(G, pos=pos,
        node_color='lightblue', 
        with_labels=True, 
        node_size=500)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)

enter image description here

We would get that the shortest path, following the described logic, would be:

shortest_path_w_prod(G, 'b', 'r')
# ['b', 'a', 'f', 'c', 'e', 'r']

Whereas the shortest path from nx.shortest_path, following the dijkstra algorithm, would give:

nx.shortest_path(G, 'b', 'r', 'weight')
# ['b', 'a', 'c', 'e', 'r']

Upvotes: 2

Related Questions