/* -*- 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;

}