COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_mean_cycle.h @ 2476:059dcdda37c5

Last change on this file since 2476:059dcdda37c5 was 2437:02c7076bf894, checked in by Balazs Dezso, 13 years ago

Small improvements in MinMeanCycle? class.

Patch from Peter Kovacs

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