alpar@389: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@389: * alpar@389: * This file is a part of LEMON, a generic C++ optimization library. alpar@389: * alpar@877: * Copyright (C) 2003-2010 alpar@389: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@389: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@389: * alpar@389: * Permission to use, modify and distribute this software is granted alpar@389: * provided that this copyright notice appears in all copies. For alpar@389: * precise terms see the accompanying LICENSE file. alpar@389: * alpar@389: * This software is provided "AS IS" with no warranty of any kind, alpar@389: * express or implied, and with no claim as to its suitability for any alpar@389: * purpose. alpar@389: * alpar@389: */ alpar@389: alpar@423: #include alpar@389: alpar@389: #include "test_tools.h" alpar@389: #include alpar@389: #include kpeter@1060: #include alpar@389: #include alpar@389: #include alpar@389: #include kpeter@394: #include alpar@389: alpar@389: using namespace lemon; alpar@389: alpar@423: char test_lgf[] = alpar@423: "@nodes\n" alpar@423: "label\n" alpar@423: "0\n" alpar@423: "1\n" alpar@423: "2\n" alpar@423: "3\n" alpar@423: "4\n" alpar@423: "5\n" alpar@423: "6\n" alpar@423: "7\n" alpar@423: "8\n" alpar@423: "9\n" alpar@423: "@arcs\n" alpar@423: " label capacity\n" alpar@423: "0 1 0 20\n" alpar@423: "0 2 1 0\n" alpar@423: "1 1 2 3\n" alpar@423: "1 2 3 8\n" alpar@423: "1 3 4 8\n" alpar@423: "2 5 5 5\n" alpar@423: "3 2 6 5\n" alpar@423: "3 5 7 5\n" alpar@423: "3 6 8 5\n" alpar@423: "4 3 9 3\n" alpar@423: "5 7 10 3\n" alpar@423: "5 6 11 10\n" alpar@423: "5 8 12 10\n" alpar@423: "6 8 13 8\n" alpar@423: "8 9 14 20\n" alpar@423: "8 1 15 5\n" alpar@423: "9 5 16 5\n" alpar@423: "@attributes\n" alpar@423: "source 1\n" alpar@423: "target 8\n"; alpar@423: kpeter@1060: kpeter@1060: // Checks the general interface of a max flow algorithm kpeter@1060: template kpeter@1060: struct MaxFlowClassConcept kpeter@1060: { kpeter@1060: kpeter@1060: template kpeter@1060: struct Constraints { kpeter@1060: kpeter@1060: typedef typename GR::Node Node; kpeter@1060: typedef typename GR::Arc Arc; kpeter@1060: typedef typename CAP::Value Value; kpeter@1060: typedef concepts::ReadWriteMap FlowMap; kpeter@1060: typedef concepts::WriteMap CutMap; kpeter@1060: kpeter@1060: GR g; kpeter@1060: Node n; kpeter@1060: Arc e; kpeter@1060: CAP cap; kpeter@1060: FlowMap flow; kpeter@1060: CutMap cut; kpeter@1060: Value v; kpeter@1060: bool b; kpeter@1060: kpeter@1060: void constraints() { kpeter@1060: checkConcept(); kpeter@1060: kpeter@1060: const Constraints& me = *this; kpeter@1060: kpeter@1060: typedef typename MF kpeter@1060: ::template SetFlowMap kpeter@1060: ::Create MaxFlowType; kpeter@1060: typedef typename MF::Create MaxFlowType2; kpeter@1060: MaxFlowType max_flow(me.g, me.cap, me.n, me.n); kpeter@1060: const MaxFlowType& const_max_flow = max_flow; kpeter@1060: kpeter@1060: max_flow kpeter@1060: .capacityMap(cap) kpeter@1060: .flowMap(flow) kpeter@1060: .source(n) kpeter@1060: .target(n); kpeter@1060: kpeter@1060: typename MaxFlowType::Tolerance tol = const_max_flow.tolerance(); kpeter@1060: max_flow.tolerance(tol); kpeter@1060: kpeter@1060: max_flow.init(); kpeter@1060: max_flow.init(cap); kpeter@1060: max_flow.run(); kpeter@1060: kpeter@1060: v = const_max_flow.flowValue(); kpeter@1060: v = const_max_flow.flow(e); kpeter@1060: const FlowMap& fm = const_max_flow.flowMap(); kpeter@1060: kpeter@1060: b = const_max_flow.minCut(n); kpeter@1060: const_max_flow.minCutMap(cut); kpeter@1060: kpeter@1060: ignore_unused_variable_warning(fm); kpeter@1060: } kpeter@1060: kpeter@1060: }; kpeter@1060: kpeter@1060: }; kpeter@1060: kpeter@1060: // Checks the specific parts of Preflow's interface kpeter@394: void checkPreflowCompile() alpar@389: { kpeter@1060: typedef int Value; alpar@389: typedef concepts::Digraph Digraph; kpeter@1060: typedef concepts::ReadMap CapMap; kpeter@394: typedef Elevator Elev; kpeter@394: typedef LinkedElevator LinkedElev; kpeter@394: alpar@389: Digraph g; kpeter@1060: Digraph::Node n; alpar@389: CapMap cap; alpar@389: kpeter@585: typedef Preflow kpeter@1060: ::SetElevator kpeter@1060: ::SetStandardElevator kpeter@1060: ::Create PreflowType; kpeter@585: PreflowType preflow_test(g, cap, n, n); kpeter@585: const PreflowType& const_preflow_test = preflow_test; alpar@389: kpeter@689: const PreflowType::Elevator& elev = const_preflow_test.elevator(); kpeter@689: preflow_test.elevator(const_cast(elev)); kpeter@585: kpeter@1060: bool b = preflow_test.init(cap); alpar@389: preflow_test.startFirstPhase(); alpar@389: preflow_test.startSecondPhase(); alpar@389: preflow_test.runMinCut(); alpar@389: kpeter@1060: ignore_unused_variable_warning(b); alpar@389: } alpar@389: kpeter@1060: // Checks the specific parts of EdmondsKarp's interface kpeter@1060: void checkEdmondsKarpCompile() kpeter@1060: { kpeter@1060: typedef int Value; kpeter@1060: typedef concepts::Digraph Digraph; kpeter@1060: typedef concepts::ReadMap CapMap; kpeter@1060: typedef Elevator Elev; kpeter@1060: typedef LinkedElevator LinkedElev; kpeter@1060: kpeter@1060: Digraph g; kpeter@1060: Digraph::Node n; kpeter@1060: CapMap cap; kpeter@1060: kpeter@1060: EdmondsKarp ek_test(g, cap, n, n); kpeter@1060: kpeter@1060: ek_test.init(cap); kpeter@1060: bool b = ek_test.checkedInit(cap); kpeter@1060: b = ek_test.augment(); kpeter@1060: ek_test.start(); kpeter@1060: kpeter@1060: ignore_unused_variable_warning(b); kpeter@1060: } kpeter@1060: kpeter@1060: kpeter@1060: template kpeter@1060: T cutValue (const SmartDigraph& g, alpar@389: const SmartDigraph::NodeMap& cut, kpeter@1060: const SmartDigraph::ArcMap& cap) { alpar@389: kpeter@1060: T c=0; alpar@389: for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) { alpar@389: if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e]; alpar@389: } alpar@389: return c; alpar@389: } alpar@389: kpeter@1060: template alpar@389: bool checkFlow(const SmartDigraph& g, kpeter@1060: const SmartDigraph::ArcMap& flow, kpeter@1060: const SmartDigraph::ArcMap& cap, alpar@389: SmartDigraph::Node s, SmartDigraph::Node t) { alpar@389: alpar@389: for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { alpar@389: if (flow[e] < 0 || flow[e] > cap[e]) return false; alpar@389: } alpar@389: alpar@389: for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) { alpar@389: if (n == s || n == t) continue; kpeter@1060: T sum = 0; alpar@389: for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) { alpar@389: sum += flow[e]; alpar@389: } alpar@389: for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) { alpar@389: sum -= flow[e]; alpar@389: } alpar@389: if (sum != 0) return false; alpar@389: } alpar@389: return true; alpar@389: } alpar@389: alpar@923: void initFlowTest() alpar@923: { alpar@923: DIGRAPH_TYPEDEFS(SmartDigraph); alpar@923: alpar@923: SmartDigraph g; alpar@923: SmartDigraph::ArcMap cap(g),iflow(g); alpar@923: Node s=g.addNode(); Node t=g.addNode(); alpar@923: Node n1=g.addNode(); Node n2=g.addNode(); alpar@923: Arc a; alpar@923: a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; alpar@923: a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; alpar@923: a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; alpar@923: alpar@923: Preflow pre(g,cap,s,t); alpar@923: pre.init(iflow); alpar@923: pre.startFirstPhase(); alpar@923: check(pre.flowValue() == 10, "The incorrect max flow value."); alpar@923: check(pre.minCut(s), "Wrong min cut (Node s)."); alpar@923: check(pre.minCut(n1), "Wrong min cut (Node n1)."); alpar@923: check(!pre.minCut(n2), "Wrong min cut (Node n2)."); alpar@923: check(!pre.minCut(t), "Wrong min cut (Node t)."); alpar@923: } alpar@923: kpeter@1060: template kpeter@1060: void checkMaxFlowAlg() { kpeter@1060: typedef SmartDigraph Digraph; kpeter@1060: DIGRAPH_TYPEDEFS(Digraph); alpar@923: kpeter@1060: typedef typename MF::Value Value; kpeter@1060: typedef Digraph::ArcMap CapMap; kpeter@1060: typedef CapMap FlowMap; kpeter@1060: typedef BoolNodeMap CutMap; alpar@389: alpar@389: Digraph g; alpar@389: Node s, t; alpar@389: CapMap cap(g); alpar@423: std::istringstream input(test_lgf); kpeter@1060: DigraphReader(g,input) kpeter@1060: .arcMap("capacity", cap) kpeter@1060: .node("source",s) kpeter@1060: .node("target",t) kpeter@1060: .run(); alpar@389: kpeter@1060: MF max_flow(g, cap, s, t); kpeter@1060: max_flow.run(); alpar@389: kpeter@1060: check(checkFlow(g, max_flow.flowMap(), cap, s, t), alpar@389: "The flow is not feasible."); alpar@389: alpar@389: CutMap min_cut(g); kpeter@1060: max_flow.minCutMap(min_cut); kpeter@1060: Value min_cut_value = cutValue(g, min_cut, cap); alpar@389: kpeter@1060: check(max_flow.flowValue() == min_cut_value, kpeter@1060: "The max flow value is not equal to the min cut value."); alpar@389: alpar@389: FlowMap flow(g); kpeter@1060: for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e]; alpar@389: kpeter@1060: Value flow_value = max_flow.flowValue(); alpar@389: kpeter@1060: for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e]; kpeter@1060: max_flow.init(flow); kpeter@1060: kpeter@1060: SF::startFirstPhase(max_flow); // start first phase of the algorithm alpar@389: alpar@389: CutMap min_cut1(g); kpeter@1060: max_flow.minCutMap(min_cut1); kpeter@1060: min_cut_value = cutValue(g, min_cut1, cap); alpar@389: kpeter@1060: check(max_flow.flowValue() == min_cut_value && kpeter@1060: min_cut_value == 2 * flow_value, alpar@389: "The max flow value or the min cut value is wrong."); alpar@389: kpeter@1060: SF::startSecondPhase(max_flow); // start second phase of the algorithm alpar@389: kpeter@1060: check(checkFlow(g, max_flow.flowMap(), cap, s, t), alpar@389: "The flow is not feasible."); alpar@389: alpar@389: CutMap min_cut2(g); kpeter@1060: max_flow.minCutMap(min_cut2); kpeter@1060: min_cut_value = cutValue(g, min_cut2, cap); alpar@389: kpeter@1060: check(max_flow.flowValue() == min_cut_value && kpeter@1060: min_cut_value == 2 * flow_value, kpeter@1060: "The max flow value or the min cut value was not doubled"); alpar@389: alpar@389: kpeter@1060: max_flow.flowMap(flow); alpar@389: kpeter@1060: NodeIt tmp1(g, s); alpar@389: ++tmp1; kpeter@1060: if (tmp1 != INVALID) s = tmp1; alpar@389: kpeter@1060: NodeIt tmp2(g, t); alpar@389: ++tmp2; kpeter@1060: if (tmp2 != INVALID) t = tmp2; alpar@389: kpeter@1060: max_flow.source(s); kpeter@1060: max_flow.target(t); alpar@389: kpeter@1060: max_flow.run(); alpar@389: alpar@389: CutMap min_cut3(g); kpeter@1060: max_flow.minCutMap(min_cut3); kpeter@1060: min_cut_value=cutValue(g, min_cut3, cap); alpar@389: kpeter@1060: check(max_flow.flowValue() == min_cut_value, kpeter@1060: "The max flow value or the min cut value is wrong."); kpeter@1060: } alpar@389: kpeter@1060: // Struct for calling start functions of a general max flow algorithm kpeter@1060: template kpeter@1060: struct GeneralStartFunctions { kpeter@1060: kpeter@1060: static void startFirstPhase(MF& mf) { kpeter@1060: mf.start(); kpeter@1060: } kpeter@1060: kpeter@1060: static void startSecondPhase(MF& mf) { kpeter@1060: ignore_unused_variable_warning(mf); kpeter@1060: } kpeter@1060: kpeter@1060: }; kpeter@1060: kpeter@1060: // Struct for calling start functions of Preflow kpeter@1060: template kpeter@1060: struct PreflowStartFunctions { kpeter@1060: kpeter@1060: static void startFirstPhase(MF& mf) { kpeter@1060: mf.startFirstPhase(); kpeter@1060: } kpeter@1060: kpeter@1060: static void startSecondPhase(MF& mf) { kpeter@1060: mf.startSecondPhase(); kpeter@1060: } kpeter@1060: kpeter@1060: }; kpeter@1060: kpeter@1060: int main() { kpeter@1060: kpeter@1060: typedef concepts::Digraph GR; kpeter@1060: typedef concepts::ReadMap CM1; kpeter@1060: typedef concepts::ReadMap CM2; kpeter@1060: kpeter@1060: // Check the interface of Preflow kpeter@1060: checkConcept< MaxFlowClassConcept, kpeter@1060: Preflow >(); kpeter@1060: checkConcept< MaxFlowClassConcept, kpeter@1060: Preflow >(); kpeter@1060: kpeter@1060: // Check the interface of EdmondsKarp kpeter@1060: checkConcept< MaxFlowClassConcept, kpeter@1060: EdmondsKarp >(); kpeter@1060: checkConcept< MaxFlowClassConcept, kpeter@1060: EdmondsKarp >(); kpeter@1060: kpeter@1060: // Check Preflow kpeter@1060: typedef Preflow > PType1; kpeter@1060: typedef Preflow > PType2; kpeter@1060: checkMaxFlowAlg >(); kpeter@1060: checkMaxFlowAlg >(); kpeter@1060: initFlowTest(); kpeter@1060: kpeter@1060: // Check EdmondsKarp kpeter@1060: typedef EdmondsKarp > EKType1; kpeter@1060: typedef EdmondsKarp > EKType2; kpeter@1060: checkMaxFlowAlg >(); kpeter@1060: checkMaxFlowAlg >(); alpar@389: alpar@923: initFlowTest(); alpar@923: alpar@389: return 0; alpar@389: }