Edmonds-Karp for Max Flow having timeout

[Mae4ashy]

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:

  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

[salem c]

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.

[Mae4ashy]

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

[lastchance]

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

#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

[Mae4ashy]

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 :).