source: lemon-main/test/max_flow_test.cc @ 1076:38c432e01489

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2010
 * 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>

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);

      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();

  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;
  typedef Elevator<Digraph, Digraph::Node> Elev;
  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;

  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();

  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) {

  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
    if (flow[e] < 0 || flow[e] > cap[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 (sum != 0) return false;
  }
  return true;
}

void initFlowTest()
{
  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, "The 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() {
  typedef SmartDigraph Digraph;
  DIGRAPH_TYPEDEFS(Digraph);

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

  Digraph g;
  Node s, t;
  CapMap cap(g);
  std::istringstream input(test_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(checkFlow(g, max_flow.flowMap(), cap, s, t),
        "The flow is not feasible.");

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

  check(max_flow.flowValue() == min_cut_value,
        "The max flow value is not equal to the min cut value.");

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

  Value flow_value = max_flow.flowValue();

  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(max_flow.flowValue() == min_cut_value &&
        min_cut_value == 2 * flow_value,
        "The max flow value or the min cut value is wrong.");

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

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

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

  check(max_flow.flowValue() == min_cut_value &&
        min_cut_value == 2 * flow_value,
        "The max flow value or the min cut value was not doubled");


  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(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) {
    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;
  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
  initFlowTest();
  
  // Check EdmondsKarp
  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();

  initFlowTest();
  
  return 0;
}