COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_mean_cycle.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

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