Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Edmonds-Karp Algorithm for a graph which has nodes with flow capacities

I am implementing this algorithm for a directed graph. But the interesting thing about this graph nodes have also their own flow capacities. I think, this subtle change of the original problem must be handled in a special way. Because, In original max-flow problem It was okay to find any path from start to finish(actually, in Edmonds-Karp algorithm, we need to do BFS, and choose the first path that reaches the final node) But with this node-capacity extension, we need to be more careful about 'this path selection' job. I know it because, I implemented the original-algorithm and found myself getting smaller flow values than max-flow, I doubt that it has to do with this node-capacity restrictions.

I put a lot effort on this and came up with some ideas like transforming the initial graph into a graph which has no capacity constraint on nodes by adding self loops (adding self loops to each node and finding paths which includes this self-loops for each node on the path) or adding virtual nodes and edges whose weights supersede the initial node-capacity constraints) However, I am not convinced that any of these are nice solution for this problem.

Any idea would be much appreciated.

Thanks in advance.

like image 606
bfaskiplar Avatar asked Jan 05 '12 23:01

bfaskiplar


1 Answers

There's a simple reduction from the max-flow problem with node capacities to a regular max-flow problem:

For every vertex v in your graph, replace with two vertices v_in and v_out. Every incoming edge to v should point to v_in and every outgoing edge from v should point from v_out. Then create one additional edge from v_in to v_out with capacity c_v, the capacity of vertex v.

So you just run Edmunds-Karp on the transformed graph.

So let's say you have the following graph in your problem (vertex v has capacity 2):

s --> v --> t
   1  2  1

This would correspond to this graph in the max-flow problem:

s --> v_in --> v_out --> t
   1        2         1

It should be apparent that the max-flow obtained is the solution (and it's not particularly difficult to prove either).

like image 127
tskuzzy Avatar answered Oct 01 '22 00:10

tskuzzy