alpar@2409
|
1 |
/* -*- C++ -*-
|
alpar@2409
|
2 |
*
|
alpar@2409
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
alpar@2409
|
4 |
*
|
alpar@2409
|
5 |
* Copyright (C) 2003-2007
|
alpar@2409
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@2409
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
alpar@2409
|
8 |
*
|
alpar@2409
|
9 |
* Permission to use, modify and distribute this software is granted
|
alpar@2409
|
10 |
* provided that this copyright notice appears in all copies. For
|
alpar@2409
|
11 |
* precise terms see the accompanying LICENSE file.
|
alpar@2409
|
12 |
*
|
alpar@2409
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@2409
|
14 |
* express or implied, and with no claim as to its suitability for any
|
alpar@2409
|
15 |
* purpose.
|
alpar@2409
|
16 |
*
|
alpar@2409
|
17 |
*/
|
alpar@2409
|
18 |
|
alpar@2409
|
19 |
#ifndef LEMON_MIN_MEAN_CYCLE_H
|
alpar@2409
|
20 |
#define LEMON_MIN_MEAN_CYCLE_H
|
alpar@2409
|
21 |
|
alpar@2409
|
22 |
/// \ingroup min_cost_flow
|
alpar@2409
|
23 |
///
|
alpar@2409
|
24 |
/// \file
|
alpar@2409
|
25 |
/// \brief Karp algorithm for finding a minimum mean cycle.
|
alpar@2409
|
26 |
|
alpar@2409
|
27 |
#include <lemon/graph_utils.h>
|
alpar@2409
|
28 |
#include <lemon/topology.h>
|
alpar@2409
|
29 |
#include <lemon/path.h>
|
alpar@2409
|
30 |
|
alpar@2409
|
31 |
namespace lemon {
|
alpar@2409
|
32 |
|
alpar@2409
|
33 |
/// \addtogroup min_cost_flow
|
alpar@2409
|
34 |
/// @{
|
alpar@2409
|
35 |
|
alpar@2409
|
36 |
/// \brief Implementation of Karp's algorithm for finding a
|
alpar@2409
|
37 |
/// minimum mean cycle.
|
alpar@2409
|
38 |
///
|
alpar@2409
|
39 |
/// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's
|
alpar@2409
|
40 |
/// algorithm for finding a minimum mean cycle.
|
alpar@2409
|
41 |
///
|
alpar@2409
|
42 |
/// \param Graph The directed graph type the algorithm runs on.
|
alpar@2409
|
43 |
/// \param LengthMap The type of the length (cost) map.
|
alpar@2409
|
44 |
///
|
alpar@2409
|
45 |
/// \author Peter Kovacs
|
alpar@2409
|
46 |
|
alpar@2409
|
47 |
#ifdef DOXYGEN
|
alpar@2409
|
48 |
template <typename Graph, typename LengthMap>
|
alpar@2409
|
49 |
#else
|
alpar@2409
|
50 |
template <typename Graph,
|
alpar@2409
|
51 |
typename LengthMap = typename Graph::template EdgeMap<int> >
|
alpar@2409
|
52 |
#endif
|
alpar@2409
|
53 |
|
alpar@2409
|
54 |
class MinMeanCycle
|
alpar@2409
|
55 |
{
|
alpar@2409
|
56 |
typedef typename Graph::Node Node;
|
alpar@2409
|
57 |
typedef typename Graph::NodeIt NodeIt;
|
alpar@2409
|
58 |
typedef typename Graph::Edge Edge;
|
alpar@2409
|
59 |
typedef typename Graph::EdgeIt EdgeIt;
|
alpar@2409
|
60 |
typedef typename Graph::InEdgeIt InEdgeIt;
|
alpar@2409
|
61 |
typedef typename Graph::OutEdgeIt OutEdgeIt;
|
alpar@2409
|
62 |
|
alpar@2409
|
63 |
typedef typename LengthMap::Value Length;
|
alpar@2409
|
64 |
|
alpar@2409
|
65 |
typedef typename Graph::template NodeMap<int> IntNodeMap;
|
alpar@2409
|
66 |
typedef typename Graph::template NodeMap<Edge> PredNodeMap;
|
alpar@2409
|
67 |
typedef Path<Graph> Path;
|
alpar@2409
|
68 |
typedef std::vector<Node> NodeVector;
|
alpar@2409
|
69 |
typedef typename NodeVector::iterator NodeVectorIt;
|
alpar@2409
|
70 |
|
alpar@2409
|
71 |
protected:
|
alpar@2409
|
72 |
|
alpar@2409
|
73 |
/// \brief Data sturcture for path data.
|
alpar@2409
|
74 |
struct PathData {
|
alpar@2409
|
75 |
bool found;
|
alpar@2409
|
76 |
Length dist;
|
alpar@2409
|
77 |
Edge pred;
|
alpar@2409
|
78 |
PathData(bool _found = false, Length _dist = 0) :
|
alpar@2409
|
79 |
found(_found), dist(_dist), pred(INVALID) {}
|
alpar@2409
|
80 |
PathData(bool _found, Length _dist, Edge _pred) :
|
alpar@2409
|
81 |
found(_found), dist(_dist), pred(_pred) {}
|
alpar@2409
|
82 |
};
|
alpar@2409
|
83 |
|
alpar@2409
|
84 |
private:
|
alpar@2409
|
85 |
|
alpar@2409
|
86 |
typedef typename Graph::template NodeMap<std::vector<PathData> > PathVectorNodeMap;
|
alpar@2409
|
87 |
|
alpar@2409
|
88 |
protected:
|
alpar@2409
|
89 |
|
alpar@2409
|
90 |
/// \brief Node map for storing path data.
|
alpar@2409
|
91 |
///
|
alpar@2409
|
92 |
/// Node map for storing path data of all nodes in the current
|
alpar@2409
|
93 |
/// component. dmap[v][k] is the length of a shortest directed walk
|
alpar@2409
|
94 |
/// to node v from the starting node containing exactly k edges.
|
alpar@2409
|
95 |
PathVectorNodeMap dmap;
|
alpar@2409
|
96 |
|
alpar@2409
|
97 |
/// \brief The directed graph the algorithm runs on.
|
alpar@2409
|
98 |
const Graph& graph;
|
alpar@2409
|
99 |
/// \brief The length of the edges.
|
alpar@2409
|
100 |
const LengthMap& length;
|
alpar@2409
|
101 |
|
alpar@2409
|
102 |
/// \brief The total length of the found cycle.
|
alpar@2409
|
103 |
Length cycle_length;
|
alpar@2409
|
104 |
/// \brief The number of edges in the found cycle.
|
alpar@2409
|
105 |
int cycle_size;
|
alpar@2409
|
106 |
/// \brief The found cycle.
|
alpar@2409
|
107 |
Path *cycle_path;
|
alpar@2409
|
108 |
/// \brief The found cycle.
|
alpar@2409
|
109 |
bool local_path;
|
alpar@2409
|
110 |
|
alpar@2409
|
111 |
/// \brief Node map for identifying strongly connected components.
|
alpar@2409
|
112 |
IntNodeMap comp;
|
alpar@2409
|
113 |
/// \brief The number of strongly connected components.
|
alpar@2409
|
114 |
int comp_num;
|
alpar@2409
|
115 |
/// \brief %Counter for identifying the current component.
|
alpar@2409
|
116 |
int comp_cnt;
|
alpar@2409
|
117 |
/// \brief Nodes of the current component.
|
alpar@2409
|
118 |
NodeVector nodes;
|
alpar@2409
|
119 |
/// \brief The processed nodes in the last round.
|
alpar@2409
|
120 |
NodeVector process;
|
alpar@2409
|
121 |
|
alpar@2409
|
122 |
public :
|
alpar@2409
|
123 |
|
alpar@2409
|
124 |
/// \brief The constructor of the class.
|
alpar@2409
|
125 |
///
|
alpar@2409
|
126 |
/// The constructor of the class.
|
alpar@2409
|
127 |
///
|
alpar@2409
|
128 |
/// \param _graph The directed graph the algorithm runs on.
|
alpar@2409
|
129 |
/// \param _length The length (cost) of the edges.
|
alpar@2409
|
130 |
MinMeanCycle( const Graph& _graph,
|
alpar@2409
|
131 |
const LengthMap& _length ) :
|
alpar@2409
|
132 |
graph(_graph), length(_length), dmap(_graph),
|
alpar@2409
|
133 |
cycle_length(0), cycle_size(-1), comp(_graph),
|
alpar@2409
|
134 |
cycle_path(NULL), local_path(false)
|
alpar@2409
|
135 |
{ }
|
alpar@2409
|
136 |
|
alpar@2409
|
137 |
/// \brief The destructor of the class.
|
alpar@2409
|
138 |
~MinMeanCycle() {
|
alpar@2409
|
139 |
if (local_path) delete cycle_path;
|
alpar@2409
|
140 |
}
|
alpar@2409
|
141 |
|
alpar@2409
|
142 |
protected:
|
alpar@2409
|
143 |
|
alpar@2409
|
144 |
/// \brief Initializes the internal data structures.
|
alpar@2409
|
145 |
void init() {
|
alpar@2409
|
146 |
comp_num = stronglyConnectedComponents(graph, comp);
|
alpar@2409
|
147 |
if (!cycle_path) {
|
alpar@2409
|
148 |
local_path = true;
|
alpar@2409
|
149 |
cycle_path = new Path;
|
alpar@2409
|
150 |
}
|
alpar@2409
|
151 |
}
|
alpar@2409
|
152 |
|
alpar@2409
|
153 |
/// \brief Initializes the internal data structures for the current
|
alpar@2409
|
154 |
/// component.
|
alpar@2409
|
155 |
void initCurrent() {
|
alpar@2409
|
156 |
nodes.clear();
|
alpar@2409
|
157 |
// Finding the nodes of the current component
|
alpar@2409
|
158 |
for (NodeIt v(graph); v != INVALID; ++v) {
|
alpar@2409
|
159 |
if (comp[v] == comp_cnt) nodes.push_back(v);
|
alpar@2409
|
160 |
}
|
alpar@2409
|
161 |
|
alpar@2409
|
162 |
// Creating vectors for all nodes
|
alpar@2409
|
163 |
int n = nodes.size();
|
alpar@2409
|
164 |
for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
|
alpar@2409
|
165 |
dmap[*vi].resize(n + 1);
|
alpar@2409
|
166 |
}
|
alpar@2409
|
167 |
}
|
alpar@2409
|
168 |
|
alpar@2409
|
169 |
/// \brief Processes all rounds of computing required path data.
|
alpar@2409
|
170 |
void processRounds() {
|
alpar@2409
|
171 |
dmap[nodes[0]][0] = PathData(true, 0);
|
alpar@2409
|
172 |
process.clear();
|
alpar@2409
|
173 |
for (OutEdgeIt oe(graph, nodes[0]); oe != INVALID; ++oe) {
|
alpar@2409
|
174 |
Node v = graph.target(oe);
|
alpar@2409
|
175 |
if (comp[v] != comp_cnt || v == nodes[0]) continue;
|
alpar@2409
|
176 |
dmap[v][1] = PathData(true, length[oe], oe);
|
alpar@2409
|
177 |
process.push_back(v);
|
alpar@2409
|
178 |
}
|
alpar@2409
|
179 |
int n = nodes.size(), k;
|
alpar@2409
|
180 |
for (k = 2; k <= n && process.size() < n; ++k) {
|
alpar@2409
|
181 |
processNextBuildRound(k);
|
alpar@2409
|
182 |
}
|
alpar@2409
|
183 |
for ( ; k <= n; ++k) {
|
alpar@2409
|
184 |
processNextFullRound(k);
|
alpar@2409
|
185 |
}
|
alpar@2409
|
186 |
}
|
alpar@2409
|
187 |
|
alpar@2409
|
188 |
/// \brief Processes one round of computing required path data and
|
alpar@2409
|
189 |
/// rebuilds \ref process vector.
|
alpar@2409
|
190 |
void processNextBuildRound(int k) {
|
alpar@2409
|
191 |
NodeVector next;
|
alpar@2409
|
192 |
for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) {
|
alpar@2409
|
193 |
for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
|
alpar@2409
|
194 |
Node v = graph.target(oe);
|
alpar@2409
|
195 |
if (comp[v] != comp_cnt) continue;
|
alpar@2409
|
196 |
if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
|
alpar@2409
|
197 |
if (!dmap[v][k].found) next.push_back(v);
|
alpar@2409
|
198 |
dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
|
alpar@2409
|
199 |
}
|
alpar@2409
|
200 |
}
|
alpar@2409
|
201 |
}
|
alpar@2409
|
202 |
process.swap(next);
|
alpar@2409
|
203 |
}
|
alpar@2409
|
204 |
|
alpar@2409
|
205 |
/// \brief Processes one round of computing required path data
|
alpar@2409
|
206 |
/// using \ref nodes vector instead of \ref process vector.
|
alpar@2409
|
207 |
void processNextFullRound(int k) {
|
alpar@2409
|
208 |
for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {
|
alpar@2409
|
209 |
for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
|
alpar@2409
|
210 |
Node v = graph.target(oe);
|
alpar@2409
|
211 |
if (comp[v] != comp_cnt) continue;
|
alpar@2409
|
212 |
if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
|
alpar@2409
|
213 |
dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
|
alpar@2409
|
214 |
}
|
alpar@2409
|
215 |
}
|
alpar@2409
|
216 |
}
|
alpar@2409
|
217 |
}
|
alpar@2409
|
218 |
|
alpar@2409
|
219 |
/// \brief Finds the minimum cycle mean value according to the path
|
alpar@2409
|
220 |
/// data stored in \ref dmap.
|
alpar@2409
|
221 |
///
|
alpar@2409
|
222 |
/// Finds the minimum cycle mean value according to the path data
|
alpar@2409
|
223 |
/// stored in \ref dmap.
|
alpar@2409
|
224 |
///
|
alpar@2409
|
225 |
/// \retval min_length The total length of the found cycle.
|
alpar@2409
|
226 |
/// \retval min_size The number of edges in the found cycle.
|
alpar@2409
|
227 |
/// \retval min_node A node for obtaining a critical cycle.
|
alpar@2409
|
228 |
///
|
alpar@2409
|
229 |
/// \return \c true if a cycle exists in the graph.
|
alpar@2409
|
230 |
bool findMinCycleMean(Length &min_length, int &min_size, Node &min_node) {
|
alpar@2409
|
231 |
bool found_min = false;
|
alpar@2409
|
232 |
for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
|
alpar@2409
|
233 |
Length len;
|
alpar@2409
|
234 |
int size;
|
alpar@2409
|
235 |
bool found_one = false;
|
alpar@2409
|
236 |
int n = nodes.size();
|
alpar@2409
|
237 |
for (int k = 0; k < n; ++k) {
|
alpar@2409
|
238 |
Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist;
|
alpar@2409
|
239 |
int _size = n - k;
|
alpar@2409
|
240 |
if ( dmap[*vi][n].found && dmap[*vi][k].found && (!found_one || len * _size < _len * size) ) {
|
alpar@2409
|
241 |
found_one = true;
|
alpar@2409
|
242 |
len = _len;
|
alpar@2409
|
243 |
size = _size;
|
alpar@2409
|
244 |
}
|
alpar@2409
|
245 |
}
|
alpar@2409
|
246 |
if (found_one && (!found_min || len * min_size < min_length * size)) {
|
alpar@2409
|
247 |
found_min = true;
|
alpar@2409
|
248 |
min_length = len;
|
alpar@2409
|
249 |
min_size = size;
|
alpar@2409
|
250 |
min_node = *vi;
|
alpar@2409
|
251 |
}
|
alpar@2409
|
252 |
}
|
alpar@2409
|
253 |
return found_min;
|
alpar@2409
|
254 |
}
|
alpar@2409
|
255 |
|
alpar@2409
|
256 |
/// \brief Finds a critical (minimum mean) cycle according to the
|
alpar@2409
|
257 |
/// path data stored in \ref dmap.
|
alpar@2409
|
258 |
void findCycle(const Node &min_n) {
|
alpar@2409
|
259 |
IntNodeMap reached(graph, -1);
|
alpar@2409
|
260 |
int r = reached[min_n] = dmap[min_n].size() - 1;
|
alpar@2409
|
261 |
Node u = graph.source(dmap[min_n][r].pred);
|
alpar@2409
|
262 |
while (reached[u] < 0) {
|
alpar@2409
|
263 |
reached[u] = --r;
|
alpar@2409
|
264 |
u = graph.source(dmap[u][r].pred);
|
alpar@2409
|
265 |
}
|
alpar@2409
|
266 |
r = reached[u];
|
alpar@2409
|
267 |
Edge ce = dmap[u][r].pred;
|
alpar@2409
|
268 |
cycle_path->addFront(ce);
|
alpar@2409
|
269 |
Node v;
|
alpar@2409
|
270 |
while ((v = graph.source(ce)) != u) {
|
alpar@2409
|
271 |
ce = dmap[v][--r].pred;
|
alpar@2409
|
272 |
cycle_path->addFront(ce);
|
alpar@2409
|
273 |
}
|
alpar@2409
|
274 |
}
|
alpar@2409
|
275 |
|
alpar@2409
|
276 |
public:
|
alpar@2409
|
277 |
|
alpar@2409
|
278 |
/// \brief Runs the algorithm.
|
alpar@2409
|
279 |
///
|
alpar@2409
|
280 |
/// Runs the algorithm.
|
alpar@2409
|
281 |
///
|
alpar@2409
|
282 |
/// \return \c true if a cycle exists in the graph.
|
alpar@2409
|
283 |
bool run() {
|
alpar@2409
|
284 |
init();
|
alpar@2409
|
285 |
// Searching for the minimum mean cycle in all components
|
alpar@2409
|
286 |
bool found_cycle = false;
|
alpar@2409
|
287 |
Node cycle_node;
|
alpar@2409
|
288 |
for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {
|
alpar@2409
|
289 |
|
alpar@2409
|
290 |
initCurrent();
|
alpar@2409
|
291 |
processRounds();
|
alpar@2409
|
292 |
|
alpar@2409
|
293 |
Length min_length;
|
alpar@2409
|
294 |
int min_size;
|
alpar@2409
|
295 |
Node min_node;
|
alpar@2409
|
296 |
bool found_min = findMinCycleMean(min_length, min_size, min_node);
|
alpar@2409
|
297 |
|
alpar@2409
|
298 |
if ( found_min && (!found_cycle || min_length * cycle_size < cycle_length * min_size) ) {
|
alpar@2409
|
299 |
found_cycle = true;
|
alpar@2409
|
300 |
cycle_length = min_length;
|
alpar@2409
|
301 |
cycle_size = min_size;
|
alpar@2409
|
302 |
cycle_node = min_node;
|
alpar@2409
|
303 |
}
|
alpar@2409
|
304 |
}
|
alpar@2409
|
305 |
if (found_cycle) findCycle(cycle_node);
|
alpar@2409
|
306 |
return found_cycle;
|
alpar@2409
|
307 |
}
|
alpar@2409
|
308 |
|
alpar@2409
|
309 |
/// \brief Returns the total length of the found critical cycle.
|
alpar@2409
|
310 |
///
|
alpar@2409
|
311 |
/// Returns the total length of the found critical cycle.
|
alpar@2409
|
312 |
///
|
alpar@2409
|
313 |
/// \pre \ref run() must be called before using this function.
|
alpar@2409
|
314 |
Length cycleLength() const {
|
alpar@2409
|
315 |
return cycle_length;
|
alpar@2409
|
316 |
}
|
alpar@2409
|
317 |
|
alpar@2409
|
318 |
/// \brief Returns the number of edges in the found critical
|
alpar@2409
|
319 |
/// cycle.
|
alpar@2409
|
320 |
///
|
alpar@2409
|
321 |
/// Returns the number of edges in the found critical cycle.
|
alpar@2409
|
322 |
///
|
alpar@2409
|
323 |
/// \pre \ref run() must be called before using this function.
|
alpar@2409
|
324 |
int cycleEdgeNum() const {
|
alpar@2409
|
325 |
return cycle_size;
|
alpar@2409
|
326 |
}
|
alpar@2409
|
327 |
|
alpar@2409
|
328 |
/// \brief Returns the mean length of the found critical cycle.
|
alpar@2409
|
329 |
///
|
alpar@2409
|
330 |
/// Returns the mean length of the found critical cycle.
|
alpar@2409
|
331 |
///
|
alpar@2409
|
332 |
/// \pre \ref run() must be called before using this function.
|
alpar@2409
|
333 |
///
|
alpar@2409
|
334 |
/// \warning LengthMap::Value must be convertible to double.
|
alpar@2409
|
335 |
double minMean() const {
|
alpar@2409
|
336 |
return (double)cycle_length / (double)cycle_size;
|
alpar@2409
|
337 |
}
|
alpar@2409
|
338 |
|
alpar@2409
|
339 |
/// \brief Returns a const reference to the \ref lemon::Path "Path"
|
alpar@2409
|
340 |
/// structure of the found flow.
|
alpar@2409
|
341 |
///
|
alpar@2409
|
342 |
/// Returns a const reference to the \ref lemon::Path "Path"
|
alpar@2409
|
343 |
/// structure of the found flow.
|
alpar@2409
|
344 |
///
|
alpar@2409
|
345 |
/// \pre \ref run() must be called before using this function.
|
alpar@2409
|
346 |
///
|
alpar@2409
|
347 |
/// \sa \ref cyclePath()
|
alpar@2409
|
348 |
const Path &cycle() const {
|
alpar@2409
|
349 |
return *cycle_path;
|
alpar@2409
|
350 |
}
|
alpar@2409
|
351 |
|
alpar@2409
|
352 |
/// \brief Sets the \ref lemon::Path "Path" structure storing the
|
alpar@2409
|
353 |
/// found cycle.
|
alpar@2409
|
354 |
///
|
alpar@2409
|
355 |
/// Sets the \ref lemon::Path "Path" structure storing the found
|
alpar@2409
|
356 |
/// cycle. If you don't use this function before calling
|
alpar@2409
|
357 |
/// \ref run(), it will allocate one. The destuctor deallocates
|
alpar@2409
|
358 |
/// this automatically allocated map, of course.
|
alpar@2409
|
359 |
///
|
alpar@2409
|
360 |
/// \note The algorithm calls only the \ref lemon::Path::addFront()
|
alpar@2409
|
361 |
/// "addFront()" method of the given \ref lemon::Path "Path"
|
alpar@2409
|
362 |
/// structure.
|
alpar@2409
|
363 |
///
|
alpar@2409
|
364 |
/// \return \c (*this)
|
alpar@2409
|
365 |
MinMeanCycle &cyclePath(Path& path) {
|
alpar@2409
|
366 |
if (local_path) {
|
alpar@2409
|
367 |
delete cycle_path;
|
alpar@2409
|
368 |
local_path = false;
|
alpar@2409
|
369 |
}
|
alpar@2409
|
370 |
cycle_path = &path;
|
alpar@2409
|
371 |
return *this;
|
alpar@2409
|
372 |
}
|
alpar@2409
|
373 |
|
alpar@2409
|
374 |
}; //class MinMeanCycle
|
alpar@2409
|
375 |
|
alpar@2409
|
376 |
///@}
|
alpar@2409
|
377 |
|
alpar@2409
|
378 |
} //namespace lemon
|
alpar@2409
|
379 |
|
alpar@2409
|
380 |
#endif //LEMON_MIN_MEAN_CYCLE_H
|