[410] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
| 4 | * |
---|
[761] | 5 | * Copyright (C) 2003-2011 |
---|
[410] | 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> |
---|
[588] | 22 | #include <lemon/adaptors.h> |
---|
| 23 | #include <lemon/concepts/digraph.h> |
---|
| 24 | #include <lemon/concepts/maps.h> |
---|
| 25 | #include <lemon/lgf_reader.h> |
---|
[410] | 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" |
---|
[588] | 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; |
---|
[807] | 69 | ::lemon::ignore_unused_variable_warning(v); |
---|
[588] | 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> |
---|
[761] | 87 | typename CapMap::Value |
---|
[588] | 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 | } |
---|
[410] | 97 | |
---|
| 98 | int main() { |
---|
[588] | 99 | SmartDigraph graph; |
---|
| 100 | SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph); |
---|
| 101 | SmartDigraph::NodeMap<bool> cut(graph); |
---|
[410] | 102 | |
---|
[588] | 103 | istringstream input(lgf); |
---|
| 104 | digraphReader(graph, input) |
---|
| 105 | .arcMap("cap1", cap1) |
---|
| 106 | .arcMap("cap2", cap2) |
---|
| 107 | .arcMap("cap3", cap3) |
---|
| 108 | .run(); |
---|
[410] | 109 | |
---|
[588] | 110 | { |
---|
| 111 | HaoOrlin<SmartDigraph> ho(graph, cap1); |
---|
| 112 | ho.run(); |
---|
| 113 | ho.minCutMap(cut); |
---|
[761] | 114 | |
---|
[589] | 115 | check(ho.minCutValue() == 1, "Wrong cut value"); |
---|
| 116 | check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); |
---|
[588] | 117 | } |
---|
| 118 | { |
---|
| 119 | HaoOrlin<SmartDigraph> ho(graph, cap2); |
---|
| 120 | ho.run(); |
---|
| 121 | ho.minCutMap(cut); |
---|
[589] | 122 | |
---|
| 123 | check(ho.minCutValue() == 1, "Wrong cut value"); |
---|
| 124 | check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value"); |
---|
[588] | 125 | } |
---|
| 126 | { |
---|
| 127 | HaoOrlin<SmartDigraph> ho(graph, cap3); |
---|
| 128 | ho.run(); |
---|
| 129 | ho.minCutMap(cut); |
---|
[761] | 130 | |
---|
[589] | 131 | check(ho.minCutValue() == 1, "Wrong cut value"); |
---|
| 132 | check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); |
---|
[588] | 133 | } |
---|
[761] | 134 | |
---|
[588] | 135 | typedef Undirector<SmartDigraph> UGraph; |
---|
| 136 | UGraph ugraph(graph); |
---|
[761] | 137 | |
---|
[588] | 138 | { |
---|
| 139 | HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1); |
---|
| 140 | ho.run(); |
---|
| 141 | ho.minCutMap(cut); |
---|
[761] | 142 | |
---|
[589] | 143 | check(ho.minCutValue() == 2, "Wrong cut value"); |
---|
| 144 | check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); |
---|
[588] | 145 | } |
---|
| 146 | { |
---|
| 147 | HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2); |
---|
| 148 | ho.run(); |
---|
| 149 | ho.minCutMap(cut); |
---|
[761] | 150 | |
---|
[589] | 151 | check(ho.minCutValue() == 5, "Wrong cut value"); |
---|
| 152 | check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); |
---|
[588] | 153 | } |
---|
| 154 | { |
---|
| 155 | HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3); |
---|
| 156 | ho.run(); |
---|
| 157 | ho.minCutMap(cut); |
---|
[761] | 158 | |
---|
[588] | 159 | check(ho.minCutValue() == 5, "Wrong cut value"); |
---|
[589] | 160 | check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); |
---|
[588] | 161 | } |
---|
[410] | 162 | |
---|
| 163 | return 0; |
---|
| 164 | } |
---|