Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_MIN_MEAN_CYCLE_H
20 #define LEMON_MIN_MEAN_CYCLE_H
22 /// \ingroup shortest_path
25 /// \brief Karp's algorithm for finding a minimum mean (directed) cycle.
28 #include <lemon/graph_utils.h>
29 #include <lemon/topology.h>
30 #include <lemon/path.h>
34 /// \addtogroup shortest_path
37 /// \brief Implementation of Karp's algorithm for finding a
38 /// minimum mean (directed) cycle.
40 /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's
41 /// algorithm for finding a minimum mean (directed) cycle.
43 /// \param Graph The directed graph type the algorithm runs on.
44 /// \param LengthMap The type of the length (cost) map.
46 /// \author Peter Kovacs
48 template <typename Graph,
49 typename LengthMap = typename Graph::template EdgeMap<int> >
52 typedef typename Graph::Node Node;
53 typedef typename Graph::NodeIt NodeIt;
54 typedef typename Graph::Edge Edge;
55 typedef typename Graph::EdgeIt EdgeIt;
56 typedef typename Graph::OutEdgeIt OutEdgeIt;
58 typedef typename LengthMap::Value Length;
60 typedef typename Graph::template NodeMap<int> IntNodeMap;
61 typedef typename Graph::template NodeMap<Edge> PredNodeMap;
62 typedef Path<Graph> Path;
63 typedef std::vector<Node> NodeVector;
67 /// \brief Data structure for path data.
73 PathData(bool _found = false, Length _dist = 0) :
74 found(_found), dist(_dist), pred(INVALID) {}
75 PathData(bool _found, Length _dist, Edge _pred) :
76 found(_found), dist(_dist), pred(_pred) {}
81 typedef typename Graph::template NodeMap<std::vector<PathData> >
86 /// \brief Node map for storing path data.
88 /// Node map for storing path data of all nodes in the current
89 /// component. dmap[v][k] is the length of a shortest directed walk
90 /// to node v from the starting node containing exactly k edges.
93 /// \brief The directed graph the algorithm runs on.
95 /// \brief The length of the edges.
96 const LengthMap &length;
98 /// \brief The total length of the found cycle.
100 /// \brief The number of edges in the found cycle.
102 /// \brief A node for obtaining a minimum mean cycle.
105 /// \brief The found cycle.
107 /// \brief The algorithm uses local \ref lemon::Path "Path"
108 /// structure to store the found cycle.
111 /// \brief Node map for identifying strongly connected components.
113 /// \brief The number of strongly connected components.
115 /// \brief Counter for identifying the current component.
117 /// \brief Nodes of the current component.
119 /// \brief The processed nodes in the last round.
124 /// \brief The constructor of the class.
126 /// The constructor of the class.
128 /// \param _graph The directed graph the algorithm runs on.
129 /// \param _length The length (cost) of the edges.
130 MinMeanCycle( const Graph &_graph,
131 const LengthMap &_length ) :
132 graph(_graph), length(_length), dmap(_graph), comp(_graph),
133 cycle_length(0), cycle_size(-1), cycle_node(INVALID),
134 cycle_path(NULL), local_path(false)
137 /// \brief The destructor of the class.
139 if (local_path) delete cycle_path;
144 /// \brief Initializes the internal data structures for the current
148 // Finding the nodes of the current component
149 for (NodeIt v(graph); v != INVALID; ++v) {
150 if (comp[v] == comp_cnt) nodes.push_back(v);
152 // Creating vectors for all nodes
153 int n = nodes.size();
154 for (int i = 0; i < n; ++i) {
155 dmap[nodes[i]].resize(n + 1);
159 /// \brief Processes all rounds of computing required path data for
160 /// the current component.
161 void processRounds() {
162 dmap[nodes[0]][0] = PathData(true, 0);
164 // Processing the first round
165 for (OutEdgeIt e(graph, nodes[0]); e != INVALID; ++e) {
166 Node v = graph.target(e);
167 if (comp[v] != comp_cnt || v == nodes[0]) continue;
168 dmap[v][1] = PathData(true, length[e], e);
169 process.push_back(v);
171 // Processing other rounds
172 int n = nodes.size(), k;
173 for (k = 2; k <= n && process.size() < n; ++k)
174 processNextBuildRound(k);
176 processNextFullRound(k);
179 /// \brief Processes one round of computing required path data and
180 /// rebuilds \ref process vector.
181 void processNextBuildRound(int k) {
183 for (int i = 0; i < process.size(); ++i) {
184 for (OutEdgeIt e(graph, process[i]); e != INVALID; ++e) {
185 Node v = graph.target(e);
186 if (comp[v] != comp_cnt) continue;
187 if (!dmap[v][k].found) {
189 dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e);
191 else if (dmap[process[i]][k-1].dist + length[e] < dmap[v][k].dist) {
192 dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e);
199 /// \brief Processes one round of computing required path data
200 /// using \ref nodes vector instead of \ref process vector.
201 void processNextFullRound(int k) {
202 for (int i = 0; i < nodes.size(); ++i) {
203 for (OutEdgeIt e(graph, nodes[i]); e != INVALID; ++e) {
204 Node v = graph.target(e);
205 if (comp[v] != comp_cnt) continue;
206 if ( !dmap[v][k].found ||
207 dmap[nodes[i]][k-1].dist + length[e] < dmap[v][k].dist ) {
208 dmap[v][k] = PathData(true, dmap[nodes[i]][k-1].dist + length[e], e);
214 /// \brief Finds the minimum cycle mean value in the current
216 bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) {
217 bool found_min = false;
218 for (int i = 0; i < nodes.size(); ++i) {
219 int n = nodes.size();
220 if (!dmap[nodes[i]][n].found) continue;
223 bool found_one = false;
224 for (int k = 0; k < n; ++k) {
225 if (!dmap[nodes[i]][k].found) continue;
226 Length _len = dmap[nodes[i]][n].dist - dmap[nodes[i]][k].dist;
228 if (!found_one || len * _size < _len * size) {
235 (!found_min || len * min_size < min_length * size) ) {
247 /// \brief Runs the algorithm.
249 /// Runs the algorithm.
251 /// \return \c true if a cycle exists in the graph.
253 /// \note Apart from the return value, <tt>m.run()</tt> is just a
254 /// shortcut of the following code.
266 /// \brief Initializes the internal data structures.
268 /// Initializes the internal data structures.
272 comp_num = stronglyConnectedComponents(graph, comp);
275 cycle_path = new Path;
279 /// \brief Finds the minimum cycle mean value in the graph.
281 /// Computes all the required path data and finds the minimum cycle
282 /// mean value in the graph.
284 /// \return \c true if a cycle exists in the graph.
286 /// \pre \ref init() must be called before using this function.
288 cycle_node = INVALID;
289 for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {
296 bool found_min = findCurrentMin(min_length, min_size, min_node);
298 if ( found_min && (cycle_node == INVALID ||
299 min_length * cycle_size < cycle_length * min_size) ) {
300 cycle_length = min_length;
301 cycle_size = min_size;
302 cycle_node = min_node;
305 return (cycle_node != INVALID);
308 /// \brief Finds a critical (minimum mean) cycle.
310 /// Finds a critical (minimum mean) cycle using the path data
311 /// stored in \ref dmap.
313 /// \return \c true if a cycle exists in the graph.
315 /// \pre \ref init() and \ref findMinMean() must be called before
316 /// using this function.
318 if (cycle_node == INVALID) return false;
321 IntNodeMap reached(graph, -1);
322 int r = reached[cycle_node] = dmap[cycle_node].size() - 1;
323 Node u = graph.source(dmap[cycle_node][r].pred);
324 while (reached[u] < 0) {
326 u = graph.source(dmap[u][r].pred);
329 Edge e = dmap[u][r].pred;
330 cycle_path->addFront(e);
331 cycle_length = cycle_length + length[e];
334 while ((v = graph.source(e)) != u) {
335 e = dmap[v][--r].pred;
336 cycle_path->addFront(e);
337 cycle_length = cycle_length + length[e];
343 /// \brief Resets the internal data structures.
345 /// Resets the internal data structures so that \ref findMinMean()
346 /// and \ref findCycle() can be called again (e.g. when the
347 /// underlaying graph has been modified).
351 for (NodeIt u(graph); u != INVALID; ++u)
353 cycle_node = INVALID;
354 if (cycle_path) cycle_path->clear();
355 comp_num = stronglyConnectedComponents(graph, comp);
358 /// \brief Returns the total length of the found cycle.
360 /// Returns the total length of the found cycle.
362 /// \pre \ref run() or \ref findCycle() must be called before
363 /// using this function. If only \ref findMinMean() is called,
364 /// the return value is not valid.
365 Length cycleLength() const {
369 /// \brief Returns the number of edges in the found cycle.
371 /// Returns the number of edges in the found cycle.
373 /// \pre \ref run() or \ref findCycle() must be called before
374 /// using this function. If only \ref findMinMean() is called,
375 /// the return value is not valid.
376 int cycleEdgeNum() const {
380 /// \brief Returns the mean length of the found cycle.
382 /// Returns the mean length of the found cycle.
384 /// \pre \ref run() or \ref findMinMean() must be called before
385 /// using this function.
387 /// \warning LengthMap::Value must be convertible to double.
389 /// \note <tt>m.minMean()</tt> is just a shortcut of the following
392 /// return m.cycleLength() / double(m.cycleEdgeNum());
394 /// However if only \ref findMinMean() is called before using this
395 /// function, <tt>m.cycleLength()</tt> and <tt>m.cycleEdgeNum()</tt>
396 /// are not valid alone, only their ratio is valid.
397 double minMean() const {
398 return cycle_length / (double)cycle_size;
401 /// \brief Returns a const reference to the \ref lemon::Path "Path"
402 /// structure of the found cycle.
404 /// Returns a const reference to the \ref lemon::Path "Path"
405 /// structure of the found cycle.
407 /// \pre \ref run() must be called before using this function.
409 /// \sa \ref cyclePath()
410 const Path& cycle() const {
414 /// \brief Sets the \ref lemon::Path "Path" structure storing the
417 /// Sets the \ref lemon::Path "Path" structure storing the found
418 /// cycle. If you don't use this function before calling
419 /// \ref run(), it will allocate one. The destuctor deallocates
420 /// this automatically allocated map, of course.
422 /// \note The algorithm calls only the \ref lemon::Path::addFront()
423 /// "addFront()" method of the given \ref lemon::Path "Path"
426 /// \return \c (*this)
427 MinMeanCycle& cyclePath(Path &path) {
436 }; //class MinMeanCycle
442 #endif //LEMON_MIN_MEAN_CYCLE_H