#include <iostream>
#include <lemon/smart_graph.h>
#include <lemon/preflow.h>
#include <lemon/lp.h>
#include <lemon/cplex.h>	// use this for CPLEX
//#include <lemon/glpk.h>	// use this for GLPK

using namespace std;
using namespace lemon;

int main() {
  typedef SmartDigraph GR;
  typedef CplexLp LP;		// use this for CPLEX
  // typedef GlpkLp LP;		// use this for GLPK
  // typedef Lp LP; 		// use this for the default LP solver

  // Building a digraph with arc capacities
  GR g;
  GR::ArcMap<int> capacity(g);
  
  GR::Node s = g.addNode();
  GR::Node n1 = g.addNode();
  GR::Node n2 = g.addNode();
  GR::Node t = g.addNode();

  GR::Arc a1 = g.addArc(s, n1);
  GR::Arc a2 = g.addArc(s, n2);
  GR::Arc a3 = g.addArc(n1, t);
  GR::Arc a4 = g.addArc(n2, t);
  
  capacity[a1] = 10;
  capacity[a2] = 4;
  capacity[a3] = 7;
  capacity[a4] = 5;

  // Find maximum s-t flow with LP
  LP lp;
  GR::ArcMap<LP::Col> f(g);
  lp.addColSet(f);

  // Capacity constraints
  for (GR::ArcIt a(g); a != INVALID; ++a) {
    lp.colLowerBound(f[a], 0);
    lp.colUpperBound(f[a], capacity[a]);
  }

  // Flow conservation constraints
  for (GR::NodeIt n(g); n != INVALID; ++n) {
    if (n == s || n == t) continue;
    Lp::Expr e;
    for (GR::OutArcIt a(g, n); a != INVALID; ++a) e += f[a];
    for (GR::InArcIt a(g, n); a != INVALID; ++a) e -= f[a];
    lp.addRow(e == 0);
  }
  
  // Objective function
  Lp::Expr o;
  for (GR::OutArcIt a(g, s); a != INVALID; ++a) o += f[a];
  for (GR::InArcIt a(g, s); a != INVALID; ++a) o -= f[a];

  lp.max();
  lp.obj(o);
  
  // Obtain results
  if (lp.solve() == Lp::SOLVED && lp.primalType() == Lp::OPTIMAL) {
    cout << "LP optimal solution found" << endl;
    cout << "Maximum flow value: " << lp.primal() << endl;
  } else {
    cout << "LP optimal solution not found" << endl;
  }
  cout << endl;
  
  // Find maximum s-t flow with Preflow
  Preflow<GR> preflow(g, capacity, s, t);
  preflow.run();
  
  cout << "Preflow algorithm finished" << endl;
  cout << "Maximum flow value: " << preflow.flowValue() << endl;

  return 0;
}