Edmonds-Karp for Max Flow having timeout

Hello there :)

So here's the thing: I've written a code for the Edmonds-Karp Algorithm for Max Flow in a Graph. And it is working for very small graphs, but I get a timeout for bigger graphs. I implemented it almost the same as the code that can be found online, for example on geeksforgeeks.

The only difference is, that i don't use an adjacency matrix, but a matrix for the capacities (0 if there is no edge between two vertices) and a matrix for the flow values that can be set for the vertices.

Here's my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
  template<typename C>
bool getAugmentingPath(DiGraph<C>& g, std::vector<size_t>& path){ //bfs
  std::vector<bool> visited(g.size(), false);
  
  std::list<size_t> q; //create Queue
  visited[0] = true; //mark source as visited and add to queue
  q.push_back(0);
  
  path[0] = 0;
  
  while(!q.empty()){
    int u;
    u = q.front(); //remove front of queue
    q.pop_front();
    
    //check adjacent vertices
    for(std::size_t v = 1; v<g.size(); v++){
      if(visited[v] == false && g.getEdgeCapacity(u,v) != 0){
        
        if(v == g.size()-1){
          path[v] = u;
          return true;
        }
        
        visited[v] = true;
        q.push_back(v);
        path[v] = u;
      }
    }
  }
  
  return false;
}

//Ford-Fulkerson
template<typename C>
void maxFlow(DiGraph<C>& g)
{
    int u,v,a,b;
    int n = g.size();
    int MAX = std::numeric_limits<int>::max();
    
    DiGraph<C> rGraph(n); //residual network
    
    for(u=0; u<n; u++){ //transfer capacities
      for(v=0; v<n; v++){
        rGraph.setEdgeCapacity(u,v,g.getEdgeCapacity(u,v));
      }
    }
    std::vector<size_t> path(n,0); //vector containing path found through BFS
     
    for(int u=0; u<n; ++u){ //no flow initially
      for(int v=0; v<n; ++v){
      g.setFlowValue(u,v,0);
      rGraph.setFlowValue(u,v,0);
      }
    }
    
    
    while(getAugmentingPath(g, path))
    {
        int path_flow = MAX;
        
        for(v=n-1; v!=0; v=path[v]){ //find maximal flow through path
          u = path[v];
          path_flow = std::min(path_flow, rGraph.getEdgeCapacity(u,v));
        }
        
        for(v = n-1; v!=0; v=path[v]){ //update flow
          u = path[v];
          a = rGraph.getFlowValue(u,v);
          b = g.getFlowValue(u,v);
          rGraph.setFlowValue(u,v,a-=path_flow);
          g.setFlowValue(u,v,b+=path_flow);
        }
       
    }

}



The addition of the flow values in the flow vector is made later in the main function.
I got the timeout after initializing the path-vector. But without initializing it, there will be a segmentation fault. Plus, the small cases only work after removing the while(getAugmentingPath)-loop, so i guess there is a problem with the BFS-algorithm :).

Thanks for your help, i really appreciate it!
Mae
Last edited on
By "timeout", you mean you submitted it to some online coding assessment and got told "time limit exceeded" ?

Also, http://www.sscce.org/
You have a main() and a test case, so post it.
Make it easy for people to run what you're running.
Ahh, I'm sorry, I didn't want to flood this post with code xd

Yes, I submitted it and there was a virtual timer that expired.
Here's my class: https://codeshare.io/9OxZ
That's the main(): https://codeshare.io/8pkY
Now you can just copy-paste it :)

Here's how the input works:
- "random" followed by number of vertices n and edges m,
- "edges" followed by number of vertices n and a sequence of egdes in the format a b capacity,
terminated by end
- "matrix" followed by number of vertices n and a sequence of n*n capacity values

So for example the small case that I said was working looks like this:
random 5 10
(although it's only working after removing the while-loop and just running what's inside)

Edit: I figured it out after changing the function signature of getAugmentingPath a little bit, thanks
Last edited on
Here's an attempt at coding it from scratch. The example graph is that from the Wikipedia article on Edmonds-Karp:
https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
with nodes A-G mapped to indices 1-7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <limits>
using namespace std;

const int startIndex = 1;              // 0 or 1 for first array index
const double LARGE = numeric_limits<double>::max();

//----------------------------------------------------------------------

struct Edge
{
   double flow;
   double capacity;
};

using Digraph = vector< map<int,Edge> >;

//----------------------------------------------------------------------

void writeGraph( Digraph& g )
{
   for ( int a = startIndex; a < g.size(); a++ )
   {
      for ( const auto &pr : g[a] )
      {
         int b  = pr.first ;
         Edge e = pr.second;
         if ( e.capacity > 0.0 ) cout << a << " to " << b << "   flow: " << e.flow << "   capacity: " << e.capacity << '\n';
      }
   }
   cout << '\n';
}

//----------------------------------------------------------------------

Digraph readGraph( istream &in )
{
   int N;
   int a, b;
   double capacity;

   in >> N;
   N += startIndex;          // Keep everything 0-based internally

   Digraph g( N );
   while( in >> a >> b >> capacity )
   { 
      g[a][b] = { 0.0, capacity };
      g[b][a] = { 0.0, 0.0      };     // for a one-way edge
//    g[b][a] = { 0.0, capacity };     // for a two-way edge
   }
   return g;
}

//----------------------------------------------------------------------

vector<int> getPath( Digraph &g, int source, int target )       // find a path from source to target with spare capacity
{
   queue<int> Q;
   vector<int> predecessor( g.size(), -1 );                     // -1 signifies no predecessor on path
   
   Q.push( source );
   while( !Q.empty() )
   {
      int a = Q.front();   Q.pop();
      for ( auto &pr : g[a] )
      {
         int b = pr.first;                                      // end node for this edge
         // Check:
         //     not used             not start                 spare capacity
         if ( predecessor[b] < 0 && b != source && pr.second.capacity > pr.second.flow )
         {
            predecessor[b] = a;
            Q.push( b );
         }
         if ( predecessor[target] >= 0 ) return predecessor;    // return as soon as a path is found
      }
   }

   return predecessor;
}

//----------------------------------------------------------------------

double MaxFlow( Digraph &g, int source, int target )            // maximum flow by Edmonds-Karp algorithm
{
   double totalFlow = 0.0;                                      // the total flow from source to target

   while( true )
   {
      // Try to find path with spare capacity
      vector<int> predecessor = getPath( g, source, target );
   
      if ( predecessor[target] >= 0 )                           // found a path with capacity
      {
         double extraFlow = LARGE;
   
         // Find maximum extra flow that can be routed along this path
         for ( int b = target, a = predecessor[b]; a >= 0; b = a, a = predecessor[b] )   // source has no predecessor ( a = -1)
         {
            Edge e = g[a][b];
            extraFlow = min( extraFlow, e.capacity - e.flow );
         }
   
         // Update the current flow situation
         for ( int b = target, a = predecessor[b]; a >= 0; b = a, a = predecessor[b] )
         {
            g[a][b].flow += extraFlow;
            g[b][a].flow -= extraFlow;
         }

         // Update the total flow
         totalFlow += extraFlow;
      }
      else                                                      // no spare capacity
      {
         return totalFlow;
      }
   }
}

//======================================================================

int main()
{
   // Replace in by an ifstream if you want to read from file
   stringstream in( "7       \n"              // N
                    "1 2 3.0 \n"              // node1 node2 capacity
                    "1 4 3.0 \n"              // etc.
                    "2 3 4.0 \n"
                    "3 1 3.0 \n"
                    "3 4 1.0 \n"
                    "3 5 2.0 \n"
                    "4 5 2.0 \n"
                    "4 6 6.0 \n"
                    "5 2 1.0 \n"
                    "5 7 1.0 \n"
                    "6 7 9.0 \n" );

   Digraph g = readGraph( in );
   int source = 1, target = 7;

   cout << "Maximum flow: " << MaxFlow( g, source, target ) << "\n";

   cout << "Final graph:\n";
   writeGraph( g );
}


Maximum flow: 5
Final graph:
1 to 2   flow: 2   capacity: 3
1 to 4   flow: 3   capacity: 3
2 to 3   flow: 2   capacity: 4
3 to 1   flow: 0   capacity: 3
3 to 4   flow: 1   capacity: 1
3 to 5   flow: 1   capacity: 2
4 to 5   flow: 0   capacity: 2
4 to 6   flow: 4   capacity: 6
5 to 2   flow: 0   capacity: 1
5 to 7   flow: 1   capacity: 1
6 to 7   flow: 4   capacity: 9


Last edited on
Oh wow, thanks. I think now I understand the stuff that went wrong with my approach. There were several mistakes that I found, but at some points I didn't really understand why the stuff was wrong. Comparing to your algorithm helped a lot :).
Topic archived. No new replies allowed.