test/gomory_hu_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 07 Aug 2013 06:29:34 +0200
changeset 982 3e711ee55d31
parent 969 7e368d9b67f7
child 983 8b2d4e5d96e4
permissions -rw-r--r--
Add explicit namespace to ignore_unused_variable_warning() usages (#294)
     1 #include <iostream>
     2 
     3 #include "test_tools.h"
     4 #include <lemon/smart_graph.h>
     5 #include <lemon/concepts/graph.h>
     6 #include <lemon/concepts/maps.h>
     7 #include <lemon/lgf_reader.h>
     8 #include <lemon/gomory_hu.h>
     9 #include <cstdlib>
    10 
    11 using namespace std;
    12 using namespace lemon;
    13 
    14 typedef SmartGraph Graph;
    15 
    16 char test_lgf[] =
    17   "@nodes\n"
    18   "label\n"
    19   "0\n"
    20   "1\n"
    21   "2\n"
    22   "3\n"
    23   "4\n"
    24   "@arcs\n"
    25   "     label capacity\n"
    26   "0 1  0     1\n"
    27   "1 2  1     1\n"
    28   "2 3  2     1\n"
    29   "0 3  4     5\n"
    30   "0 3  5     10\n"
    31   "0 3  6     7\n"
    32   "4 2  7     1\n"
    33   "@attributes\n"
    34   "source 0\n"
    35   "target 3\n";
    36   
    37 void checkGomoryHuCompile()
    38 {
    39   typedef int Value;
    40   typedef concepts::Graph Graph;
    41 
    42   typedef Graph::Node Node;
    43   typedef Graph::Edge Edge;
    44   typedef concepts::ReadMap<Edge, Value> CapMap;
    45   typedef concepts::ReadWriteMap<Node, bool> CutMap;
    46 
    47   Graph g;
    48   Node n;
    49   CapMap cap;
    50   CutMap cut;
    51   Value v;
    52   int d;
    53   ::lemon::ignore_unused_variable_warning(v,d);
    54 
    55   GomoryHu<Graph, CapMap> gh_test(g, cap);
    56   const GomoryHu<Graph, CapMap>&
    57     const_gh_test = gh_test;
    58 
    59   gh_test.run();
    60 
    61   n = const_gh_test.predNode(n);
    62   v = const_gh_test.predValue(n);
    63   d = const_gh_test.rootDist(n);
    64   v = const_gh_test.minCutValue(n, n);
    65   v = const_gh_test.minCutMap(n, n, cut);
    66 }
    67 
    68 GRAPH_TYPEDEFS(Graph);
    69 typedef Graph::EdgeMap<int> IntEdgeMap;
    70 typedef Graph::NodeMap<bool> BoolNodeMap;
    71 
    72 int cutValue(const Graph& graph, const BoolNodeMap& cut,
    73 	     const IntEdgeMap& capacity) {
    74 
    75   int sum = 0;
    76   for (EdgeIt e(graph); e != INVALID; ++e) {
    77     Node s = graph.u(e);
    78     Node t = graph.v(e);
    79 
    80     if (cut[s] != cut[t]) {
    81       sum += capacity[e];
    82     }
    83   }
    84   return sum;
    85 }
    86 
    87 
    88 int main() {
    89   Graph graph;
    90   IntEdgeMap capacity(graph);
    91 
    92   std::istringstream input(test_lgf);
    93   GraphReader<Graph>(graph, input).
    94     edgeMap("capacity", capacity).run();
    95 
    96   GomoryHu<Graph> ght(graph, capacity);
    97   ght.run();
    98 
    99   for (NodeIt u(graph); u != INVALID; ++u) {
   100     for (NodeIt v(graph); v != u; ++v) {
   101       Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
   102       pf.runMinCut();
   103       BoolNodeMap cm(graph);
   104       ght.minCutMap(u, v, cm);
   105       check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
   106       check(cm[u] != cm[v], "Wrong cut 2");
   107       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
   108 
   109       int sum=0;
   110       for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
   111         sum+=capacity[a]; 
   112       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
   113 
   114       sum=0;
   115       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
   116         sum++;
   117       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
   118         sum++;
   119       check(sum == countNodes(graph), "Problem with MinCutNodeIt");
   120     }
   121   }
   122   
   123   return 0;
   124 }