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 +}