test/gomory_hu_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 06 Aug 2013 17:58:59 +0200
changeset 1082 cae19e9eeca4
parent 877 141f9c0db4a3
parent 1007 7e368d9b67f7
child 1084 8b2d4e5d96e4
permissions -rw-r--r--
Merge #463
     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   ignore_unused_variable_warning(v,d);
    72 
    73   GomoryHu<Graph, CapMap> gh_test(g, cap);
    74   const GomoryHu<Graph, CapMap>&
    75     const_gh_test = gh_test;
    76 
    77   gh_test.run();
    78 
    79   n = const_gh_test.predNode(n);
    80   v = const_gh_test.predValue(n);
    81   d = const_gh_test.rootDist(n);
    82   v = const_gh_test.minCutValue(n, n);
    83   v = const_gh_test.minCutMap(n, n, cut);
    84 }
    85 
    86 GRAPH_TYPEDEFS(Graph);
    87 typedef Graph::EdgeMap<int> IntEdgeMap;
    88 typedef Graph::NodeMap<bool> BoolNodeMap;
    89 
    90 int cutValue(const Graph& graph, const BoolNodeMap& cut,
    91              const IntEdgeMap& capacity) {
    92 
    93   int sum = 0;
    94   for (EdgeIt e(graph); e != INVALID; ++e) {
    95     Node s = graph.u(e);
    96     Node t = graph.v(e);
    97 
    98     if (cut[s] != cut[t]) {
    99       sum += capacity[e];
   100     }
   101   }
   102   return sum;
   103 }
   104 
   105 
   106 int main() {
   107   Graph graph;
   108   IntEdgeMap capacity(graph);
   109 
   110   std::istringstream input(test_lgf);
   111   GraphReader<Graph>(graph, input).
   112     edgeMap("capacity", capacity).run();
   113 
   114   GomoryHu<Graph> ght(graph, capacity);
   115   ght.run();
   116 
   117   for (NodeIt u(graph); u != INVALID; ++u) {
   118     for (NodeIt v(graph); v != u; ++v) {
   119       Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
   120       pf.runMinCut();
   121       BoolNodeMap cm(graph);
   122       ght.minCutMap(u, v, cm);
   123       check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
   124       check(cm[u] != cm[v], "Wrong cut 2");
   125       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
   126 
   127       int sum=0;
   128       for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
   129         sum+=capacity[a];
   130       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
   131 
   132       sum=0;
   133       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
   134         sum++;
   135       for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
   136         sum++;
   137       check(sum == countNodes(graph), "Problem with MinCutNodeIt");
   138     }
   139   }
   140 
   141   return 0;
   142 }