diff --git a/test/preflow_test.cc b/test/preflow_test.cc new file mode 100644 --- /dev/null +++ b/test/preflow_test.cc @@ -0,0 +1,250 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * 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; + + 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; +} + +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."); + + return 0; +}