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 min_cost_flow
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 min_cost_flow
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, m.run() is just a shortcut
254 /// of the following code.
266 /// \brief Initializes the internal data structures.
268 comp_num = stronglyConnectedComponents(graph, comp);
271 cycle_path = new Path;
275 /// \brief Finds the minimum cycle mean value in the graph.
277 /// Computes all the required path data and finds the minimum cycle
278 /// mean value in the graph.
280 /// \return \c true if a cycle exists in the graph.
282 /// \pre \ref init() must be called before using this function.
284 cycle_node = INVALID;
285 for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {
292 bool found_min = findCurrentMin(min_length, min_size, min_node);
294 if ( found_min && (cycle_node == INVALID ||
295 min_length * cycle_size < cycle_length * min_size) ) {
296 cycle_length = min_length;
297 cycle_size = min_size;
298 cycle_node = min_node;
301 return (cycle_node != INVALID);
304 /// \brief Finds a critical (minimum mean) cycle.
306 /// Finds a critical (minimum mean) cycle using the path data
307 /// stored in \ref dmap.
309 /// \return \c true if a cycle exists in the graph.
311 /// \pre \ref init() and \ref findMinMean() must be called before
312 /// using this function.
314 if (cycle_node == INVALID) return false;
317 IntNodeMap reached(graph, -1);
318 int r = reached[cycle_node] = dmap[cycle_node].size() - 1;
319 Node u = graph.source(dmap[cycle_node][r].pred);
320 while (reached[u] < 0) {
322 u = graph.source(dmap[u][r].pred);
325 Edge e = dmap[u][r].pred;
326 cycle_path->addFront(e);
327 cycle_length = cycle_length + length[e];
330 while ((v = graph.source(e)) != u) {
331 e = dmap[v][--r].pred;
332 cycle_path->addFront(e);
333 cycle_length = cycle_length + length[e];
339 /// \brief Resets the internal data structures.
341 /// Resets the internal data structures so that \ref findMinMean()
342 /// and \ref findCycle() can be called again (e.g. when the
343 /// underlaying graph has been modified).
345 for (NodeIt u(graph); u != INVALID; ++u)
347 cycle_node = INVALID;
348 if (cycle_path) cycle_path->clear();
349 comp_num = stronglyConnectedComponents(graph, comp);
352 /// \brief Returns the total length of the found cycle.
354 /// Returns the total length of the found cycle.
356 /// \pre \ref run() must be called before using this function.
357 Length cycleLength() const {
361 /// \brief Returns the number of edges in the found cycle.
363 /// Returns the number of edges in the found cycle.
365 /// \pre \ref run() must be called before using this function.
366 int cycleEdgeNum() const {
370 /// \brief Returns the mean length of the found cycle.
372 /// Returns the mean length of the found cycle.
374 /// \pre \ref run() must be called before using this function.
376 /// \warning LengthMap::Value must be convertible to double.
378 /// \note m.minMean() is just a shortcut of the following code.
380 /// return m.cycleEdgeNum() / double(m.cycleLength());
382 double minMean() const {
383 return cycle_length / (double)cycle_size;
386 /// \brief Returns a const reference to the \ref lemon::Path "Path"
387 /// structure of the found cycle.
389 /// Returns a const reference to the \ref lemon::Path "Path"
390 /// structure of the found cycle.
392 /// \pre \ref run() must be called before using this function.
394 /// \sa \ref cyclePath()
395 const Path& cycle() const {
399 /// \brief Sets the \ref lemon::Path "Path" structure storing the
402 /// Sets the \ref lemon::Path "Path" structure storing the found
403 /// cycle. If you don't use this function before calling
404 /// \ref run(), it will allocate one. The destuctor deallocates
405 /// this automatically allocated map, of course.
407 /// \note The algorithm calls only the \ref lemon::Path::addFront()
408 /// "addFront()" method of the given \ref lemon::Path "Path"
411 /// \return \c (*this)
412 MinMeanCycle& cyclePath(Path &path) {
421 }; //class MinMeanCycle
427 #endif //LEMON_MIN_MEAN_CYCLE_H