source: lemon-main/test/gomory_hu_test.cc @ 889:0bca98cbebbb

/* -*- 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/concepts/graph.h>
#include <lemon/concepts/maps.h>
#include <lemon/lgf_reader.h>
#include <lemon/gomory_hu.h>
#include <cstdlib>

using namespace std;
using namespace lemon;

typedef SmartGraph Graph;

char test_lgf[] =
  "@nodes\n"
  "label\n"
  "0\n"
  "1\n"
  "2\n"
  "3\n"
  "4\n"
  "@arcs\n"
  "     label capacity\n"
  "0 1  0     1\n"
  "1 2  1     1\n"
  "2 3  2     1\n"
  "0 3  4     5\n"
  "0 3  5     10\n"
  "0 3  6     7\n"
  "4 2  7     1\n"
  "@attributes\n"
  "source 0\n"
  "target 3\n";

void checkGomoryHuCompile()
{
  typedef int Value;
  typedef concepts::Graph Graph;

  typedef Graph::Node Node;
  typedef Graph::Edge Edge;
  typedef concepts::ReadMap<Edge, Value> CapMap;
  typedef concepts::ReadWriteMap<Node, bool> CutMap;

  Graph g;
  Node n;
  CapMap cap;
  CutMap cut;
  Value v;
  int d;

  GomoryHu<Graph, CapMap> gh_test(g, cap);
  const GomoryHu<Graph, CapMap>&
    const_gh_test = gh_test;

  gh_test.run();

  n = const_gh_test.predNode(n);
  v = const_gh_test.predValue(n);
  d = const_gh_test.rootDist(n);
  v = const_gh_test.minCutValue(n, n);
  v = const_gh_test.minCutMap(n, n, cut);
}

GRAPH_TYPEDEFS(Graph);
typedef Graph::EdgeMap<int> IntEdgeMap;
typedef Graph::NodeMap<bool> BoolNodeMap;

int cutValue(const Graph& graph, const BoolNodeMap& cut,
             const IntEdgeMap& capacity) {

  int sum = 0;
  for (EdgeIt e(graph); e != INVALID; ++e) {
    Node s = graph.u(e);
    Node t = graph.v(e);

    if (cut[s] != cut[t]) {
      sum += capacity[e];
    }
  }
  return sum;
}


int main() {
  Graph graph;
  IntEdgeMap capacity(graph);

  std::istringstream input(test_lgf);
  GraphReader<Graph>(graph, input).
    edgeMap("capacity", capacity).run();

  GomoryHu<Graph> ght(graph, capacity);
  ght.run();

  for (NodeIt u(graph); u != INVALID; ++u) {
    for (NodeIt v(graph); v != u; ++v) {
      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
      pf.runMinCut();
      BoolNodeMap cm(graph);
      ght.minCutMap(u, v, cm);
      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
      check(cm[u] != cm[v], "Wrong cut 2");
      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");

      int sum=0;
      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
        sum+=capacity[a];
      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");

      sum=0;
      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
        sum++;
      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
        sum++;
      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
    }
  }

  return 0;
}