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@1092:  * Copyright (C) 2003-2013
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 <iostream>
alpar@389: 
alpar@389: #include "test_tools.h"
alpar@389: #include <lemon/smart_graph.h>
alpar@389: #include <lemon/preflow.h>
kpeter@1060: #include <lemon/edmonds_karp.h>
alpar@389: #include <lemon/concepts/digraph.h>
alpar@389: #include <lemon/concepts/maps.h>
alpar@389: #include <lemon/lgf_reader.h>
kpeter@394: #include <lemon/elevator.h>
kpeter@1167: #include <lemon/tolerance.h>
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@1169: char test_lgf_float[] =
kpeter@1169:   "@nodes\n"
kpeter@1169:   "label\n"
kpeter@1169:   "0\n"
kpeter@1169:   "1\n"
kpeter@1169:   "2\n"
kpeter@1169:   "3\n"
kpeter@1169:   "4\n"
kpeter@1169:   "5\n"
kpeter@1169:   "6\n"
kpeter@1169:   "7\n"
kpeter@1169:   "8\n"
kpeter@1169:   "9\n"
kpeter@1169:   "@arcs\n"
kpeter@1169:   "      capacity\n"
kpeter@1169:   "0 1 0.1\n"
kpeter@1169:   "0 2 0.1\n"
kpeter@1169:   "0 3 0.1\n"
kpeter@1169:   "1 4 0.1\n"
kpeter@1169:   "2 4 0.1\n"
kpeter@1169:   "3 4 0.1\n"
kpeter@1169:   "4 5 0.3\n"
kpeter@1169:   "5 6 0.1\n"
kpeter@1169:   "5 7 0.1\n"
kpeter@1169:   "5 8 0.1\n"
kpeter@1169:   "6 9 0.1\n"
kpeter@1169:   "7 9 0.1\n"
kpeter@1169:   "8 9 0.1\n"
kpeter@1169:   "@attributes\n"
kpeter@1169:   "source 0\n"
kpeter@1169:   "target 9\n";
kpeter@1169: 
kpeter@1060: // Checks the general interface of a max flow algorithm
kpeter@1060: template <typename GR, typename CAP>
kpeter@1060: struct MaxFlowClassConcept
kpeter@1060: {
kpeter@1060: 
kpeter@1060:   template <typename MF>
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<Arc, Value> FlowMap;
kpeter@1060:     typedef concepts::WriteMap<Node, bool> 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<concepts::Digraph, GR>();
kpeter@1060: 
kpeter@1060:       const Constraints& me = *this;
kpeter@1060: 
kpeter@1060:       typedef typename MF
kpeter@1060:           ::template SetFlowMap<FlowMap>
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: 
alpar@1087:       ::lemon::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<Digraph::Arc, Value> CapMap;
kpeter@394:   typedef Elevator<Digraph, Digraph::Node> Elev;
kpeter@394:   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
kpeter@394: 
alpar@389:   Digraph g;
kpeter@1060:   Digraph::Node n;
alpar@389:   CapMap cap;
alpar@389: 
kpeter@585:   typedef Preflow<Digraph, CapMap>
kpeter@1060:       ::SetElevator<Elev>
kpeter@1060:       ::SetStandardElevator<LinkedElev>
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<PreflowType::Elevator&>(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: 
alpar@1087:   ::lemon::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<Digraph::Arc, Value> CapMap;
kpeter@1060: 
kpeter@1060:   Digraph g;
kpeter@1060:   Digraph::Node n;
kpeter@1060:   CapMap cap;
kpeter@1060: 
kpeter@1060:   EdmondsKarp<Digraph, CapMap> 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: 
alpar@1087:   ::lemon::ignore_unused_variable_warning(b);
kpeter@1060: }
kpeter@1060: 
kpeter@1060: 
kpeter@1060: template <typename T>
kpeter@1166: T cutValue(const SmartDigraph& g,
kpeter@1166:            const SmartDigraph::NodeMap<bool>& cut,
kpeter@1166:            const SmartDigraph::ArcMap<T>& cap) {
alpar@389: 
kpeter@1166:   T c = 0;
kpeter@1166:   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
kpeter@1166:     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 <typename T>
alpar@389: bool checkFlow(const SmartDigraph& g,
kpeter@1060:                const SmartDigraph::ArcMap<T>& flow,
kpeter@1060:                const SmartDigraph::ArcMap<T>& cap,
kpeter@1167:                SmartDigraph::Node s, SmartDigraph::Node t,
kpeter@1167:                const Tolerance<T>& tol) {
alpar@389: 
alpar@389:   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
kpeter@1167:     if (tol.negative(flow[e]) || tol.less(cap[e], flow[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:     }
kpeter@1167:     if (tol.nonZero(sum)) return false;
alpar@389:   }
alpar@389:   return true;
alpar@389: }
alpar@389: 
kpeter@1166: void checkInitPreflow()
alpar@923: {
alpar@923:   DIGRAPH_TYPEDEFS(SmartDigraph);
alpar@1092: 
alpar@923:   SmartDigraph g;
kpeter@1166:   SmartDigraph::ArcMap<int> cap(g), iflow(g);
kpeter@1166:   Node s = g.addNode(); Node t = g.addNode();
kpeter@1166:   Node n1 = g.addNode(); Node n2 = g.addNode();
alpar@923:   Arc a;
kpeter@1166:   a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20;
kpeter@1166:   a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0;
kpeter@1166:   a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0;
alpar@923: 
kpeter@1166:   Preflow<SmartDigraph> pre(g, cap, s, t);
alpar@923:   pre.init(iflow);
alpar@923:   pre.startFirstPhase();
kpeter@1166: 
kpeter@1166:   check(pre.flowValue() == 10, "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 <typename MF, typename SF>
kpeter@1168: void checkMaxFlowAlg(const char *input_lgf,  typename MF::Value expected) {
kpeter@1060:   typedef SmartDigraph Digraph;
kpeter@1060:   DIGRAPH_TYPEDEFS(Digraph);
alpar@923: 
kpeter@1060:   typedef typename MF::Value Value;
kpeter@1060:   typedef Digraph::ArcMap<Value> CapMap;
kpeter@1060:   typedef CapMap FlowMap;
kpeter@1060:   typedef BoolNodeMap CutMap;
alpar@389: 
kpeter@1167:   Tolerance<Value> tol;
kpeter@1167: 
alpar@389:   Digraph g;
alpar@389:   Node s, t;
alpar@389:   CapMap cap(g);
kpeter@1168:   std::istringstream input(input_lgf);
kpeter@1169:   DigraphReader<Digraph>(g, input)
kpeter@1060:       .arcMap("capacity", cap)
kpeter@1169:       .node("source", s)
kpeter@1169:       .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@1168:   check(!tol.different(expected, max_flow.flowValue()),
kpeter@1168:         "Incorrect max flow value.");
kpeter@1167:   check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
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@1168:   check(!tol.different(expected, min_cut_value),
kpeter@1168:         "Incorrect min cut value.");
alpar@389: 
alpar@389:   FlowMap flow(g);
kpeter@1169:   for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
kpeter@1169:   for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * 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@1169:   check(!tol.different(17 * expected, max_flow.flowValue()),
kpeter@1168:         "Incorrect max flow value.");
kpeter@1169:   check(!tol.different(17 * expected, min_cut_value),
kpeter@1168:         "Incorrect min cut value.");
alpar@389: 
kpeter@1060:   SF::startSecondPhase(max_flow);       // start second phase of the algorithm
alpar@389: 
kpeter@1167:   check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
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@1169:   check(!tol.different(17 * expected, max_flow.flowValue()),
kpeter@1168:         "Incorrect max flow value.");
kpeter@1169:   check(!tol.different(17 * expected, min_cut_value),
kpeter@1168:         "Incorrect min cut value.");
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@1166:   min_cut_value = cutValue(g, min_cut3, cap);
alpar@389: 
kpeter@1167:   check(!tol.different(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 <typename MF>
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) {
alpar@1087:     ::lemon::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 <typename MF>
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<GR::Arc, int> CM1;
kpeter@1060:   typedef concepts::ReadMap<GR::Arc, double> CM2;
kpeter@1060: 
kpeter@1060:   // Check the interface of Preflow
kpeter@1060:   checkConcept< MaxFlowClassConcept<GR, CM1>,
kpeter@1060:                 Preflow<GR, CM1> >();
kpeter@1060:   checkConcept< MaxFlowClassConcept<GR, CM2>,
kpeter@1060:                 Preflow<GR, CM2> >();
kpeter@1060: 
kpeter@1060:   // Check the interface of EdmondsKarp
kpeter@1060:   checkConcept< MaxFlowClassConcept<GR, CM1>,
kpeter@1060:                 EdmondsKarp<GR, CM1> >();
kpeter@1060:   checkConcept< MaxFlowClassConcept<GR, CM2>,
kpeter@1060:                 EdmondsKarp<GR, CM2> >();
kpeter@1060: 
kpeter@1060:   // Check Preflow
kpeter@1060:   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
kpeter@1060:   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
kpeter@1168:   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
kpeter@1169: 
kpeter@1168:   checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
kpeter@1168:   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
kpeter@1168:   checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
kpeter@1166: 
alpar@1178:   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3f);
kpeter@1169:   checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
kpeter@1169: 
kpeter@1166:   checkInitPreflow();
alpar@1092: 
kpeter@1060:   // Check EdmondsKarp
kpeter@1060:   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
kpeter@1060:   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
kpeter@1168:   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
kpeter@1169: 
kpeter@1168:   checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
kpeter@1168:   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
kpeter@1168:   checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
alpar@389: 
alpar@1178:   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3f);
kpeter@1169:   checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
kpeter@1169: 
alpar@389:   return 0;
alpar@389: }