1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/hao_orlin_test.cc	Thu Dec 10 17:05:35 2009 +0100
     1.3 @@ -0,0 +1,163 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2009
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#include <sstream>
    1.23 +
    1.24 +#include <lemon/smart_graph.h>
    1.25 +#include <lemon/adaptors.h>
    1.26 +#include <lemon/concepts/digraph.h>
    1.27 +#include <lemon/concepts/maps.h>
    1.28 +#include <lemon/lgf_reader.h>
    1.29 +#include <lemon/hao_orlin.h>
    1.30 +
    1.31 +#include "test_tools.h"
    1.32 +
    1.33 +using namespace lemon;
    1.34 +using namespace std;
    1.35 +
    1.36 +const std::string lgf =
    1.37 +  "@nodes\n"
    1.38 +  "label\n"
    1.39 +  "0\n"
    1.40 +  "1\n"
    1.41 +  "2\n"
    1.42 +  "3\n"
    1.43 +  "4\n"
    1.44 +  "5\n"
    1.45 +  "@edges\n"
    1.46 +  "     cap1 cap2 cap3\n"
    1.47 +  "0 1  1    1    1   \n"
    1.48 +  "0 2  2    2    4   \n"
    1.49 +  "1 2  4    4    4   \n"
    1.50 +  "3 4  1    1    1   \n"
    1.51 +  "3 5  2    2    4   \n"
    1.52 +  "4 5  4    4    4   \n"
    1.53 +  "5 4  4    4    4   \n"
    1.54 +  "2 3  1    6    6   \n"
    1.55 +  "4 0  1    6    6   \n";
    1.56 +
    1.57 +void checkHaoOrlinCompile()
    1.58 +{
    1.59 +  typedef int Value;
    1.60 +  typedef concepts::Digraph Digraph;
    1.61 +
    1.62 +  typedef Digraph::Node Node;
    1.63 +  typedef Digraph::Arc Arc;
    1.64 +  typedef concepts::ReadMap<Arc, Value> CapMap;
    1.65 +  typedef concepts::WriteMap<Node, bool> CutMap;
    1.66 +
    1.67 +  Digraph g;
    1.68 +  Node n;
    1.69 +  CapMap cap;
    1.70 +  CutMap cut;
    1.71 +  Value v;
    1.72 +
    1.73 +  HaoOrlin<Digraph, CapMap> ho_test(g, cap);
    1.74 +  const HaoOrlin<Digraph, CapMap>&
    1.75 +    const_ho_test = ho_test;
    1.76 +
    1.77 +  ho_test.init();
    1.78 +  ho_test.init(n);
    1.79 +  ho_test.calculateOut();
    1.80 +  ho_test.calculateIn();
    1.81 +  ho_test.run();
    1.82 +  ho_test.run(n);
    1.83 +
    1.84 +  v = const_ho_test.minCutValue();
    1.85 +  v = const_ho_test.minCutMap(cut);
    1.86 +}
    1.87 +
    1.88 +template <typename Graph, typename CapMap, typename CutMap>
    1.89 +typename CapMap::Value 
    1.90 +  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    1.91 +{
    1.92 +  typename CapMap::Value sum = 0;
    1.93 +  for (typename Graph::ArcIt a(graph); a != INVALID; ++a) {
    1.94 +    if (cut[graph.source(a)] && !cut[graph.target(a)])
    1.95 +      sum += cap[a];
    1.96 +  }
    1.97 +  return sum;
    1.98 +}
    1.99 +
   1.100 +int main() {
   1.101 +  SmartDigraph graph;
   1.102 +  SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph);
   1.103 +  SmartDigraph::NodeMap<bool> cut(graph);
   1.104 +
   1.105 +  istringstream input(lgf);
   1.106 +  digraphReader(graph, input)
   1.107 +    .arcMap("cap1", cap1)
   1.108 +    .arcMap("cap2", cap2)
   1.109 +    .arcMap("cap3", cap3)
   1.110 +    .run();
   1.111 +
   1.112 +  {
   1.113 +    HaoOrlin<SmartDigraph> ho(graph, cap1);
   1.114 +    ho.run();
   1.115 +    ho.minCutMap(cut);
   1.116 +    
   1.117 +    check(ho.minCutValue() == 1, "Wrong cut value");
   1.118 +    check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
   1.119 +  }
   1.120 +  {
   1.121 +    HaoOrlin<SmartDigraph> ho(graph, cap2);
   1.122 +    ho.run();
   1.123 +    ho.minCutMap(cut);
   1.124 +
   1.125 +    check(ho.minCutValue() == 1, "Wrong cut value");
   1.126 +    check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
   1.127 +  }
   1.128 +  {
   1.129 +    HaoOrlin<SmartDigraph> ho(graph, cap3);
   1.130 +    ho.run();
   1.131 +    ho.minCutMap(cut);
   1.132 +    
   1.133 +    check(ho.minCutValue() == 1, "Wrong cut value");
   1.134 +    check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
   1.135 +  }
   1.136 +  
   1.137 +  typedef Undirector<SmartDigraph> UGraph;
   1.138 +  UGraph ugraph(graph);
   1.139 +  
   1.140 +  {
   1.141 +    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
   1.142 +    ho.run();
   1.143 +    ho.minCutMap(cut);
   1.144 +    
   1.145 +    check(ho.minCutValue() == 2, "Wrong cut value");
   1.146 +    check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
   1.147 +  }
   1.148 +  {
   1.149 +    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2);
   1.150 +    ho.run();
   1.151 +    ho.minCutMap(cut);
   1.152 +    
   1.153 +    check(ho.minCutValue() == 5, "Wrong cut value");
   1.154 +    check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
   1.155 +  }
   1.156 +  {
   1.157 +    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3);
   1.158 +    ho.run();
   1.159 +    ho.minCutMap(cut);
   1.160 +    
   1.161 +    check(ho.minCutValue() == 5, "Wrong cut value");
   1.162 +    check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
   1.163 +  }
   1.164 +
   1.165 +  return 0;
   1.166 +}