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 <iostream>
alpar@404: 
alpar@404: #include "test_tools.h"
alpar@404: #include <lemon/smart_graph.h>
alpar@404: #include <lemon/preflow.h>
kpeter@1228: #include <lemon/edmonds_karp.h>
alpar@404: #include <lemon/concepts/digraph.h>
alpar@404: #include <lemon/concepts/maps.h>
alpar@404: #include <lemon/lgf_reader.h>
kpeter@409: #include <lemon/elevator.h>
kpeter@1383: #include <lemon/tolerance.h>
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 <typename GR, typename CAP>
kpeter@1228: struct MaxFlowClassConcept
kpeter@1228: {
kpeter@1228: 
kpeter@1228:   template <typename MF>
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<Arc, Value> FlowMap;
kpeter@1228:     typedef concepts::WriteMap<Node, bool> 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<concepts::Digraph, GR>();
kpeter@1228: 
kpeter@1228:       const Constraints& me = *this;
kpeter@1228: 
kpeter@1228:       typedef typename MF
kpeter@1228:           ::template SetFlowMap<FlowMap>
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<Digraph::Arc, Value> CapMap;
kpeter@409:   typedef Elevator<Digraph, Digraph::Node> Elev;
kpeter@409:   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
kpeter@409: 
alpar@404:   Digraph g;
kpeter@1228:   Digraph::Node n;
alpar@404:   CapMap cap;
alpar@404: 
kpeter@632:   typedef Preflow<Digraph, CapMap>
kpeter@1228:       ::SetElevator<Elev>
kpeter@1228:       ::SetStandardElevator<LinkedElev>
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<PreflowType::Elevator&>(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<Digraph::Arc, Value> CapMap;
kpeter@1228: 
kpeter@1228:   Digraph g;
kpeter@1228:   Digraph::Node n;
kpeter@1228:   CapMap cap;
kpeter@1228: 
kpeter@1228:   EdmondsKarp<Digraph, CapMap> 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 <typename T>
kpeter@1382: T cutValue(const SmartDigraph& g,
kpeter@1382:            const SmartDigraph::NodeMap<bool>& cut,
kpeter@1382:            const SmartDigraph::ArcMap<T>& 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 <typename T>
alpar@404: bool checkFlow(const SmartDigraph& g,
kpeter@1228:                const SmartDigraph::ArcMap<T>& flow,
kpeter@1228:                const SmartDigraph::ArcMap<T>& cap,
kpeter@1383:                SmartDigraph::Node s, SmartDigraph::Node t,
kpeter@1383:                const Tolerance<T>& 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<int> 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<SmartDigraph> 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 <typename MF, typename SF>
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<Value> CapMap;
kpeter@1228:   typedef CapMap FlowMap;
kpeter@1228:   typedef BoolNodeMap CutMap;
alpar@404: 
kpeter@1383:   Tolerance<Value> 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<Digraph>(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 <typename MF>
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 <typename MF>
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<GR::Arc, int> CM1;
kpeter@1228:   typedef concepts::ReadMap<GR::Arc, double> CM2;
kpeter@1228: 
kpeter@1228:   // Check the interface of Preflow
kpeter@1228:   checkConcept< MaxFlowClassConcept<GR, CM1>,
kpeter@1228:                 Preflow<GR, CM1> >();
kpeter@1228:   checkConcept< MaxFlowClassConcept<GR, CM2>,
kpeter@1228:                 Preflow<GR, CM2> >();
kpeter@1228: 
kpeter@1228:   // Check the interface of EdmondsKarp
kpeter@1228:   checkConcept< MaxFlowClassConcept<GR, CM1>,
kpeter@1228:                 EdmondsKarp<GR, CM1> >();
kpeter@1228:   checkConcept< MaxFlowClassConcept<GR, CM2>,
kpeter@1228:                 EdmondsKarp<GR, CM2> >();
kpeter@1228: 
kpeter@1228:   // Check Preflow
kpeter@1228:   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
kpeter@1228:   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
kpeter@1384:   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
kpeter@1385: 
kpeter@1384:   checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
kpeter@1384:   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
kpeter@1384:   checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
kpeter@1382: 
kpeter@1385:   checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
kpeter@1385:   checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
kpeter@1385: 
kpeter@1382:   checkInitPreflow();
alpar@1270: 
kpeter@1228:   // Check EdmondsKarp
kpeter@1228:   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
kpeter@1228:   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
kpeter@1384:   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
kpeter@1385: 
kpeter@1384:   checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
kpeter@1384:   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
kpeter@1384:   checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
alpar@404: 
kpeter@1385:   checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
kpeter@1385:   checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
kpeter@1385: 
alpar@404:   return 0;
alpar@404: }