Index: test/min_cost_flow_test.cc
===================================================================
--- test/min_cost_flow_test.cc	(revision 2553)
+++ test/min_cost_flow_test.cc	(revision 2584)
@@ -18,111 +18,312 @@
 
 #include <iostream>
+#include <fstream>
+
+#include <lemon/list_graph.h>
+#include <lemon/smart_graph.h>
+#include <lemon/graph_reader.h>
+#include <lemon/dimacs.h>
+#include <lemon/time_measure.h>
+
+#include <lemon/cycle_canceling.h>
+#include <lemon/capacity_scaling.h>
+#include <lemon/cost_scaling.h>
+#include <lemon/network_simplex.h>
+
+#include <lemon/min_cost_flow.h>
+#include <lemon/min_cost_max_flow.h>
+
 #include "test_tools.h"
-#include <lemon/list_graph.h>
-#include <lemon/ssp_min_cost_flow.h>
-//#include <path.h>
-//#include <maps.h>
 
 using namespace lemon;
 
-
-bool passed = true;
-/*
-void check(bool rc, char *msg="") {
-  passed = passed && rc;
-  if(!rc) {
-    std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
- 
-
-  }
+// Checks the feasibility of a flow
+template < typename Graph, typename LowerMap, typename CapacityMap,
+           typename SupplyMap, typename FlowMap >
+bool checkFlow( const Graph& gr,
+                const LowerMap& lower, const CapacityMap& upper,
+                const SupplyMap& supply, const FlowMap& flow )
+{
+  GRAPH_TYPEDEFS(typename Graph);
+  for (EdgeIt e(gr); e != INVALID; ++e)
+    if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
+
+  for (NodeIt n(gr); n != INVALID; ++n) {
+    typename SupplyMap::Value sum = 0;
+    for (OutEdgeIt e(gr, n); e != INVALID; ++e)
+      sum += flow[e];
+    for (InEdgeIt e(gr, n); e != INVALID; ++e)
+      sum -= flow[e];
+    if (sum != supply[n]) return false;
+  }
+
+  return true;
 }
-*/
-
+
+// Checks the optimalitiy of a flow
+template < typename Graph, typename LowerMap, typename CapacityMap,
+           typename CostMap, typename FlowMap, typename PotentialMap >
+bool checkOptimality( const Graph& gr, const LowerMap& lower,
+                      const CapacityMap& upper, const CostMap& cost,
+                      const FlowMap& flow, const PotentialMap& pi )
+{
+  GRAPH_TYPEDEFS(typename Graph);
+  // Checking the Complementary Slackness optimality condition
+  bool opt = true;
+  for (EdgeIt e(gr); e != INVALID; ++e) {
+    typename CostMap::Value red_cost =
+      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
+    opt = red_cost == 0 ||
+          (red_cost > 0 && flow[e] == lower[e]) ||
+          (red_cost < 0 && flow[e] == upper[e]);
+    if (!opt) break;
+  }
+  return opt;
+}
+
+// Runs a minimum cost flow algorithm and checks the results
+template < typename MinCostFlowImpl, typename Graph,
+           typename LowerMap, typename CapacityMap,
+           typename CostMap, typename SupplyMap >
+void checkMcf( std::string test_id,
+               const MinCostFlowImpl& mcf, const Graph& gr,
+               const LowerMap& lower, const CapacityMap& upper,
+               const CostMap& cost, const SupplyMap& supply,
+               bool mcf_result, bool result,
+               typename CostMap::Value total )
+{
+  check(mcf_result == result, "Wrong result " + test_id);
+  if (result) {
+    check(checkFlow(gr, lower, upper, supply, mcf.flowMap()),
+          "The flow is not feasible " + test_id);
+    check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
+    check(checkOptimality(gr, lower, upper, cost, mcf.flowMap(), mcf.potentialMap()),
+          "Wrong potentials " + test_id);
+  }
+}
 
 int main()
 {
-  typedef ListGraph Graph;
-  typedef Graph::Node Node;
-  typedef Graph::Edge Edge;
-
-  Graph graph;
-
-  //Ahuja könyv példája
-
-  Node s=graph.addNode();
-  Node v1=graph.addNode();  
-  Node v2=graph.addNode();
-  Node v3=graph.addNode();
-  Node v4=graph.addNode();
-  Node v5=graph.addNode();
-  Node t=graph.addNode();
-
-  Edge s_v1=graph.addEdge(s, v1);
-  Edge v1_v2=graph.addEdge(v1, v2);
-  Edge s_v3=graph.addEdge(s, v3);
-  Edge v2_v4=graph.addEdge(v2, v4);
-  Edge v2_v5=graph.addEdge(v2, v5);
-  Edge v3_v5=graph.addEdge(v3, v5);
-  Edge v4_t=graph.addEdge(v4, t);
-  Edge v5_t=graph.addEdge(v5, t);
-  
-
-  Graph::EdgeMap<int> length(graph);
-
-  length.set(s_v1, 6);
-  length.set(v1_v2, 4);
-  length.set(s_v3, 10);
-  length.set(v2_v4, 5);
-  length.set(v2_v5, 1);
-  length.set(v3_v5, 4);
-  length.set(v4_t, 8);
-  length.set(v5_t, 8);
-
-  Graph::EdgeMap<int> capacity(graph);
-
-  capacity.set(s_v1, 2);
-  capacity.set(v1_v2, 2);
-  capacity.set(s_v3, 1);
-  capacity.set(v2_v4, 1);
-  capacity.set(v2_v5, 1);
-  capacity.set(v3_v5, 1);
-  capacity.set(v4_t, 1);
-  capacity.set(v5_t, 2);
-
-  //  ConstMap<Edge, int> const1map(1);
-  std::cout << "Mincostflows algorithm test..." << std::endl;
-
-  SspMinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
-    surb_test(graph, length, capacity, s, t);
-
-  int k=1;
-
-  surb_test.augment();
-  check(  surb_test.flowValue() == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
-
-  check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
-
-  check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
-  
-  k=2;
-  
-  check(  surb_test.run(k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
-
-  check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
-  
-  surb_test.augment();
-  surb_test.augment();
-  surb_test.augment();
-  k=4;
-
-  check(  surb_test.run(k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
-
-  check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
-
-
-  std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
-	    << std::endl;
-
-  return passed ? 0 : 1;
-
+  // Various tests on a small graph
+  {
+    typedef ListGraph Graph;
+    GRAPH_TYPEDEFS(ListGraph);
+
+    // Reading the test graph
+    Graph gr;
+    Graph::EdgeMap<int> c(gr), l1(gr), l2(gr), u(gr);
+    Graph::NodeMap<int> s1(gr), s2(gr), s3(gr);
+    Node v, w;
+
+    std::string fname;
+    if(getenv("srcdir"))
+      fname = std::string(getenv("srcdir"));
+    else fname = ".";
+    fname += "/test/min_cost_flow_test.lgf";
+
+    std::ifstream input(fname.c_str());
+    check(input, "Input file '" << fname << "' not found");
+    GraphReader<Graph>(input, gr).
+      readEdgeMap("cost", c).
+      readEdgeMap("capacity", u).
+      readEdgeMap("lower1", l1).
+      readEdgeMap("lower2", l2).
+      readNodeMap("supply1", s1).
+      readNodeMap("supply2", s2).
+      readNodeMap("supply3", s3).
+      readNode("source", v).
+      readNode("target", w).
+      run();
+    input.close();
+
+    // Testing CapacityScaling (scaling enabled)
+    {
+      CapacityScaling<Graph> mcf1(gr,u,c,s1);        checkMcf("#A1",mcf1,gr,l1,u,c,s1,mcf1.run(),true,    0);
+      CapacityScaling<Graph> mcf2(gr,u,c,s2);        checkMcf("#A2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
+      CapacityScaling<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#A3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
+      CapacityScaling<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#A4",mcf4,gr,l2,u,c,s1,mcf4.run(),false,   0);
+      CapacityScaling<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#A5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
+      CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#A6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
+    }
+    // Testing CapacityScaling (scaling disabled)
+    {
+      CapacityScaling<Graph> mcf1(gr,u,c,s1);        checkMcf("#B1",mcf1,gr,l1,u,c,s1,mcf1.run(false),true,    0);
+      CapacityScaling<Graph> mcf2(gr,u,c,s2);        checkMcf("#B2",mcf2,gr,l1,u,c,s2,mcf2.run(false),true, 5240);
+      CapacityScaling<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#B3",mcf3,gr,l1,u,c,s3,mcf3.run(false),true, 7620);
+      CapacityScaling<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#B4",mcf4,gr,l2,u,c,s1,mcf4.run(false),false,   0);
+      CapacityScaling<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#B5",mcf5,gr,l2,u,c,s2,mcf5.run(false),true, 5970);
+      CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#B6",mcf6,gr,l2,u,c,s3,mcf6.run(false),true, 8010);
+    }
+
+    // Testing CostScaling
+    {
+      CostScaling<Graph> mcf1(gr,u,c,s1);        checkMcf("#C1",mcf1,gr,l1,u,c,s1,mcf1.run(),true,    0);
+      CostScaling<Graph> mcf2(gr,u,c,s2);        checkMcf("#C2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
+      CostScaling<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#C3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
+      CostScaling<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#C4",mcf4,gr,l2,u,c,s1,mcf4.run(),false,   0);
+      CostScaling<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#C5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
+      CostScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#C6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
+    }
+
+    // Testing NetworkSimplex (with the default pivot rule)
+    {
+      NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#D1",mcf1,gr,l1,u,c,s1,mcf1.run(),true,    0);
+      NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#D2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
+      NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#D3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
+      NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#D4",mcf4,gr,l2,u,c,s1,mcf4.run(),false,   0);
+      NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#D5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
+      NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#D6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
+    }
+    // Testing NetworkSimplex (with FIRST_ELIGIBLE_PIVOT)
+    {
+      NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::FIRST_ELIGIBLE_PIVOT;
+      NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#E1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true,    0);
+      NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#E2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
+      NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#E3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
+      NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#E4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false,   0);
+      NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#E5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
+      NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#E6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
+    }
+    // Testing NetworkSimplex (with BEST_ELIGIBLE_PIVOT)
+    {
+      NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BEST_ELIGIBLE_PIVOT;
+      NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#F1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true,    0);
+      NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#F2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
+      NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#F3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
+      NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#F4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false,   0);
+      NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#F5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
+      NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#F6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
+    }
+    // Testing NetworkSimplex (with BLOCK_SEARCH_PIVOT)
+    {
+      NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BLOCK_SEARCH_PIVOT;
+      NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#G1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true,    0);
+      NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#G2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
+      NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#G3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
+      NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#G4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false,   0);
+      NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#G5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
+      NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#G6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
+    }
+    // Testing NetworkSimplex (with LIMITED_SEARCH_PIVOT)
+    {
+      NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::LIMITED_SEARCH_PIVOT;
+      NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#H1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true,    0);
+      NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#H2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
+      NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#H3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
+      NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#H4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false,   0);
+      NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#H5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
+      NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#H6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
+    }
+    // Testing NetworkSimplex (with CANDIDATE_LIST_PIVOT)
+    {
+      NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::CANDIDATE_LIST_PIVOT;
+      NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#I1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true,    0);
+      NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#I2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
+      NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#I3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
+      NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#I4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false,   0);
+      NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#I5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
+      NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#I6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
+    }
+
+    // Testing CycleCanceling (with BellmanFord)
+    {
+      CycleCanceling<Graph> mcf1(gr,u,c,s1);        checkMcf("#J1",mcf1,gr,l1,u,c,s1,mcf1.run(),true,    0);
+      CycleCanceling<Graph> mcf2(gr,u,c,s2);        checkMcf("#J2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
+      CycleCanceling<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#J3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
+      CycleCanceling<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#J4",mcf4,gr,l2,u,c,s1,mcf4.run(),false,   0);
+      CycleCanceling<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#J5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
+      CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#J6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
+    }
+    // Testing CycleCanceling (with MinMeanCycle)
+    {
+      CycleCanceling<Graph> mcf1(gr,u,c,s1);        checkMcf("#K1",mcf1,gr,l1,u,c,s1,mcf1.run(true),true,    0);
+      CycleCanceling<Graph> mcf2(gr,u,c,s2);        checkMcf("#K2",mcf2,gr,l1,u,c,s2,mcf2.run(true),true, 5240);
+      CycleCanceling<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#K3",mcf3,gr,l1,u,c,s3,mcf3.run(true),true, 7620);
+      CycleCanceling<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#K4",mcf4,gr,l2,u,c,s1,mcf4.run(true),false,   0);
+      CycleCanceling<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#K5",mcf5,gr,l2,u,c,s2,mcf5.run(true),true, 5970);
+      CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#K6",mcf6,gr,l2,u,c,s3,mcf6.run(true),true, 8010);
+    }
+
+    // Testing MinCostFlow
+    {
+      MinCostFlow<Graph> mcf1(gr,u,c,s1);        checkMcf("#L1",mcf1,gr,l1,u,c,s1,mcf1.run(),true,    0);
+      MinCostFlow<Graph> mcf2(gr,u,c,s2);        checkMcf("#L2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
+      MinCostFlow<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#L3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
+      MinCostFlow<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#L4",mcf4,gr,l2,u,c,s1,mcf4.run(),false,   0);
+      MinCostFlow<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#L5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
+      MinCostFlow<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#L6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
+    }
+
+    // Testing MinCostMaxFlow
+    {
+      MinCostMaxFlow<Graph> mcmf(gr,u,c,v,w);
+      mcmf.run();
+      checkMcf("#M1",mcmf,gr,l1,u,c,s3,true,true,7620);
+    }
+  }
+
+  // Benchmark test on a DIMACS network
+  {
+    typedef SmartGraph Graph;
+    GRAPH_TYPEDEFS(SmartGraph);
+
+    // Reading the test graph
+    Graph graph;
+    Graph::EdgeMap<int> lower(graph), capacity(graph), cost(graph);
+    Graph::NodeMap<int> supply(graph);
+
+    std::string fname;
+    if(getenv("srcdir"))
+      fname = std::string(getenv("srcdir"));
+    else fname = ".";
+    fname += "/test/min_cost_flow_test.net";
+
+    std::ifstream input(fname.c_str());
+    check(input, "Input file '" << fname << "' not found");
+    readDimacs(input, graph, lower, capacity, cost, supply);
+    input.close();
+
+    // NetworkSimplex
+    {
+      Timer t;
+      NetworkSimplex<Graph> mcf(graph, lower, capacity, cost, supply);
+      bool res = mcf.run();
+      t.stop();
+      checkMcf("#T3", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
+      std::cout << "NetworkSimplex";
+      std::cout << std::endl << t << std::endl;
+    }
+    // CapacityScaling
+    {
+      Timer t;
+      CapacityScaling<Graph> mcf(graph, lower, capacity, cost, supply);
+      bool res = mcf.run();
+      t.stop();
+      checkMcf("#T1", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
+      std::cout << "CapacityScaling";
+      std::cout << std::endl << t << std::endl;
+    }
+    // CostScaling
+    {
+      Timer t;
+      CostScaling<Graph> mcf(graph, lower, capacity, cost, supply);
+      bool res = mcf.run();
+      t.stop();
+      checkMcf("#T2", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
+      std::cout << "CostScaling";
+      std::cout << std::endl << t << std::endl;
+    }
+    // CycleCanceling
+    {
+      Timer t;
+      CycleCanceling<Graph> mcf(graph, lower, capacity, cost, supply);
+      bool res = mcf.run();
+      t.stop();
+      checkMcf("#T4", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
+      std::cout << "CycleCanceling";
+      std::cout << std::endl << t << std::endl;
+    }
+  }
+
+  return 0;
 }
