test/gomory_hu_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 13 Sep 2012 11:56:19 +0200
changeset 998 7fdaa05a69a1
parent 596 293551ad254f
child 1008 d216e1c8b3fa
permissions -rw-r--r--
Merge #449 to branches >=1.2
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <iostream>
    20 
    21 #include "test_tools.h"
    22 #include <lemon/smart_graph.h>
    23 #include <lemon/concepts/graph.h>
    24 #include <lemon/concepts/maps.h>
    25 #include <lemon/lgf_reader.h>
    26 #include <lemon/gomory_hu.h>
    27 #include <cstdlib>
    28 
    29 using namespace std;
    30 using namespace lemon;
    31 
    32 typedef SmartGraph Graph;
    33 
    34 char test_lgf[] =
    35   "@nodes\n"
    36   "label\n"
    37   "0\n"
    38   "1\n"
    39   "2\n"
    40   "3\n"
    41   "4\n"
    42   "@arcs\n"
    43   "     label capacity\n"
    44   "0 1  0     1\n"
    45   "1 2  1     1\n"
    46   "2 3  2     1\n"
    47   "0 3  4     5\n"
    48   "0 3  5     10\n"
    49   "0 3  6     7\n"
    50   "4 2  7     1\n"
    51   "@attributes\n"
    52   "source 0\n"
    53   "target 3\n";
    54 
    55 void checkGomoryHuCompile()
    56 {
    57   typedef int Value;
    58   typedef concepts::Graph Graph;
    59 
    60   typedef Graph::Node Node;
    61   typedef Graph::Edge Edge;
    62   typedef concepts::ReadMap<Edge, Value> CapMap;
    63   typedef concepts::ReadWriteMap<Node, bool> CutMap;
    64 
    65   Graph g;
    66   Node n;
    67   CapMap cap;
    68   CutMap cut;
    69   Value v;
    70   int d;
    71 
    72   GomoryHu<Graph, CapMap> gh_test(g, cap);
    73   const GomoryHu<Graph, CapMap>&
    74     const_gh_test = gh_test;
    75 
    76   gh_test.run();
    77 
    78   n = const_gh_test.predNode(n);
    79   v = const_gh_test.predValue(n);
    80   d = const_gh_test.rootDist(n);
    81   v = const_gh_test.minCutValue(n, n);
    82   v = const_gh_test.minCutMap(n, n, cut);
    83 }
    84 
    85 GRAPH_TYPEDEFS(Graph);
    86 typedef Graph::EdgeMap<int> IntEdgeMap;
    87 typedef Graph::NodeMap<bool> BoolNodeMap;
    88 
    89 int cutValue(const Graph& graph, const BoolNodeMap& cut,
    90              const IntEdgeMap& capacity) {
    91 
    92   int sum = 0;
    93   for (EdgeIt e(graph); e != INVALID; ++e) {
    94     Node s = graph.u(e);
    95     Node t = graph.v(e);
    96 
    97     if (cut[s] != cut[t]) {
    98       sum += capacity[e];
    99     }
   100   }
   101   return sum;
   102 }
   103 
   104 
   105 int main() {
   106   Graph graph;
   107   IntEdgeMap capacity(graph);
   108 
   109   std::istringstream input(test_lgf);
   110   GraphReader<Graph>(graph, input).
   111     edgeMap("capacity", capacity).run();
   112 
   113   GomoryHu<Graph> ght(graph, capacity);
   114   ght.run();
   115 
   116   for (NodeIt u(graph); u != INVALID; ++u) {
   117     for (NodeIt v(graph); v != u; ++v) {
   118       Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
   119       pf.runMinCut();
   120       BoolNodeMap cm(graph);
   121       ght.minCutMap(u, v, cm);
   122       check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
   123       check(cm[u] != cm[v], "Wrong cut 2");
   124       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
   125 
   126       int sum=0;
   127       for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
   128         sum+=capacity[a];
   129       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
   130 
   131       sum=0;
   132       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
   133         sum++;
   134       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
   135         sum++;
   136       check(sum == countNodes(graph), "Problem with MinCutNodeIt");
   137     }
   138   }
   139 
   140   return 0;
   141 }