source: lemon/test/max_flow_test.cc @ 1384:259e3a90ad97

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2013
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <iostream>

#include "test_tools.h"
#include <lemon/smart_graph.h>
#include <lemon/preflow.h>
#include <lemon/edmonds_karp.h>
#include <lemon/concepts/digraph.h>
#include <lemon/concepts/maps.h>
#include <lemon/lgf_reader.h>
#include <lemon/elevator.h>
#include <lemon/tolerance.h>

using namespace lemon;

char test_lgf[] =
  "@nodes\n"
  "label\n"
  "0\n"
  "1\n"
  "2\n"
  "3\n"
  "4\n"
  "5\n"
  "6\n"
  "7\n"
  "8\n"
  "9\n"
  "@arcs\n"
  "    label capacity\n"
  "0 1 0     20\n"
  "0 2 1     0\n"
  "1 1 2     3\n"
  "1 2 3     8\n"
  "1 3 4     8\n"
  "2 5 5     5\n"
  "3 2 6     5\n"
  "3 5 7     5\n"
  "3 6 8     5\n"
  "4 3 9     3\n"
  "5 7 10    3\n"
  "5 6 11    10\n"
  "5 8 12    10\n"
  "6 8 13    8\n"
  "8 9 14    20\n"
  "8 1 15    5\n"
  "9 5 16    5\n"
  "@attributes\n"
  "source 1\n"
  "target 8\n";

// Checks the general interface of a max flow algorithm
template <typename GR, typename CAP>
struct MaxFlowClassConcept
{

  template <typename MF>
  struct Constraints {

    typedef typename GR::Node Node;
    typedef typename GR::Arc Arc;
    typedef typename CAP::Value Value;
    typedef concepts::ReadWriteMap<Arc, Value> FlowMap;
    typedef concepts::WriteMap<Node, bool> CutMap;

    GR g;
    Node n;
    Arc e;
    CAP cap;
    FlowMap flow;
    CutMap cut;
    Value v;
    bool b;

    void constraints() {
      checkConcept<concepts::Digraph, GR>();

      const Constraints& me = *this;

      typedef typename MF
          ::template SetFlowMap<FlowMap>
          ::Create MaxFlowType;
      typedef typename MF::Create MaxFlowType2;
      MaxFlowType max_flow(me.g, me.cap, me.n, me.n);
      const MaxFlowType& const_max_flow = max_flow;

      max_flow
          .capacityMap(cap)
          .flowMap(flow)
          .source(n)
          .target(n);

      typename MaxFlowType::Tolerance tol = const_max_flow.tolerance();
      max_flow.tolerance(tol);

      max_flow.init();
      max_flow.init(cap);
      max_flow.run();

      v = const_max_flow.flowValue();
      v = const_max_flow.flow(e);
      const FlowMap& fm = const_max_flow.flowMap();

      b = const_max_flow.minCut(n);
      const_max_flow.minCutMap(cut);

      ::lemon::ignore_unused_variable_warning(fm);
    }

  };

};

// Checks the specific parts of Preflow's interface
void checkPreflowCompile()
{
  typedef int Value;
  typedef concepts::Digraph Digraph;
  typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
  typedef Elevator<Digraph, Digraph::Node> Elev;
  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;

  Digraph g;
  Digraph::Node n;
  CapMap cap;

  typedef Preflow<Digraph, CapMap>
      ::SetElevator<Elev>
      ::SetStandardElevator<LinkedElev>
      ::Create PreflowType;
  PreflowType preflow_test(g, cap, n, n);
  const PreflowType& const_preflow_test = preflow_test;

  const PreflowType::Elevator& elev = const_preflow_test.elevator();
  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));

  bool b = preflow_test.init(cap);
  preflow_test.startFirstPhase();
  preflow_test.startSecondPhase();
  preflow_test.runMinCut();

  ::lemon::ignore_unused_variable_warning(b);
}

// Checks the specific parts of EdmondsKarp's interface
void checkEdmondsKarpCompile()
{
  typedef int Value;
  typedef concepts::Digraph Digraph;
  typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;

  Digraph g;
  Digraph::Node n;
  CapMap cap;

  EdmondsKarp<Digraph, CapMap> ek_test(g, cap, n, n);

  ek_test.init(cap);
  bool b = ek_test.checkedInit(cap);
  b = ek_test.augment();
  ek_test.start();

  ::lemon::ignore_unused_variable_warning(b);
}


template <typename T>
T cutValue(const SmartDigraph& g,
           const SmartDigraph::NodeMap<bool>& cut,
           const SmartDigraph::ArcMap<T>& cap) {

  T c = 0;
  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
    if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e];
  }
  return c;
}

template <typename T>
bool checkFlow(const SmartDigraph& g,
               const SmartDigraph::ArcMap<T>& flow,
               const SmartDigraph::ArcMap<T>& cap,
               SmartDigraph::Node s, SmartDigraph::Node t,
               const Tolerance<T>& tol) {

  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
    if (tol.negative(flow[e]) || tol.less(cap[e], flow[e])) return false;
  }

  for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
    if (n == s || n == t) continue;
    T sum = 0;
    for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
      sum += flow[e];
    }
    for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
      sum -= flow[e];
    }
    if (tol.nonZero(sum)) return false;
  }
  return true;
}

void checkInitPreflow()
{
  DIGRAPH_TYPEDEFS(SmartDigraph);

  SmartDigraph g;
  SmartDigraph::ArcMap<int> cap(g), iflow(g);
  Node s = g.addNode(); Node t = g.addNode();
  Node n1 = g.addNode(); Node n2 = g.addNode();
  Arc a;
  a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20;
  a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0;
  a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0;

  Preflow<SmartDigraph> pre(g, cap, s, t);
  pre.init(iflow);
  pre.startFirstPhase();

  check(pre.flowValue() == 10, "Incorrect max flow value.");
  check(pre.minCut(s), "Wrong min cut (Node s).");
  check(pre.minCut(n1), "Wrong min cut (Node n1).");
  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
  check(!pre.minCut(t), "Wrong min cut (Node t).");
}

template <typename MF, typename SF>
void checkMaxFlowAlg(const char *input_lgf,  typename MF::Value expected) {
  typedef SmartDigraph Digraph;
  DIGRAPH_TYPEDEFS(Digraph);

  typedef typename MF::Value Value;
  typedef Digraph::ArcMap<Value> CapMap;
  typedef CapMap FlowMap;
  typedef BoolNodeMap CutMap;

  Tolerance<Value> tol;

  Digraph g;
  Node s, t;
  CapMap cap(g);
  std::istringstream input(input_lgf);
  DigraphReader<Digraph>(g,input)
      .arcMap("capacity", cap)
      .node("source",s)
      .node("target",t)
      .run();

  MF max_flow(g, cap, s, t);
  max_flow.run();

  check(!tol.different(expected, max_flow.flowValue()),
        "Incorrect max flow value.");
  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
        "The flow is not feasible.");

  CutMap min_cut(g);
  max_flow.minCutMap(min_cut);
  Value min_cut_value = cutValue(g, min_cut, cap);

  check(!tol.different(expected, min_cut_value),
        "Incorrect min cut value.");

  FlowMap flow(g);
  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
  max_flow.init(flow);

  SF::startFirstPhase(max_flow);       // start first phase of the algorithm

  CutMap min_cut1(g);
  max_flow.minCutMap(min_cut1);
  min_cut_value = cutValue(g, min_cut1, cap);

  check(!tol.different(2 * expected, max_flow.flowValue()),
        "Incorrect max flow value.");
  check(!tol.different(2 * expected, min_cut_value),
        "Incorrect min cut value.");

  SF::startSecondPhase(max_flow);       // start second phase of the algorithm

  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
        "The flow is not feasible.");

  CutMap min_cut2(g);
  max_flow.minCutMap(min_cut2);
  min_cut_value = cutValue(g, min_cut2, cap);

  check(!tol.different(2 * expected, max_flow.flowValue()),
        "Incorrect max flow value.");
  check(!tol.different(2 * expected, min_cut_value),
        "Incorrect min cut value.");

  max_flow.flowMap(flow);

  NodeIt tmp1(g, s);
  ++tmp1;
  if (tmp1 != INVALID) s = tmp1;

  NodeIt tmp2(g, t);
  ++tmp2;
  if (tmp2 != INVALID) t = tmp2;

  max_flow.source(s);
  max_flow.target(t);

  max_flow.run();

  CutMap min_cut3(g);
  max_flow.minCutMap(min_cut3);
  min_cut_value = cutValue(g, min_cut3, cap);

  check(!tol.different(max_flow.flowValue(), min_cut_value),
        "The max flow value or the min cut value is wrong.");
}

// Struct for calling start functions of a general max flow algorithm
template <typename MF>
struct GeneralStartFunctions {

  static void startFirstPhase(MF& mf) {
    mf.start();
  }

  static void startSecondPhase(MF& mf) {
    ::lemon::ignore_unused_variable_warning(mf);
  }

};

// Struct for calling start functions of Preflow
template <typename MF>
struct PreflowStartFunctions {

  static void startFirstPhase(MF& mf) {
    mf.startFirstPhase();
  }

  static void startSecondPhase(MF& mf) {
    mf.startSecondPhase();
  }

};

int main() {

  typedef concepts::Digraph GR;
  typedef concepts::ReadMap<GR::Arc, int> CM1;
  typedef concepts::ReadMap<GR::Arc, double> CM2;

  // Check the interface of Preflow
  checkConcept< MaxFlowClassConcept<GR, CM1>,
                Preflow<GR, CM1> >();
  checkConcept< MaxFlowClassConcept<GR, CM2>,
                Preflow<GR, CM2> >();

  // Check the interface of EdmondsKarp
  checkConcept< MaxFlowClassConcept<GR, CM1>,
                EdmondsKarp<GR, CM1> >();
  checkConcept< MaxFlowClassConcept<GR, CM2>,
                EdmondsKarp<GR, CM2> >();

  // Check Preflow
  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);

  checkInitPreflow();

  // Check EdmondsKarp
  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);

  return 0;
}