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.
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']].