deba@1967
|
1 |
/* -*- C++ -*-
|
deba@1968
|
2 |
* lemon/minimum_cut.h - Part of LEMON, a generic C++ optimization library
|
deba@1967
|
3 |
*
|
deba@1967
|
4 |
* Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@1967
|
5 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@1967
|
6 |
*
|
deba@1967
|
7 |
* Permission to use, modify and distribute this software is granted
|
deba@1967
|
8 |
* provided that this copyright notice appears in all copies. For
|
deba@1967
|
9 |
* precise terms see the accompanying LICENSE file.
|
deba@1967
|
10 |
*
|
deba@1967
|
11 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@1967
|
12 |
* express or implied, and with no claim as to its suitability for any
|
deba@1967
|
13 |
* purpose.
|
deba@1967
|
14 |
*
|
deba@1967
|
15 |
*/
|
deba@1967
|
16 |
|
deba@1968
|
17 |
#ifndef LEMON_MINIMUM_CUT_H
|
deba@1968
|
18 |
#define LEMON_MINIMUM_CUT_H
|
deba@1967
|
19 |
|
deba@1967
|
20 |
|
deba@1967
|
21 |
/// \ingroup topology
|
deba@1967
|
22 |
/// \file
|
deba@1968
|
23 |
/// \brief Maximum cardinality search and minimum cut in undirected graphs.
|
deba@1967
|
24 |
|
deba@1967
|
25 |
#include <lemon/list_graph.h>
|
deba@1967
|
26 |
#include <lemon/bin_heap.h>
|
deba@1967
|
27 |
#include <lemon/linear_heap.h>
|
deba@1967
|
28 |
|
deba@1967
|
29 |
#include <lemon/invalid.h>
|
deba@1967
|
30 |
#include <lemon/error.h>
|
deba@1967
|
31 |
#include <lemon/maps.h>
|
deba@1967
|
32 |
|
deba@1967
|
33 |
#include <functional>
|
deba@1967
|
34 |
|
deba@1967
|
35 |
namespace lemon {
|
deba@1967
|
36 |
|
deba@1968
|
37 |
namespace _minimum_cut_bits {
|
deba@1967
|
38 |
|
deba@1967
|
39 |
template <typename CapacityMap>
|
deba@1967
|
40 |
struct HeapSelector {
|
deba@1967
|
41 |
template <typename Key, typename Value, typename Ref>
|
deba@1967
|
42 |
struct Selector {
|
deba@1967
|
43 |
typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
|
deba@1967
|
44 |
};
|
deba@1967
|
45 |
};
|
deba@1967
|
46 |
|
deba@1967
|
47 |
template <typename CapacityKey>
|
deba@1967
|
48 |
struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
|
deba@1967
|
49 |
template <typename Key, typename Value, typename Ref>
|
deba@1967
|
50 |
struct Selector {
|
deba@1967
|
51 |
typedef LinearHeap<Key, Ref, false > Heap;
|
deba@1967
|
52 |
};
|
deba@1967
|
53 |
};
|
deba@1967
|
54 |
|
deba@1967
|
55 |
}
|
deba@1967
|
56 |
|
deba@1967
|
57 |
/// \brief Default traits class of MaxCardinalitySearch class.
|
deba@1967
|
58 |
///
|
deba@1967
|
59 |
/// Default traits class of MaxCardinalitySearch class.
|
deba@1967
|
60 |
/// \param Graph Graph type.
|
deba@1967
|
61 |
/// \param CapacityMap Type of length map.
|
deba@1967
|
62 |
template <typename _Graph, typename _CapacityMap>
|
deba@1967
|
63 |
struct MaxCardinalitySearchDefaultTraits {
|
deba@1967
|
64 |
/// The graph type the algorithm runs on.
|
deba@1967
|
65 |
typedef _Graph Graph;
|
deba@1967
|
66 |
|
deba@1967
|
67 |
/// \brief The type of the map that stores the edge capacities.
|
deba@1967
|
68 |
///
|
deba@1967
|
69 |
/// The type of the map that stores the edge capacities.
|
deba@1967
|
70 |
/// It must meet the \ref concept::ReadMap "ReadMap" concept.
|
deba@1967
|
71 |
typedef _CapacityMap CapacityMap;
|
deba@1967
|
72 |
|
deba@1967
|
73 |
/// \brief The type of the capacity of the edges.
|
deba@1967
|
74 |
typedef typename CapacityMap::Value Value;
|
deba@1967
|
75 |
|
deba@1967
|
76 |
/// \brief The cross reference type used by heap.
|
deba@1967
|
77 |
///
|
deba@1967
|
78 |
/// The cross reference type used by heap.
|
deba@1967
|
79 |
/// Usually it is \c Graph::NodeMap<int>.
|
deba@1967
|
80 |
typedef typename Graph::template NodeMap<int> HeapCrossRef;
|
deba@1967
|
81 |
|
deba@1967
|
82 |
/// \brief Instantiates a HeapCrossRef.
|
deba@1967
|
83 |
///
|
deba@1967
|
84 |
/// This function instantiates a \ref HeapCrossRef.
|
deba@1967
|
85 |
/// \param graph is the graph, to which we would like to define the
|
deba@1967
|
86 |
/// HeapCrossRef.
|
deba@1967
|
87 |
static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
|
deba@1967
|
88 |
return new HeapCrossRef(graph);
|
deba@1967
|
89 |
}
|
deba@1967
|
90 |
|
deba@1967
|
91 |
/// \brief The heap type used by MaxCardinalitySearch algorithm.
|
deba@1967
|
92 |
///
|
deba@1967
|
93 |
/// The heap type used by MaxCardinalitySearch algorithm. It should
|
deba@1967
|
94 |
/// maximalize the priorities. The default heap type is
|
deba@1967
|
95 |
/// the \ref BinHeap, but it is specialized when the
|
deba@1967
|
96 |
/// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
|
deba@1967
|
97 |
/// to LinearHeap.
|
deba@1967
|
98 |
///
|
deba@1967
|
99 |
/// \sa MaxCardinalitySearch
|
deba@1968
|
100 |
typedef typename _minimum_cut_bits
|
deba@1967
|
101 |
::HeapSelector<CapacityMap>
|
deba@1967
|
102 |
::template Selector<typename Graph::Node, Value, HeapCrossRef>
|
deba@1967
|
103 |
::Heap Heap;
|
deba@1967
|
104 |
|
deba@1967
|
105 |
/// \brief Instantiates a Heap.
|
deba@1967
|
106 |
///
|
deba@1967
|
107 |
/// This function instantiates a \ref Heap.
|
deba@1967
|
108 |
/// \param crossref The cross reference of the heap.
|
deba@1967
|
109 |
static Heap *createHeap(HeapCrossRef& crossref) {
|
deba@1967
|
110 |
return new Heap(crossref);
|
deba@1967
|
111 |
}
|
deba@1967
|
112 |
|
deba@1967
|
113 |
/// \brief The type of the map that stores whether a nodes is processed.
|
deba@1967
|
114 |
///
|
deba@1967
|
115 |
/// The type of the map that stores whether a nodes is processed.
|
deba@1967
|
116 |
/// It must meet the \ref concept::WriteMap "WriteMap" concept.
|
deba@1967
|
117 |
/// By default it is a NullMap.
|
deba@1967
|
118 |
typedef NullMap<typename Graph::Node, bool> ProcessedMap;
|
deba@1967
|
119 |
|
deba@1967
|
120 |
/// \brief Instantiates a ProcessedMap.
|
deba@1967
|
121 |
///
|
deba@1967
|
122 |
/// This function instantiates a \ref ProcessedMap.
|
deba@1967
|
123 |
/// \param g is the graph, to which
|
deba@1967
|
124 |
/// we would like to define the \ref ProcessedMap
|
deba@1967
|
125 |
#ifdef DOXYGEN
|
deba@1967
|
126 |
static ProcessedMap *createProcessedMap(const Graph &graph)
|
deba@1967
|
127 |
#else
|
deba@1967
|
128 |
static ProcessedMap *createProcessedMap(const Graph &)
|
deba@1967
|
129 |
#endif
|
deba@1967
|
130 |
{
|
deba@1967
|
131 |
return new ProcessedMap();
|
deba@1967
|
132 |
}
|
deba@1967
|
133 |
|
deba@1967
|
134 |
/// \brief The type of the map that stores the cardinalties of the nodes.
|
deba@1967
|
135 |
///
|
deba@1967
|
136 |
/// The type of the map that stores the cardinalities of the nodes.
|
deba@1967
|
137 |
/// It must meet the \ref concept::WriteMap "WriteMap" concept.
|
deba@1967
|
138 |
typedef typename Graph::template NodeMap<Value> CardinalityMap;
|
deba@1967
|
139 |
|
deba@1967
|
140 |
/// \brief Instantiates a CardinalityMap.
|
deba@1967
|
141 |
///
|
deba@1967
|
142 |
/// This function instantiates a \ref CardinalityMap.
|
deba@1967
|
143 |
/// \param graph is the graph, to which we would like to define the \ref
|
deba@1967
|
144 |
/// CardinalityMap
|
deba@1967
|
145 |
static CardinalityMap *createCardinalityMap(const Graph &graph) {
|
deba@1967
|
146 |
return new CardinalityMap(graph);
|
deba@1967
|
147 |
}
|
deba@1967
|
148 |
|
deba@1967
|
149 |
};
|
deba@1967
|
150 |
|
deba@1967
|
151 |
/// \ingroup topology
|
deba@1967
|
152 |
///
|
deba@1967
|
153 |
/// \brief Maximum Cardinality Search algorithm class.
|
deba@1967
|
154 |
///
|
deba@1967
|
155 |
/// This class provides an efficient implementation of Maximum Cardinality
|
deba@1967
|
156 |
/// Search algorithm. The maximum cardinality search chooses first time any
|
deba@1967
|
157 |
/// node of the graph. Then every time chooses that node which connected
|
deba@1967
|
158 |
/// to the processed nodes at most in the sum of capacities on the out
|
deba@1967
|
159 |
/// edges. If there is a cut in the graph the algorithm should choose
|
deba@1967
|
160 |
/// again any unprocessed node of the graph. Each nodes cardinality is
|
deba@1967
|
161 |
/// the sum of capacities on the out edges to the nodes which are processed
|
deba@1967
|
162 |
/// before the given node.
|
deba@1967
|
163 |
///
|
deba@1967
|
164 |
/// The edge capacities are passed to the algorithm using a
|
deba@1967
|
165 |
/// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
|
deba@1967
|
166 |
/// kind of capacity.
|
deba@1967
|
167 |
///
|
deba@1967
|
168 |
/// The type of the capacity is determined by the \ref
|
deba@1967
|
169 |
/// concept::ReadMap::Value "Value" of the capacity map.
|
deba@1967
|
170 |
///
|
deba@1967
|
171 |
/// It is also possible to change the underlying priority heap.
|
deba@1967
|
172 |
///
|
deba@1967
|
173 |
///
|
deba@1967
|
174 |
/// \param _Graph The graph type the algorithm runs on. The default value
|
deba@1967
|
175 |
/// is \ref ListGraph. The value of Graph is not used directly by
|
deba@1967
|
176 |
/// the search algorithm, it is only passed to
|
deba@1967
|
177 |
/// \ref MaxCardinalitySearchDefaultTraits.
|
deba@1967
|
178 |
/// \param _CapacityMap This read-only EdgeMap determines the capacities of
|
deba@1967
|
179 |
/// the edges. It is read once for each edge, so the map may involve in
|
deba@1967
|
180 |
/// relatively time consuming process to compute the edge capacity if
|
deba@1967
|
181 |
/// it is necessary. The default map type is \ref
|
deba@1967
|
182 |
/// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
|
deba@1967
|
183 |
/// of CapacityMap is not used directly by search algorithm, it is only
|
deba@1967
|
184 |
/// passed to \ref MaxCardinalitySearchDefaultTraits.
|
deba@1967
|
185 |
/// \param _Traits Traits class to set various data types used by the
|
deba@1967
|
186 |
/// algorithm. The default traits class is
|
deba@1967
|
187 |
/// \ref MaxCardinalitySearchDefaultTraits
|
deba@1967
|
188 |
/// "MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>".
|
deba@1967
|
189 |
/// See \ref MaxCardinalitySearchDefaultTraits
|
deba@1967
|
190 |
/// for the documentation of a MaxCardinalitySearch traits class.
|
deba@1967
|
191 |
///
|
deba@1967
|
192 |
/// \author Balazs Dezso
|
deba@1967
|
193 |
|
deba@1967
|
194 |
#ifdef DOXYGEN
|
deba@1967
|
195 |
template <typename _Graph, typename _CapacityMap, typename _Traits>
|
deba@1967
|
196 |
#else
|
deba@1967
|
197 |
template <typename _Graph = ListUGraph,
|
deba@1967
|
198 |
typename _CapacityMap = typename _Graph::template EdgeMap<int>,
|
deba@1967
|
199 |
typename _Traits =
|
deba@1967
|
200 |
MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
|
deba@1967
|
201 |
#endif
|
deba@1967
|
202 |
class MaxCardinalitySearch {
|
deba@1967
|
203 |
public:
|
deba@1967
|
204 |
/// \brief \ref Exception for uninitialized parameters.
|
deba@1967
|
205 |
///
|
deba@1967
|
206 |
/// This error represents problems in the initialization
|
deba@1967
|
207 |
/// of the parameters of the algorithms.
|
deba@1967
|
208 |
class UninitializedParameter : public lemon::UninitializedParameter {
|
deba@1967
|
209 |
public:
|
deba@1967
|
210 |
virtual const char* exceptionName() const {
|
deba@1967
|
211 |
return "lemon::MaxCardinalitySearch::UninitializedParameter";
|
deba@1967
|
212 |
}
|
deba@1967
|
213 |
};
|
deba@1967
|
214 |
|
deba@1967
|
215 |
typedef _Traits Traits;
|
deba@1967
|
216 |
///The type of the underlying graph.
|
deba@1967
|
217 |
typedef typename Traits::Graph Graph;
|
deba@1967
|
218 |
|
deba@1967
|
219 |
///The type of the capacity of the edges.
|
deba@1967
|
220 |
typedef typename Traits::CapacityMap::Value Value;
|
deba@1967
|
221 |
///The type of the map that stores the edge capacities.
|
deba@1967
|
222 |
typedef typename Traits::CapacityMap CapacityMap;
|
deba@1967
|
223 |
///The type of the map indicating if a node is processed.
|
deba@1967
|
224 |
typedef typename Traits::ProcessedMap ProcessedMap;
|
deba@1967
|
225 |
///The type of the map that stores the cardinalities of the nodes.
|
deba@1967
|
226 |
typedef typename Traits::CardinalityMap CardinalityMap;
|
deba@1967
|
227 |
///The cross reference type used for the current heap.
|
deba@1967
|
228 |
typedef typename Traits::HeapCrossRef HeapCrossRef;
|
deba@1967
|
229 |
///The heap type used by the algorithm. It maximize the priorities.
|
deba@1967
|
230 |
typedef typename Traits::Heap Heap;
|
deba@1967
|
231 |
private:
|
deba@1967
|
232 |
/// Pointer to the underlying graph.
|
deba@1967
|
233 |
const Graph *_graph;
|
deba@1967
|
234 |
/// Pointer to the capacity map
|
deba@1967
|
235 |
const CapacityMap *_capacity;
|
deba@1967
|
236 |
///Pointer to the map of cardinality.
|
deba@1967
|
237 |
CardinalityMap *_cardinality;
|
deba@1967
|
238 |
///Indicates if \ref _cardinality is locally allocated (\c true) or not.
|
deba@1967
|
239 |
bool local_cardinality;
|
deba@1967
|
240 |
///Pointer to the map of processed status of the nodes.
|
deba@1967
|
241 |
ProcessedMap *_processed;
|
deba@1967
|
242 |
///Indicates if \ref _processed is locally allocated (\c true) or not.
|
deba@1967
|
243 |
bool local_processed;
|
deba@1967
|
244 |
///Pointer to the heap cross references.
|
deba@1967
|
245 |
HeapCrossRef *_heap_cross_ref;
|
deba@1967
|
246 |
///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
|
deba@1967
|
247 |
bool local_heap_cross_ref;
|
deba@1967
|
248 |
///Pointer to the heap.
|
deba@1967
|
249 |
Heap *_heap;
|
deba@1967
|
250 |
///Indicates if \ref _heap is locally allocated (\c true) or not.
|
deba@1967
|
251 |
bool local_heap;
|
deba@1967
|
252 |
|
deba@1967
|
253 |
public :
|
deba@1967
|
254 |
|
deba@1967
|
255 |
typedef MaxCardinalitySearch Create;
|
deba@1967
|
256 |
|
deba@1967
|
257 |
///\name Named template parameters
|
deba@1967
|
258 |
|
deba@1967
|
259 |
///@{
|
deba@1967
|
260 |
|
deba@1967
|
261 |
template <class T>
|
deba@1967
|
262 |
struct DefCardinalityMapTraits : public Traits {
|
deba@1967
|
263 |
typedef T CardinalityMap;
|
deba@1967
|
264 |
static CardinalityMap *createCardinalityMap(const Graph &)
|
deba@1967
|
265 |
{
|
deba@1967
|
266 |
throw UninitializedParameter();
|
deba@1967
|
267 |
}
|
deba@1967
|
268 |
};
|
deba@1967
|
269 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
deba@1967
|
270 |
/// CardinalityMap type
|
deba@1967
|
271 |
///
|
deba@1967
|
272 |
/// \ref named-templ-param "Named parameter" for setting CardinalityMap
|
deba@1967
|
273 |
/// type
|
deba@1967
|
274 |
template <class T>
|
deba@1967
|
275 |
struct DefCardinalityMap
|
deba@1967
|
276 |
: public MaxCardinalitySearch<Graph, CapacityMap,
|
deba@1967
|
277 |
DefCardinalityMapTraits<T> > {
|
deba@1967
|
278 |
typedef MaxCardinalitySearch<Graph, CapacityMap,
|
deba@1967
|
279 |
DefCardinalityMapTraits<T> > Create;
|
deba@1967
|
280 |
};
|
deba@1967
|
281 |
|
deba@1967
|
282 |
template <class T>
|
deba@1967
|
283 |
struct DefProcessedMapTraits : public Traits {
|
deba@1967
|
284 |
typedef T ProcessedMap;
|
deba@1967
|
285 |
static ProcessedMap *createProcessedMap(const Graph &) {
|
deba@1967
|
286 |
throw UninitializedParameter();
|
deba@1967
|
287 |
}
|
deba@1967
|
288 |
};
|
deba@1967
|
289 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
deba@1967
|
290 |
/// ProcessedMap type
|
deba@1967
|
291 |
///
|
deba@1967
|
292 |
/// \ref named-templ-param "Named parameter" for setting ProcessedMap type
|
deba@1967
|
293 |
///
|
deba@1967
|
294 |
template <class T>
|
deba@1967
|
295 |
struct DefProcessedMap
|
deba@1967
|
296 |
: public MaxCardinalitySearch<Graph, CapacityMap,
|
deba@1967
|
297 |
DefProcessedMapTraits<T> > {
|
deba@1967
|
298 |
typedef MaxCardinalitySearch<Graph, CapacityMap,
|
deba@1967
|
299 |
DefProcessedMapTraits<T> > Create;
|
deba@1967
|
300 |
};
|
deba@1967
|
301 |
|
deba@1967
|
302 |
template <class H, class CR>
|
deba@1967
|
303 |
struct DefHeapTraits : public Traits {
|
deba@1967
|
304 |
typedef CR HeapCrossRef;
|
deba@1967
|
305 |
typedef H Heap;
|
deba@1967
|
306 |
static HeapCrossRef *createHeapCrossRef(const Graph &) {
|
deba@1967
|
307 |
throw UninitializedParameter();
|
deba@1967
|
308 |
}
|
deba@1967
|
309 |
static Heap *createHeap(HeapCrossRef &) {
|
deba@1967
|
310 |
throw UninitializedParameter();
|
deba@1967
|
311 |
}
|
deba@1967
|
312 |
};
|
deba@1967
|
313 |
/// \brief \ref named-templ-param "Named parameter" for setting heap
|
deba@1967
|
314 |
/// and cross reference type
|
deba@1967
|
315 |
///
|
deba@1967
|
316 |
/// \ref named-templ-param "Named parameter" for setting heap and cross
|
deba@1967
|
317 |
/// reference type
|
deba@1967
|
318 |
template <class H, class CR = typename Graph::template NodeMap<int> >
|
deba@1967
|
319 |
struct DefHeap
|
deba@1967
|
320 |
: public MaxCardinalitySearch<Graph, CapacityMap,
|
deba@1967
|
321 |
DefHeapTraits<H, CR> > {
|
deba@1967
|
322 |
typedef MaxCardinalitySearch< Graph, CapacityMap,
|
deba@1967
|
323 |
DefHeapTraits<H, CR> > Create;
|
deba@1967
|
324 |
};
|
deba@1967
|
325 |
|
deba@1967
|
326 |
template <class H, class CR>
|
deba@1967
|
327 |
struct DefStandardHeapTraits : public Traits {
|
deba@1967
|
328 |
typedef CR HeapCrossRef;
|
deba@1967
|
329 |
typedef H Heap;
|
deba@1967
|
330 |
static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
|
deba@1967
|
331 |
return new HeapCrossRef(graph);
|
deba@1967
|
332 |
}
|
deba@1967
|
333 |
static Heap *createHeap(HeapCrossRef &crossref) {
|
deba@1967
|
334 |
return new Heap(crossref);
|
deba@1967
|
335 |
}
|
deba@1967
|
336 |
};
|
deba@1967
|
337 |
|
deba@1967
|
338 |
/// \brief \ref named-templ-param "Named parameter" for setting heap and
|
deba@1967
|
339 |
/// cross reference type with automatic allocation
|
deba@1967
|
340 |
///
|
deba@1967
|
341 |
/// \ref named-templ-param "Named parameter" for setting heap and cross
|
deba@1967
|
342 |
/// reference type. It can allocate the heap and the cross reference
|
deba@1967
|
343 |
/// object if the cross reference's constructor waits for the graph as
|
deba@1967
|
344 |
/// parameter and the heap's constructor waits for the cross reference.
|
deba@1967
|
345 |
template <class H, class CR = typename Graph::template NodeMap<int> >
|
deba@1967
|
346 |
struct DefStandardHeap
|
deba@1967
|
347 |
: public MaxCardinalitySearch<Graph, CapacityMap,
|
deba@1967
|
348 |
DefStandardHeapTraits<H, CR> > {
|
deba@1967
|
349 |
typedef MaxCardinalitySearch<Graph, CapacityMap,
|
deba@1967
|
350 |
DefStandardHeapTraits<H, CR> >
|
deba@1967
|
351 |
Create;
|
deba@1967
|
352 |
};
|
deba@1967
|
353 |
|
deba@1967
|
354 |
///@}
|
deba@1967
|
355 |
|
deba@1967
|
356 |
|
deba@1967
|
357 |
protected:
|
deba@1967
|
358 |
|
deba@1967
|
359 |
MaxCardinalitySearch() {}
|
deba@1967
|
360 |
|
deba@1967
|
361 |
public:
|
deba@1967
|
362 |
|
deba@1967
|
363 |
/// \brief Constructor.
|
deba@1967
|
364 |
///
|
deba@1967
|
365 |
///\param _graph the graph the algorithm will run on.
|
deba@1967
|
366 |
///\param _capacity the capacity map used by the algorithm.
|
deba@1967
|
367 |
MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) :
|
deba@1967
|
368 |
_graph(&graph), _capacity(&capacity),
|
deba@1967
|
369 |
_cardinality(0), local_cardinality(false),
|
deba@1967
|
370 |
_processed(0), local_processed(false),
|
deba@1967
|
371 |
_heap_cross_ref(0), local_heap_cross_ref(false),
|
deba@1967
|
372 |
_heap(0), local_heap(false)
|
deba@1967
|
373 |
{ }
|
deba@1967
|
374 |
|
deba@1967
|
375 |
/// \brief Destructor.
|
deba@1967
|
376 |
~MaxCardinalitySearch() {
|
deba@1967
|
377 |
if(local_cardinality) delete _cardinality;
|
deba@1967
|
378 |
if(local_processed) delete _processed;
|
deba@1967
|
379 |
if(local_heap_cross_ref) delete _heap_cross_ref;
|
deba@1967
|
380 |
if(local_heap) delete _heap;
|
deba@1967
|
381 |
}
|
deba@1967
|
382 |
|
deba@1967
|
383 |
/// \brief Sets the capacity map.
|
deba@1967
|
384 |
///
|
deba@1967
|
385 |
/// Sets the capacity map.
|
deba@1967
|
386 |
/// \return <tt> (*this) </tt>
|
deba@1967
|
387 |
MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
|
deba@1967
|
388 |
_capacity = &m;
|
deba@1967
|
389 |
return *this;
|
deba@1967
|
390 |
}
|
deba@1967
|
391 |
|
deba@1967
|
392 |
/// \brief Sets the map storing the cardinalities calculated by the
|
deba@1967
|
393 |
/// algorithm.
|
deba@1967
|
394 |
///
|
deba@1967
|
395 |
/// Sets the map storing the cardinalities calculated by the algorithm.
|
deba@1967
|
396 |
/// If you don't use this function before calling \ref run(),
|
deba@1967
|
397 |
/// it will allocate one. The destuctor deallocates this
|
deba@1967
|
398 |
/// automatically allocated map, of course.
|
deba@1967
|
399 |
/// \return <tt> (*this) </tt>
|
deba@1967
|
400 |
MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
|
deba@1967
|
401 |
if(local_cardinality) {
|
deba@1967
|
402 |
delete _cardinality;
|
deba@1967
|
403 |
local_cardinality=false;
|
deba@1967
|
404 |
}
|
deba@1967
|
405 |
_cardinality = &m;
|
deba@1967
|
406 |
return *this;
|
deba@1967
|
407 |
}
|
deba@1967
|
408 |
|
deba@1967
|
409 |
/// \brief Sets the map storing the processed nodes.
|
deba@1967
|
410 |
///
|
deba@1967
|
411 |
/// Sets the map storing the processed nodes.
|
deba@1967
|
412 |
/// If you don't use this function before calling \ref run(),
|
deba@1967
|
413 |
/// it will allocate one. The destuctor deallocates this
|
deba@1967
|
414 |
/// automatically allocated map, of course.
|
deba@1967
|
415 |
/// \return <tt> (*this) </tt>
|
deba@1967
|
416 |
MaxCardinalitySearch &processedMap(ProcessedMap &m)
|
deba@1967
|
417 |
{
|
deba@1967
|
418 |
if(local_processed) {
|
deba@1967
|
419 |
delete _processed;
|
deba@1967
|
420 |
local_processed=false;
|
deba@1967
|
421 |
}
|
deba@1967
|
422 |
_processed = &m;
|
deba@1967
|
423 |
return *this;
|
deba@1967
|
424 |
}
|
deba@1967
|
425 |
|
deba@1967
|
426 |
/// \brief Sets the heap and the cross reference used by algorithm.
|
deba@1967
|
427 |
///
|
deba@1967
|
428 |
/// Sets the heap and the cross reference used by algorithm.
|
deba@1967
|
429 |
/// If you don't use this function before calling \ref run(),
|
deba@1967
|
430 |
/// it will allocate one. The destuctor deallocates this
|
deba@1967
|
431 |
/// automatically allocated map, of course.
|
deba@1967
|
432 |
/// \return <tt> (*this) </tt>
|
deba@1967
|
433 |
MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) {
|
deba@1967
|
434 |
if(local_heap_cross_ref) {
|
deba@1967
|
435 |
delete _heap_cross_ref;
|
deba@1967
|
436 |
local_heap_cross_ref = false;
|
deba@1967
|
437 |
}
|
deba@1967
|
438 |
_heap_cross_ref = &crossRef;
|
deba@1967
|
439 |
if(local_heap) {
|
deba@1967
|
440 |
delete _heap;
|
deba@1967
|
441 |
local_heap = false;
|
deba@1967
|
442 |
}
|
deba@1967
|
443 |
_heap = &heap;
|
deba@1967
|
444 |
return *this;
|
deba@1967
|
445 |
}
|
deba@1967
|
446 |
|
deba@1967
|
447 |
private:
|
deba@1967
|
448 |
|
deba@1967
|
449 |
typedef typename Graph::Node Node;
|
deba@1967
|
450 |
typedef typename Graph::NodeIt NodeIt;
|
deba@1967
|
451 |
typedef typename Graph::Edge Edge;
|
deba@1967
|
452 |
typedef typename Graph::InEdgeIt InEdgeIt;
|
deba@1967
|
453 |
|
deba@1967
|
454 |
void create_maps() {
|
deba@1967
|
455 |
if(!_cardinality) {
|
deba@1967
|
456 |
local_cardinality = true;
|
deba@1967
|
457 |
_cardinality = Traits::createCardinalityMap(*_graph);
|
deba@1967
|
458 |
}
|
deba@1967
|
459 |
if(!_processed) {
|
deba@1967
|
460 |
local_processed = true;
|
deba@1967
|
461 |
_processed = Traits::createProcessedMap(*_graph);
|
deba@1967
|
462 |
}
|
deba@1967
|
463 |
if (!_heap_cross_ref) {
|
deba@1967
|
464 |
local_heap_cross_ref = true;
|
deba@1967
|
465 |
_heap_cross_ref = Traits::createHeapCrossRef(*_graph);
|
deba@1967
|
466 |
}
|
deba@1967
|
467 |
if (!_heap) {
|
deba@1967
|
468 |
local_heap = true;
|
deba@1967
|
469 |
_heap = Traits::createHeap(*_heap_cross_ref);
|
deba@1967
|
470 |
}
|
deba@1967
|
471 |
}
|
deba@1967
|
472 |
|
deba@1967
|
473 |
void finalizeNodeData(Node node, Value capacity) {
|
deba@1967
|
474 |
_processed->set(node, true);
|
deba@1967
|
475 |
_cardinality->set(node, capacity);
|
deba@1967
|
476 |
}
|
deba@1967
|
477 |
|
deba@1967
|
478 |
public:
|
deba@1967
|
479 |
/// \name Execution control
|
deba@1967
|
480 |
/// The simplest way to execute the algorithm is to use
|
deba@1967
|
481 |
/// one of the member functions called \c run(...).
|
deba@1967
|
482 |
/// \n
|
deba@1967
|
483 |
/// If you need more control on the execution,
|
deba@1967
|
484 |
/// first you must call \ref init(), then you can add several source nodes
|
deba@1967
|
485 |
/// with \ref addSource().
|
deba@1967
|
486 |
/// Finally \ref start() will perform the actual path
|
deba@1967
|
487 |
/// computation.
|
deba@1967
|
488 |
|
deba@1967
|
489 |
///@{
|
deba@1967
|
490 |
|
deba@1967
|
491 |
/// \brief Initializes the internal data structures.
|
deba@1967
|
492 |
///
|
deba@1967
|
493 |
/// Initializes the internal data structures.
|
deba@1967
|
494 |
void init() {
|
deba@1967
|
495 |
create_maps();
|
deba@1967
|
496 |
_heap->clear();
|
deba@1967
|
497 |
for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
|
deba@1967
|
498 |
_processed->set(it, false);
|
deba@1967
|
499 |
_heap_cross_ref->set(it, Heap::PRE_HEAP);
|
deba@1967
|
500 |
}
|
deba@1967
|
501 |
}
|
deba@1967
|
502 |
|
deba@1967
|
503 |
/// \brief Adds a new source node.
|
deba@1967
|
504 |
///
|
deba@1967
|
505 |
/// Adds a new source node to the priority heap.
|
deba@1967
|
506 |
///
|
deba@1967
|
507 |
/// It checks if the node has not yet been added to the heap.
|
deba@1967
|
508 |
void addSource(Node source, Value capacity = 0) {
|
deba@1967
|
509 |
if(_heap->state(source) == Heap::PRE_HEAP) {
|
deba@1967
|
510 |
_heap->push(source, capacity);
|
deba@1967
|
511 |
}
|
deba@1967
|
512 |
}
|
deba@1967
|
513 |
|
deba@1967
|
514 |
/// \brief Processes the next node in the priority heap
|
deba@1967
|
515 |
///
|
deba@1967
|
516 |
/// Processes the next node in the priority heap.
|
deba@1967
|
517 |
///
|
deba@1967
|
518 |
/// \return The processed node.
|
deba@1967
|
519 |
///
|
deba@1967
|
520 |
/// \warning The priority heap must not be empty!
|
deba@1967
|
521 |
Node processNextNode() {
|
deba@1967
|
522 |
Node node = _heap->top();
|
deba@1967
|
523 |
finalizeNodeData(node, _heap->prio());
|
deba@1967
|
524 |
_heap->pop();
|
deba@1967
|
525 |
|
deba@1967
|
526 |
for (InEdgeIt it(*_graph, node); it != INVALID; ++it) {
|
deba@1967
|
527 |
Node source = _graph->source(it);
|
deba@1967
|
528 |
switch (_heap->state(source)) {
|
deba@1967
|
529 |
case Heap::PRE_HEAP:
|
deba@1967
|
530 |
_heap->push(source, (*_capacity)[it]);
|
deba@1967
|
531 |
break;
|
deba@1967
|
532 |
case Heap::IN_HEAP:
|
deba@1967
|
533 |
_heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
|
deba@1967
|
534 |
break;
|
deba@1967
|
535 |
case Heap::POST_HEAP:
|
deba@1967
|
536 |
break;
|
deba@1967
|
537 |
}
|
deba@1967
|
538 |
}
|
deba@1967
|
539 |
return node;
|
deba@1967
|
540 |
}
|
deba@1967
|
541 |
|
deba@1967
|
542 |
/// \brief Next node to be processed.
|
deba@1967
|
543 |
///
|
deba@1967
|
544 |
/// Next node to be processed.
|
deba@1967
|
545 |
///
|
deba@1967
|
546 |
/// \return The next node to be processed or INVALID if the
|
deba@1967
|
547 |
/// priority heap is empty.
|
deba@1967
|
548 |
Node nextNode() {
|
deba@1967
|
549 |
return _heap->empty() ? _heap->top() : INVALID;
|
deba@1967
|
550 |
}
|
deba@1967
|
551 |
|
deba@1967
|
552 |
/// \brief Returns \c false if there are nodes
|
deba@1967
|
553 |
/// to be processed in the priority heap
|
deba@1967
|
554 |
///
|
deba@1967
|
555 |
/// Returns \c false if there are nodes
|
deba@1967
|
556 |
/// to be processed in the priority heap
|
deba@1967
|
557 |
bool emptyQueue() { return _heap->empty(); }
|
deba@1967
|
558 |
/// \brief Returns the number of the nodes to be processed
|
deba@1967
|
559 |
/// in the priority heap
|
deba@1967
|
560 |
///
|
deba@1967
|
561 |
/// Returns the number of the nodes to be processed in the priority heap
|
deba@1967
|
562 |
int queueSize() { return _heap->size(); }
|
deba@1967
|
563 |
|
deba@1967
|
564 |
/// \brief Executes the algorithm.
|
deba@1967
|
565 |
///
|
deba@1967
|
566 |
/// Executes the algorithm.
|
deba@1967
|
567 |
///
|
deba@1967
|
568 |
///\pre init() must be called and at least one node should be added
|
deba@1967
|
569 |
/// with addSource() before using this function.
|
deba@1967
|
570 |
///
|
deba@1967
|
571 |
/// This method runs the Maximum Cardinality Search algorithm from the
|
deba@1967
|
572 |
/// source node(s).
|
deba@1967
|
573 |
void start() {
|
deba@1967
|
574 |
while ( !_heap->empty() ) processNextNode();
|
deba@1967
|
575 |
}
|
deba@1967
|
576 |
|
deba@1967
|
577 |
/// \brief Executes the algorithm until \c dest is reached.
|
deba@1967
|
578 |
///
|
deba@1967
|
579 |
/// Executes the algorithm until \c dest is reached.
|
deba@1967
|
580 |
///
|
deba@1967
|
581 |
/// \pre init() must be called and at least one node should be added
|
deba@1967
|
582 |
/// with addSource() before using this function.
|
deba@1967
|
583 |
///
|
deba@1967
|
584 |
/// This method runs the %MaxCardinalitySearch algorithm from the source
|
deba@1967
|
585 |
/// nodes.
|
deba@1967
|
586 |
void start(Node dest) {
|
deba@1967
|
587 |
while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
|
deba@1967
|
588 |
if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
|
deba@1967
|
589 |
}
|
deba@1967
|
590 |
|
deba@1967
|
591 |
/// \brief Executes the algorithm until a condition is met.
|
deba@1967
|
592 |
///
|
deba@1967
|
593 |
/// Executes the algorithm until a condition is met.
|
deba@1967
|
594 |
///
|
deba@1967
|
595 |
/// \pre init() must be called and at least one node should be added
|
deba@1967
|
596 |
/// with addSource() before using this function.
|
deba@1967
|
597 |
///
|
deba@1967
|
598 |
/// \param nm must be a bool (or convertible) node map. The algorithm
|
deba@1967
|
599 |
/// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
|
deba@1967
|
600 |
template <typename NodeBoolMap>
|
deba@1967
|
601 |
void start(const NodeBoolMap &nm) {
|
deba@1967
|
602 |
while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
|
deba@1967
|
603 |
if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
|
deba@1967
|
604 |
}
|
deba@1967
|
605 |
|
deba@1967
|
606 |
/// \brief Runs the maximal cardinality search algorithm from node \c s.
|
deba@1967
|
607 |
///
|
deba@1967
|
608 |
/// This method runs the %MaxCardinalitySearch algorithm from a root
|
deba@1967
|
609 |
/// node \c s.
|
deba@1967
|
610 |
///
|
deba@1967
|
611 |
///\note d.run(s) is just a shortcut of the following code.
|
deba@1967
|
612 |
///\code
|
deba@1967
|
613 |
/// d.init();
|
deba@1967
|
614 |
/// d.addSource(s);
|
deba@1967
|
615 |
/// d.start();
|
deba@1967
|
616 |
///\endcode
|
deba@1967
|
617 |
void run(Node s) {
|
deba@1967
|
618 |
init();
|
deba@1967
|
619 |
addSource(s);
|
deba@1967
|
620 |
start();
|
deba@1967
|
621 |
}
|
deba@1967
|
622 |
|
deba@1967
|
623 |
/// \brief Runs the maximal cardinality search algorithm for the
|
deba@1967
|
624 |
/// whole graph.
|
deba@1967
|
625 |
///
|
deba@1967
|
626 |
/// This method runs the %MaxCardinalitySearch algorithm from all
|
deba@1967
|
627 |
/// unprocessed node of the graph.
|
deba@1967
|
628 |
///
|
deba@1967
|
629 |
///\note d.run(s) is just a shortcut of the following code.
|
deba@1967
|
630 |
///\code
|
deba@1967
|
631 |
/// d.init();
|
deba@1967
|
632 |
/// for (NodeIt it(graph); it != INVALID; ++it) {
|
deba@1967
|
633 |
/// if (!d.reached(it)) {
|
deba@1967
|
634 |
/// d.addSource(s);
|
deba@1967
|
635 |
/// d.start();
|
deba@1967
|
636 |
/// }
|
deba@1967
|
637 |
/// }
|
deba@1967
|
638 |
///\endcode
|
deba@1967
|
639 |
void run() {
|
deba@1967
|
640 |
init();
|
deba@1967
|
641 |
for (NodeIt it(*_graph); it != INVALID; ++it) {
|
deba@1967
|
642 |
if (!reached(it)) {
|
deba@1967
|
643 |
addSource(it);
|
deba@1967
|
644 |
start();
|
deba@1967
|
645 |
}
|
deba@1967
|
646 |
}
|
deba@1967
|
647 |
}
|
deba@1967
|
648 |
|
deba@1967
|
649 |
///@}
|
deba@1967
|
650 |
|
deba@1967
|
651 |
/// \name Query Functions
|
deba@1967
|
652 |
/// The result of the maximum cardinality search algorithm can be
|
deba@1967
|
653 |
/// obtained using these functions.
|
deba@1967
|
654 |
/// \n
|
deba@1967
|
655 |
/// Before the use of these functions, either run() or start() must be
|
deba@1967
|
656 |
/// called.
|
deba@1967
|
657 |
|
deba@1967
|
658 |
///@{
|
deba@1967
|
659 |
|
deba@1967
|
660 |
/// \brief The cardinality of a node.
|
deba@1967
|
661 |
///
|
deba@1967
|
662 |
/// Returns the cardinality of a node.
|
deba@1967
|
663 |
/// \pre \ref run() must be called before using this function.
|
deba@1967
|
664 |
/// \warning If node \c v in unreachable from the root the return value
|
deba@1967
|
665 |
/// of this funcion is undefined.
|
deba@1967
|
666 |
Value cardinality(Node node) const { return (*_cardinality)[node]; }
|
deba@1967
|
667 |
|
deba@1967
|
668 |
/// \brief Returns a reference to the NodeMap of cardinalities.
|
deba@1967
|
669 |
///
|
deba@1967
|
670 |
/// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
|
deba@1967
|
671 |
/// must be called before using this function.
|
deba@1967
|
672 |
const CardinalityMap &cardinalityMap() const { return *_cardinality;}
|
deba@1967
|
673 |
|
deba@1967
|
674 |
/// \brief Checks if a node is reachable from the root.
|
deba@1967
|
675 |
///
|
deba@1967
|
676 |
/// Returns \c true if \c v is reachable from the root.
|
deba@1967
|
677 |
/// \warning The source nodes are inditated as unreached.
|
deba@1967
|
678 |
/// \pre \ref run() must be called before using this function.
|
deba@1967
|
679 |
bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
|
deba@1967
|
680 |
|
deba@1967
|
681 |
/// \brief Checks if a node is processed.
|
deba@1967
|
682 |
///
|
deba@1967
|
683 |
/// Returns \c true if \c v is processed, i.e. the shortest
|
deba@1967
|
684 |
/// path to \c v has already found.
|
deba@1967
|
685 |
/// \pre \ref run() must be called before using this function.
|
deba@1967
|
686 |
bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
|
deba@1967
|
687 |
|
deba@1967
|
688 |
///@}
|
deba@1967
|
689 |
};
|
deba@1967
|
690 |
|
deba@1968
|
691 |
/// \brief Default traits class of MinimumCut class.
|
deba@1967
|
692 |
///
|
deba@1968
|
693 |
/// Default traits class of MinimumCut class.
|
deba@1967
|
694 |
/// \param Graph Graph type.
|
deba@1967
|
695 |
/// \param CapacityMap Type of length map.
|
deba@1967
|
696 |
template <typename _Graph, typename _CapacityMap>
|
deba@1968
|
697 |
struct MinimumCutDefaultTraits {
|
deba@1967
|
698 |
/// \brief The type of the capacity of the edges.
|
deba@1967
|
699 |
typedef typename _CapacityMap::Value Value;
|
deba@1967
|
700 |
|
deba@1967
|
701 |
/// The graph type the algorithm runs on.
|
deba@1967
|
702 |
typedef _Graph Graph;
|
deba@1967
|
703 |
|
deba@1967
|
704 |
/// The WorkGraph type which is an EraseableGraph
|
deba@1967
|
705 |
typedef ListUGraph WorkGraph;
|
deba@1967
|
706 |
|
deba@1967
|
707 |
/// \brief Instantiates a WorkGraph.
|
deba@1967
|
708 |
///
|
deba@1967
|
709 |
/// This function instantiates a \ref WorkGraph.
|
deba@1967
|
710 |
static WorkGraph *createWorkGraph() {
|
deba@1967
|
711 |
return new WorkGraph();
|
deba@1967
|
712 |
}
|
deba@1967
|
713 |
|
deba@1967
|
714 |
/// \brief The type of the map that stores the edge capacities.
|
deba@1967
|
715 |
///
|
deba@1967
|
716 |
/// The type of the map that stores the edge capacities.
|
deba@1967
|
717 |
/// It must meet the \ref concept::ReadMap "ReadMap" concept.
|
deba@1967
|
718 |
typedef _CapacityMap CapacityMap;
|
deba@1967
|
719 |
|
deba@1967
|
720 |
/// \brief Instantiates a CapacityMap.
|
deba@1967
|
721 |
///
|
deba@1967
|
722 |
/// This function instantiates a \ref CapacityMap.
|
deba@1967
|
723 |
#ifdef DOXYGEN
|
deba@1967
|
724 |
static CapacityMap *createCapacityMap(const Graph& graph)
|
deba@1967
|
725 |
#else
|
deba@1967
|
726 |
static CapacityMap *createCapacityMap(const Graph&)
|
deba@1967
|
727 |
#endif
|
deba@1967
|
728 |
{
|
deba@1967
|
729 |
throw UninitializedParameter();
|
deba@1967
|
730 |
}
|
deba@1967
|
731 |
|
deba@1967
|
732 |
/// \brief The WorkCapacityMap type
|
deba@1967
|
733 |
///
|
deba@1967
|
734 |
/// The type of the map that stores the working edge capacities.
|
deba@1967
|
735 |
typedef WorkGraph::UEdgeMap<Value> WorkCapacityMap;
|
deba@1967
|
736 |
|
deba@1967
|
737 |
/// \brief Instantiates a WorkCapacityMap.
|
deba@1967
|
738 |
///
|
deba@1967
|
739 |
/// This function instantiates a \ref WorkCapacityMap.
|
deba@1967
|
740 |
static WorkCapacityMap *createWorkCapacityMap(const WorkGraph& graph) {
|
deba@1967
|
741 |
return new WorkCapacityMap(graph);
|
deba@1967
|
742 |
}
|
deba@1967
|
743 |
|
deba@1967
|
744 |
/// \brief The cross reference type used by heap.
|
deba@1967
|
745 |
///
|
deba@1967
|
746 |
/// The cross reference type used by heap.
|
deba@1967
|
747 |
/// Usually it is \c Graph::NodeMap<int>.
|
deba@1967
|
748 |
typedef WorkGraph::NodeMap<int> HeapCrossRef;
|
deba@1967
|
749 |
|
deba@1967
|
750 |
/// \brief Instantiates a HeapCrossRef.
|
deba@1967
|
751 |
///
|
deba@1967
|
752 |
/// This function instantiates a \ref HeapCrossRef.
|
deba@1967
|
753 |
/// \param graph is the graph, to which we would like to define the
|
deba@1967
|
754 |
/// HeapCrossRef.
|
deba@1967
|
755 |
static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
|
deba@1967
|
756 |
return new HeapCrossRef(graph);
|
deba@1967
|
757 |
}
|
deba@1967
|
758 |
|
deba@1968
|
759 |
/// \brief The heap type used by MinimumCut algorithm.
|
deba@1967
|
760 |
///
|
deba@1968
|
761 |
/// The heap type used by MinimumCut algorithm. It should
|
deba@1967
|
762 |
/// maximalize the priorities and the heap's key type is
|
deba@1967
|
763 |
/// the work graph's node.
|
deba@1967
|
764 |
///
|
deba@1967
|
765 |
/// \sa BinHeap
|
deba@1968
|
766 |
/// \sa MinimumCut
|
deba@1968
|
767 |
typedef typename _minimum_cut_bits
|
deba@1967
|
768 |
::HeapSelector<CapacityMap>
|
deba@1967
|
769 |
::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>
|
deba@1967
|
770 |
::Heap Heap;
|
deba@1967
|
771 |
|
deba@1967
|
772 |
/// \brief Instantiates a Heap.
|
deba@1967
|
773 |
///
|
deba@1967
|
774 |
/// This function instantiates a \ref Heap.
|
deba@1967
|
775 |
/// \param crossref The cross reference of the heap.
|
deba@1967
|
776 |
static Heap *createHeap(HeapCrossRef& crossref) {
|
deba@1967
|
777 |
return new Heap(crossref);
|
deba@1967
|
778 |
}
|
deba@1967
|
779 |
|
deba@1967
|
780 |
/// \brief Map from the WorkGraph's node type to the Graph's node type.
|
deba@1967
|
781 |
///
|
deba@1967
|
782 |
/// Map from the WorkGraph's node type to the Graph's node type.
|
deba@1967
|
783 |
typedef typename WorkGraph
|
deba@1967
|
784 |
::template NodeMap<typename Graph::Node> NodeRefMap;
|
deba@1967
|
785 |
|
deba@1967
|
786 |
/// \brief Instantiates a NodeRefMap.
|
deba@1967
|
787 |
///
|
deba@1967
|
788 |
/// This function instantiates a \ref NodeRefMap.
|
deba@1967
|
789 |
static NodeRefMap *createNodeRefMap(const WorkGraph& graph) {
|
deba@1967
|
790 |
return new NodeRefMap(graph);
|
deba@1967
|
791 |
}
|
deba@1967
|
792 |
|
deba@1967
|
793 |
/// \brief Map from the Graph's node type to the Graph's node type.
|
deba@1967
|
794 |
///
|
deba@1967
|
795 |
/// Map from the Graph's node type to the Graph's node type.
|
deba@1967
|
796 |
typedef typename Graph
|
deba@1967
|
797 |
::template NodeMap<typename Graph::Node> ListRefMap;
|
deba@1967
|
798 |
|
deba@1967
|
799 |
/// \brief Instantiates a ListRefMap.
|
deba@1967
|
800 |
///
|
deba@1967
|
801 |
/// This function instantiates a \ref ListRefMap.
|
deba@1967
|
802 |
static ListRefMap *createListRefMap(const Graph& graph) {
|
deba@1967
|
803 |
return new ListRefMap(graph);
|
deba@1967
|
804 |
}
|
deba@1967
|
805 |
|
deba@1967
|
806 |
|
deba@1967
|
807 |
};
|
deba@1967
|
808 |
|
deba@1968
|
809 |
namespace _minimum_cut_bits {
|
deba@1967
|
810 |
template <typename _Key>
|
deba@1967
|
811 |
class LastTwoMap {
|
deba@1967
|
812 |
public:
|
deba@1967
|
813 |
typedef _Key Key;
|
deba@1967
|
814 |
typedef bool Value;
|
deba@1967
|
815 |
|
deba@1967
|
816 |
LastTwoMap(int _num) : num(_num) {}
|
deba@1967
|
817 |
void set(const Key& key, bool val) {
|
deba@1967
|
818 |
if (!val) return;
|
deba@1967
|
819 |
--num;
|
deba@1967
|
820 |
if (num > 1) return;
|
deba@1967
|
821 |
keys[num] = key;
|
deba@1967
|
822 |
}
|
deba@1967
|
823 |
|
deba@1967
|
824 |
Key operator[](int index) const { return keys[index]; }
|
deba@1967
|
825 |
private:
|
deba@1967
|
826 |
Key keys[2];
|
deba@1967
|
827 |
int num;
|
deba@1967
|
828 |
};
|
deba@1967
|
829 |
}
|
deba@1967
|
830 |
|
deba@1967
|
831 |
/// \ingroup topology
|
deba@1967
|
832 |
///
|
deba@1968
|
833 |
/// \brief Calculates the minimum cut in an undirected graph.
|
deba@1967
|
834 |
///
|
deba@1968
|
835 |
/// Calculates the minimum cut in an undirected graph.
|
deba@1967
|
836 |
/// The algorithm separates the graph's nodes to two partitions with the
|
deba@1968
|
837 |
/// minimum sum of edge capacities between the two partitions. The
|
deba@1967
|
838 |
/// algorithm can be used to test the network reliability specifically
|
deba@1967
|
839 |
/// to test how many links have to be destroyed in the network to split it
|
deba@1967
|
840 |
/// at least two distinict subnetwork.
|
deba@1967
|
841 |
///
|
deba@1967
|
842 |
/// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci
|
deba@1967
|
843 |
/// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity
|
deba@1967
|
844 |
/// map is used then it uses LinearHeap which results O(n*e) time complexity.
|
deba@1967
|
845 |
#ifdef DOXYGEN
|
deba@1967
|
846 |
template <typename _Graph, typename _CapacityMap, typename _Traits>
|
deba@1967
|
847 |
#else
|
deba@1967
|
848 |
template <typename _Graph = ListUGraph,
|
deba@1967
|
849 |
typename _CapacityMap = typename _Graph::template UEdgeMap<int>,
|
deba@1968
|
850 |
typename _Traits = MinimumCutDefaultTraits<_Graph, _CapacityMap> >
|
deba@1967
|
851 |
#endif
|
deba@1968
|
852 |
class MinimumCut {
|
deba@1967
|
853 |
public:
|
deba@1967
|
854 |
/// \brief \ref Exception for uninitialized parameters.
|
deba@1967
|
855 |
///
|
deba@1967
|
856 |
/// This error represents problems in the initialization
|
deba@1967
|
857 |
/// of the parameters of the algorithms.
|
deba@1967
|
858 |
class UninitializedParameter : public lemon::UninitializedParameter {
|
deba@1967
|
859 |
public:
|
deba@1967
|
860 |
virtual const char* exceptionName() const {
|
deba@1968
|
861 |
return "lemon::MinimumCut::UninitializedParameter";
|
deba@1967
|
862 |
}
|
deba@1967
|
863 |
};
|
deba@1967
|
864 |
|
deba@1967
|
865 |
|
deba@1967
|
866 |
private:
|
deba@1967
|
867 |
|
deba@1967
|
868 |
typedef _Traits Traits;
|
deba@1967
|
869 |
/// The type of the underlying graph.
|
deba@1967
|
870 |
typedef typename Traits::Graph Graph;
|
deba@1967
|
871 |
|
deba@1967
|
872 |
/// The type of the capacity of the edges.
|
deba@1967
|
873 |
typedef typename Traits::CapacityMap::Value Value;
|
deba@1967
|
874 |
/// The type of the map that stores the edge capacities.
|
deba@1967
|
875 |
typedef typename Traits::CapacityMap CapacityMap;
|
deba@1967
|
876 |
/// The type of the work graph
|
deba@1967
|
877 |
typedef typename Traits::WorkGraph WorkGraph;
|
deba@1967
|
878 |
/// The type of the work capacity map
|
deba@1967
|
879 |
typedef typename Traits::WorkCapacityMap WorkCapacityMap;
|
deba@1967
|
880 |
/// The cross reference type used for the current heap.
|
deba@1967
|
881 |
typedef typename Traits::HeapCrossRef HeapCrossRef;
|
deba@1967
|
882 |
/// The heap type used by the max cardinality algorithm.
|
deba@1967
|
883 |
typedef typename Traits::Heap Heap;
|
deba@1967
|
884 |
/// The node refrefernces between the original and work graph type.
|
deba@1967
|
885 |
typedef typename Traits::NodeRefMap NodeRefMap;
|
deba@1967
|
886 |
/// The list node refrefernces in the original graph type.
|
deba@1967
|
887 |
typedef typename Traits::ListRefMap ListRefMap;
|
deba@1967
|
888 |
|
deba@1967
|
889 |
public:
|
deba@1967
|
890 |
|
deba@1967
|
891 |
///\name Named template parameters
|
deba@1967
|
892 |
|
deba@1967
|
893 |
///@{
|
deba@1967
|
894 |
|
deba@1967
|
895 |
struct DefNeutralCapacityTraits : public Traits {
|
deba@1967
|
896 |
typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
|
deba@1967
|
897 |
static CapacityMap *createCapacityMap(const Graph&) {
|
deba@1967
|
898 |
return new CapacityMap();
|
deba@1967
|
899 |
}
|
deba@1967
|
900 |
};
|
deba@1967
|
901 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
deba@1967
|
902 |
/// the capacity type to constMap<UEdge, int, 1>()
|
deba@1967
|
903 |
///
|
deba@1967
|
904 |
/// \ref named-templ-param "Named parameter" for setting
|
deba@1967
|
905 |
/// the capacity type to constMap<UEdge, int, 1>()
|
deba@1967
|
906 |
struct DefNeutralCapacity
|
deba@1968
|
907 |
: public MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> {
|
deba@1968
|
908 |
typedef MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
|
deba@1967
|
909 |
};
|
deba@1967
|
910 |
|
deba@1967
|
911 |
|
deba@1967
|
912 |
template <class H, class CR>
|
deba@1967
|
913 |
struct DefHeapTraits : public Traits {
|
deba@1967
|
914 |
typedef CR HeapCrossRef;
|
deba@1967
|
915 |
typedef H Heap;
|
deba@1967
|
916 |
static HeapCrossRef *createHeapCrossRef(const WorkGraph &) {
|
deba@1967
|
917 |
throw UninitializedParameter();
|
deba@1967
|
918 |
}
|
deba@1967
|
919 |
static Heap *createHeap(HeapCrossRef &) {
|
deba@1967
|
920 |
throw UninitializedParameter();
|
deba@1967
|
921 |
}
|
deba@1967
|
922 |
};
|
deba@1967
|
923 |
/// \brief \ref named-templ-param "Named parameter" for setting heap
|
deba@1967
|
924 |
/// and cross reference type
|
deba@1967
|
925 |
///
|
deba@1967
|
926 |
/// \ref named-templ-param "Named parameter" for setting heap and cross
|
deba@1967
|
927 |
/// reference type
|
deba@1967
|
928 |
template <class H, class CR = typename Graph::template NodeMap<int> >
|
deba@1967
|
929 |
struct DefHeap
|
deba@1968
|
930 |
: public MinimumCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {
|
deba@1968
|
931 |
typedef MinimumCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
|
deba@1967
|
932 |
};
|
deba@1967
|
933 |
|
deba@1967
|
934 |
template <class H, class CR>
|
deba@1967
|
935 |
struct DefStandardHeapTraits : public Traits {
|
deba@1967
|
936 |
typedef CR HeapCrossRef;
|
deba@1967
|
937 |
typedef H Heap;
|
deba@1967
|
938 |
static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
|
deba@1967
|
939 |
return new HeapCrossRef(graph);
|
deba@1967
|
940 |
}
|
deba@1967
|
941 |
static Heap *createHeap(HeapCrossRef &crossref) {
|
deba@1967
|
942 |
return new Heap(crossref);
|
deba@1967
|
943 |
}
|
deba@1967
|
944 |
};
|
deba@1967
|
945 |
|
deba@1967
|
946 |
/// \brief \ref named-templ-param "Named parameter" for setting heap and
|
deba@1967
|
947 |
/// cross reference type with automatic allocation
|
deba@1967
|
948 |
///
|
deba@1967
|
949 |
/// \ref named-templ-param "Named parameter" for setting heap and cross
|
deba@1967
|
950 |
/// reference type. It can allocate the heap and the cross reference
|
deba@1967
|
951 |
/// object if the cross reference's constructor waits for the graph as
|
deba@1967
|
952 |
/// parameter and the heap's constructor waits for the cross reference.
|
deba@1967
|
953 |
template <class H, class CR = typename Graph::template NodeMap<int> >
|
deba@1967
|
954 |
struct DefStandardHeap
|
deba@1968
|
955 |
: public MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {
|
deba@1968
|
956 |
typedef MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >
|
deba@1967
|
957 |
Create;
|
deba@1967
|
958 |
};
|
deba@1967
|
959 |
|
deba@1967
|
960 |
///@}
|
deba@1967
|
961 |
|
deba@1967
|
962 |
|
deba@1967
|
963 |
private:
|
deba@1967
|
964 |
/// Pointer to the underlying graph.
|
deba@1967
|
965 |
const Graph *_graph;
|
deba@1967
|
966 |
/// Pointer to the capacity map
|
deba@1967
|
967 |
const CapacityMap *_capacity;
|
deba@1967
|
968 |
/// \brief Indicates if \ref _capacity is locally allocated
|
deba@1967
|
969 |
/// (\c true) or not.
|
deba@1967
|
970 |
bool local_capacity;
|
deba@1967
|
971 |
|
deba@1967
|
972 |
/// Pointer to the work graph.
|
deba@1967
|
973 |
WorkGraph *_work_graph;
|
deba@1967
|
974 |
/// \brief Indicates if \ref _work_graph is locally allocated
|
deba@1967
|
975 |
/// (\c true) or not.
|
deba@1967
|
976 |
bool local_work_graph;
|
deba@1967
|
977 |
/// Pointer to the work capacity map
|
deba@1967
|
978 |
WorkCapacityMap *_work_capacity;
|
deba@1967
|
979 |
/// \brief Indicates if \ref _work_capacity is locally allocated
|
deba@1967
|
980 |
/// (\c true) or not.
|
deba@1967
|
981 |
bool local_work_capacity;
|
deba@1967
|
982 |
/// Pointer to the heap cross references.
|
deba@1967
|
983 |
HeapCrossRef *_heap_cross_ref;
|
deba@1967
|
984 |
/// \brief Indicates if \ref _heap_cross_ref is locally allocated
|
deba@1967
|
985 |
/// (\c true) or not.
|
deba@1967
|
986 |
bool local_heap_cross_ref;
|
deba@1967
|
987 |
/// Pointer to the heap.
|
deba@1967
|
988 |
Heap *_heap;
|
deba@1967
|
989 |
/// Indicates if \ref _heap is locally allocated (\c true) or not.
|
deba@1967
|
990 |
bool local_heap;
|
deba@1967
|
991 |
|
deba@1968
|
992 |
/// The minimum cut value.
|
deba@1968
|
993 |
Value _minimum_cut;
|
deba@1967
|
994 |
/// The number of the nodes of the work graph.
|
deba@1967
|
995 |
int _node_num;
|
deba@1967
|
996 |
/// The first and last node of the min cut in the next list;
|
deba@1967
|
997 |
typename Graph::Node _first_node, _last_node;
|
deba@1967
|
998 |
|
deba@1967
|
999 |
/// \brief The first and last element in the list associated
|
deba@1967
|
1000 |
/// to the work graph node.
|
deba@1967
|
1001 |
NodeRefMap *_first, *_last;
|
deba@1967
|
1002 |
/// \brief The next node in the node lists.
|
deba@1967
|
1003 |
ListRefMap *_next;
|
deba@1967
|
1004 |
|
deba@1967
|
1005 |
void create_structures() {
|
deba@1967
|
1006 |
if (!_capacity) {
|
deba@1967
|
1007 |
local_capacity = true;
|
deba@1967
|
1008 |
_capacity = Traits::createCapacityMap(*_graph);
|
deba@1967
|
1009 |
}
|
deba@1967
|
1010 |
if(!_work_graph) {
|
deba@1967
|
1011 |
local_work_graph = true;
|
deba@1967
|
1012 |
_work_graph = Traits::createWorkGraph();
|
deba@1967
|
1013 |
}
|
deba@1967
|
1014 |
if(!_work_capacity) {
|
deba@1967
|
1015 |
local_work_capacity = true;
|
deba@1967
|
1016 |
_work_capacity = Traits::createWorkCapacityMap(*_work_graph);
|
deba@1967
|
1017 |
}
|
deba@1967
|
1018 |
|
deba@1967
|
1019 |
_first = Traits::createNodeRefMap(*_work_graph);
|
deba@1967
|
1020 |
_last = Traits::createNodeRefMap(*_work_graph);
|
deba@1967
|
1021 |
|
deba@1967
|
1022 |
_next = Traits::createListRefMap(*_graph);
|
deba@1967
|
1023 |
|
deba@1967
|
1024 |
typename Graph::template NodeMap<typename WorkGraph::Node> ref(*_graph);
|
deba@1967
|
1025 |
|
deba@1967
|
1026 |
for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
|
deba@1967
|
1027 |
_next->set(it, INVALID);
|
deba@1967
|
1028 |
typename WorkGraph::Node node = _work_graph->addNode();
|
deba@1967
|
1029 |
_first->set(node, it);
|
deba@1967
|
1030 |
_last->set(node, it);
|
deba@1967
|
1031 |
ref.set(it, node);
|
deba@1967
|
1032 |
}
|
deba@1967
|
1033 |
|
deba@1967
|
1034 |
for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
|
deba@1967
|
1035 |
if (_graph->source(it) == _graph->target(it)) continue;
|
deba@1967
|
1036 |
typename WorkGraph::UEdge uedge =
|
deba@1967
|
1037 |
_work_graph->addEdge(ref[_graph->source(it)],
|
deba@1967
|
1038 |
ref[_graph->target(it)]);
|
deba@1967
|
1039 |
_work_capacity->set(uedge, (*_capacity)[it]);
|
deba@1967
|
1040 |
|
deba@1967
|
1041 |
}
|
deba@1967
|
1042 |
|
deba@1967
|
1043 |
if (!_heap_cross_ref) {
|
deba@1967
|
1044 |
local_heap_cross_ref = true;
|
deba@1967
|
1045 |
_heap_cross_ref = Traits::createHeapCrossRef(*_work_graph);
|
deba@1967
|
1046 |
}
|
deba@1967
|
1047 |
if (!_heap) {
|
deba@1967
|
1048 |
local_heap = true;
|
deba@1967
|
1049 |
_heap = Traits::createHeap(*_heap_cross_ref);
|
deba@1967
|
1050 |
}
|
deba@1967
|
1051 |
}
|
deba@1967
|
1052 |
|
deba@1967
|
1053 |
public :
|
deba@1967
|
1054 |
|
deba@1968
|
1055 |
typedef MinimumCut Create;
|
deba@1967
|
1056 |
|
deba@1967
|
1057 |
|
deba@1967
|
1058 |
/// \brief Constructor.
|
deba@1967
|
1059 |
///
|
deba@1967
|
1060 |
///\param graph the graph the algorithm will run on.
|
deba@1967
|
1061 |
///\param capacity the capacity map used by the algorithm.
|
deba@1968
|
1062 |
MinimumCut(const Graph& graph, const CapacityMap& capacity)
|
deba@1967
|
1063 |
: _graph(&graph),
|
deba@1967
|
1064 |
_capacity(&capacity), local_capacity(false),
|
deba@1967
|
1065 |
_work_graph(0), local_work_graph(false),
|
deba@1967
|
1066 |
_work_capacity(0), local_work_capacity(false),
|
deba@1967
|
1067 |
_heap_cross_ref(0), local_heap_cross_ref(false),
|
deba@1967
|
1068 |
_heap(0), local_heap(false),
|
deba@1967
|
1069 |
_first(0), _last(0), _next(0) {}
|
deba@1967
|
1070 |
|
deba@1967
|
1071 |
/// \brief Constructor.
|
deba@1967
|
1072 |
///
|
deba@1967
|
1073 |
/// This constructor can be used only when the Traits class
|
deba@1967
|
1074 |
/// defines how can we instantiate a local capacity map.
|
deba@1967
|
1075 |
/// If the DefNeutralCapacity used the algorithm automatically
|
deba@1967
|
1076 |
/// construct the capacity map.
|
deba@1967
|
1077 |
///
|
deba@1967
|
1078 |
///\param graph the graph the algorithm will run on.
|
deba@1968
|
1079 |
MinimumCut(const Graph& graph)
|
deba@1967
|
1080 |
: _graph(&graph),
|
deba@1967
|
1081 |
_capacity(0), local_capacity(false),
|
deba@1967
|
1082 |
_work_graph(0), local_work_graph(false),
|
deba@1967
|
1083 |
_work_capacity(0), local_work_capacity(false),
|
deba@1967
|
1084 |
_heap_cross_ref(0), local_heap_cross_ref(false),
|
deba@1967
|
1085 |
_heap(0), local_heap(false),
|
deba@1967
|
1086 |
_first(0), _last(0), _next(0) {}
|
deba@1967
|
1087 |
|
deba@1967
|
1088 |
/// \brief Destructor.
|
deba@1967
|
1089 |
///
|
deba@1967
|
1090 |
/// Destructor.
|
deba@1968
|
1091 |
~MinimumCut() {
|
deba@1967
|
1092 |
if (local_heap) delete _heap;
|
deba@1967
|
1093 |
if (local_heap_cross_ref) delete _heap_cross_ref;
|
deba@1967
|
1094 |
if (_first) delete _first;
|
deba@1967
|
1095 |
if (_last) delete _last;
|
deba@1967
|
1096 |
if (_next) delete _next;
|
deba@1967
|
1097 |
if (local_work_capacity) delete _work_capacity;
|
deba@1967
|
1098 |
if (local_work_graph) delete _work_graph;
|
deba@1967
|
1099 |
if (local_capacity) delete _capacity;
|
deba@1967
|
1100 |
}
|
deba@1967
|
1101 |
|
deba@1967
|
1102 |
/// \brief Sets the heap and the cross reference used by algorithm.
|
deba@1967
|
1103 |
///
|
deba@1967
|
1104 |
/// Sets the heap and the cross reference used by algorithm.
|
deba@1967
|
1105 |
/// If you don't use this function before calling \ref run(),
|
deba@1967
|
1106 |
/// it will allocate one. The destuctor deallocates this
|
deba@1967
|
1107 |
/// automatically allocated heap and cross reference, of course.
|
deba@1967
|
1108 |
/// \return <tt> (*this) </tt>
|
deba@1968
|
1109 |
MinimumCut &heap(Heap& heap, HeapCrossRef &crossRef)
|
deba@1967
|
1110 |
{
|
deba@1967
|
1111 |
if (local_heap_cross_ref) {
|
deba@1967
|
1112 |
delete _heap_cross_ref;
|
deba@1967
|
1113 |
local_heap_cross_ref=false;
|
deba@1967
|
1114 |
}
|
deba@1967
|
1115 |
_heap_cross_ref = &crossRef;
|
deba@1967
|
1116 |
if (local_heap) {
|
deba@1967
|
1117 |
delete _heap;
|
deba@1967
|
1118 |
local_heap=false;
|
deba@1967
|
1119 |
}
|
deba@1967
|
1120 |
_heap = &heap;
|
deba@1967
|
1121 |
return *this;
|
deba@1967
|
1122 |
}
|
deba@1967
|
1123 |
|
deba@1967
|
1124 |
/// \brief Sets the work graph.
|
deba@1967
|
1125 |
///
|
deba@1967
|
1126 |
/// Sets the work graph used by algorithm.
|
deba@1967
|
1127 |
/// If you don't use this function before calling \ref run(),
|
deba@1967
|
1128 |
/// it will allocate one. The destuctor deallocates this
|
deba@1967
|
1129 |
/// automatically allocated graph, of course.
|
deba@1967
|
1130 |
/// \return <tt> (*this) </tt>
|
deba@1968
|
1131 |
MinimumCut &workGraph(WorkGraph& work_graph)
|
deba@1967
|
1132 |
{
|
deba@1967
|
1133 |
if(local_work_graph) {
|
deba@1967
|
1134 |
delete _work_graph;
|
deba@1967
|
1135 |
local_work_graph=false;
|
deba@1967
|
1136 |
}
|
deba@1967
|
1137 |
_work_graph = &work_graph;
|
deba@1967
|
1138 |
return *this;
|
deba@1967
|
1139 |
}
|
deba@1967
|
1140 |
|
deba@1967
|
1141 |
/// \brief Sets the work capacity map.
|
deba@1967
|
1142 |
///
|
deba@1967
|
1143 |
/// Sets the work capacity map used by algorithm.
|
deba@1967
|
1144 |
/// If you don't use this function before calling \ref run(),
|
deba@1967
|
1145 |
/// it will allocate one. The destuctor deallocates this
|
deba@1967
|
1146 |
/// automatically allocated graph, of course.
|
deba@1967
|
1147 |
/// \return <tt> (*this) </tt>
|
deba@1968
|
1148 |
MinimumCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
|
deba@1967
|
1149 |
{
|
deba@1967
|
1150 |
if(local_work_capacity) {
|
deba@1967
|
1151 |
delete _work_capacity;
|
deba@1967
|
1152 |
local_work_capacity=false;
|
deba@1967
|
1153 |
}
|
deba@1967
|
1154 |
_work_capacity = &work_capacity_map;
|
deba@1967
|
1155 |
return *this;
|
deba@1967
|
1156 |
}
|
deba@1967
|
1157 |
|
deba@1967
|
1158 |
/// \name Execution control
|
deba@1967
|
1159 |
/// The simplest way to execute the algorithm is to use
|
deba@1967
|
1160 |
/// one of the member functions called \c run().
|
deba@1967
|
1161 |
/// \n
|
deba@1967
|
1162 |
/// If you need more control on the execution,
|
deba@1967
|
1163 |
/// first you must call \ref init() and then call the start()
|
deba@1967
|
1164 |
/// or proper times the processNextPhase() member functions.
|
deba@1967
|
1165 |
|
deba@1967
|
1166 |
///@{
|
deba@1967
|
1167 |
|
deba@1967
|
1168 |
/// \brief Initializes the internal data structures.
|
deba@1967
|
1169 |
///
|
deba@1967
|
1170 |
/// Initializes the internal data structures.
|
deba@1967
|
1171 |
void init() {
|
deba@1967
|
1172 |
create_structures();
|
deba@1967
|
1173 |
_first_node = _last_node = INVALID;
|
deba@1967
|
1174 |
_node_num = countNodes(*_graph);
|
deba@1967
|
1175 |
}
|
deba@1967
|
1176 |
|
deba@1967
|
1177 |
/// \brief Processes the next phase
|
deba@1967
|
1178 |
///
|
deba@1967
|
1179 |
/// Processes the next phase in the algorithm. The function
|
deba@1967
|
1180 |
/// should be called countNodes(graph) - 1 times to get
|
deba@1968
|
1181 |
/// surely the minimum cut in the graph. The
|
deba@1967
|
1182 |
///
|
deba@1967
|
1183 |
///\return %True when the algorithm finished.
|
deba@1967
|
1184 |
bool processNextPhase() {
|
deba@1967
|
1185 |
if (_node_num <= 1) return true;
|
deba@1968
|
1186 |
using namespace _minimum_cut_bits;
|
deba@1967
|
1187 |
|
deba@1967
|
1188 |
typedef typename WorkGraph::Node Node;
|
deba@1967
|
1189 |
typedef typename WorkGraph::NodeIt NodeIt;
|
deba@1967
|
1190 |
typedef typename WorkGraph::UEdge UEdge;
|
deba@1967
|
1191 |
typedef typename WorkGraph::IncEdgeIt IncEdgeIt;
|
deba@1967
|
1192 |
|
deba@1967
|
1193 |
typedef typename MaxCardinalitySearch<WorkGraph, WorkCapacityMap>::
|
deba@1967
|
1194 |
template DefHeap<Heap, HeapCrossRef>::
|
deba@1967
|
1195 |
template DefCardinalityMap<NullMap<Node, Value> >::
|
deba@1967
|
1196 |
template DefProcessedMap<LastTwoMap<Node> >::
|
deba@1967
|
1197 |
Create MaxCardinalitySearch;
|
deba@1967
|
1198 |
|
deba@1967
|
1199 |
MaxCardinalitySearch mcs(*_work_graph, *_work_capacity);
|
deba@1967
|
1200 |
for (NodeIt it(*_work_graph); it != INVALID; ++it) {
|
deba@1967
|
1201 |
_heap_cross_ref->set(it, Heap::PRE_HEAP);
|
deba@1967
|
1202 |
}
|
deba@1967
|
1203 |
mcs.heap(*_heap, *_heap_cross_ref);
|
deba@1967
|
1204 |
|
deba@1967
|
1205 |
LastTwoMap<Node> last_two_nodes(_node_num);
|
deba@1967
|
1206 |
mcs.processedMap(last_two_nodes);
|
deba@1967
|
1207 |
|
deba@1967
|
1208 |
NullMap<Node, Value> cardinality;
|
deba@1967
|
1209 |
mcs.cardinalityMap(cardinality);
|
deba@1967
|
1210 |
|
deba@1967
|
1211 |
mcs.run();
|
deba@1967
|
1212 |
|
deba@1967
|
1213 |
Node new_node = _work_graph->addNode();
|
deba@1967
|
1214 |
|
deba@1967
|
1215 |
typename WorkGraph::template NodeMap<UEdge> edges(*_work_graph, INVALID);
|
deba@1967
|
1216 |
|
deba@1967
|
1217 |
Node first_node = last_two_nodes[0];
|
deba@1967
|
1218 |
Node second_node = last_two_nodes[1];
|
deba@1967
|
1219 |
|
deba@1967
|
1220 |
_next->set((*_last)[first_node], (*_first)[second_node]);
|
deba@1967
|
1221 |
_first->set(new_node, (*_first)[first_node]);
|
deba@1967
|
1222 |
_last->set(new_node, (*_last)[second_node]);
|
deba@1967
|
1223 |
|
deba@1967
|
1224 |
Value current_cut = 0;
|
deba@1967
|
1225 |
for (IncEdgeIt it(*_work_graph, first_node); it != INVALID; ++it) {
|
deba@1967
|
1226 |
Node node = _work_graph->runningNode(it);
|
deba@1967
|
1227 |
current_cut += (*_work_capacity)[it];
|
deba@1967
|
1228 |
if (node == second_node) continue;
|
deba@1967
|
1229 |
if (edges[node] == INVALID) {
|
deba@1967
|
1230 |
edges[node] = _work_graph->addEdge(new_node, node);
|
deba@1967
|
1231 |
(*_work_capacity)[edges[node]] = (*_work_capacity)[it];
|
deba@1967
|
1232 |
} else {
|
deba@1967
|
1233 |
(*_work_capacity)[edges[node]] += (*_work_capacity)[it];
|
deba@1967
|
1234 |
}
|
deba@1967
|
1235 |
}
|
deba@1967
|
1236 |
|
deba@1968
|
1237 |
if (_first_node == INVALID || current_cut < _minimum_cut) {
|
deba@1967
|
1238 |
_first_node = (*_first)[first_node];
|
deba@1967
|
1239 |
_last_node = (*_last)[first_node];
|
deba@1968
|
1240 |
_minimum_cut = current_cut;
|
deba@1967
|
1241 |
}
|
deba@1967
|
1242 |
|
deba@1967
|
1243 |
_work_graph->erase(first_node);
|
deba@1967
|
1244 |
|
deba@1967
|
1245 |
for (IncEdgeIt it(*_work_graph, second_node); it != INVALID; ++it) {
|
deba@1967
|
1246 |
Node node = _work_graph->runningNode(it);
|
deba@1967
|
1247 |
if (edges[node] == INVALID) {
|
deba@1967
|
1248 |
edges[node] = _work_graph->addEdge(new_node, node);
|
deba@1967
|
1249 |
(*_work_capacity)[edges[node]] = (*_work_capacity)[it];
|
deba@1967
|
1250 |
} else {
|
deba@1967
|
1251 |
(*_work_capacity)[edges[node]] += (*_work_capacity)[it];
|
deba@1967
|
1252 |
}
|
deba@1967
|
1253 |
}
|
deba@1967
|
1254 |
_work_graph->erase(second_node);
|
deba@1967
|
1255 |
|
deba@1967
|
1256 |
--_node_num;
|
deba@1967
|
1257 |
return _node_num == 1;
|
deba@1967
|
1258 |
}
|
deba@1967
|
1259 |
|
deba@1967
|
1260 |
/// \brief Executes the algorithm.
|
deba@1967
|
1261 |
///
|
deba@1967
|
1262 |
/// Executes the algorithm.
|
deba@1967
|
1263 |
///
|
deba@1967
|
1264 |
/// \pre init() must be called
|
deba@1967
|
1265 |
void start() {
|
deba@1967
|
1266 |
while (!processNextPhase());
|
deba@1967
|
1267 |
}
|
deba@1967
|
1268 |
|
deba@1967
|
1269 |
|
deba@1968
|
1270 |
/// \brief Runs %MinimumCut algorithm.
|
deba@1967
|
1271 |
///
|
deba@1968
|
1272 |
/// This method runs the %Minimum cut algorithm
|
deba@1967
|
1273 |
///
|
deba@1967
|
1274 |
/// \note mc.run(s) is just a shortcut of the following code.
|
deba@1967
|
1275 |
///\code
|
deba@1967
|
1276 |
/// mc.init();
|
deba@1967
|
1277 |
/// mc.start();
|
deba@1967
|
1278 |
///\endcode
|
deba@1967
|
1279 |
void run() {
|
deba@1967
|
1280 |
init();
|
deba@1967
|
1281 |
start();
|
deba@1967
|
1282 |
}
|
deba@1967
|
1283 |
|
deba@1967
|
1284 |
///@}
|
deba@1967
|
1285 |
|
deba@1967
|
1286 |
/// \name Query Functions
|
deba@1968
|
1287 |
/// The result of the %MinimumCut algorithm can be obtained using these
|
deba@1967
|
1288 |
/// functions.\n
|
deba@1967
|
1289 |
/// Before the use of these functions,
|
deba@1967
|
1290 |
/// either run() or start() must be called.
|
deba@1967
|
1291 |
|
deba@1967
|
1292 |
///@{
|
deba@1967
|
1293 |
|
deba@1968
|
1294 |
/// \brief Returns the minimum cut value.
|
deba@1967
|
1295 |
///
|
deba@1968
|
1296 |
/// Returns the minimum cut value if the algorithm finished.
|
deba@1967
|
1297 |
/// After the first processNextPhase() it is a value of a
|
deba@1967
|
1298 |
/// valid cut in the graph.
|
deba@1967
|
1299 |
Value minCut() const {
|
deba@1968
|
1300 |
return _minimum_cut;
|
deba@1967
|
1301 |
}
|
deba@1967
|
1302 |
|
deba@1968
|
1303 |
/// \brief Returns a minimum cut in a NodeMap.
|
deba@1967
|
1304 |
///
|
deba@1967
|
1305 |
/// It sets the nodes of one of the two partitions to true in
|
deba@1967
|
1306 |
/// the given BoolNodeMap. The map contains a valid cut if the
|
deba@1967
|
1307 |
/// map have been setted false previously.
|
deba@1967
|
1308 |
template <typename NodeMap>
|
deba@1967
|
1309 |
Value quickMinCut(NodeMap& nodeMap) const {
|
deba@1967
|
1310 |
for (typename Graph::Node it = _first_node;
|
deba@1967
|
1311 |
it != _last_node; it = (*_next)[it]) {
|
deba@1967
|
1312 |
nodeMap.set(it, true);
|
deba@1967
|
1313 |
}
|
deba@1967
|
1314 |
nodeMap.set(_last_node, true);
|
deba@1967
|
1315 |
return minCut();
|
deba@1967
|
1316 |
}
|
deba@1967
|
1317 |
|
deba@1968
|
1318 |
/// \brief Returns a minimum cut in a NodeMap.
|
deba@1967
|
1319 |
///
|
deba@1967
|
1320 |
/// It sets the nodes of one of the two partitions to true and
|
deba@1967
|
1321 |
/// the other partition to false. The function first set all of the
|
deba@1967
|
1322 |
/// nodes to false and after it call the quickMinCut() member.
|
deba@1967
|
1323 |
template <typename NodeMap>
|
deba@1967
|
1324 |
Value minCut(NodeMap& nodeMap) const {
|
deba@1967
|
1325 |
for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
|
deba@1967
|
1326 |
nodeMap.set(it, false);
|
deba@1967
|
1327 |
}
|
deba@1967
|
1328 |
quickMinCut(nodeMap);
|
deba@1967
|
1329 |
return minCut();
|
deba@1967
|
1330 |
}
|
deba@1967
|
1331 |
|
deba@1968
|
1332 |
/// \brief Returns a minimum cut in an EdgeMap.
|
deba@1967
|
1333 |
///
|
deba@1967
|
1334 |
/// If an undirected edge is cut edge then it will be
|
deba@1967
|
1335 |
/// setted to true and the others will be setted to false in the given map.
|
deba@1967
|
1336 |
template <typename EdgeMap>
|
deba@1967
|
1337 |
Value cutEdges(EdgeMap& edgeMap) const {
|
deba@1967
|
1338 |
typename Graph::template NodeMap<bool> cut(*_graph, false);
|
deba@1967
|
1339 |
quickMinCut(cut);
|
deba@1967
|
1340 |
for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
|
deba@1967
|
1341 |
edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
|
deba@1967
|
1342 |
}
|
deba@1967
|
1343 |
return minCut();
|
deba@1967
|
1344 |
}
|
deba@1967
|
1345 |
|
deba@1967
|
1346 |
///@}
|
deba@1967
|
1347 |
|
deba@1967
|
1348 |
};
|
deba@1967
|
1349 |
}
|
deba@1967
|
1350 |
|
deba@1967
|
1351 |
#endif
|