# source:lemon-0.x/lemon/min_mean_cycle.h@2413:21eb3ccdc3df

Last change on this file since 2413:21eb3ccdc3df was 2413:21eb3ccdc3df, checked in by Balazs Dezso, 13 years ago

Right dimacs format for min cost flows
Bug fixes in tolerance and min_mean_cycle

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