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-2013
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
checkHaoOrlinCompile()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 ::lemon::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
cutValue(const Graph & graph,const CapMap & cap,const CutMap & cut)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
main()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 }
165