test/hao_orlin_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 13 Nov 2009 00:24:39 +0100
changeset 819 d93490b861e9
parent 596 293551ad254f
child 877 141f9c0db4a3
child 969 7e368d9b67f7
permissions -rw-r--r--
Adds tests for the new MCF algorithms (#180)
     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-2009
     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 <sstream>
    20 
    21 #include <lemon/smart_graph.h>
    22 #include <lemon/adaptors.h>
    23 #include <lemon/concepts/digraph.h>
    24 #include <lemon/concepts/maps.h>
    25 #include <lemon/lgf_reader.h>
    26 #include <lemon/hao_orlin.h>
    27 
    28 #include "test_tools.h"
    29 
    30 using namespace lemon;
    31 using namespace std;
    32 
    33 const std::string lgf =
    34   "@nodes\n"
    35   "label\n"
    36   "0\n"
    37   "1\n"
    38   "2\n"
    39   "3\n"
    40   "4\n"
    41   "5\n"
    42   "@edges\n"
    43   "     cap1 cap2 cap3\n"
    44   "0 1  1    1    1   \n"
    45   "0 2  2    2    4   \n"
    46   "1 2  4    4    4   \n"
    47   "3 4  1    1    1   \n"
    48   "3 5  2    2    4   \n"
    49   "4 5  4    4    4   \n"
    50   "5 4  4    4    4   \n"
    51   "2 3  1    6    6   \n"
    52   "4 0  1    6    6   \n";
    53 
    54 void checkHaoOrlinCompile()
    55 {
    56   typedef int Value;
    57   typedef concepts::Digraph Digraph;
    58 
    59   typedef Digraph::Node Node;
    60   typedef Digraph::Arc Arc;
    61   typedef concepts::ReadMap<Arc, Value> CapMap;
    62   typedef concepts::WriteMap<Node, bool> CutMap;
    63 
    64   Digraph g;
    65   Node n;
    66   CapMap cap;
    67   CutMap cut;
    68   Value v;
    69 
    70   HaoOrlin<Digraph, CapMap> ho_test(g, cap);
    71   const HaoOrlin<Digraph, CapMap>&
    72     const_ho_test = ho_test;
    73 
    74   ho_test.init();
    75   ho_test.init(n);
    76   ho_test.calculateOut();
    77   ho_test.calculateIn();
    78   ho_test.run();
    79   ho_test.run(n);
    80 
    81   v = const_ho_test.minCutValue();
    82   v = const_ho_test.minCutMap(cut);
    83 }
    84 
    85 template <typename Graph, typename CapMap, typename CutMap>
    86 typename CapMap::Value 
    87   cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    88 {
    89   typename CapMap::Value sum = 0;
    90   for (typename Graph::ArcIt a(graph); a != INVALID; ++a) {
    91     if (cut[graph.source(a)] && !cut[graph.target(a)])
    92       sum += cap[a];
    93   }
    94   return sum;
    95 }
    96 
    97 int main() {
    98   SmartDigraph graph;
    99   SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph);
   100   SmartDigraph::NodeMap<bool> cut(graph);
   101 
   102   istringstream input(lgf);
   103   digraphReader(graph, input)
   104     .arcMap("cap1", cap1)
   105     .arcMap("cap2", cap2)
   106     .arcMap("cap3", cap3)
   107     .run();
   108 
   109   {
   110     HaoOrlin<SmartDigraph> ho(graph, cap1);
   111     ho.run();
   112     ho.minCutMap(cut);
   113     
   114     check(ho.minCutValue() == 1, "Wrong cut value");
   115     check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
   116   }
   117   {
   118     HaoOrlin<SmartDigraph> ho(graph, cap2);
   119     ho.run();
   120     ho.minCutMap(cut);
   121 
   122     check(ho.minCutValue() == 1, "Wrong cut value");
   123     check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
   124   }
   125   {
   126     HaoOrlin<SmartDigraph> ho(graph, cap3);
   127     ho.run();
   128     ho.minCutMap(cut);
   129     
   130     check(ho.minCutValue() == 1, "Wrong cut value");
   131     check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
   132   }
   133   
   134   typedef Undirector<SmartDigraph> UGraph;
   135   UGraph ugraph(graph);
   136   
   137   {
   138     HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
   139     ho.run();
   140     ho.minCutMap(cut);
   141     
   142     check(ho.minCutValue() == 2, "Wrong cut value");
   143     check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
   144   }
   145   {
   146     HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2);
   147     ho.run();
   148     ho.minCutMap(cut);
   149     
   150     check(ho.minCutValue() == 5, "Wrong cut value");
   151     check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
   152   }
   153   {
   154     HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3);
   155     ho.run();
   156     ho.minCutMap(cut);
   157     
   158     check(ho.minCutValue() == 5, "Wrong cut value");
   159     check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
   160   }
   161 
   162   return 0;
   163 }