How to find a shortest path for edge capacity to meet demand?

Question

G is a undirected graph with edge capacities. And for any given input(SourceNode, TargetNode, demand), how to find all path that all edge in the path should satisfy capacity >= demand.

I know networkx has netowrk_simplex() or min_cost_flow() can achieved similar funcitons but the path it returns is in the form of a flow, not a simple path I want.

For example:

G = nx.Graph()
G.add_edge("a", "b", capacity=4)
G.add_edge("a", "c", capacity=10)
G.add_edge("b", "d", capacity=9)
G.add_edge("c", "d", capacity=5)

I want to achieve this:

path = path(G, source, target, demand=5)
path
"[a,c,d]"

path [a,b,d] is not satisfy because the edge(a,b) capacity 4 is less than the demand 5.

If there are more than one path meet the demand, the function can return a path list.

Thank you.

Answer 1

I think the easiest way to tackle this is to just drop all edges that don't meet the criteria and then run the shortest path analysis.

Rather than creating a new graph and modifying it, however, we can use a "restricted view" of the existing graph and do the analysis on that:

def path(graph, source, target, demand):
    H = nx.restricted_view(
        graph,
        [], 
        tuple((x, y) for x, y, attr in graph.edges(data = True) if attr['capacity'] < demand))

    return [path for path in nx.all_shortest_paths(H, source, target, demand)]

The restricted_view method takes the name of the graph and iterables of nodes and edges (only a tuple of tuples for edges is allowed I believe) to remove. Since no nodes are removed, an empty list [] is passed in.

The tuple generator expression uses x, y, attr to represent the first node, second node, and dictionary of node attributes and returns a set of edges that meet the given criteria, which are then removed in the restricted view.

The return statement includes a list comprehension since the all_shortest_paths method returns a generator object by default.

Testing with your criteria:

desired_paths = path(G, 'a', 'd', 5)
print(desired_paths)

>>>[['a','c','d']]

For additional testing, I added two edges ('a','e') and ('e','d') and confirmed that the output then becomes [['a','c','d'],['a','e','d']].