How to create a graph and call the algorithm with this code

Question

I've been trying to understand this code; it's an implementation of the push-relabel algorithm in C++:

// Adjacency list implementation of FIFO push relabel maximum flow
// with the gap relabeling heuristic.  This implementation is
// significantly faster than straight Ford-Fulkerson.  It solves
// random problems with 10000 vertices and 1000000 edges in a few
// seconds, though it is possible to construct test cases that
// achieve the worst-case.
//
// Running time:
//     O(|V|^3)
//
// INPUT: 
//     - graph, constructed using AddEdge()
//     - source
//     - sink
//
// OUTPUT:
//     - maximum flow value
//     - To obtain the actual flow values, look at all edges with
//       capacity > 0 (zero capacity edges are residual edges).

#include <cmath>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

typedef long long LL;

struct Edge {
  int from, to, cap, flow, index;
  Edge(int from, int to, int cap, int flow, int index) :
    from(from), to(to), cap(cap), flow(flow), index(index) {}
};

struct PushRelabel {
  int N;
  vector<vector<Edge> > G;
  vector<LL> excess;
  vector<int> dist, active, count;
  queue<int> Q;

  PushRelabel(int N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {}

  void AddEdge(int from, int to, int cap) {
    G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
    if (from == to) G[from].back().index++;
    G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
  }

  void Enqueue(int v) { 
    if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); } 
  }

  void Push(Edge &e) {
    int amt = int(min(excess[e.from], LL(e.cap - e.flow)));
    if (dist[e.from] <= dist[e.to] || amt == 0) return;
    e.flow += amt;
    G[e.to][e.index].flow -= amt;
    excess[e.to] += amt;    
    excess[e.from] -= amt;
    Enqueue(e.to);
  }

  void Gap(int k) {
    for (int v = 0; v < N; v++) {
      if (dist[v] < k) continue;
      count[dist[v]]--;
      dist[v] = max(dist[v], N+1);
      count[dist[v]]++;
      Enqueue(v);
    }
  }

  void Relabel(int v) {
    count[dist[v]]--;
    dist[v] = 2*N;
    for (int i = 0; i < G[v].size(); i++) 
      if (G[v][i].cap - G[v][i].flow > 0)
    dist[v] = min(dist[v], dist[G[v][i].to] + 1);
    count[dist[v]]++;
    Enqueue(v);
  }

  void Discharge(int v) {
    for (int i = 0; excess[v] > 0 && i < G[v].size(); i++) Push(G[v][i]);
    if (excess[v] > 0) {
      if (count[dist[v]] == 1) 
    Gap(dist[v]); 
      else
    Relabel(v);
    }
  }

  LL GetMaxFlow(int s, int t) {
    count[0] = N-1;
    count[N] = 1;
    dist[s] = N;
    active[s] = active[t] = true;
    for (int i = 0; i < G[s].size(); i++) {
      excess[s] += G[s][i].cap;
      Push(G[s][i]);
    }

    while (!Q.empty()) {
      int v = Q.front();
      Q.pop();
      active[v] = false;
      Discharge(v);
    }

    LL totflow = 0;
    for (int i = 0; i < G[s].size(); i++) totflow += G[s][i].flow;
    return totflow;
  }
};

The code compiles and works, but I can't understand how I should pass input to it. Ideally a main() function should read the source and the sink (which are "imaginary" anyway and are only neccessary for the algorithm to work), and then all the data neccessary to build the graph with AddEdge(). But how to do that is currently beyond me.

My main() should look like this

int main()
{
    int source, sink;
    vector < vector < int > > graph;
    std::cin >> source >> sink;
    //here should be the nested for loops to read in the graph

    // and here the arguments should be passed to AddEdge
    return 0;
}

I think that source should be used to iniialise some Edge.froms, and it should be similar with sink and some Edge.tos, but I can't figure how to build a graph.

Answer 1

Create an instance of the struct PushRelabel(N) with N nodes:

struct PushRelabel prGraph(N);

Then you build the graph with the AddEdge function. Assuming the nice Edge structure, this could be done as

std::vector<Edge> edges;

for( auto e : edges )
  prGraph.AddEdge(e.from, e.to, e.cap);

Then there is a GetMaxFlow function taking your source s and sink t which computes and returns the flow:

int s, t;
auto flow = prGraph.getMaxFlow(s, t);

Of course, you need to read all the edges and capacities and the number of nodes yourself, I hope this is a starting point.

---

int main()
{
   struct PushRelabel prGraph(4);
   prGraph.AddEdge(0,1,2);
   prGraph.AddEdge(0,2,2);
   prGraph.AddEdge(1,3,1);
   prGraph.AddEdge(2,3,3);

   std::cout<< prGraph.GetMaxFlow(0,3) << std::endl;
}

For this graph with source s = 0 and sink t = 3

    1
   / \
c(2)  c(1)
 /     \
0       3
 \     /
c(2)  c(3)  
   \ /
    2

Outputs 3, as it should.