/* -*- mode: C++; indent-tabs-mode: nil; -*- * * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2011 * 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; ::lemon::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); ::lemon::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; }