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 kpeter@2584: #include kpeter@2584: kpeter@2584: #include kpeter@2584: #include kpeter@2584: #include kpeter@2584: #include kpeter@2584: #include kpeter@2584: kpeter@2584: #include kpeter@2584: #include kpeter@2584: #include kpeter@2584: #include kpeter@2584: kpeter@2584: #include kpeter@2584: #include 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 c(gr), l1(gr), l2(gr), u(gr); kpeter@2584: Graph::NodeMap 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(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 mcf1(gr,u,c,s1); checkMcf("#A1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); kpeter@2584: CapacityScaling mcf2(gr,u,c,s2); checkMcf("#A2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); kpeter@2584: CapacityScaling mcf3(gr,u,c,v,w,27); checkMcf("#A3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); kpeter@2584: CapacityScaling mcf4(gr,l2,u,c,s1); checkMcf("#A4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); kpeter@2584: CapacityScaling mcf5(gr,l2,u,c,s2); checkMcf("#A5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); kpeter@2584: CapacityScaling 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 mcf1(gr,u,c,s1); checkMcf("#B1",mcf1,gr,l1,u,c,s1,mcf1.run(false),true, 0); kpeter@2584: CapacityScaling mcf2(gr,u,c,s2); checkMcf("#B2",mcf2,gr,l1,u,c,s2,mcf2.run(false),true, 5240); kpeter@2584: CapacityScaling mcf3(gr,u,c,v,w,27); checkMcf("#B3",mcf3,gr,l1,u,c,s3,mcf3.run(false),true, 7620); kpeter@2584: CapacityScaling mcf4(gr,l2,u,c,s1); checkMcf("#B4",mcf4,gr,l2,u,c,s1,mcf4.run(false),false, 0); kpeter@2584: CapacityScaling mcf5(gr,l2,u,c,s2); checkMcf("#B5",mcf5,gr,l2,u,c,s2,mcf5.run(false),true, 5970); kpeter@2584: CapacityScaling 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 mcf1(gr,u,c,s1); checkMcf("#C1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); kpeter@2584: CostScaling mcf2(gr,u,c,s2); checkMcf("#C2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); kpeter@2584: CostScaling mcf3(gr,u,c,v,w,27); checkMcf("#C3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); kpeter@2584: CostScaling mcf4(gr,l2,u,c,s1); checkMcf("#C4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); kpeter@2584: CostScaling mcf5(gr,l2,u,c,s2); checkMcf("#C5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); kpeter@2584: CostScaling 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 mcf1(gr,u,c,s1); checkMcf("#D1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); kpeter@2584: NetworkSimplex mcf2(gr,u,c,s2); checkMcf("#D2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); kpeter@2584: NetworkSimplex mcf3(gr,u,c,v,w,27); checkMcf("#D3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); kpeter@2584: NetworkSimplex mcf4(gr,l2,u,c,s1); checkMcf("#D4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); kpeter@2584: NetworkSimplex mcf5(gr,l2,u,c,s2); checkMcf("#D5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); kpeter@2584: NetworkSimplex 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::PivotRuleEnum pr = NetworkSimplex::FIRST_ELIGIBLE_PIVOT; kpeter@2584: NetworkSimplex mcf1(gr,u,c,s1); checkMcf("#E1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); kpeter@2584: NetworkSimplex mcf2(gr,u,c,s2); checkMcf("#E2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); kpeter@2584: NetworkSimplex mcf3(gr,u,c,v,w,27); checkMcf("#E3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); kpeter@2584: NetworkSimplex mcf4(gr,l2,u,c,s1); checkMcf("#E4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); kpeter@2584: NetworkSimplex mcf5(gr,l2,u,c,s2); checkMcf("#E5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); kpeter@2584: NetworkSimplex 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::PivotRuleEnum pr = NetworkSimplex::BEST_ELIGIBLE_PIVOT; kpeter@2584: NetworkSimplex mcf1(gr,u,c,s1); checkMcf("#F1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); kpeter@2584: NetworkSimplex mcf2(gr,u,c,s2); checkMcf("#F2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); kpeter@2584: NetworkSimplex mcf3(gr,u,c,v,w,27); checkMcf("#F3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); kpeter@2584: NetworkSimplex mcf4(gr,l2,u,c,s1); checkMcf("#F4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); kpeter@2584: NetworkSimplex mcf5(gr,l2,u,c,s2); checkMcf("#F5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); kpeter@2584: NetworkSimplex 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::PivotRuleEnum pr = NetworkSimplex::BLOCK_SEARCH_PIVOT; kpeter@2584: NetworkSimplex mcf1(gr,u,c,s1); checkMcf("#G1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); kpeter@2584: NetworkSimplex mcf2(gr,u,c,s2); checkMcf("#G2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); kpeter@2584: NetworkSimplex mcf3(gr,u,c,v,w,27); checkMcf("#G3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); kpeter@2584: NetworkSimplex mcf4(gr,l2,u,c,s1); checkMcf("#G4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); kpeter@2584: NetworkSimplex mcf5(gr,l2,u,c,s2); checkMcf("#G5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); kpeter@2584: NetworkSimplex 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::PivotRuleEnum pr = NetworkSimplex::CANDIDATE_LIST_PIVOT; kpeter@2584: NetworkSimplex mcf1(gr,u,c,s1); checkMcf("#I1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); kpeter@2584: NetworkSimplex mcf2(gr,u,c,s2); checkMcf("#I2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); kpeter@2584: NetworkSimplex mcf3(gr,u,c,v,w,27); checkMcf("#I3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); kpeter@2584: NetworkSimplex mcf4(gr,l2,u,c,s1); checkMcf("#I4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); kpeter@2584: NetworkSimplex mcf5(gr,l2,u,c,s2); checkMcf("#I5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); kpeter@2584: NetworkSimplex 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::PivotRuleEnum pr = NetworkSimplex::ALTERING_LIST_PIVOT; kpeter@2621: NetworkSimplex mcf1(gr,u,c,s1); checkMcf("#H1",mcf1,gr,l1,u,c,s1,mcf1.run(pr),true, 0); kpeter@2621: NetworkSimplex mcf2(gr,u,c,s2); checkMcf("#H2",mcf2,gr,l1,u,c,s2,mcf2.run(pr),true, 5240); kpeter@2621: NetworkSimplex mcf3(gr,u,c,v,w,27); checkMcf("#H3",mcf3,gr,l1,u,c,s3,mcf3.run(pr),true, 7620); kpeter@2621: NetworkSimplex mcf4(gr,l2,u,c,s1); checkMcf("#H4",mcf4,gr,l2,u,c,s1,mcf4.run(pr),false, 0); kpeter@2621: NetworkSimplex mcf5(gr,l2,u,c,s2); checkMcf("#H5",mcf5,gr,l2,u,c,s2,mcf5.run(pr),true, 5970); kpeter@2621: NetworkSimplex 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 mcf1(gr,u,c,s1); checkMcf("#J1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); kpeter@2584: CycleCanceling mcf2(gr,u,c,s2); checkMcf("#J2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); kpeter@2584: CycleCanceling mcf3(gr,u,c,v,w,27); checkMcf("#J3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); kpeter@2584: CycleCanceling mcf4(gr,l2,u,c,s1); checkMcf("#J4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); kpeter@2584: CycleCanceling mcf5(gr,l2,u,c,s2); checkMcf("#J5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); kpeter@2584: CycleCanceling 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 mcf1(gr,u,c,s1); checkMcf("#K1",mcf1,gr,l1,u,c,s1,mcf1.run(true),true, 0); kpeter@2584: CycleCanceling mcf2(gr,u,c,s2); checkMcf("#K2",mcf2,gr,l1,u,c,s2,mcf2.run(true),true, 5240); kpeter@2584: CycleCanceling mcf3(gr,u,c,v,w,27); checkMcf("#K3",mcf3,gr,l1,u,c,s3,mcf3.run(true),true, 7620); kpeter@2584: CycleCanceling mcf4(gr,l2,u,c,s1); checkMcf("#K4",mcf4,gr,l2,u,c,s1,mcf4.run(true),false, 0); kpeter@2584: CycleCanceling mcf5(gr,l2,u,c,s2); checkMcf("#K5",mcf5,gr,l2,u,c,s2,mcf5.run(true),true, 5970); kpeter@2584: CycleCanceling 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 mcf1(gr,u,c,s1); checkMcf("#L1",mcf1,gr,l1,u,c,s1,mcf1.run(),true, 0); kpeter@2584: MinCostFlow mcf2(gr,u,c,s2); checkMcf("#L2",mcf2,gr,l1,u,c,s2,mcf2.run(),true, 5240); kpeter@2584: MinCostFlow mcf3(gr,u,c,v,w,27); checkMcf("#L3",mcf3,gr,l1,u,c,s3,mcf3.run(),true, 7620); kpeter@2584: MinCostFlow mcf4(gr,l2,u,c,s1); checkMcf("#L4",mcf4,gr,l2,u,c,s1,mcf4.run(),false, 0); kpeter@2584: MinCostFlow mcf5(gr,l2,u,c,s2); checkMcf("#L5",mcf5,gr,l2,u,c,s2,mcf5.run(),true, 5970); kpeter@2584: MinCostFlow 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 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 lower(graph), capacity(graph), cost(graph); kpeter@2584: Graph::NodeMap 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 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 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 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 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: }