alpar@404: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@404: * alpar@404: * This file is a part of LEMON, a generic C++ optimization library. alpar@404: * alpar@1084: * Copyright (C) 2003-2011 alpar@404: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@404: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@404: * alpar@404: * Permission to use, modify and distribute this software is granted alpar@404: * provided that this copyright notice appears in all copies. For alpar@404: * precise terms see the accompanying LICENSE file. alpar@404: * alpar@404: * This software is provided "AS IS" with no warranty of any kind, alpar@404: * express or implied, and with no claim as to its suitability for any alpar@404: * purpose. alpar@404: * alpar@404: */ alpar@404: alpar@442: #include alpar@404: alpar@404: #include "test_tools.h" alpar@404: #include alpar@404: #include alpar@404: #include alpar@404: #include alpar@404: #include kpeter@409: #include alpar@404: alpar@404: using namespace lemon; alpar@404: alpar@442: char test_lgf[] = alpar@442: "@nodes\n" alpar@442: "label\n" alpar@442: "0\n" alpar@442: "1\n" alpar@442: "2\n" alpar@442: "3\n" alpar@442: "4\n" alpar@442: "5\n" alpar@442: "6\n" alpar@442: "7\n" alpar@442: "8\n" alpar@442: "9\n" alpar@442: "@arcs\n" alpar@442: " label capacity\n" alpar@442: "0 1 0 20\n" alpar@442: "0 2 1 0\n" alpar@442: "1 1 2 3\n" alpar@442: "1 2 3 8\n" alpar@442: "1 3 4 8\n" alpar@442: "2 5 5 5\n" alpar@442: "3 2 6 5\n" alpar@442: "3 5 7 5\n" alpar@442: "3 6 8 5\n" alpar@442: "4 3 9 3\n" alpar@442: "5 7 10 3\n" alpar@442: "5 6 11 10\n" alpar@442: "5 8 12 10\n" alpar@442: "6 8 13 8\n" alpar@442: "8 9 14 20\n" alpar@442: "8 1 15 5\n" alpar@442: "9 5 16 5\n" alpar@442: "@attributes\n" alpar@442: "source 1\n" alpar@442: "target 8\n"; alpar@442: kpeter@409: void checkPreflowCompile() alpar@404: { alpar@404: typedef int VType; alpar@404: typedef concepts::Digraph Digraph; alpar@404: alpar@404: typedef Digraph::Node Node; alpar@404: typedef Digraph::Arc Arc; alpar@404: typedef concepts::ReadMap CapMap; alpar@404: typedef concepts::ReadWriteMap FlowMap; alpar@404: typedef concepts::WriteMap CutMap; alpar@404: kpeter@409: typedef Elevator Elev; kpeter@409: typedef LinkedElevator LinkedElev; kpeter@409: alpar@404: Digraph g; alpar@404: Node n; alpar@404: Arc e; alpar@404: CapMap cap; alpar@404: FlowMap flow; alpar@404: CutMap cut; kpeter@632: VType v; kpeter@632: bool b; alpar@404: kpeter@632: typedef Preflow kpeter@632: ::SetFlowMap kpeter@632: ::SetElevator kpeter@632: ::SetStandardElevator kpeter@632: ::Create PreflowType; kpeter@632: PreflowType preflow_test(g, cap, n, n); kpeter@632: const PreflowType& const_preflow_test = preflow_test; alpar@404: kpeter@736: const PreflowType::Elevator& elev = const_preflow_test.elevator(); kpeter@736: preflow_test.elevator(const_cast(elev)); kpeter@736: PreflowType::Tolerance tol = const_preflow_test.tolerance(); kpeter@736: preflow_test.tolerance(tol); kpeter@632: kpeter@632: preflow_test kpeter@632: .capacityMap(cap) kpeter@632: .flowMap(flow) kpeter@632: .source(n) kpeter@632: .target(n); alpar@404: alpar@404: preflow_test.init(); kpeter@407: preflow_test.init(cap); alpar@404: preflow_test.startFirstPhase(); alpar@404: preflow_test.startSecondPhase(); alpar@404: preflow_test.run(); alpar@404: preflow_test.runMinCut(); alpar@404: kpeter@632: v = const_preflow_test.flowValue(); kpeter@632: v = const_preflow_test.flow(e); kpeter@632: const FlowMap& fm = const_preflow_test.flowMap(); kpeter@632: b = const_preflow_test.minCut(n); kpeter@632: const_preflow_test.minCutMap(cut); alpar@956: kpeter@632: ignore_unused_variable_warning(fm); alpar@404: } alpar@404: alpar@404: int cutValue (const SmartDigraph& g, alpar@404: const SmartDigraph::NodeMap& cut, alpar@404: const SmartDigraph::ArcMap& cap) { alpar@404: alpar@404: int c=0; alpar@404: for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { alpar@404: if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; alpar@404: } alpar@404: return c; alpar@404: } alpar@404: alpar@404: bool checkFlow(const SmartDigraph& g, alpar@404: const SmartDigraph::ArcMap& flow, alpar@404: const SmartDigraph::ArcMap& cap, alpar@404: SmartDigraph::Node s, SmartDigraph::Node t) { alpar@404: alpar@404: for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { alpar@404: if (flow[e] < 0 || flow[e] > cap[e]) return false; alpar@404: } alpar@404: alpar@404: for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { alpar@404: if (n == s || n == t) continue; alpar@404: int sum = 0; alpar@404: for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { alpar@404: sum += flow[e]; alpar@404: } alpar@404: for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { alpar@404: sum -= flow[e]; alpar@404: } alpar@404: if (sum != 0) return false; alpar@404: } alpar@404: return true; alpar@404: } alpar@404: alpar@1027: void initFlowTest() alpar@1027: { alpar@1027: DIGRAPH_TYPEDEFS(SmartDigraph); alpar@1084: alpar@1027: SmartDigraph g; alpar@1027: SmartDigraph::ArcMap cap(g),iflow(g); alpar@1027: Node s=g.addNode(); Node t=g.addNode(); alpar@1027: Node n1=g.addNode(); Node n2=g.addNode(); alpar@1027: Arc a; alpar@1027: a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; alpar@1027: a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; alpar@1027: a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; alpar@1027: alpar@1027: Preflow pre(g,cap,s,t); alpar@1027: pre.init(iflow); alpar@1027: pre.startFirstPhase(); alpar@1027: check(pre.flowValue() == 10, "The incorrect max flow value."); alpar@1027: check(pre.minCut(s), "Wrong min cut (Node s)."); alpar@1027: check(pre.minCut(n1), "Wrong min cut (Node n1)."); alpar@1027: check(!pre.minCut(n2), "Wrong min cut (Node n2)."); alpar@1027: check(!pre.minCut(t), "Wrong min cut (Node t)."); alpar@1027: } alpar@1027: alpar@1027: alpar@404: int main() { alpar@404: alpar@404: typedef SmartDigraph Digraph; alpar@404: alpar@404: typedef Digraph::Node Node; alpar@404: typedef Digraph::NodeIt NodeIt; alpar@404: typedef Digraph::ArcIt ArcIt; alpar@404: typedef Digraph::ArcMap CapMap; alpar@404: typedef Digraph::ArcMap FlowMap; alpar@404: typedef Digraph::NodeMap CutMap; alpar@404: alpar@404: typedef Preflow PType; alpar@404: alpar@404: Digraph g; alpar@404: Node s, t; alpar@404: CapMap cap(g); alpar@442: std::istringstream input(test_lgf); alpar@442: DigraphReader(g,input). alpar@404: arcMap("capacity", cap). alpar@404: node("source",s). alpar@404: node("target",t). alpar@404: run(); alpar@404: alpar@404: PType preflow_test(g, cap, s, t); alpar@404: preflow_test.run(); alpar@404: alpar@404: check(checkFlow(g, preflow_test.flowMap(), cap, s, t), alpar@404: "The flow is not feasible."); alpar@404: alpar@404: CutMap min_cut(g); alpar@404: preflow_test.minCutMap(min_cut); alpar@404: int min_cut_value=cutValue(g,min_cut,cap); alpar@404: alpar@404: check(preflow_test.flowValue() == min_cut_value, alpar@404: "The max flow value is not equal to the three min cut values."); alpar@404: alpar@404: FlowMap flow(g); alpar@404: for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e]; alpar@404: alpar@404: int flow_value=preflow_test.flowValue(); alpar@404: alpar@404: for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; kpeter@407: preflow_test.init(flow); alpar@404: preflow_test.startFirstPhase(); alpar@404: alpar@404: CutMap min_cut1(g); alpar@404: preflow_test.minCutMap(min_cut1); alpar@404: min_cut_value=cutValue(g,min_cut1,cap); alpar@404: alpar@404: check(preflow_test.flowValue() == min_cut_value && alpar@404: min_cut_value == 2*flow_value, alpar@404: "The max flow value or the min cut value is wrong."); alpar@404: alpar@404: preflow_test.startSecondPhase(); alpar@404: alpar@404: check(checkFlow(g, preflow_test.flowMap(), cap, s, t), alpar@404: "The flow is not feasible."); alpar@404: alpar@404: CutMap min_cut2(g); alpar@404: preflow_test.minCutMap(min_cut2); alpar@404: min_cut_value=cutValue(g,min_cut2,cap); alpar@404: alpar@404: check(preflow_test.flowValue() == min_cut_value && alpar@404: min_cut_value == 2*flow_value, alpar@404: "The max flow value or the three min cut values were not doubled"); alpar@404: alpar@404: alpar@404: preflow_test.flowMap(flow); alpar@404: alpar@404: NodeIt tmp1(g,s); alpar@404: ++tmp1; alpar@404: if ( tmp1 != INVALID ) s=tmp1; alpar@404: alpar@404: NodeIt tmp2(g,t); alpar@404: ++tmp2; alpar@404: if ( tmp2 != INVALID ) t=tmp2; alpar@404: alpar@404: preflow_test.source(s); alpar@404: preflow_test.target(t); alpar@404: alpar@404: preflow_test.run(); alpar@404: alpar@404: CutMap min_cut3(g); alpar@404: preflow_test.minCutMap(min_cut3); alpar@404: min_cut_value=cutValue(g,min_cut3,cap); alpar@404: alpar@404: alpar@404: check(preflow_test.flowValue() == min_cut_value, alpar@404: "The max flow value or the three min cut values are incorrect."); alpar@404: alpar@1027: initFlowTest(); alpar@1084: alpar@404: return 0; alpar@404: }