test/hao_orlin_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 16 Mar 2013 16:20:41 +0100
changeset 1070 ee9bac10f58e
parent 877 141f9c0db4a3
parent 1007 7e368d9b67f7
child 1084 8b2d4e5d96e4
permissions -rw-r--r--
Debug checking for capacity bounds in min cost flow algorithms (#454)
     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 <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   ignore_unused_variable_warning(v);
    70 
    71   HaoOrlin<Digraph, CapMap> ho_test(g, cap);
    72   const HaoOrlin<Digraph, CapMap>&
    73     const_ho_test = ho_test;
    74 
    75   ho_test.init();
    76   ho_test.init(n);
    77   ho_test.calculateOut();
    78   ho_test.calculateIn();
    79   ho_test.run();
    80   ho_test.run(n);
    81 
    82   v = const_ho_test.minCutValue();
    83   v = const_ho_test.minCutMap(cut);
    84 }
    85 
    86 template <typename Graph, typename CapMap, typename CutMap>
    87 typename CapMap::Value
    88   cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    89 {
    90   typename CapMap::Value sum = 0;
    91   for (typename Graph::ArcIt a(graph); a != INVALID; ++a) {
    92     if (cut[graph.source(a)] && !cut[graph.target(a)])
    93       sum += cap[a];
    94   }
    95   return sum;
    96 }
    97 
    98 int main() {
    99   SmartDigraph graph;
   100   SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph);
   101   SmartDigraph::NodeMap<bool> cut(graph);
   102 
   103   istringstream input(lgf);
   104   digraphReader(graph, input)
   105     .arcMap("cap1", cap1)
   106     .arcMap("cap2", cap2)
   107     .arcMap("cap3", cap3)
   108     .run();
   109 
   110   {
   111     HaoOrlin<SmartDigraph> ho(graph, cap1);
   112     ho.run();
   113     ho.minCutMap(cut);
   114 
   115     check(ho.minCutValue() == 1, "Wrong cut value");
   116     check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
   117   }
   118   {
   119     HaoOrlin<SmartDigraph> ho(graph, cap2);
   120     ho.run();
   121     ho.minCutMap(cut);
   122 
   123     check(ho.minCutValue() == 1, "Wrong cut value");
   124     check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
   125   }
   126   {
   127     HaoOrlin<SmartDigraph> ho(graph, cap3);
   128     ho.run();
   129     ho.minCutMap(cut);
   130 
   131     check(ho.minCutValue() == 1, "Wrong cut value");
   132     check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
   133   }
   134 
   135   typedef Undirector<SmartDigraph> UGraph;
   136   UGraph ugraph(graph);
   137 
   138   {
   139     HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
   140     ho.run();
   141     ho.minCutMap(cut);
   142 
   143     check(ho.minCutValue() == 2, "Wrong cut value");
   144     check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
   145   }
   146   {
   147     HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2);
   148     ho.run();
   149     ho.minCutMap(cut);
   150 
   151     check(ho.minCutValue() == 5, "Wrong cut value");
   152     check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
   153   }
   154   {
   155     HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3);
   156     ho.run();
   157     ho.minCutMap(cut);
   158 
   159     check(ho.minCutValue() == 5, "Wrong cut value");
   160     check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
   161   }
   162 
   163   return 0;
   164 }