source: lemon-main/test/edmonds_karp_test.cc @ 1059:08f2dc76e82e

/* -*- 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/edmonds_karp.h>
#include <lemon/concepts/digraph.h>
#include <lemon/concepts/maps.h>
#include <lemon/lgf_reader.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";

void checkEdmondKarpCompile() {
  typedef int VType;
  typedef concepts::Digraph Digraph;

  typedef Digraph::Node Node;
  typedef Digraph::Arc Arc;
  typedef concepts::ReadMap<Arc,VType> CapMap;
  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
  typedef concepts::WriteMap<Node,bool> CutMap;

  Digraph g;
  Node n;
  Arc e;
  CapMap cap;
  FlowMap flow;
  CutMap cut;
  VType v;
  bool b;
  ignore_unused_variable_warning(v,b);
  typedef EdmondsKarp<Digraph, CapMap>
              ::SetFlowMap<FlowMap>
              ::Create EKType;
  EKType ek_test(g, cap, n, n);
  const EKType& const_ek_test = ek_test;

  EKType::Tolerance tol = const_ek_test.tolerance();
  ek_test.tolerance(tol);

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

  ek_test.init();
  ek_test.start();

  v = const_ek_test.flowValue();
  v = const_ek_test.flow(e);

  const FlowMap& fm = const_ek_test.flowMap();
  b = const_ek_test.minCut(n);
  const_ek_test.minCutMap(cut);

  ignore_unused_variable_warning(fm);
}

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

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

bool checkFlow(const SmartDigraph& g,
               const SmartDigraph::ArcMap<int>& flow,
               const SmartDigraph::ArcMap<int>& 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;
    int 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;
}

int main() {

  typedef SmartDigraph Digraph;

  typedef Digraph::Node Node;
  typedef Digraph::NodeIt NodeIt;
  typedef Digraph::ArcIt ArcIt;
  typedef Digraph::ArcMap<int> CapMap;
  typedef Digraph::ArcMap<int> FlowMap;
  typedef Digraph::NodeMap<bool> CutMap;

  typedef EdmondsKarp<Digraph, CapMap> EKType;

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

  EKType ek_test(g, cap, s, t);
  ek_test.run();

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

  CutMap min_cut(g);
  ek_test.minCutMap(min_cut);
  int min_cut_value=cutValue(g,min_cut,cap);

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

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

  int flow_value=ek_test.flowValue();

  for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
  ek_test.init(flow);
  ek_test.start();

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

  check(ek_test.flowValue() == min_cut_value &&
        min_cut_value == 2*flow_value,
        "The max flow value or the min cut value is wrong.");

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

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

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


  ek_test.flowMap(flow);

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

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

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

  ek_test.run();

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


  check(ek_test.flowValue() == min_cut_value,
        "The max flow value or the three min cut values are incorrect.");

  return 0;
}