deba@490
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
deba@490
|
2 |
*
|
deba@490
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
deba@490
|
4 |
*
|
deba@490
|
5 |
* Copyright (C) 2003-2008
|
deba@490
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@490
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@490
|
8 |
*
|
deba@490
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@490
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@490
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@490
|
12 |
*
|
deba@490
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@490
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@490
|
15 |
* purpose.
|
deba@490
|
16 |
*
|
deba@490
|
17 |
*/
|
deba@490
|
18 |
|
deba@490
|
19 |
#ifndef LEMON_MIN_COST_ARBORESCENCE_H
|
deba@490
|
20 |
#define LEMON_MIN_COST_ARBORESCENCE_H
|
deba@490
|
21 |
|
deba@490
|
22 |
///\ingroup spantree
|
deba@490
|
23 |
///\file
|
deba@490
|
24 |
///\brief Minimum Cost Arborescence algorithm.
|
deba@490
|
25 |
|
deba@490
|
26 |
#include <vector>
|
deba@490
|
27 |
|
deba@490
|
28 |
#include <lemon/list_graph.h>
|
deba@490
|
29 |
#include <lemon/bin_heap.h>
|
deba@490
|
30 |
#include <lemon/assert.h>
|
deba@490
|
31 |
|
deba@490
|
32 |
namespace lemon {
|
deba@490
|
33 |
|
deba@490
|
34 |
|
deba@490
|
35 |
/// \brief Default traits class for MinCostArborescence class.
|
deba@490
|
36 |
///
|
deba@490
|
37 |
/// Default traits class for MinCostArborescence class.
|
kpeter@559
|
38 |
/// \param GR Digraph type.
|
kpeter@559
|
39 |
/// \param CM Type of cost map.
|
kpeter@559
|
40 |
template <class GR, class CM>
|
deba@490
|
41 |
struct MinCostArborescenceDefaultTraits{
|
deba@490
|
42 |
|
deba@490
|
43 |
/// \brief The digraph type the algorithm runs on.
|
kpeter@559
|
44 |
typedef GR Digraph;
|
deba@490
|
45 |
|
deba@490
|
46 |
/// \brief The type of the map that stores the arc costs.
|
deba@490
|
47 |
///
|
deba@490
|
48 |
/// The type of the map that stores the arc costs.
|
deba@490
|
49 |
/// It must meet the \ref concepts::ReadMap "ReadMap" concept.
|
kpeter@559
|
50 |
typedef CM CostMap;
|
deba@490
|
51 |
|
deba@490
|
52 |
/// \brief The value type of the costs.
|
deba@490
|
53 |
///
|
deba@490
|
54 |
/// The value type of the costs.
|
deba@490
|
55 |
typedef typename CostMap::Value Value;
|
deba@490
|
56 |
|
deba@490
|
57 |
/// \brief The type of the map that stores which arcs are in the
|
deba@490
|
58 |
/// arborescence.
|
deba@490
|
59 |
///
|
deba@490
|
60 |
/// The type of the map that stores which arcs are in the
|
deba@490
|
61 |
/// arborescence. It must meet the \ref concepts::WriteMap
|
deba@490
|
62 |
/// "WriteMap" concept. Initially it will be set to false on each
|
deba@490
|
63 |
/// arc. After it will set all arborescence arcs once.
|
deba@490
|
64 |
typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
|
deba@490
|
65 |
|
kpeter@559
|
66 |
/// \brief Instantiates a \c ArborescenceMap.
|
deba@490
|
67 |
///
|
kpeter@559
|
68 |
/// This function instantiates a \c ArborescenceMap.
|
deba@490
|
69 |
/// \param digraph is the graph, to which we would like to
|
kpeter@559
|
70 |
/// calculate the \c ArborescenceMap.
|
deba@490
|
71 |
static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
|
deba@490
|
72 |
return new ArborescenceMap(digraph);
|
deba@490
|
73 |
}
|
deba@490
|
74 |
|
kpeter@559
|
75 |
/// \brief The type of the \c PredMap
|
deba@490
|
76 |
///
|
kpeter@559
|
77 |
/// The type of the \c PredMap. It is a node map with an arc value type.
|
deba@490
|
78 |
typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
|
deba@490
|
79 |
|
kpeter@559
|
80 |
/// \brief Instantiates a \c PredMap.
|
deba@490
|
81 |
///
|
kpeter@559
|
82 |
/// This function instantiates a \c PredMap.
|
kpeter@559
|
83 |
/// \param digraph The digraph to which we would like to define the
|
kpeter@559
|
84 |
/// \c PredMap.
|
deba@490
|
85 |
static PredMap *createPredMap(const Digraph &digraph){
|
deba@490
|
86 |
return new PredMap(digraph);
|
deba@490
|
87 |
}
|
deba@490
|
88 |
|
deba@490
|
89 |
};
|
deba@490
|
90 |
|
deba@490
|
91 |
/// \ingroup spantree
|
deba@490
|
92 |
///
|
deba@490
|
93 |
/// \brief %MinCostArborescence algorithm class.
|
deba@490
|
94 |
///
|
deba@490
|
95 |
/// This class provides an efficient implementation of
|
deba@490
|
96 |
/// %MinCostArborescence algorithm. The arborescence is a tree
|
deba@490
|
97 |
/// which is directed from a given source node of the digraph. One or
|
deba@490
|
98 |
/// more sources should be given for the algorithm and it will calculate
|
deba@490
|
99 |
/// the minimum cost subgraph which are union of arborescences with the
|
deba@490
|
100 |
/// given sources and spans all the nodes which are reachable from the
|
kpeter@559
|
101 |
/// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
|
deba@490
|
102 |
///
|
deba@490
|
103 |
/// The algorithm provides also an optimal dual solution, therefore
|
deba@490
|
104 |
/// the optimality of the solution can be checked.
|
deba@490
|
105 |
///
|
kpeter@559
|
106 |
/// \param GR The digraph type the algorithm runs on. The default value
|
deba@490
|
107 |
/// is \ref ListDigraph.
|
kpeter@559
|
108 |
/// \param CM This read-only ArcMap determines the costs of the
|
deba@490
|
109 |
/// arcs. It is read once for each arc, so the map may involve in
|
deba@490
|
110 |
/// relatively time consuming process to compute the arc cost if
|
deba@490
|
111 |
/// it is necessary. The default map type is \ref
|
deba@490
|
112 |
/// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
|
kpeter@559
|
113 |
/// \param TR Traits class to set various data types used
|
deba@490
|
114 |
/// by the algorithm. The default traits class is
|
deba@490
|
115 |
/// \ref MinCostArborescenceDefaultTraits
|
kpeter@559
|
116 |
/// "MinCostArborescenceDefaultTraits<GR, CM>". See \ref
|
deba@490
|
117 |
/// MinCostArborescenceDefaultTraits for the documentation of a
|
deba@490
|
118 |
/// MinCostArborescence traits class.
|
deba@490
|
119 |
#ifndef DOXYGEN
|
kpeter@559
|
120 |
template <typename GR = ListDigraph,
|
kpeter@559
|
121 |
typename CM = typename GR::template ArcMap<int>,
|
kpeter@559
|
122 |
typename TR =
|
kpeter@559
|
123 |
MinCostArborescenceDefaultTraits<GR, CM> >
|
deba@490
|
124 |
#else
|
kpeter@559
|
125 |
template <typename GR, typename CM, typedef TR>
|
deba@490
|
126 |
#endif
|
deba@490
|
127 |
class MinCostArborescence {
|
deba@490
|
128 |
public:
|
deba@490
|
129 |
|
deba@490
|
130 |
/// The traits.
|
kpeter@559
|
131 |
typedef TR Traits;
|
deba@490
|
132 |
/// The type of the underlying digraph.
|
deba@490
|
133 |
typedef typename Traits::Digraph Digraph;
|
deba@490
|
134 |
/// The type of the map that stores the arc costs.
|
deba@490
|
135 |
typedef typename Traits::CostMap CostMap;
|
deba@490
|
136 |
///The type of the costs of the arcs.
|
deba@490
|
137 |
typedef typename Traits::Value Value;
|
deba@490
|
138 |
///The type of the predecessor map.
|
deba@490
|
139 |
typedef typename Traits::PredMap PredMap;
|
deba@490
|
140 |
///The type of the map that stores which arcs are in the arborescence.
|
deba@490
|
141 |
typedef typename Traits::ArborescenceMap ArborescenceMap;
|
deba@490
|
142 |
|
deba@490
|
143 |
typedef MinCostArborescence Create;
|
deba@490
|
144 |
|
deba@490
|
145 |
private:
|
deba@490
|
146 |
|
deba@490
|
147 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
|
deba@490
|
148 |
|
deba@490
|
149 |
struct CostArc {
|
deba@490
|
150 |
|
deba@490
|
151 |
Arc arc;
|
deba@490
|
152 |
Value value;
|
deba@490
|
153 |
|
deba@490
|
154 |
CostArc() {}
|
deba@490
|
155 |
CostArc(Arc _arc, Value _value) : arc(_arc), value(_value) {}
|
deba@490
|
156 |
|
deba@490
|
157 |
};
|
deba@490
|
158 |
|
deba@490
|
159 |
const Digraph *_digraph;
|
deba@490
|
160 |
const CostMap *_cost;
|
deba@490
|
161 |
|
deba@490
|
162 |
PredMap *_pred;
|
deba@490
|
163 |
bool local_pred;
|
deba@490
|
164 |
|
deba@490
|
165 |
ArborescenceMap *_arborescence;
|
deba@490
|
166 |
bool local_arborescence;
|
deba@490
|
167 |
|
deba@490
|
168 |
typedef typename Digraph::template ArcMap<int> ArcOrder;
|
deba@490
|
169 |
ArcOrder *_arc_order;
|
deba@490
|
170 |
|
deba@490
|
171 |
typedef typename Digraph::template NodeMap<int> NodeOrder;
|
deba@490
|
172 |
NodeOrder *_node_order;
|
deba@490
|
173 |
|
deba@490
|
174 |
typedef typename Digraph::template NodeMap<CostArc> CostArcMap;
|
deba@490
|
175 |
CostArcMap *_cost_arcs;
|
deba@490
|
176 |
|
deba@490
|
177 |
struct StackLevel {
|
deba@490
|
178 |
|
deba@490
|
179 |
std::vector<CostArc> arcs;
|
deba@490
|
180 |
int node_level;
|
deba@490
|
181 |
|
deba@490
|
182 |
};
|
deba@490
|
183 |
|
deba@490
|
184 |
std::vector<StackLevel> level_stack;
|
deba@490
|
185 |
std::vector<Node> queue;
|
deba@490
|
186 |
|
deba@490
|
187 |
typedef std::vector<typename Digraph::Node> DualNodeList;
|
deba@490
|
188 |
|
deba@490
|
189 |
DualNodeList _dual_node_list;
|
deba@490
|
190 |
|
deba@490
|
191 |
struct DualVariable {
|
deba@490
|
192 |
int begin, end;
|
deba@490
|
193 |
Value value;
|
deba@490
|
194 |
|
deba@490
|
195 |
DualVariable(int _begin, int _end, Value _value)
|
deba@490
|
196 |
: begin(_begin), end(_end), value(_value) {}
|
deba@490
|
197 |
|
deba@490
|
198 |
};
|
deba@490
|
199 |
|
deba@490
|
200 |
typedef std::vector<DualVariable> DualVariables;
|
deba@490
|
201 |
|
deba@490
|
202 |
DualVariables _dual_variables;
|
deba@490
|
203 |
|
deba@490
|
204 |
typedef typename Digraph::template NodeMap<int> HeapCrossRef;
|
deba@490
|
205 |
|
deba@490
|
206 |
HeapCrossRef *_heap_cross_ref;
|
deba@490
|
207 |
|
deba@490
|
208 |
typedef BinHeap<int, HeapCrossRef> Heap;
|
deba@490
|
209 |
|
deba@490
|
210 |
Heap *_heap;
|
deba@490
|
211 |
|
deba@490
|
212 |
protected:
|
deba@490
|
213 |
|
deba@490
|
214 |
MinCostArborescence() {}
|
deba@490
|
215 |
|
deba@490
|
216 |
private:
|
deba@490
|
217 |
|
deba@490
|
218 |
void createStructures() {
|
deba@490
|
219 |
if (!_pred) {
|
deba@490
|
220 |
local_pred = true;
|
deba@490
|
221 |
_pred = Traits::createPredMap(*_digraph);
|
deba@490
|
222 |
}
|
deba@490
|
223 |
if (!_arborescence) {
|
deba@490
|
224 |
local_arborescence = true;
|
deba@490
|
225 |
_arborescence = Traits::createArborescenceMap(*_digraph);
|
deba@490
|
226 |
}
|
deba@490
|
227 |
if (!_arc_order) {
|
deba@490
|
228 |
_arc_order = new ArcOrder(*_digraph);
|
deba@490
|
229 |
}
|
deba@490
|
230 |
if (!_node_order) {
|
deba@490
|
231 |
_node_order = new NodeOrder(*_digraph);
|
deba@490
|
232 |
}
|
deba@490
|
233 |
if (!_cost_arcs) {
|
deba@490
|
234 |
_cost_arcs = new CostArcMap(*_digraph);
|
deba@490
|
235 |
}
|
deba@490
|
236 |
if (!_heap_cross_ref) {
|
deba@490
|
237 |
_heap_cross_ref = new HeapCrossRef(*_digraph, -1);
|
deba@490
|
238 |
}
|
deba@490
|
239 |
if (!_heap) {
|
deba@490
|
240 |
_heap = new Heap(*_heap_cross_ref);
|
deba@490
|
241 |
}
|
deba@490
|
242 |
}
|
deba@490
|
243 |
|
deba@490
|
244 |
void destroyStructures() {
|
deba@490
|
245 |
if (local_arborescence) {
|
deba@490
|
246 |
delete _arborescence;
|
deba@490
|
247 |
}
|
deba@490
|
248 |
if (local_pred) {
|
deba@490
|
249 |
delete _pred;
|
deba@490
|
250 |
}
|
deba@490
|
251 |
if (_arc_order) {
|
deba@490
|
252 |
delete _arc_order;
|
deba@490
|
253 |
}
|
deba@490
|
254 |
if (_node_order) {
|
deba@490
|
255 |
delete _node_order;
|
deba@490
|
256 |
}
|
deba@490
|
257 |
if (_cost_arcs) {
|
deba@490
|
258 |
delete _cost_arcs;
|
deba@490
|
259 |
}
|
deba@490
|
260 |
if (_heap) {
|
deba@490
|
261 |
delete _heap;
|
deba@490
|
262 |
}
|
deba@490
|
263 |
if (_heap_cross_ref) {
|
deba@490
|
264 |
delete _heap_cross_ref;
|
deba@490
|
265 |
}
|
deba@490
|
266 |
}
|
deba@490
|
267 |
|
deba@490
|
268 |
Arc prepare(Node node) {
|
deba@490
|
269 |
std::vector<Node> nodes;
|
deba@490
|
270 |
(*_node_order)[node] = _dual_node_list.size();
|
deba@490
|
271 |
StackLevel level;
|
deba@490
|
272 |
level.node_level = _dual_node_list.size();
|
deba@490
|
273 |
_dual_node_list.push_back(node);
|
deba@490
|
274 |
for (InArcIt it(*_digraph, node); it != INVALID; ++it) {
|
deba@490
|
275 |
Arc arc = it;
|
deba@490
|
276 |
Node source = _digraph->source(arc);
|
deba@490
|
277 |
Value value = (*_cost)[it];
|
deba@490
|
278 |
if (source == node || (*_node_order)[source] == -3) continue;
|
deba@490
|
279 |
if ((*_cost_arcs)[source].arc == INVALID) {
|
deba@490
|
280 |
(*_cost_arcs)[source].arc = arc;
|
deba@490
|
281 |
(*_cost_arcs)[source].value = value;
|
deba@490
|
282 |
nodes.push_back(source);
|
deba@490
|
283 |
} else {
|
deba@490
|
284 |
if ((*_cost_arcs)[source].value > value) {
|
deba@490
|
285 |
(*_cost_arcs)[source].arc = arc;
|
deba@490
|
286 |
(*_cost_arcs)[source].value = value;
|
deba@490
|
287 |
}
|
deba@490
|
288 |
}
|
deba@490
|
289 |
}
|
deba@490
|
290 |
CostArc minimum = (*_cost_arcs)[nodes[0]];
|
deba@490
|
291 |
for (int i = 1; i < int(nodes.size()); ++i) {
|
deba@490
|
292 |
if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
|
deba@490
|
293 |
minimum = (*_cost_arcs)[nodes[i]];
|
deba@490
|
294 |
}
|
deba@490
|
295 |
}
|
kpeter@581
|
296 |
(*_arc_order)[minimum.arc] = _dual_variables.size();
|
deba@490
|
297 |
DualVariable var(_dual_node_list.size() - 1,
|
deba@490
|
298 |
_dual_node_list.size(), minimum.value);
|
deba@490
|
299 |
_dual_variables.push_back(var);
|
deba@490
|
300 |
for (int i = 0; i < int(nodes.size()); ++i) {
|
deba@490
|
301 |
(*_cost_arcs)[nodes[i]].value -= minimum.value;
|
deba@490
|
302 |
level.arcs.push_back((*_cost_arcs)[nodes[i]]);
|
deba@490
|
303 |
(*_cost_arcs)[nodes[i]].arc = INVALID;
|
deba@490
|
304 |
}
|
deba@490
|
305 |
level_stack.push_back(level);
|
deba@490
|
306 |
return minimum.arc;
|
deba@490
|
307 |
}
|
deba@490
|
308 |
|
deba@490
|
309 |
Arc contract(Node node) {
|
deba@490
|
310 |
int node_bottom = bottom(node);
|
deba@490
|
311 |
std::vector<Node> nodes;
|
deba@490
|
312 |
while (!level_stack.empty() &&
|
deba@490
|
313 |
level_stack.back().node_level >= node_bottom) {
|
deba@490
|
314 |
for (int i = 0; i < int(level_stack.back().arcs.size()); ++i) {
|
deba@490
|
315 |
Arc arc = level_stack.back().arcs[i].arc;
|
deba@490
|
316 |
Node source = _digraph->source(arc);
|
deba@490
|
317 |
Value value = level_stack.back().arcs[i].value;
|
deba@490
|
318 |
if ((*_node_order)[source] >= node_bottom) continue;
|
deba@490
|
319 |
if ((*_cost_arcs)[source].arc == INVALID) {
|
deba@490
|
320 |
(*_cost_arcs)[source].arc = arc;
|
deba@490
|
321 |
(*_cost_arcs)[source].value = value;
|
deba@490
|
322 |
nodes.push_back(source);
|
deba@490
|
323 |
} else {
|
deba@490
|
324 |
if ((*_cost_arcs)[source].value > value) {
|
deba@490
|
325 |
(*_cost_arcs)[source].arc = arc;
|
deba@490
|
326 |
(*_cost_arcs)[source].value = value;
|
deba@490
|
327 |
}
|
deba@490
|
328 |
}
|
deba@490
|
329 |
}
|
deba@490
|
330 |
level_stack.pop_back();
|
deba@490
|
331 |
}
|
deba@490
|
332 |
CostArc minimum = (*_cost_arcs)[nodes[0]];
|
deba@490
|
333 |
for (int i = 1; i < int(nodes.size()); ++i) {
|
deba@490
|
334 |
if ((*_cost_arcs)[nodes[i]].value < minimum.value) {
|
deba@490
|
335 |
minimum = (*_cost_arcs)[nodes[i]];
|
deba@490
|
336 |
}
|
deba@490
|
337 |
}
|
kpeter@581
|
338 |
(*_arc_order)[minimum.arc] = _dual_variables.size();
|
deba@490
|
339 |
DualVariable var(node_bottom, _dual_node_list.size(), minimum.value);
|
deba@490
|
340 |
_dual_variables.push_back(var);
|
deba@490
|
341 |
StackLevel level;
|
deba@490
|
342 |
level.node_level = node_bottom;
|
deba@490
|
343 |
for (int i = 0; i < int(nodes.size()); ++i) {
|
deba@490
|
344 |
(*_cost_arcs)[nodes[i]].value -= minimum.value;
|
deba@490
|
345 |
level.arcs.push_back((*_cost_arcs)[nodes[i]]);
|
deba@490
|
346 |
(*_cost_arcs)[nodes[i]].arc = INVALID;
|
deba@490
|
347 |
}
|
deba@490
|
348 |
level_stack.push_back(level);
|
deba@490
|
349 |
return minimum.arc;
|
deba@490
|
350 |
}
|
deba@490
|
351 |
|
deba@490
|
352 |
int bottom(Node node) {
|
deba@490
|
353 |
int k = level_stack.size() - 1;
|
deba@490
|
354 |
while (level_stack[k].node_level > (*_node_order)[node]) {
|
deba@490
|
355 |
--k;
|
deba@490
|
356 |
}
|
deba@490
|
357 |
return level_stack[k].node_level;
|
deba@490
|
358 |
}
|
deba@490
|
359 |
|
deba@490
|
360 |
void finalize(Arc arc) {
|
deba@490
|
361 |
Node node = _digraph->target(arc);
|
deba@490
|
362 |
_heap->push(node, (*_arc_order)[arc]);
|
deba@490
|
363 |
_pred->set(node, arc);
|
deba@490
|
364 |
while (!_heap->empty()) {
|
deba@490
|
365 |
Node source = _heap->top();
|
deba@490
|
366 |
_heap->pop();
|
kpeter@581
|
367 |
(*_node_order)[source] = -1;
|
deba@490
|
368 |
for (OutArcIt it(*_digraph, source); it != INVALID; ++it) {
|
deba@490
|
369 |
if ((*_arc_order)[it] < 0) continue;
|
deba@490
|
370 |
Node target = _digraph->target(it);
|
deba@490
|
371 |
switch(_heap->state(target)) {
|
deba@490
|
372 |
case Heap::PRE_HEAP:
|
deba@490
|
373 |
_heap->push(target, (*_arc_order)[it]);
|
deba@490
|
374 |
_pred->set(target, it);
|
deba@490
|
375 |
break;
|
deba@490
|
376 |
case Heap::IN_HEAP:
|
deba@490
|
377 |
if ((*_arc_order)[it] < (*_heap)[target]) {
|
deba@490
|
378 |
_heap->decrease(target, (*_arc_order)[it]);
|
deba@490
|
379 |
_pred->set(target, it);
|
deba@490
|
380 |
}
|
deba@490
|
381 |
break;
|
deba@490
|
382 |
case Heap::POST_HEAP:
|
deba@490
|
383 |
break;
|
deba@490
|
384 |
}
|
deba@490
|
385 |
}
|
deba@490
|
386 |
_arborescence->set((*_pred)[source], true);
|
deba@490
|
387 |
}
|
deba@490
|
388 |
}
|
deba@490
|
389 |
|
deba@490
|
390 |
|
deba@490
|
391 |
public:
|
deba@490
|
392 |
|
deba@490
|
393 |
/// \name Named template parameters
|
deba@490
|
394 |
|
deba@490
|
395 |
/// @{
|
deba@490
|
396 |
|
deba@490
|
397 |
template <class T>
|
deba@490
|
398 |
struct DefArborescenceMapTraits : public Traits {
|
deba@490
|
399 |
typedef T ArborescenceMap;
|
deba@490
|
400 |
static ArborescenceMap *createArborescenceMap(const Digraph &)
|
deba@490
|
401 |
{
|
deba@490
|
402 |
LEMON_ASSERT(false, "ArborescenceMap is not initialized");
|
deba@490
|
403 |
return 0; // ignore warnings
|
deba@490
|
404 |
}
|
deba@490
|
405 |
};
|
deba@490
|
406 |
|
deba@490
|
407 |
/// \brief \ref named-templ-param "Named parameter" for
|
deba@490
|
408 |
/// setting ArborescenceMap type
|
deba@490
|
409 |
///
|
deba@490
|
410 |
/// \ref named-templ-param "Named parameter" for setting
|
deba@490
|
411 |
/// ArborescenceMap type
|
deba@490
|
412 |
template <class T>
|
deba@490
|
413 |
struct DefArborescenceMap
|
deba@490
|
414 |
: public MinCostArborescence<Digraph, CostMap,
|
deba@490
|
415 |
DefArborescenceMapTraits<T> > {
|
deba@490
|
416 |
};
|
deba@490
|
417 |
|
deba@490
|
418 |
template <class T>
|
deba@490
|
419 |
struct DefPredMapTraits : public Traits {
|
deba@490
|
420 |
typedef T PredMap;
|
deba@490
|
421 |
static PredMap *createPredMap(const Digraph &)
|
deba@490
|
422 |
{
|
deba@490
|
423 |
LEMON_ASSERT(false, "PredMap is not initialized");
|
deba@490
|
424 |
}
|
deba@490
|
425 |
};
|
deba@490
|
426 |
|
deba@490
|
427 |
/// \brief \ref named-templ-param "Named parameter" for
|
deba@490
|
428 |
/// setting PredMap type
|
deba@490
|
429 |
///
|
deba@490
|
430 |
/// \ref named-templ-param "Named parameter" for setting
|
deba@490
|
431 |
/// PredMap type
|
deba@490
|
432 |
template <class T>
|
deba@490
|
433 |
struct DefPredMap
|
deba@490
|
434 |
: public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
|
deba@490
|
435 |
};
|
deba@490
|
436 |
|
deba@490
|
437 |
/// @}
|
deba@490
|
438 |
|
deba@490
|
439 |
/// \brief Constructor.
|
deba@490
|
440 |
///
|
kpeter@559
|
441 |
/// \param digraph The digraph the algorithm will run on.
|
kpeter@559
|
442 |
/// \param cost The cost map used by the algorithm.
|
deba@490
|
443 |
MinCostArborescence(const Digraph& digraph, const CostMap& cost)
|
deba@490
|
444 |
: _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
|
deba@490
|
445 |
_arborescence(0), local_arborescence(false),
|
deba@490
|
446 |
_arc_order(0), _node_order(0), _cost_arcs(0),
|
deba@490
|
447 |
_heap_cross_ref(0), _heap(0) {}
|
deba@490
|
448 |
|
deba@490
|
449 |
/// \brief Destructor.
|
deba@490
|
450 |
~MinCostArborescence() {
|
deba@490
|
451 |
destroyStructures();
|
deba@490
|
452 |
}
|
deba@490
|
453 |
|
deba@490
|
454 |
/// \brief Sets the arborescence map.
|
deba@490
|
455 |
///
|
deba@490
|
456 |
/// Sets the arborescence map.
|
kpeter@559
|
457 |
/// \return <tt>(*this)</tt>
|
deba@490
|
458 |
MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
|
deba@490
|
459 |
if (local_arborescence) {
|
deba@490
|
460 |
delete _arborescence;
|
deba@490
|
461 |
}
|
deba@490
|
462 |
local_arborescence = false;
|
deba@490
|
463 |
_arborescence = &m;
|
deba@490
|
464 |
return *this;
|
deba@490
|
465 |
}
|
deba@490
|
466 |
|
deba@490
|
467 |
/// \brief Sets the arborescence map.
|
deba@490
|
468 |
///
|
deba@490
|
469 |
/// Sets the arborescence map.
|
kpeter@559
|
470 |
/// \return <tt>(*this)</tt>
|
deba@490
|
471 |
MinCostArborescence& predMap(PredMap& m) {
|
deba@490
|
472 |
if (local_pred) {
|
deba@490
|
473 |
delete _pred;
|
deba@490
|
474 |
}
|
deba@490
|
475 |
local_pred = false;
|
deba@490
|
476 |
_pred = &m;
|
deba@490
|
477 |
return *this;
|
deba@490
|
478 |
}
|
deba@490
|
479 |
|
deba@490
|
480 |
/// \name Query Functions
|
deba@490
|
481 |
/// The result of the %MinCostArborescence algorithm can be obtained
|
deba@490
|
482 |
/// using these functions.\n
|
deba@490
|
483 |
/// Before the use of these functions,
|
deba@490
|
484 |
/// either run() or start() must be called.
|
deba@490
|
485 |
|
deba@490
|
486 |
/// @{
|
deba@490
|
487 |
|
deba@490
|
488 |
/// \brief Returns a reference to the arborescence map.
|
deba@490
|
489 |
///
|
deba@490
|
490 |
/// Returns a reference to the arborescence map.
|
deba@490
|
491 |
const ArborescenceMap& arborescenceMap() const {
|
deba@490
|
492 |
return *_arborescence;
|
deba@490
|
493 |
}
|
deba@490
|
494 |
|
deba@490
|
495 |
/// \brief Returns true if the arc is in the arborescence.
|
deba@490
|
496 |
///
|
deba@490
|
497 |
/// Returns true if the arc is in the arborescence.
|
deba@490
|
498 |
/// \param arc The arc of the digraph.
|
deba@490
|
499 |
/// \pre \ref run() must be called before using this function.
|
deba@490
|
500 |
bool arborescence(Arc arc) const {
|
deba@490
|
501 |
return (*_pred)[_digraph->target(arc)] == arc;
|
deba@490
|
502 |
}
|
deba@490
|
503 |
|
deba@490
|
504 |
/// \brief Returns a reference to the pred map.
|
deba@490
|
505 |
///
|
deba@490
|
506 |
/// Returns a reference to the pred map.
|
deba@490
|
507 |
const PredMap& predMap() const {
|
deba@490
|
508 |
return *_pred;
|
deba@490
|
509 |
}
|
deba@490
|
510 |
|
deba@490
|
511 |
/// \brief Returns the predecessor arc of the given node.
|
deba@490
|
512 |
///
|
deba@490
|
513 |
/// Returns the predecessor arc of the given node.
|
deba@490
|
514 |
Arc pred(Node node) const {
|
deba@490
|
515 |
return (*_pred)[node];
|
deba@490
|
516 |
}
|
deba@490
|
517 |
|
deba@490
|
518 |
/// \brief Returns the cost of the arborescence.
|
deba@490
|
519 |
///
|
deba@490
|
520 |
/// Returns the cost of the arborescence.
|
deba@490
|
521 |
Value arborescenceValue() const {
|
deba@490
|
522 |
Value sum = 0;
|
deba@490
|
523 |
for (ArcIt it(*_digraph); it != INVALID; ++it) {
|
deba@490
|
524 |
if (arborescence(it)) {
|
deba@490
|
525 |
sum += (*_cost)[it];
|
deba@490
|
526 |
}
|
deba@490
|
527 |
}
|
deba@490
|
528 |
return sum;
|
deba@490
|
529 |
}
|
deba@490
|
530 |
|
deba@490
|
531 |
/// \brief Indicates that a node is reachable from the sources.
|
deba@490
|
532 |
///
|
deba@490
|
533 |
/// Indicates that a node is reachable from the sources.
|
deba@490
|
534 |
bool reached(Node node) const {
|
deba@490
|
535 |
return (*_node_order)[node] != -3;
|
deba@490
|
536 |
}
|
deba@490
|
537 |
|
deba@490
|
538 |
/// \brief Indicates that a node is processed.
|
deba@490
|
539 |
///
|
deba@490
|
540 |
/// Indicates that a node is processed. The arborescence path exists
|
deba@490
|
541 |
/// from the source to the given node.
|
deba@490
|
542 |
bool processed(Node node) const {
|
deba@490
|
543 |
return (*_node_order)[node] == -1;
|
deba@490
|
544 |
}
|
deba@490
|
545 |
|
deba@490
|
546 |
/// \brief Returns the number of the dual variables in basis.
|
deba@490
|
547 |
///
|
deba@490
|
548 |
/// Returns the number of the dual variables in basis.
|
deba@490
|
549 |
int dualNum() const {
|
deba@490
|
550 |
return _dual_variables.size();
|
deba@490
|
551 |
}
|
deba@490
|
552 |
|
deba@490
|
553 |
/// \brief Returns the value of the dual solution.
|
deba@490
|
554 |
///
|
deba@490
|
555 |
/// Returns the value of the dual solution. It should be
|
deba@490
|
556 |
/// equal to the arborescence value.
|
deba@490
|
557 |
Value dualValue() const {
|
deba@490
|
558 |
Value sum = 0;
|
deba@490
|
559 |
for (int i = 0; i < int(_dual_variables.size()); ++i) {
|
deba@490
|
560 |
sum += _dual_variables[i].value;
|
deba@490
|
561 |
}
|
deba@490
|
562 |
return sum;
|
deba@490
|
563 |
}
|
deba@490
|
564 |
|
deba@490
|
565 |
/// \brief Returns the number of the nodes in the dual variable.
|
deba@490
|
566 |
///
|
deba@490
|
567 |
/// Returns the number of the nodes in the dual variable.
|
deba@490
|
568 |
int dualSize(int k) const {
|
deba@490
|
569 |
return _dual_variables[k].end - _dual_variables[k].begin;
|
deba@490
|
570 |
}
|
deba@490
|
571 |
|
deba@490
|
572 |
/// \brief Returns the value of the dual variable.
|
deba@490
|
573 |
///
|
deba@490
|
574 |
/// Returns the the value of the dual variable.
|
deba@490
|
575 |
const Value& dualValue(int k) const {
|
deba@490
|
576 |
return _dual_variables[k].value;
|
deba@490
|
577 |
}
|
deba@490
|
578 |
|
deba@490
|
579 |
/// \brief Lemon iterator for get a dual variable.
|
deba@490
|
580 |
///
|
deba@490
|
581 |
/// Lemon iterator for get a dual variable. This class provides
|
deba@490
|
582 |
/// a common style lemon iterator which gives back a subset of
|
deba@490
|
583 |
/// the nodes.
|
deba@490
|
584 |
class DualIt {
|
deba@490
|
585 |
public:
|
deba@490
|
586 |
|
deba@490
|
587 |
/// \brief Constructor.
|
deba@490
|
588 |
///
|
deba@490
|
589 |
/// Constructor for get the nodeset of the variable.
|
deba@490
|
590 |
DualIt(const MinCostArborescence& algorithm, int variable)
|
deba@490
|
591 |
: _algorithm(&algorithm)
|
deba@490
|
592 |
{
|
deba@490
|
593 |
_index = _algorithm->_dual_variables[variable].begin;
|
deba@490
|
594 |
_last = _algorithm->_dual_variables[variable].end;
|
deba@490
|
595 |
}
|
deba@490
|
596 |
|
deba@490
|
597 |
/// \brief Conversion to node.
|
deba@490
|
598 |
///
|
deba@490
|
599 |
/// Conversion to node.
|
deba@490
|
600 |
operator Node() const {
|
deba@490
|
601 |
return _algorithm->_dual_node_list[_index];
|
deba@490
|
602 |
}
|
deba@490
|
603 |
|
deba@490
|
604 |
/// \brief Increment operator.
|
deba@490
|
605 |
///
|
deba@490
|
606 |
/// Increment operator.
|
deba@490
|
607 |
DualIt& operator++() {
|
deba@490
|
608 |
++_index;
|
deba@490
|
609 |
return *this;
|
deba@490
|
610 |
}
|
deba@490
|
611 |
|
deba@490
|
612 |
/// \brief Validity checking
|
deba@490
|
613 |
///
|
deba@490
|
614 |
/// Checks whether the iterator is invalid.
|
deba@490
|
615 |
bool operator==(Invalid) const {
|
deba@490
|
616 |
return _index == _last;
|
deba@490
|
617 |
}
|
deba@490
|
618 |
|
deba@490
|
619 |
/// \brief Validity checking
|
deba@490
|
620 |
///
|
deba@490
|
621 |
/// Checks whether the iterator is valid.
|
deba@490
|
622 |
bool operator!=(Invalid) const {
|
deba@490
|
623 |
return _index != _last;
|
deba@490
|
624 |
}
|
deba@490
|
625 |
|
deba@490
|
626 |
private:
|
deba@490
|
627 |
const MinCostArborescence* _algorithm;
|
deba@490
|
628 |
int _index, _last;
|
deba@490
|
629 |
};
|
deba@490
|
630 |
|
deba@490
|
631 |
/// @}
|
deba@490
|
632 |
|
deba@490
|
633 |
/// \name Execution control
|
deba@490
|
634 |
/// The simplest way to execute the algorithm is to use
|
deba@490
|
635 |
/// one of the member functions called \c run(...). \n
|
deba@490
|
636 |
/// If you need more control on the execution,
|
deba@490
|
637 |
/// first you must call \ref init(), then you can add several
|
deba@490
|
638 |
/// source nodes with \ref addSource().
|
deba@490
|
639 |
/// Finally \ref start() will perform the arborescence
|
deba@490
|
640 |
/// computation.
|
deba@490
|
641 |
|
deba@490
|
642 |
///@{
|
deba@490
|
643 |
|
deba@490
|
644 |
/// \brief Initializes the internal data structures.
|
deba@490
|
645 |
///
|
deba@490
|
646 |
/// Initializes the internal data structures.
|
deba@490
|
647 |
///
|
deba@490
|
648 |
void init() {
|
deba@490
|
649 |
createStructures();
|
deba@490
|
650 |
_heap->clear();
|
deba@490
|
651 |
for (NodeIt it(*_digraph); it != INVALID; ++it) {
|
deba@490
|
652 |
(*_cost_arcs)[it].arc = INVALID;
|
kpeter@581
|
653 |
(*_node_order)[it] = -3;
|
kpeter@581
|
654 |
(*_heap_cross_ref)[it] = Heap::PRE_HEAP;
|
deba@490
|
655 |
_pred->set(it, INVALID);
|
deba@490
|
656 |
}
|
deba@490
|
657 |
for (ArcIt it(*_digraph); it != INVALID; ++it) {
|
deba@490
|
658 |
_arborescence->set(it, false);
|
kpeter@581
|
659 |
(*_arc_order)[it] = -1;
|
deba@490
|
660 |
}
|
deba@490
|
661 |
_dual_node_list.clear();
|
deba@490
|
662 |
_dual_variables.clear();
|
deba@490
|
663 |
}
|
deba@490
|
664 |
|
deba@490
|
665 |
/// \brief Adds a new source node.
|
deba@490
|
666 |
///
|
deba@490
|
667 |
/// Adds a new source node to the algorithm.
|
deba@490
|
668 |
void addSource(Node source) {
|
deba@490
|
669 |
std::vector<Node> nodes;
|
deba@490
|
670 |
nodes.push_back(source);
|
deba@490
|
671 |
while (!nodes.empty()) {
|
deba@490
|
672 |
Node node = nodes.back();
|
deba@490
|
673 |
nodes.pop_back();
|
deba@490
|
674 |
for (OutArcIt it(*_digraph, node); it != INVALID; ++it) {
|
deba@490
|
675 |
Node target = _digraph->target(it);
|
deba@490
|
676 |
if ((*_node_order)[target] == -3) {
|
deba@490
|
677 |
(*_node_order)[target] = -2;
|
deba@490
|
678 |
nodes.push_back(target);
|
deba@490
|
679 |
queue.push_back(target);
|
deba@490
|
680 |
}
|
deba@490
|
681 |
}
|
deba@490
|
682 |
}
|
deba@490
|
683 |
(*_node_order)[source] = -1;
|
deba@490
|
684 |
}
|
deba@490
|
685 |
|
deba@490
|
686 |
/// \brief Processes the next node in the priority queue.
|
deba@490
|
687 |
///
|
deba@490
|
688 |
/// Processes the next node in the priority queue.
|
deba@490
|
689 |
///
|
deba@490
|
690 |
/// \return The processed node.
|
deba@490
|
691 |
///
|
deba@490
|
692 |
/// \warning The queue must not be empty!
|
deba@490
|
693 |
Node processNextNode() {
|
deba@490
|
694 |
Node node = queue.back();
|
deba@490
|
695 |
queue.pop_back();
|
deba@490
|
696 |
if ((*_node_order)[node] == -2) {
|
deba@490
|
697 |
Arc arc = prepare(node);
|
deba@490
|
698 |
Node source = _digraph->source(arc);
|
deba@490
|
699 |
while ((*_node_order)[source] != -1) {
|
deba@490
|
700 |
if ((*_node_order)[source] >= 0) {
|
deba@490
|
701 |
arc = contract(source);
|
deba@490
|
702 |
} else {
|
deba@490
|
703 |
arc = prepare(source);
|
deba@490
|
704 |
}
|
deba@490
|
705 |
source = _digraph->source(arc);
|
deba@490
|
706 |
}
|
deba@490
|
707 |
finalize(arc);
|
deba@490
|
708 |
level_stack.clear();
|
deba@490
|
709 |
}
|
deba@490
|
710 |
return node;
|
deba@490
|
711 |
}
|
deba@490
|
712 |
|
deba@490
|
713 |
/// \brief Returns the number of the nodes to be processed.
|
deba@490
|
714 |
///
|
deba@490
|
715 |
/// Returns the number of the nodes to be processed.
|
deba@490
|
716 |
int queueSize() const {
|
deba@490
|
717 |
return queue.size();
|
deba@490
|
718 |
}
|
deba@490
|
719 |
|
deba@490
|
720 |
/// \brief Returns \c false if there are nodes to be processed.
|
deba@490
|
721 |
///
|
deba@490
|
722 |
/// Returns \c false if there are nodes to be processed.
|
deba@490
|
723 |
bool emptyQueue() const {
|
deba@490
|
724 |
return queue.empty();
|
deba@490
|
725 |
}
|
deba@490
|
726 |
|
deba@490
|
727 |
/// \brief Executes the algorithm.
|
deba@490
|
728 |
///
|
deba@490
|
729 |
/// Executes the algorithm.
|
deba@490
|
730 |
///
|
deba@490
|
731 |
/// \pre init() must be called and at least one node should be added
|
deba@490
|
732 |
/// with addSource() before using this function.
|
deba@490
|
733 |
///
|
deba@490
|
734 |
///\note mca.start() is just a shortcut of the following code.
|
deba@490
|
735 |
///\code
|
deba@490
|
736 |
///while (!mca.emptyQueue()) {
|
deba@490
|
737 |
/// mca.processNextNode();
|
deba@490
|
738 |
///}
|
deba@490
|
739 |
///\endcode
|
deba@490
|
740 |
void start() {
|
deba@490
|
741 |
while (!emptyQueue()) {
|
deba@490
|
742 |
processNextNode();
|
deba@490
|
743 |
}
|
deba@490
|
744 |
}
|
deba@490
|
745 |
|
deba@490
|
746 |
/// \brief Runs %MinCostArborescence algorithm from node \c s.
|
deba@490
|
747 |
///
|
deba@490
|
748 |
/// This method runs the %MinCostArborescence algorithm from
|
deba@490
|
749 |
/// a root node \c s.
|
deba@490
|
750 |
///
|
deba@490
|
751 |
/// \note mca.run(s) is just a shortcut of the following code.
|
deba@490
|
752 |
/// \code
|
deba@490
|
753 |
/// mca.init();
|
deba@490
|
754 |
/// mca.addSource(s);
|
deba@490
|
755 |
/// mca.start();
|
deba@490
|
756 |
/// \endcode
|
deba@490
|
757 |
void run(Node node) {
|
deba@490
|
758 |
init();
|
deba@490
|
759 |
addSource(node);
|
deba@490
|
760 |
start();
|
deba@490
|
761 |
}
|
deba@490
|
762 |
|
deba@490
|
763 |
///@}
|
deba@490
|
764 |
|
deba@490
|
765 |
};
|
deba@490
|
766 |
|
deba@490
|
767 |
/// \ingroup spantree
|
deba@490
|
768 |
///
|
deba@490
|
769 |
/// \brief Function type interface for MinCostArborescence algorithm.
|
deba@490
|
770 |
///
|
deba@490
|
771 |
/// Function type interface for MinCostArborescence algorithm.
|
deba@490
|
772 |
/// \param digraph The Digraph that the algorithm runs on.
|
deba@490
|
773 |
/// \param cost The CostMap of the arcs.
|
deba@490
|
774 |
/// \param source The source of the arborescence.
|
deba@490
|
775 |
/// \retval arborescence The bool ArcMap which stores the arborescence.
|
deba@490
|
776 |
/// \return The cost of the arborescence.
|
deba@490
|
777 |
///
|
deba@490
|
778 |
/// \sa MinCostArborescence
|
deba@490
|
779 |
template <typename Digraph, typename CostMap, typename ArborescenceMap>
|
deba@490
|
780 |
typename CostMap::Value minCostArborescence(const Digraph& digraph,
|
deba@490
|
781 |
const CostMap& cost,
|
deba@490
|
782 |
typename Digraph::Node source,
|
deba@490
|
783 |
ArborescenceMap& arborescence) {
|
deba@490
|
784 |
typename MinCostArborescence<Digraph, CostMap>
|
deba@490
|
785 |
::template DefArborescenceMap<ArborescenceMap>
|
deba@490
|
786 |
::Create mca(digraph, cost);
|
deba@490
|
787 |
mca.arborescenceMap(arborescence);
|
deba@490
|
788 |
mca.run(source);
|
deba@490
|
789 |
return mca.arborescenceValue();
|
deba@490
|
790 |
}
|
deba@490
|
791 |
|
deba@490
|
792 |
}
|
deba@490
|
793 |
|
deba@490
|
794 |
#endif
|