test/gomory_hu_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 24 Apr 2009 12:12:14 +0100
changeset 618 b95898314e09
parent 546 d6b40ebb2617
child 877 141f9c0db4a3
child 1007 7e368d9b67f7
permissions -rw-r--r--
Merge
     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 
    54   GomoryHu<Graph, CapMap> gh_test(g, cap);
    55   const GomoryHu<Graph, CapMap>&
    56     const_gh_test = gh_test;
    57 
    58   gh_test.run();
    59 
    60   n = const_gh_test.predNode(n);
    61   v = const_gh_test.predValue(n);
    62   d = const_gh_test.rootDist(n);
    63   v = const_gh_test.minCutValue(n, n);
    64   v = const_gh_test.minCutMap(n, n, cut);
    65 }
    66 
    67 GRAPH_TYPEDEFS(Graph);
    68 typedef Graph::EdgeMap<int> IntEdgeMap;
    69 typedef Graph::NodeMap<bool> BoolNodeMap;
    70 
    71 int cutValue(const Graph& graph, const BoolNodeMap& cut,
    72 	     const IntEdgeMap& capacity) {
    73 
    74   int sum = 0;
    75   for (EdgeIt e(graph); e != INVALID; ++e) {
    76     Node s = graph.u(e);
    77     Node t = graph.v(e);
    78 
    79     if (cut[s] != cut[t]) {
    80       sum += capacity[e];
    81     }
    82   }
    83   return sum;
    84 }
    85 
    86 
    87 int main() {
    88   Graph graph;
    89   IntEdgeMap capacity(graph);
    90 
    91   std::istringstream input(test_lgf);
    92   GraphReader<Graph>(graph, input).
    93     edgeMap("capacity", capacity).run();
    94 
    95   GomoryHu<Graph> ght(graph, capacity);
    96   ght.run();
    97 
    98   for (NodeIt u(graph); u != INVALID; ++u) {
    99     for (NodeIt v(graph); v != u; ++v) {
   100       Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
   101       pf.runMinCut();
   102       BoolNodeMap cm(graph);
   103       ght.minCutMap(u, v, cm);
   104       check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
   105       check(cm[u] != cm[v], "Wrong cut 2");
   106       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
   107 
   108       int sum=0;
   109       for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
   110         sum+=capacity[a]; 
   111       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
   112 
   113       sum=0;
   114       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
   115         sum++;
   116       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
   117         sum++;
   118       check(sum == countNodes(graph), "Problem with MinCutNodeIt");
   119     }
   120   }
   121   
   122   return 0;
   123 }