alpar@906: /* -*- C++ -*-
alpar@906:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
alpar@899: #include <iostream>
kpeter@2584: #include <fstream>
kpeter@2584: 
kpeter@2584: #include <lemon/list_graph.h>
kpeter@2584: #include <lemon/smart_graph.h>
kpeter@2584: #include <lemon/graph_reader.h>
kpeter@2584: #include <lemon/dimacs.h>
kpeter@2584: #include <lemon/time_measure.h>
kpeter@2584: 
kpeter@2584: #include <lemon/cycle_canceling.h>
kpeter@2584: #include <lemon/capacity_scaling.h>
kpeter@2584: #include <lemon/cost_scaling.h>
kpeter@2584: #include <lemon/network_simplex.h>
kpeter@2584: 
kpeter@2584: #include <lemon/min_cost_flow.h>
kpeter@2584: #include <lemon/min_cost_max_flow.h>
kpeter@2584: 
alpar@899: #include "test_tools.h"
alpar@899: 
alpar@921: using namespace lemon;
alpar@899: 
kpeter@2584: // Checks the feasibility of a flow
kpeter@2584: template < typename Graph, typename LowerMap, typename CapacityMap,
kpeter@2584:            typename SupplyMap, typename FlowMap >
kpeter@2584: bool checkFlow( const Graph& gr,
kpeter@2584:                 const LowerMap& lower, const CapacityMap& upper,
kpeter@2584:                 const SupplyMap& supply, const FlowMap& flow )
kpeter@2584: {
kpeter@2584:   GRAPH_TYPEDEFS(typename Graph);
kpeter@2584:   for (EdgeIt e(gr); e != INVALID; ++e)
kpeter@2584:     if (flow[e] < lower[e] || flow[e] > upper[e]) return false;
alpar@899: 
kpeter@2584:   for (NodeIt n(gr); n != INVALID; ++n) {
kpeter@2584:     typename SupplyMap::Value sum = 0;
kpeter@2584:     for (OutEdgeIt e(gr, n); e != INVALID; ++e)
kpeter@2584:       sum += flow[e];
kpeter@2584:     for (InEdgeIt e(gr, n); e != INVALID; ++e)
kpeter@2584:       sum -= flow[e];
kpeter@2584:     if (sum != supply[n]) return false;
kpeter@2584:   }
alpar@899: 
kpeter@2584:   return true;
kpeter@2584: }
kpeter@2584: 
kpeter@2584: // Checks the optimalitiy of a flow
kpeter@2584: template < typename Graph, typename LowerMap, typename CapacityMap,
kpeter@2584:            typename CostMap, typename FlowMap, typename PotentialMap >
kpeter@2584: bool checkOptimality( const Graph& gr, const LowerMap& lower,
kpeter@2584:                       const CapacityMap& upper, const CostMap& cost,
kpeter@2584:                       const FlowMap& flow, const PotentialMap& pi )
kpeter@2584: {
kpeter@2584:   GRAPH_TYPEDEFS(typename Graph);
kpeter@2584:   // Checking the Complementary Slackness optimality condition
kpeter@2584:   bool opt = true;
kpeter@2584:   for (EdgeIt e(gr); e != INVALID; ++e) {
kpeter@2584:     typename CostMap::Value red_cost =
kpeter@2584:       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
kpeter@2584:     opt = red_cost == 0 ||
kpeter@2584:           (red_cost > 0 && flow[e] == lower[e]) ||
kpeter@2584:           (red_cost < 0 && flow[e] == upper[e]);
kpeter@2584:     if (!opt) break;
kpeter@2584:   }
kpeter@2584:   return opt;
kpeter@2584: }
kpeter@2584: 
kpeter@2584: // Runs a minimum cost flow algorithm and checks the results
kpeter@2584: template < typename MinCostFlowImpl, typename Graph,
kpeter@2584:            typename LowerMap, typename CapacityMap,
kpeter@2584:            typename CostMap, typename SupplyMap >
kpeter@2584: void checkMcf( std::string test_id,
kpeter@2584:                const MinCostFlowImpl& mcf, const Graph& gr,
kpeter@2584:                const LowerMap& lower, const CapacityMap& upper,
kpeter@2584:                const CostMap& cost, const SupplyMap& supply,
kpeter@2584:                bool mcf_result, bool result,
kpeter@2584:                typename CostMap::Value total )
kpeter@2584: {
kpeter@2584:   check(mcf_result == result, "Wrong result " + test_id);
kpeter@2584:   if (result) {
kpeter@2584:     check(checkFlow(gr, lower, upper, supply, mcf.flowMap()),
kpeter@2584:           "The flow is not feasible " + test_id);
kpeter@2584:     check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
kpeter@2584:     check(checkOptimality(gr, lower, upper, cost, mcf.flowMap(), mcf.potentialMap()),
kpeter@2584:           "Wrong potentials " + test_id);
alpar@899:   }
alpar@899: }
alpar@899: 
alpar@899: int main()
alpar@899: {
kpeter@2584:   // Various tests on a small graph
kpeter@2584:   {
kpeter@2584:     typedef ListGraph Graph;
kpeter@2584:     GRAPH_TYPEDEFS(ListGraph);
alpar@899: 
kpeter@2584:     // Reading the test graph
kpeter@2584:     Graph gr;
kpeter@2584:     Graph::EdgeMap<int> c(gr), l1(gr), l2(gr), u(gr);
kpeter@2584:     Graph::NodeMap<int> s1(gr), s2(gr), s3(gr);
kpeter@2584:     Node v, w;
alpar@899: 
kpeter@2584:     std::string fname;
kpeter@2584:     if(getenv("srcdir"))
kpeter@2584:       fname = std::string(getenv("srcdir"));
kpeter@2584:     else fname = ".";
kpeter@2584:     fname += "/test/min_cost_flow_test.lgf";
alpar@899: 
kpeter@2584:     std::ifstream input(fname.c_str());
kpeter@2584:     check(input, "Input file '" << fname << "' not found");
kpeter@2584:     GraphReader<Graph>(input, gr).
kpeter@2584:       readEdgeMap("cost", c).
kpeter@2584:       readEdgeMap("capacity", u).
kpeter@2584:       readEdgeMap("lower1", l1).
kpeter@2584:       readEdgeMap("lower2", l2).
kpeter@2584:       readNodeMap("supply1", s1).
kpeter@2584:       readNodeMap("supply2", s2).
kpeter@2584:       readNodeMap("supply3", s3).
kpeter@2584:       readNode("source", v).
kpeter@2584:       readNode("target", w).
kpeter@2584:       run();
kpeter@2584:     input.close();
alpar@899: 
kpeter@2584:     // Testing CapacityScaling (scaling enabled)
kpeter@2584:     {
kpeter@2584:       CapacityScaling<Graph> mcf1(gr,u,c,s1);        checkMcf("#A1",mcf1,gr,l1,u,c,s1,mcf1.run(),true,    0);
kpeter@2584:       CapacityScaling<Graph> mcf2(gr,u,c,s2);        checkMcf("#A2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
kpeter@2584:       CapacityScaling<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#A3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
kpeter@2584:       CapacityScaling<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#A4",mcf4,gr,l2,u,c,s1,mcf4.run(),false,   0);
kpeter@2584:       CapacityScaling<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#A5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
kpeter@2584:       CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#A6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
kpeter@2584:     }
kpeter@2584:     // Testing CapacityScaling (scaling disabled)
kpeter@2584:     {
kpeter@2584:       CapacityScaling<Graph> mcf1(gr,u,c,s1);        checkMcf("#B1",mcf1,gr,l1,u,c,s1,mcf1.run(false),true,    0);
kpeter@2584:       CapacityScaling<Graph> mcf2(gr,u,c,s2);        checkMcf("#B2",mcf2,gr,l1,u,c,s2,mcf2.run(false),true, 5240);
kpeter@2584:       CapacityScaling<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#B3",mcf3,gr,l1,u,c,s3,mcf3.run(false),true, 7620);
kpeter@2584:       CapacityScaling<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#B4",mcf4,gr,l2,u,c,s1,mcf4.run(false),false,   0);
kpeter@2584:       CapacityScaling<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#B5",mcf5,gr,l2,u,c,s2,mcf5.run(false),true, 5970);
kpeter@2584:       CapacityScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#B6",mcf6,gr,l2,u,c,s3,mcf6.run(false),true, 8010);
kpeter@2584:     }
alpar@899: 
kpeter@2584:     // Testing CostScaling
kpeter@2584:     {
kpeter@2584:       CostScaling<Graph> mcf1(gr,u,c,s1);        checkMcf("#C1",mcf1,gr,l1,u,c,s1,mcf1.run(),true,    0);
kpeter@2584:       CostScaling<Graph> mcf2(gr,u,c,s2);        checkMcf("#C2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
kpeter@2584:       CostScaling<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#C3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
kpeter@2584:       CostScaling<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#C4",mcf4,gr,l2,u,c,s1,mcf4.run(),false,   0);
kpeter@2584:       CostScaling<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#C5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
kpeter@2584:       CostScaling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#C6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
kpeter@2584:     }
alpar@899: 
kpeter@2584:     // Testing NetworkSimplex (with the default pivot rule)
kpeter@2584:     {
kpeter@2584:       NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#D1",mcf1,gr,l1,u,c,s1,mcf1.run(),true,    0);
kpeter@2584:       NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#D2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
kpeter@2584:       NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#D3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
kpeter@2584:       NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#D4",mcf4,gr,l2,u,c,s1,mcf4.run(),false,   0);
kpeter@2584:       NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#D5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
kpeter@2584:       NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#D6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
kpeter@2584:     }
kpeter@2584:     // Testing NetworkSimplex (with FIRST_ELIGIBLE_PIVOT)
kpeter@2584:     {
kpeter@2584:       NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::FIRST_ELIGIBLE_PIVOT;
kpeter@2584:       NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#E1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true,    0);
kpeter@2584:       NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#E2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
kpeter@2584:       NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#E3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
kpeter@2584:       NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#E4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false,   0);
kpeter@2584:       NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#E5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
kpeter@2584:       NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#E6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
kpeter@2584:     }
kpeter@2584:     // Testing NetworkSimplex (with BEST_ELIGIBLE_PIVOT)
kpeter@2584:     {
kpeter@2584:       NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BEST_ELIGIBLE_PIVOT;
kpeter@2584:       NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#F1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true,    0);
kpeter@2584:       NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#F2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
kpeter@2584:       NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#F3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
kpeter@2584:       NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#F4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false,   0);
kpeter@2584:       NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#F5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
kpeter@2584:       NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#F6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
kpeter@2584:     }
kpeter@2584:     // Testing NetworkSimplex (with BLOCK_SEARCH_PIVOT)
kpeter@2584:     {
kpeter@2584:       NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::BLOCK_SEARCH_PIVOT;
kpeter@2584:       NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#G1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true,    0);
kpeter@2584:       NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#G2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
kpeter@2584:       NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#G3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
kpeter@2584:       NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#G4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false,   0);
kpeter@2584:       NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#G5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
kpeter@2584:       NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#G6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
kpeter@2584:     }
kpeter@2584:     // Testing NetworkSimplex (with CANDIDATE_LIST_PIVOT)
kpeter@2584:     {
kpeter@2584:       NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::CANDIDATE_LIST_PIVOT;
kpeter@2584:       NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#I1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true,    0);
kpeter@2584:       NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#I2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
kpeter@2584:       NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#I3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
kpeter@2584:       NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#I4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false,   0);
kpeter@2584:       NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#I5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
kpeter@2584:       NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#I6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
kpeter@2584:     }
kpeter@2621:     // Testing NetworkSimplex (with ALTERING_LIST_PIVOT)
kpeter@2621:     {
kpeter@2621:       NetworkSimplex<Graph>::PivotRuleEnum pr = NetworkSimplex<Graph>::ALTERING_LIST_PIVOT;
kpeter@2621:       NetworkSimplex<Graph> mcf1(gr,u,c,s1);        checkMcf("#H1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true,    0);
kpeter@2621:       NetworkSimplex<Graph> mcf2(gr,u,c,s2);        checkMcf("#H2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240);
kpeter@2621:       NetworkSimplex<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#H3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620);
kpeter@2621:       NetworkSimplex<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#H4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false,   0);
kpeter@2621:       NetworkSimplex<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#H5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970);
kpeter@2621:       NetworkSimplex<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#H6",mcf6,gr,l2,u,c,s3,mcf6.run(pr),true, 8010);
kpeter@2621:     }
alpar@899: 
kpeter@2584:     // Testing CycleCanceling (with BellmanFord)
kpeter@2584:     {
kpeter@2584:       CycleCanceling<Graph> mcf1(gr,u,c,s1);        checkMcf("#J1",mcf1,gr,l1,u,c,s1,mcf1.run(),true,    0);
kpeter@2584:       CycleCanceling<Graph> mcf2(gr,u,c,s2);        checkMcf("#J2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
kpeter@2584:       CycleCanceling<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#J3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
kpeter@2584:       CycleCanceling<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#J4",mcf4,gr,l2,u,c,s1,mcf4.run(),false,   0);
kpeter@2584:       CycleCanceling<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#J5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
kpeter@2584:       CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#J6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
kpeter@2584:     }
kpeter@2584:     // Testing CycleCanceling (with MinMeanCycle)
kpeter@2584:     {
kpeter@2584:       CycleCanceling<Graph> mcf1(gr,u,c,s1);        checkMcf("#K1",mcf1,gr,l1,u,c,s1,mcf1.run(true),true,    0);
kpeter@2584:       CycleCanceling<Graph> mcf2(gr,u,c,s2);        checkMcf("#K2",mcf2,gr,l1,u,c,s2,mcf2.run(true),true, 5240);
kpeter@2584:       CycleCanceling<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#K3",mcf3,gr,l1,u,c,s3,mcf3.run(true),true, 7620);
kpeter@2584:       CycleCanceling<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#K4",mcf4,gr,l2,u,c,s1,mcf4.run(true),false,   0);
kpeter@2584:       CycleCanceling<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#K5",mcf5,gr,l2,u,c,s2,mcf5.run(true),true, 5970);
kpeter@2584:       CycleCanceling<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#K6",mcf6,gr,l2,u,c,s3,mcf6.run(true),true, 8010);
kpeter@2584:     }
alpar@899: 
kpeter@2584:     // Testing MinCostFlow
kpeter@2584:     {
kpeter@2584:       MinCostFlow<Graph> mcf1(gr,u,c,s1);        checkMcf("#L1",mcf1,gr,l1,u,c,s1,mcf1.run(),true,    0);
kpeter@2584:       MinCostFlow<Graph> mcf2(gr,u,c,s2);        checkMcf("#L2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240);
kpeter@2584:       MinCostFlow<Graph> mcf3(gr,u,c,v,w,27);    checkMcf("#L3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620);
kpeter@2584:       MinCostFlow<Graph> mcf4(gr,l2,u,c,s1);     checkMcf("#L4",mcf4,gr,l2,u,c,s1,mcf4.run(),false,   0);
kpeter@2584:       MinCostFlow<Graph> mcf5(gr,l2,u,c,s2);     checkMcf("#L5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970);
kpeter@2584:       MinCostFlow<Graph> mcf6(gr,l2,u,c,v,w,27); checkMcf("#L6",mcf6,gr,l2,u,c,s3,mcf6.run(),true, 8010);
kpeter@2584:     }
alpar@899: 
kpeter@2584:     // Testing MinCostMaxFlow
kpeter@2584:     {
kpeter@2584:       MinCostMaxFlow<Graph> mcmf(gr,u,c,v,w);
kpeter@2584:       mcmf.run();
kpeter@2584:       checkMcf("#M1",mcmf,gr,l1,u,c,s3,true,true,7620);
kpeter@2584:     }
kpeter@2584:   }
alpar@899: 
kpeter@2584:   // Benchmark test on a DIMACS network
kpeter@2584:   {
kpeter@2584:     typedef SmartGraph Graph;
kpeter@2584:     GRAPH_TYPEDEFS(SmartGraph);
alpar@899: 
kpeter@2584:     // Reading the test graph
kpeter@2584:     Graph graph;
kpeter@2584:     Graph::EdgeMap<int> lower(graph), capacity(graph), cost(graph);
kpeter@2584:     Graph::NodeMap<int> supply(graph);
alpar@899: 
kpeter@2584:     std::string fname;
kpeter@2584:     if(getenv("srcdir"))
kpeter@2584:       fname = std::string(getenv("srcdir"));
kpeter@2584:     else fname = ".";
kpeter@2584:     fname += "/test/min_cost_flow_test.net";
marci@941: 
kpeter@2584:     std::ifstream input(fname.c_str());
kpeter@2584:     check(input, "Input file '" << fname << "' not found");
kpeter@2584:     readDimacs(input, graph, lower, capacity, cost, supply);
kpeter@2584:     input.close();
alpar@899: 
kpeter@2584:     // NetworkSimplex
kpeter@2584:     {
kpeter@2584:       Timer t;
kpeter@2584:       NetworkSimplex<Graph> mcf(graph, lower, capacity, cost, supply);
kpeter@2584:       bool res = mcf.run();
kpeter@2584:       t.stop();
kpeter@2584:       checkMcf("#T3", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
kpeter@2584:       std::cout << "NetworkSimplex";
kpeter@2584:       std::cout << std::endl << t << std::endl;
kpeter@2584:     }
kpeter@2584:     // CapacityScaling
kpeter@2584:     {
kpeter@2584:       Timer t;
kpeter@2584:       CapacityScaling<Graph> mcf(graph, lower, capacity, cost, supply);
kpeter@2584:       bool res = mcf.run();
kpeter@2584:       t.stop();
kpeter@2584:       checkMcf("#T1", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
kpeter@2584:       std::cout << "CapacityScaling";
kpeter@2584:       std::cout << std::endl << t << std::endl;
kpeter@2584:     }
kpeter@2584:     // CostScaling
kpeter@2584:     {
kpeter@2584:       Timer t;
kpeter@2584:       CostScaling<Graph> mcf(graph, lower, capacity, cost, supply);
kpeter@2584:       bool res = mcf.run();
kpeter@2584:       t.stop();
kpeter@2584:       checkMcf("#T2", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
kpeter@2584:       std::cout << "CostScaling";
kpeter@2584:       std::cout << std::endl << t << std::endl;
kpeter@2584:     }
kpeter@2584:     // CycleCanceling
kpeter@2584:     {
kpeter@2584:       Timer t;
kpeter@2584:       CycleCanceling<Graph> mcf(graph, lower, capacity, cost, supply);
kpeter@2584:       bool res = mcf.run();
kpeter@2584:       t.stop();
kpeter@2584:       checkMcf("#T4", mcf, graph, lower, capacity, cost, supply, res, true, 196587626);
kpeter@2584:       std::cout << "CycleCanceling";
kpeter@2584:       std::cout << std::endl << t << std::endl;
kpeter@2584:     }
kpeter@2584:   }
alpar@899: 
kpeter@2584:   return 0;
alpar@899: }