test/gomory_hu_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 01 Apr 2009 17:17:47 +0100
changeset 563 dad9db81ade2
parent 545 e72bacfea6b7
child 596 293551ad254f
permissions -rw-r--r--
Fix in .hgignore
     1 #include <iostream>
     2 
     3 #include "test_tools.h"
     4 #include <lemon/smart_graph.h>
     5 #include <lemon/lgf_reader.h>
     6 #include <lemon/gomory_hu.h>
     7 #include <cstdlib>
     8 
     9 using namespace std;
    10 using namespace lemon;
    11 
    12 typedef SmartGraph Graph;
    13 
    14 char test_lgf[] =
    15   "@nodes\n"
    16   "label\n"
    17   "0\n"
    18   "1\n"
    19   "2\n"
    20   "3\n"
    21   "4\n"
    22   "@arcs\n"
    23   "     label capacity\n"
    24   "0 1  0     1\n"
    25   "1 2  1     1\n"
    26   "2 3  2     1\n"
    27   "0 3  4     5\n"
    28   "0 3  5     10\n"
    29   "0 3  6     7\n"
    30   "4 2  7     1\n"
    31   "@attributes\n"
    32   "source 0\n"
    33   "target 3\n";
    34   
    35 GRAPH_TYPEDEFS(Graph);
    36 typedef Graph::EdgeMap<int> IntEdgeMap;
    37 typedef Graph::NodeMap<bool> BoolNodeMap;
    38 
    39 int cutValue(const Graph& graph, const BoolNodeMap& cut,
    40 	     const IntEdgeMap& capacity) {
    41 
    42   int sum = 0;
    43   for (EdgeIt e(graph); e != INVALID; ++e) {
    44     Node s = graph.u(e);
    45     Node t = graph.v(e);
    46 
    47     if (cut[s] != cut[t]) {
    48       sum += capacity[e];
    49     }
    50   }
    51   return sum;
    52 }
    53 
    54 
    55 int main() {
    56   Graph graph;
    57   IntEdgeMap capacity(graph);
    58 
    59   std::istringstream input(test_lgf);
    60   GraphReader<Graph>(graph, input).
    61     edgeMap("capacity", capacity).run();
    62 
    63   GomoryHu<Graph> ght(graph, capacity);
    64   ght.run();
    65 
    66   for (NodeIt u(graph); u != INVALID; ++u) {
    67     for (NodeIt v(graph); v != u; ++v) {
    68       Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
    69       pf.runMinCut();
    70       BoolNodeMap cm(graph);
    71       ght.minCutMap(u, v, cm);
    72       check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
    73       check(cm[u] != cm[v], "Wrong cut 3");
    74       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
    75 
    76       int sum=0;
    77       for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
    78         sum+=capacity[a]; 
    79       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
    80 
    81       sum=0;
    82       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
    83         sum++;
    84       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
    85         sum++;
    86       check(sum == countNodes(graph), "Problem with MinCutNodeIt");
    87       
    88     }
    89   }
    90   
    91   return 0;
    92 }