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@1270: * Copyright (C) 2003-2013 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 kpeter@1228: #include alpar@404: #include alpar@404: #include alpar@404: #include kpeter@409: #include kpeter@1383: #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@1385: char test_lgf_float[] = kpeter@1385: "@nodes\n" kpeter@1385: "label\n" kpeter@1385: "0\n" kpeter@1385: "1\n" kpeter@1385: "2\n" kpeter@1385: "3\n" kpeter@1385: "4\n" kpeter@1385: "5\n" kpeter@1385: "6\n" kpeter@1385: "7\n" kpeter@1385: "8\n" kpeter@1385: "9\n" kpeter@1385: "@arcs\n" kpeter@1385: " capacity\n" kpeter@1385: "0 1 0.1\n" kpeter@1385: "0 2 0.1\n" kpeter@1385: "0 3 0.1\n" kpeter@1385: "1 4 0.1\n" kpeter@1385: "2 4 0.1\n" kpeter@1385: "3 4 0.1\n" kpeter@1385: "4 5 0.3\n" kpeter@1385: "5 6 0.1\n" kpeter@1385: "5 7 0.1\n" kpeter@1385: "5 8 0.1\n" kpeter@1385: "6 9 0.1\n" kpeter@1385: "7 9 0.1\n" kpeter@1385: "8 9 0.1\n" kpeter@1385: "@attributes\n" kpeter@1385: "source 0\n" kpeter@1385: "target 9\n"; kpeter@1385: kpeter@1228: // Checks the general interface of a max flow algorithm kpeter@1228: template kpeter@1228: struct MaxFlowClassConcept kpeter@1228: { kpeter@1228: kpeter@1228: template kpeter@1228: struct Constraints { kpeter@1228: kpeter@1228: typedef typename GR::Node Node; kpeter@1228: typedef typename GR::Arc Arc; kpeter@1228: typedef typename CAP::Value Value; kpeter@1228: typedef concepts::ReadWriteMap FlowMap; kpeter@1228: typedef concepts::WriteMap CutMap; kpeter@1228: kpeter@1228: GR g; kpeter@1228: Node n; kpeter@1228: Arc e; kpeter@1228: CAP cap; kpeter@1228: FlowMap flow; kpeter@1228: CutMap cut; kpeter@1228: Value v; kpeter@1228: bool b; kpeter@1228: kpeter@1228: void constraints() { kpeter@1228: checkConcept(); kpeter@1228: kpeter@1228: const Constraints& me = *this; kpeter@1228: kpeter@1228: typedef typename MF kpeter@1228: ::template SetFlowMap kpeter@1228: ::Create MaxFlowType; kpeter@1228: typedef typename MF::Create MaxFlowType2; kpeter@1228: MaxFlowType max_flow(me.g, me.cap, me.n, me.n); kpeter@1228: const MaxFlowType& const_max_flow = max_flow; kpeter@1228: kpeter@1228: max_flow kpeter@1228: .capacityMap(cap) kpeter@1228: .flowMap(flow) kpeter@1228: .source(n) kpeter@1228: .target(n); kpeter@1228: kpeter@1228: typename MaxFlowType::Tolerance tol = const_max_flow.tolerance(); kpeter@1228: max_flow.tolerance(tol); kpeter@1228: kpeter@1228: max_flow.init(); kpeter@1228: max_flow.init(cap); kpeter@1228: max_flow.run(); kpeter@1228: kpeter@1228: v = const_max_flow.flowValue(); kpeter@1228: v = const_max_flow.flow(e); kpeter@1228: const FlowMap& fm = const_max_flow.flowMap(); kpeter@1228: kpeter@1228: b = const_max_flow.minCut(n); kpeter@1228: const_max_flow.minCutMap(cut); kpeter@1228: alpar@1262: ::lemon::ignore_unused_variable_warning(fm); kpeter@1228: } kpeter@1228: kpeter@1228: }; kpeter@1228: kpeter@1228: }; kpeter@1228: kpeter@1228: // Checks the specific parts of Preflow's interface kpeter@409: void checkPreflowCompile() alpar@404: { kpeter@1228: typedef int Value; alpar@404: typedef concepts::Digraph Digraph; kpeter@1228: typedef concepts::ReadMap CapMap; kpeter@409: typedef Elevator Elev; kpeter@409: typedef LinkedElevator LinkedElev; kpeter@409: alpar@404: Digraph g; kpeter@1228: Digraph::Node n; alpar@404: CapMap cap; alpar@404: kpeter@632: typedef Preflow kpeter@1228: ::SetElevator kpeter@1228: ::SetStandardElevator kpeter@1228: ::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@632: kpeter@1228: bool b = preflow_test.init(cap); alpar@404: preflow_test.startFirstPhase(); alpar@404: preflow_test.startSecondPhase(); alpar@404: preflow_test.runMinCut(); alpar@404: alpar@1262: ::lemon::ignore_unused_variable_warning(b); alpar@404: } alpar@404: kpeter@1228: // Checks the specific parts of EdmondsKarp's interface kpeter@1228: void checkEdmondsKarpCompile() kpeter@1228: { kpeter@1228: typedef int Value; kpeter@1228: typedef concepts::Digraph Digraph; kpeter@1228: typedef concepts::ReadMap CapMap; kpeter@1228: kpeter@1228: Digraph g; kpeter@1228: Digraph::Node n; kpeter@1228: CapMap cap; kpeter@1228: kpeter@1228: EdmondsKarp ek_test(g, cap, n, n); kpeter@1228: kpeter@1228: ek_test.init(cap); kpeter@1228: bool b = ek_test.checkedInit(cap); kpeter@1228: b = ek_test.augment(); kpeter@1228: ek_test.start(); kpeter@1228: alpar@1262: ::lemon::ignore_unused_variable_warning(b); kpeter@1228: } kpeter@1228: kpeter@1228: kpeter@1228: template kpeter@1382: T cutValue(const SmartDigraph& g, kpeter@1382: const SmartDigraph::NodeMap& cut, kpeter@1382: const SmartDigraph::ArcMap& cap) { alpar@404: kpeter@1382: T c = 0; kpeter@1382: for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { kpeter@1382: if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e]; alpar@404: } alpar@404: return c; alpar@404: } alpar@404: kpeter@1228: template alpar@404: bool checkFlow(const SmartDigraph& g, kpeter@1228: const SmartDigraph::ArcMap& flow, kpeter@1228: const SmartDigraph::ArcMap& cap, kpeter@1383: SmartDigraph::Node s, SmartDigraph::Node t, kpeter@1383: const Tolerance& tol) { alpar@404: alpar@404: for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) { kpeter@1383: if (tol.negative(flow[e]) || tol.less(cap[e], flow[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; kpeter@1228: T 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: } kpeter@1383: if (tol.nonZero(sum)) return false; alpar@404: } alpar@404: return true; alpar@404: } alpar@404: kpeter@1382: void checkInitPreflow() alpar@1027: { alpar@1027: DIGRAPH_TYPEDEFS(SmartDigraph); alpar@1270: alpar@1027: SmartDigraph g; kpeter@1382: SmartDigraph::ArcMap cap(g), iflow(g); kpeter@1382: Node s = g.addNode(); Node t = g.addNode(); kpeter@1382: Node n1 = g.addNode(); Node n2 = g.addNode(); alpar@1027: Arc a; kpeter@1382: a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20; kpeter@1382: a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0; kpeter@1382: a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0; alpar@1027: kpeter@1382: Preflow pre(g, cap, s, t); alpar@1027: pre.init(iflow); alpar@1027: pre.startFirstPhase(); kpeter@1382: kpeter@1382: check(pre.flowValue() == 10, "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: kpeter@1228: template kpeter@1384: void checkMaxFlowAlg(const char *input_lgf, typename MF::Value expected) { kpeter@1228: typedef SmartDigraph Digraph; kpeter@1228: DIGRAPH_TYPEDEFS(Digraph); alpar@1027: kpeter@1228: typedef typename MF::Value Value; kpeter@1228: typedef Digraph::ArcMap CapMap; kpeter@1228: typedef CapMap FlowMap; kpeter@1228: typedef BoolNodeMap CutMap; alpar@404: kpeter@1383: Tolerance tol; kpeter@1383: alpar@404: Digraph g; alpar@404: Node s, t; alpar@404: CapMap cap(g); kpeter@1384: std::istringstream input(input_lgf); kpeter@1385: DigraphReader(g, input) kpeter@1228: .arcMap("capacity", cap) kpeter@1385: .node("source", s) kpeter@1385: .node("target", t) kpeter@1228: .run(); alpar@404: kpeter@1228: MF max_flow(g, cap, s, t); kpeter@1228: max_flow.run(); alpar@404: kpeter@1384: check(!tol.different(expected, max_flow.flowValue()), kpeter@1384: "Incorrect max flow value."); kpeter@1383: check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol), alpar@404: "The flow is not feasible."); alpar@404: alpar@404: CutMap min_cut(g); kpeter@1228: max_flow.minCutMap(min_cut); kpeter@1228: Value min_cut_value = cutValue(g, min_cut, cap); alpar@404: kpeter@1384: check(!tol.different(expected, min_cut_value), kpeter@1384: "Incorrect min cut value."); alpar@404: alpar@404: FlowMap flow(g); kpeter@1385: for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e]; kpeter@1385: for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e]; kpeter@1228: max_flow.init(flow); kpeter@1228: kpeter@1228: SF::startFirstPhase(max_flow); // start first phase of the algorithm alpar@404: alpar@404: CutMap min_cut1(g); kpeter@1228: max_flow.minCutMap(min_cut1); kpeter@1228: min_cut_value = cutValue(g, min_cut1, cap); alpar@404: kpeter@1385: check(!tol.different(17 * expected, max_flow.flowValue()), kpeter@1384: "Incorrect max flow value."); kpeter@1385: check(!tol.different(17 * expected, min_cut_value), kpeter@1384: "Incorrect min cut value."); alpar@404: kpeter@1228: SF::startSecondPhase(max_flow); // start second phase of the algorithm alpar@404: kpeter@1383: check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol), alpar@404: "The flow is not feasible."); alpar@404: alpar@404: CutMap min_cut2(g); kpeter@1228: max_flow.minCutMap(min_cut2); kpeter@1228: min_cut_value = cutValue(g, min_cut2, cap); alpar@404: kpeter@1385: check(!tol.different(17 * expected, max_flow.flowValue()), kpeter@1384: "Incorrect max flow value."); kpeter@1385: check(!tol.different(17 * expected, min_cut_value), kpeter@1384: "Incorrect min cut value."); alpar@404: kpeter@1228: max_flow.flowMap(flow); alpar@404: kpeter@1228: NodeIt tmp1(g, s); alpar@404: ++tmp1; kpeter@1228: if (tmp1 != INVALID) s = tmp1; alpar@404: kpeter@1228: NodeIt tmp2(g, t); alpar@404: ++tmp2; kpeter@1228: if (tmp2 != INVALID) t = tmp2; alpar@404: kpeter@1228: max_flow.source(s); kpeter@1228: max_flow.target(t); alpar@404: kpeter@1228: max_flow.run(); alpar@404: alpar@404: CutMap min_cut3(g); kpeter@1228: max_flow.minCutMap(min_cut3); kpeter@1382: min_cut_value = cutValue(g, min_cut3, cap); alpar@404: kpeter@1383: check(!tol.different(max_flow.flowValue(), min_cut_value), kpeter@1228: "The max flow value or the min cut value is wrong."); kpeter@1228: } alpar@404: kpeter@1228: // Struct for calling start functions of a general max flow algorithm kpeter@1228: template kpeter@1228: struct GeneralStartFunctions { kpeter@1228: kpeter@1228: static void startFirstPhase(MF& mf) { kpeter@1228: mf.start(); kpeter@1228: } kpeter@1228: kpeter@1228: static void startSecondPhase(MF& mf) { alpar@1262: ::lemon::ignore_unused_variable_warning(mf); kpeter@1228: } kpeter@1228: kpeter@1228: }; kpeter@1228: kpeter@1228: // Struct for calling start functions of Preflow kpeter@1228: template kpeter@1228: struct PreflowStartFunctions { kpeter@1228: kpeter@1228: static void startFirstPhase(MF& mf) { kpeter@1228: mf.startFirstPhase(); kpeter@1228: } kpeter@1228: kpeter@1228: static void startSecondPhase(MF& mf) { kpeter@1228: mf.startSecondPhase(); kpeter@1228: } kpeter@1228: kpeter@1228: }; kpeter@1228: kpeter@1228: int main() { kpeter@1228: kpeter@1228: typedef concepts::Digraph GR; kpeter@1228: typedef concepts::ReadMap CM1; kpeter@1228: typedef concepts::ReadMap CM2; kpeter@1228: kpeter@1228: // Check the interface of Preflow kpeter@1228: checkConcept< MaxFlowClassConcept, kpeter@1228: Preflow >(); kpeter@1228: checkConcept< MaxFlowClassConcept, kpeter@1228: Preflow >(); kpeter@1228: kpeter@1228: // Check the interface of EdmondsKarp kpeter@1228: checkConcept< MaxFlowClassConcept, kpeter@1228: EdmondsKarp >(); kpeter@1228: checkConcept< MaxFlowClassConcept, kpeter@1228: EdmondsKarp >(); kpeter@1228: kpeter@1228: // Check Preflow kpeter@1228: typedef Preflow > PType1; kpeter@1228: typedef Preflow > PType2; kpeter@1384: typedef Preflow > PType3; kpeter@1385: kpeter@1384: checkMaxFlowAlg >(test_lgf, 13); kpeter@1384: checkMaxFlowAlg >(test_lgf, 13); kpeter@1384: checkMaxFlowAlg >(test_lgf, 13); kpeter@1382: kpeter@1385: checkMaxFlowAlg >(test_lgf_float, 0.3); kpeter@1385: checkMaxFlowAlg >(test_lgf_float, 0.3); kpeter@1385: kpeter@1382: checkInitPreflow(); alpar@1270: kpeter@1228: // Check EdmondsKarp kpeter@1228: typedef EdmondsKarp > EKType1; kpeter@1228: typedef EdmondsKarp > EKType2; kpeter@1384: typedef EdmondsKarp > EKType3; kpeter@1385: kpeter@1384: checkMaxFlowAlg >(test_lgf, 13); kpeter@1384: checkMaxFlowAlg >(test_lgf, 13); kpeter@1384: checkMaxFlowAlg >(test_lgf, 13); alpar@404: kpeter@1385: checkMaxFlowAlg >(test_lgf_float, 0.3); kpeter@1385: checkMaxFlowAlg >(test_lgf_float, 0.3); kpeter@1385: alpar@404: return 0; alpar@404: }