# HG changeset patch # User Peter Kovacs # Date 1362091475 -3600 # Node ID 45befc97b1bcf5bc47d9ff0acf02316b1520cae5 # Parent 08f2dc76e82e8b919459d9cfc95577ef6238c536 Merge test files of Preflow and EdmondsKarp (#177) diff -r 08f2dc76e82e -r 45befc97b1bc lemon/edmonds_karp.h --- a/lemon/edmonds_karp.h Thu Feb 28 18:13:48 2013 +0100 +++ b/lemon/edmonds_karp.h Thu Feb 28 23:44:35 2013 +0100 @@ -167,6 +167,8 @@ public: + typedef EdmondsKarp Create; + ///\name Named template parameters ///@{ diff -r 08f2dc76e82e -r 45befc97b1bc test/CMakeLists.txt --- a/test/CMakeLists.txt Thu Feb 28 18:13:48 2013 +0100 +++ b/test/CMakeLists.txt Thu Feb 28 23:44:35 2013 +0100 @@ -25,7 +25,6 @@ dijkstra_test dim_test edge_set_test - edmonds_karp_test error_test euler_test fractional_matching_test @@ -42,13 +41,13 @@ matching_test max_cardinality_search_test max_clique_test + max_flow_test min_cost_arborescence_test min_cost_flow_test min_mean_cycle_test nagamochi_ibaraki_test path_test planarity_test - preflow_test radix_sort_test random_test suurballe_test diff -r 08f2dc76e82e -r 45befc97b1bc test/edmonds_karp_test.cc --- a/test/edmonds_karp_test.cc Thu Feb 28 18:13:48 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,236 +0,0 @@ -/* -*- mode: C++; indent-tabs-mode: nil; -*- - * - * This file is a part of LEMON, a generic C++ optimization library. - * - * Copyright (C) 2003-2010 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#include - -#include "test_tools.h" -#include -#include -#include -#include -#include - -using namespace lemon; - -char test_lgf[] = - "@nodes\n" - "label\n" - "0\n" - "1\n" - "2\n" - "3\n" - "4\n" - "5\n" - "6\n" - "7\n" - "8\n" - "9\n" - "@arcs\n" - " label capacity\n" - "0 1 0 20\n" - "0 2 1 0\n" - "1 1 2 3\n" - "1 2 3 8\n" - "1 3 4 8\n" - "2 5 5 5\n" - "3 2 6 5\n" - "3 5 7 5\n" - "3 6 8 5\n" - "4 3 9 3\n" - "5 7 10 3\n" - "5 6 11 10\n" - "5 8 12 10\n" - "6 8 13 8\n" - "8 9 14 20\n" - "8 1 15 5\n" - "9 5 16 5\n" - "@attributes\n" - "source 1\n" - "target 8\n"; - -void checkEdmondKarpCompile() { - typedef int VType; - typedef concepts::Digraph Digraph; - - typedef Digraph::Node Node; - typedef Digraph::Arc Arc; - typedef concepts::ReadMap CapMap; - typedef concepts::ReadWriteMap FlowMap; - typedef concepts::WriteMap CutMap; - - Digraph g; - Node n; - Arc e; - CapMap cap; - FlowMap flow; - CutMap cut; - VType v; - bool b; - ignore_unused_variable_warning(v,b); - typedef EdmondsKarp - ::SetFlowMap - ::Create EKType; - EKType ek_test(g, cap, n, n); - const EKType& const_ek_test = ek_test; - - EKType::Tolerance tol = const_ek_test.tolerance(); - ek_test.tolerance(tol); - - ek_test - .capacityMap(cap) - .flowMap(flow) - .source(n) - .target(n); - - ek_test.init(); - ek_test.start(); - - v = const_ek_test.flowValue(); - v = const_ek_test.flow(e); - - const FlowMap& fm = const_ek_test.flowMap(); - b = const_ek_test.minCut(n); - const_ek_test.minCutMap(cut); - - ignore_unused_variable_warning(fm); -} - -int cutValue (const SmartDigraph& g, - const SmartDigraph::NodeMap& cut, - const SmartDigraph::ArcMap& cap) { - - int c=0; - for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { - if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; - } - return c; -} - -bool checkFlow(const SmartDigraph& g, - const SmartDigraph::ArcMap& flow, - const SmartDigraph::ArcMap& cap, - SmartDigraph::Node s, SmartDigraph::Node t) { - - for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { - if (flow[e] < 0 || flow[e] > cap[e]) return false; - } - - for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { - if (n == s || n == t) continue; - int sum = 0; - for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { - sum += flow[e]; - } - for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { - sum -= flow[e]; - } - if (sum != 0) return false; - } - return true; -} - -int main() { - - typedef SmartDigraph Digraph; - - typedef Digraph::Node Node; - typedef Digraph::NodeIt NodeIt; - typedef Digraph::ArcIt ArcIt; - typedef Digraph::ArcMap CapMap; - typedef Digraph::ArcMap FlowMap; - typedef Digraph::NodeMap CutMap; - - typedef EdmondsKarp EKType; - - Digraph g; - Node s, t; - CapMap cap(g); - std::istringstream input(test_lgf); - DigraphReader(g,input). - arcMap("capacity", cap). - node("source",s). - node("target",t). - run(); - - EKType ek_test(g, cap, s, t); - ek_test.run(); - - check(checkFlow(g, ek_test.flowMap(), cap, s, t), - "The flow is not feasible."); - - CutMap min_cut(g); - ek_test.minCutMap(min_cut); - int min_cut_value=cutValue(g,min_cut,cap); - - check(ek_test.flowValue() == min_cut_value, - "The max flow value is not equal to the three min cut values."); - - FlowMap flow(g); - for(ArcIt e(g); e!=INVALID; ++e) flow[e] = ek_test.flowMap()[e]; - - int flow_value=ek_test.flowValue(); - - for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; - ek_test.init(flow); - ek_test.start(); - - CutMap min_cut1(g); - ek_test.minCutMap(min_cut1); - min_cut_value=cutValue(g,min_cut1,cap); - - check(ek_test.flowValue() == min_cut_value && - min_cut_value == 2*flow_value, - "The max flow value or the min cut value is wrong."); - - check(checkFlow(g, ek_test.flowMap(), cap, s, t), - "The flow is not feasible."); - - CutMap min_cut2(g); - ek_test.minCutMap(min_cut2); - min_cut_value=cutValue(g,min_cut2,cap); - - check(ek_test.flowValue() == min_cut_value && - min_cut_value == 2*flow_value, - "The max flow value or the three min cut values were not doubled."); - - - ek_test.flowMap(flow); - - NodeIt tmp1(g,s); - ++tmp1; - if ( tmp1 != INVALID ) s=tmp1; - - NodeIt tmp2(g,t); - ++tmp2; - if ( tmp2 != INVALID ) t=tmp2; - - ek_test.source(s); - ek_test.target(t); - - ek_test.run(); - - CutMap min_cut3(g); - ek_test.minCutMap(min_cut3); - min_cut_value=cutValue(g,min_cut3,cap); - - - check(ek_test.flowValue() == min_cut_value, - "The max flow value or the three min cut values are incorrect."); - - return 0; -} diff -r 08f2dc76e82e -r 45befc97b1bc test/max_flow_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/max_flow_test.cc Thu Feb 28 23:44:35 2013 +0100 @@ -0,0 +1,395 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#include + +#include "test_tools.h" +#include +#include +#include +#include +#include +#include +#include + +using namespace lemon; + +char test_lgf[] = + "@nodes\n" + "label\n" + "0\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "8\n" + "9\n" + "@arcs\n" + " label capacity\n" + "0 1 0 20\n" + "0 2 1 0\n" + "1 1 2 3\n" + "1 2 3 8\n" + "1 3 4 8\n" + "2 5 5 5\n" + "3 2 6 5\n" + "3 5 7 5\n" + "3 6 8 5\n" + "4 3 9 3\n" + "5 7 10 3\n" + "5 6 11 10\n" + "5 8 12 10\n" + "6 8 13 8\n" + "8 9 14 20\n" + "8 1 15 5\n" + "9 5 16 5\n" + "@attributes\n" + "source 1\n" + "target 8\n"; + + +// Checks the general interface of a max flow algorithm +template +struct MaxFlowClassConcept +{ + + template + struct Constraints { + + typedef typename GR::Node Node; + typedef typename GR::Arc Arc; + typedef typename CAP::Value Value; + typedef concepts::ReadWriteMap FlowMap; + typedef concepts::WriteMap CutMap; + + GR g; + Node n; + Arc e; + CAP cap; + FlowMap flow; + CutMap cut; + Value v; + bool b; + + void constraints() { + checkConcept(); + + const Constraints& me = *this; + + typedef typename MF + ::template SetFlowMap + ::Create MaxFlowType; + typedef typename MF::Create MaxFlowType2; + MaxFlowType max_flow(me.g, me.cap, me.n, me.n); + const MaxFlowType& const_max_flow = max_flow; + + max_flow + .capacityMap(cap) + .flowMap(flow) + .source(n) + .target(n); + + typename MaxFlowType::Tolerance tol = const_max_flow.tolerance(); + max_flow.tolerance(tol); + + max_flow.init(); + max_flow.init(cap); + max_flow.run(); + + v = const_max_flow.flowValue(); + v = const_max_flow.flow(e); + const FlowMap& fm = const_max_flow.flowMap(); + + b = const_max_flow.minCut(n); + const_max_flow.minCutMap(cut); + + ignore_unused_variable_warning(fm); + } + + }; + +}; + +// Checks the specific parts of Preflow's interface +void checkPreflowCompile() +{ + typedef int Value; + typedef concepts::Digraph Digraph; + typedef concepts::ReadMap CapMap; + typedef Elevator Elev; + typedef LinkedElevator LinkedElev; + + Digraph g; + Digraph::Node n; + CapMap cap; + + typedef Preflow + ::SetElevator + ::SetStandardElevator + ::Create PreflowType; + PreflowType preflow_test(g, cap, n, n); + const PreflowType& const_preflow_test = preflow_test; + + const PreflowType::Elevator& elev = const_preflow_test.elevator(); + preflow_test.elevator(const_cast(elev)); + + bool b = preflow_test.init(cap); + preflow_test.startFirstPhase(); + preflow_test.startSecondPhase(); + preflow_test.runMinCut(); + + ignore_unused_variable_warning(b); +} + +// Checks the specific parts of EdmondsKarp's interface +void checkEdmondsKarpCompile() +{ + typedef int Value; + typedef concepts::Digraph Digraph; + typedef concepts::ReadMap CapMap; + typedef Elevator Elev; + typedef LinkedElevator LinkedElev; + + Digraph g; + Digraph::Node n; + CapMap cap; + + EdmondsKarp ek_test(g, cap, n, n); + + ek_test.init(cap); + bool b = ek_test.checkedInit(cap); + b = ek_test.augment(); + ek_test.start(); + + ignore_unused_variable_warning(b); +} + + +template +T cutValue (const SmartDigraph& g, + const SmartDigraph::NodeMap& cut, + const SmartDigraph::ArcMap& cap) { + + T c=0; + for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { + if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; + } + return c; +} + +template +bool checkFlow(const SmartDigraph& g, + const SmartDigraph::ArcMap& flow, + const SmartDigraph::ArcMap& cap, + SmartDigraph::Node s, SmartDigraph::Node t) { + + for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { + if (flow[e] < 0 || flow[e] > cap[e]) return false; + } + + for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { + if (n == s || n == t) continue; + T sum = 0; + for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { + sum += flow[e]; + } + for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { + sum -= flow[e]; + } + if (sum != 0) return false; + } + return true; +} + +void initFlowTest() +{ + DIGRAPH_TYPEDEFS(SmartDigraph); + + SmartDigraph g; + SmartDigraph::ArcMap cap(g),iflow(g); + Node s=g.addNode(); Node t=g.addNode(); + Node n1=g.addNode(); Node n2=g.addNode(); + Arc a; + a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; + a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; + a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; + + Preflow pre(g,cap,s,t); + pre.init(iflow); + pre.startFirstPhase(); + check(pre.flowValue() == 10, "The incorrect max flow value."); + check(pre.minCut(s), "Wrong min cut (Node s)."); + check(pre.minCut(n1), "Wrong min cut (Node n1)."); + check(!pre.minCut(n2), "Wrong min cut (Node n2)."); + check(!pre.minCut(t), "Wrong min cut (Node t)."); +} + +template +void checkMaxFlowAlg() { + typedef SmartDigraph Digraph; + DIGRAPH_TYPEDEFS(Digraph); + + typedef typename MF::Value Value; + typedef Digraph::ArcMap CapMap; + typedef CapMap FlowMap; + typedef BoolNodeMap CutMap; + + Digraph g; + Node s, t; + CapMap cap(g); + std::istringstream input(test_lgf); + DigraphReader(g,input) + .arcMap("capacity", cap) + .node("source",s) + .node("target",t) + .run(); + + MF max_flow(g, cap, s, t); + max_flow.run(); + + check(checkFlow(g, max_flow.flowMap(), cap, s, t), + "The flow is not feasible."); + + CutMap min_cut(g); + max_flow.minCutMap(min_cut); + Value min_cut_value = cutValue(g, min_cut, cap); + + check(max_flow.flowValue() == min_cut_value, + "The max flow value is not equal to the min cut value."); + + FlowMap flow(g); + for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e]; + + Value flow_value = max_flow.flowValue(); + + for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e]; + max_flow.init(flow); + + SF::startFirstPhase(max_flow); // start first phase of the algorithm + + CutMap min_cut1(g); + max_flow.minCutMap(min_cut1); + min_cut_value = cutValue(g, min_cut1, cap); + + check(max_flow.flowValue() == min_cut_value && + min_cut_value == 2 * flow_value, + "The max flow value or the min cut value is wrong."); + + SF::startSecondPhase(max_flow); // start second phase of the algorithm + + check(checkFlow(g, max_flow.flowMap(), cap, s, t), + "The flow is not feasible."); + + CutMap min_cut2(g); + max_flow.minCutMap(min_cut2); + min_cut_value = cutValue(g, min_cut2, cap); + + check(max_flow.flowValue() == min_cut_value && + min_cut_value == 2 * flow_value, + "The max flow value or the min cut value was not doubled"); + + + max_flow.flowMap(flow); + + NodeIt tmp1(g, s); + ++tmp1; + if (tmp1 != INVALID) s = tmp1; + + NodeIt tmp2(g, t); + ++tmp2; + if (tmp2 != INVALID) t = tmp2; + + max_flow.source(s); + max_flow.target(t); + + max_flow.run(); + + CutMap min_cut3(g); + max_flow.minCutMap(min_cut3); + min_cut_value=cutValue(g, min_cut3, cap); + + check(max_flow.flowValue() == min_cut_value, + "The max flow value or the min cut value is wrong."); +} + +// Struct for calling start functions of a general max flow algorithm +template +struct GeneralStartFunctions { + + static void startFirstPhase(MF& mf) { + mf.start(); + } + + static void startSecondPhase(MF& mf) { + ignore_unused_variable_warning(mf); + } + +}; + +// Struct for calling start functions of Preflow +template +struct PreflowStartFunctions { + + static void startFirstPhase(MF& mf) { + mf.startFirstPhase(); + } + + static void startSecondPhase(MF& mf) { + mf.startSecondPhase(); + } + +}; + +int main() { + + typedef concepts::Digraph GR; + typedef concepts::ReadMap CM1; + typedef concepts::ReadMap CM2; + + // Check the interface of Preflow + checkConcept< MaxFlowClassConcept, + Preflow >(); + checkConcept< MaxFlowClassConcept, + Preflow >(); + + // Check the interface of EdmondsKarp + checkConcept< MaxFlowClassConcept, + EdmondsKarp >(); + checkConcept< MaxFlowClassConcept, + EdmondsKarp >(); + + // Check Preflow + typedef Preflow > PType1; + typedef Preflow > PType2; + checkMaxFlowAlg >(); + checkMaxFlowAlg >(); + initFlowTest(); + + // Check EdmondsKarp + typedef EdmondsKarp > EKType1; + typedef EdmondsKarp > EKType2; + checkMaxFlowAlg >(); + checkMaxFlowAlg >(); + + initFlowTest(); + + return 0; +} diff -r 08f2dc76e82e -r 45befc97b1bc test/preflow_test.cc --- a/test/preflow_test.cc Thu Feb 28 18:13:48 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,277 +0,0 @@ -/* -*- mode: C++; indent-tabs-mode: nil; -*- - * - * This file is a part of LEMON, a generic C++ optimization library. - * - * Copyright (C) 2003-2010 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#include - -#include "test_tools.h" -#include -#include -#include -#include -#include -#include - -using namespace lemon; - -char test_lgf[] = - "@nodes\n" - "label\n" - "0\n" - "1\n" - "2\n" - "3\n" - "4\n" - "5\n" - "6\n" - "7\n" - "8\n" - "9\n" - "@arcs\n" - " label capacity\n" - "0 1 0 20\n" - "0 2 1 0\n" - "1 1 2 3\n" - "1 2 3 8\n" - "1 3 4 8\n" - "2 5 5 5\n" - "3 2 6 5\n" - "3 5 7 5\n" - "3 6 8 5\n" - "4 3 9 3\n" - "5 7 10 3\n" - "5 6 11 10\n" - "5 8 12 10\n" - "6 8 13 8\n" - "8 9 14 20\n" - "8 1 15 5\n" - "9 5 16 5\n" - "@attributes\n" - "source 1\n" - "target 8\n"; - -void checkPreflowCompile() -{ - typedef int VType; - typedef concepts::Digraph Digraph; - - typedef Digraph::Node Node; - typedef Digraph::Arc Arc; - typedef concepts::ReadMap CapMap; - typedef concepts::ReadWriteMap FlowMap; - typedef concepts::WriteMap CutMap; - - typedef Elevator Elev; - typedef LinkedElevator LinkedElev; - - Digraph g; - Node n; - Arc e; - CapMap cap; - FlowMap flow; - CutMap cut; - VType v; - bool b; - ignore_unused_variable_warning(v,b); - - typedef Preflow - ::SetFlowMap - ::SetElevator - ::SetStandardElevator - ::Create PreflowType; - PreflowType preflow_test(g, cap, n, n); - const PreflowType& const_preflow_test = preflow_test; - - const PreflowType::Elevator& elev = const_preflow_test.elevator(); - preflow_test.elevator(const_cast(elev)); - PreflowType::Tolerance tol = const_preflow_test.tolerance(); - preflow_test.tolerance(tol); - - preflow_test - .capacityMap(cap) - .flowMap(flow) - .source(n) - .target(n); - - preflow_test.init(); - preflow_test.init(cap); - preflow_test.startFirstPhase(); - preflow_test.startSecondPhase(); - preflow_test.run(); - preflow_test.runMinCut(); - - v = const_preflow_test.flowValue(); - v = const_preflow_test.flow(e); - const FlowMap& fm = const_preflow_test.flowMap(); - b = const_preflow_test.minCut(n); - const_preflow_test.minCutMap(cut); - - ignore_unused_variable_warning(fm); -} - -int cutValue (const SmartDigraph& g, - const SmartDigraph::NodeMap& cut, - const SmartDigraph::ArcMap& cap) { - - int c=0; - for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { - if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; - } - return c; -} - -bool checkFlow(const SmartDigraph& g, - const SmartDigraph::ArcMap& flow, - const SmartDigraph::ArcMap& cap, - SmartDigraph::Node s, SmartDigraph::Node t) { - - for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { - if (flow[e] < 0 || flow[e] > cap[e]) return false; - } - - for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { - if (n == s || n == t) continue; - int sum = 0; - for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { - sum += flow[e]; - } - for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { - sum -= flow[e]; - } - if (sum != 0) return false; - } - return true; -} - -void initFlowTest() -{ - DIGRAPH_TYPEDEFS(SmartDigraph); - - SmartDigraph g; - SmartDigraph::ArcMap cap(g),iflow(g); - Node s=g.addNode(); Node t=g.addNode(); - Node n1=g.addNode(); Node n2=g.addNode(); - Arc a; - a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; - a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; - a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; - - Preflow pre(g,cap,s,t); - pre.init(iflow); - pre.startFirstPhase(); - check(pre.flowValue() == 10, "The incorrect max flow value."); - check(pre.minCut(s), "Wrong min cut (Node s)."); - check(pre.minCut(n1), "Wrong min cut (Node n1)."); - check(!pre.minCut(n2), "Wrong min cut (Node n2)."); - check(!pre.minCut(t), "Wrong min cut (Node t)."); -} - - -int main() { - - typedef SmartDigraph Digraph; - - typedef Digraph::Node Node; - typedef Digraph::NodeIt NodeIt; - typedef Digraph::ArcIt ArcIt; - typedef Digraph::ArcMap CapMap; - typedef Digraph::ArcMap FlowMap; - typedef Digraph::NodeMap CutMap; - - typedef Preflow PType; - - Digraph g; - Node s, t; - CapMap cap(g); - std::istringstream input(test_lgf); - DigraphReader(g,input). - arcMap("capacity", cap). - node("source",s). - node("target",t). - run(); - - PType preflow_test(g, cap, s, t); - preflow_test.run(); - - check(checkFlow(g, preflow_test.flowMap(), cap, s, t), - "The flow is not feasible."); - - CutMap min_cut(g); - preflow_test.minCutMap(min_cut); - int min_cut_value=cutValue(g,min_cut,cap); - - check(preflow_test.flowValue() == min_cut_value, - "The max flow value is not equal to the three min cut values."); - - FlowMap flow(g); - for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e]; - - int flow_value=preflow_test.flowValue(); - - for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; - preflow_test.init(flow); - preflow_test.startFirstPhase(); - - CutMap min_cut1(g); - preflow_test.minCutMap(min_cut1); - min_cut_value=cutValue(g,min_cut1,cap); - - check(preflow_test.flowValue() == min_cut_value && - min_cut_value == 2*flow_value, - "The max flow value or the min cut value is wrong."); - - preflow_test.startSecondPhase(); - - check(checkFlow(g, preflow_test.flowMap(), cap, s, t), - "The flow is not feasible."); - - CutMap min_cut2(g); - preflow_test.minCutMap(min_cut2); - min_cut_value=cutValue(g,min_cut2,cap); - - check(preflow_test.flowValue() == min_cut_value && - min_cut_value == 2*flow_value, - "The max flow value or the three min cut values were not doubled"); - - - preflow_test.flowMap(flow); - - NodeIt tmp1(g,s); - ++tmp1; - if ( tmp1 != INVALID ) s=tmp1; - - NodeIt tmp2(g,t); - ++tmp2; - if ( tmp2 != INVALID ) t=tmp2; - - preflow_test.source(s); - preflow_test.target(t); - - preflow_test.run(); - - CutMap min_cut3(g); - preflow_test.minCutMap(min_cut3); - min_cut_value=cutValue(g,min_cut3,cap); - - - check(preflow_test.flowValue() == min_cut_value, - "The max flow value or the three min cut values are incorrect."); - - initFlowTest(); - - return 0; -}