8

I was trying to implement Edmonds-Karp in C++ for maximum flow, and I wrote it slightly differently:

  1. Instead of going through all edges in residual graph, I only went through the edges that are present in the original graph, using the adjacency list.
  2. I did not update any back-edges when updating the residual graph with min flow.

Interestingly, when I ran my code, it gave me correct results. So I went to Wikipedia's example, where it specifically show how a back-edge is being used. When I fed this graph to my code, I got the correct answer again. I also checked the resultant flow matrix, and it was identical to Wikipedia's.

Can someone explain why we must add and update back-edges, and maybe give an example where they are critical?

Here's the code that I wrote (updated to include back edges):

xyz
  • 3,349
  • 1
  • 23
  • 29
  • Just to be sure to understand well, does it mean that when you take an arc in the reverse way, you do not update the value of the flow on this arc ? – Damien Prot Aug 09 '16 at 07:17
  • @DamienProt I had this idea that instead of iterating through the residual graph, I go through only the original adjacency list. So I never visit any back edge, and saw no point updating any. – xyz Aug 09 '16 at 07:21

2 Answers2

7

Consider the following flow network enter image description here

Suppose the first flow is s → u → v → t. (If you object that that the BFS of Edmonds-Karp would never choose this, then augment the graph with some more vertices between s and v and between u and t).

Without reversing flow u → v, it is impossible to obtain the optimal flow of 20.

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185
  • BFS discovers shortest paths first (number of edges). It will grab the two 10 flow paths first, and the 1 weight edge won't be considered. I just ran my code with your graph and the max flow is indeed 20. – xyz Aug 09 '16 at 07:28
  • 1
    @prakharsingh95 : I completely agree with the answer of Ami Tavory, it does not make sense to forget about back edges. – Damien Prot Aug 09 '16 at 07:37
  • Sorry, I was on mobile and somehow missed it. Indeed you are correct. In fact, @ead gave the same example. From what I understand, this means that when there is are longer paths with bigger net flow than a short path, which shares edges with them it becomes necessary to to add back edges. – xyz Aug 09 '16 at 07:44
  • @DamienProt Yeah, back edges are important. I just couldn't figure out why! – xyz Aug 09 '16 at 07:45
  • I might be crazy, but couldn't we collapse any series of nodes with one incoming and one outgoing into one node with the min of the set of the original edges? For ex: A - (5) -> B - (4) -> C - (5) -> D can be reduced to A - (4) -> D – mBrice1024 Apr 17 '19 at 15:54
6

try out the following case:

int main() {
    Digraph<int> g(8);
    g.addEdge(0,1,1);
    g.addEdge(1,2,1);
    g.addEdge(2,4,1);
    g.addEdge(0,3,1);
    g.addEdge(3,4,1);
    g.addEdge(4,7,1);
    g.addEdge(3,5,1);
    g.addEdge(5,6,1);
    g.addEdge(6,7,1);

    cout<<g.maxFlowEdmondsKarp(0,7);

    return 0;
}

Visualization: enter image description here

your program takes the shortest way 0-3-4-7 first and has then no chance to find 0-1-2-4-7 and 0-3-5-6-7. You get 1 but 2 would be the right answer.

Would you have inserted the back-edge, then you would find the following paths:

  1. 0-3-4-7
  2. 0-1-2-4-3(back-edge!)-5-6-7, getting the max flow 2.
ead
  • 32,758
  • 6
  • 90
  • 153