CODEWITHSUNDEEP
pythonnetworkx
W3LS
W3LS

Reputation: 13

NetworkX weighted digraph algorithms

I am trying to solve a problem similar to what I have described below. Could you please suggest a solution or recommend some algorithms to try in NetworkX. Many thanks.

Say there is a ball that has a starting momentum of 100. How far can the ball get down each of all the possible paths before it loses all momentum, and stops?

When the ball rolls uphill it loses momentum (i.e. the edge has a negative weight).

When the ball rolls downhill it gains momentum (i.e. the edge has a positive weight).

Examples:

1st path: (1)--[weight: -50]-->(2)--[weight: 40]-->(3)--[weight: -50]-->(4)--[weight: -90]-->(5)

2nd path: (1)--[weight: -105]-->(6)

Etc.

So, in the first path the ball gets only as far as node 4. In the second path the ball doesn’t get past node 1.

Upvotes: 0

Views: 396

Answers (2)

W3LS
W3LS

Reputation: 13

The bellman_ford_predecessor_and_distance algorithm seems to work. If the distance <= -100 then the ball stopped at the predecessor node, so I copied the graph, removed the relevant edges, and ran the algorithm again to check.

import networkx as nx

G = nx.DiGraph()

G.add_edge(1, 2, weight= -50)
G.add_edge(2, 3, weight= 40)
G.add_edge(3, 4, weight= -50)
G.add_edge(4, 5, weight= -90)
G.add_edge(1, 6, weight= -105)
G.add_edge(6, 7, weight= 110)

pred, dist = nx.bellman_ford_predecessor_and_distance(G, 1)

print(pred, dist)

F = G

for x, y in dist.items():
 if y <= -100:
  z = pred.get(x)[0]
  F.remove_edge(z,x)  

pred, dist = nx.bellman_ford_predecessor_and_distance(G, 1)

print(pred, dist)

Upvotes: 1

Mykola Zotko
Mykola Zotko

Reputation: 17794

I haven‘t found any special algorithm in Networkx for this purpose. You can use the following function, which uses Bellman-Ford Algorithm:

import networkx as nx

G = nx.DiGraph()
G.add_weighted_edges_from([(1, 2, -50), (2, 3, 40), (3, 4, -50),
                           (4, 5, -90), (1, 6, -105)])

def func(graph, source, target, start_weight):
    total = start_weight
    path = []
    p = nx.bellman_ford_path(graph, source, target)
    for u, v in zip(p, p[1:]):
        total += G[u][v]['weight']
        path.append(u)
        if total < 0:
            return path
    else:
        return path

print(func(G, 1, 5, 100))
# [1, 2, 3, 4]

print(func(G, 1, 6, 100))
# [1]

Upvotes: 1

Related Questions