COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_mean_cycle.h @ 2412:086fc76d591d

Last change on this file since 2412:086fc76d591d was 2409:fe0a8fe16271, checked in by Alpar Juttner, 17 years ago

Minimum mean cycle algorithm contributed by Peter Kovacs.

File size: 11.2 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 cycle.
38  ///
39  /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's
40  /// algorithm for finding a minimum mean 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::InEdgeIt InEdgeIt;
61    typedef typename Graph::OutEdgeIt OutEdgeIt;
62
63    typedef typename LengthMap::Value Length;
64   
65    typedef typename Graph::template NodeMap<int> IntNodeMap;
66    typedef typename Graph::template NodeMap<Edge> PredNodeMap;
67    typedef Path<Graph> Path;
68    typedef std::vector<Node> NodeVector;
69    typedef typename NodeVector::iterator NodeVectorIt;
70
71  protected:
72 
73    /// \brief Data sturcture for path data.
74    struct PathData {
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> > PathVectorNodeMap;
87 
88  protected:
89
90    /// \brief Node map for storing path data.
91    ///
92    /// Node map for storing path data of all nodes in the current
93    /// component. dmap[v][k] is the length of a shortest directed walk
94    /// to node v from the starting node containing exactly k edges.
95    PathVectorNodeMap dmap;
96   
97    /// \brief The directed graph the algorithm runs on.
98    const Graph& graph;
99    /// \brief The length of the edges.
100    const LengthMap& length;
101   
102    /// \brief The total length of the found cycle.
103    Length cycle_length;
104    /// \brief The number of edges in the found cycle.
105    int cycle_size;
106    /// \brief The found cycle.
107    Path *cycle_path;
108    /// \brief The found cycle.
109    bool local_path;
110   
111    /// \brief Node map for identifying strongly connected components.
112    IntNodeMap comp;
113    /// \brief The number of strongly connected components.
114    int comp_num;
115    /// \brief %Counter for identifying the current component.
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;
121   
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.
130    MinMeanCycle( const Graph& _graph,
131                  const LengthMap& _length ) :
132      graph(_graph), length(_length), dmap(_graph),
133      cycle_length(0), cycle_size(-1), comp(_graph),
134      cycle_path(NULL), local_path(false)
135    { }
136
137    /// \brief The destructor of the class.
138    ~MinMeanCycle() {
139      if (local_path) delete cycle_path;
140    }
141
142  protected:
143   
144    /// \brief Initializes the internal data structures.
145    void init() {
146      comp_num = stronglyConnectedComponents(graph, comp);
147      if (!cycle_path) {
148        local_path = true;
149        cycle_path = new Path;
150      }
151    }
152
153    /// \brief Initializes the internal data structures for the current
154    /// component.
155    void initCurrent() {
156      nodes.clear();
157      // Finding the nodes of the current component
158      for (NodeIt v(graph); v != INVALID; ++v) {
159        if (comp[v] == comp_cnt) nodes.push_back(v);
160      }
161
162      // Creating vectors for all nodes
163      int n = nodes.size();
164      for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
165        dmap[*vi].resize(n + 1);
166      }
167    }
168   
169    /// \brief Processes all rounds of computing required path data.
170    void processRounds() {
171      dmap[nodes[0]][0] = PathData(true, 0);
172      process.clear();
173      for (OutEdgeIt oe(graph, nodes[0]); oe != INVALID; ++oe) {
174        Node v = graph.target(oe);
175        if (comp[v] != comp_cnt || v == nodes[0]) continue;
176        dmap[v][1] = PathData(true, length[oe], oe);
177        process.push_back(v);
178      }
179      int n = nodes.size(), k;
180      for (k = 2; k <= n && process.size() < n; ++k) {
181        processNextBuildRound(k);
182      }
183      for ( ; k <= n; ++k) {
184        processNextFullRound(k);
185      }
186    }
187   
188    /// \brief Processes one round of computing required path data and
189    /// rebuilds \ref process vector.
190    void processNextBuildRound(int k) {
191      NodeVector next;
192      for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) {
193        for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
194          Node v = graph.target(oe);
195          if (comp[v] != comp_cnt) continue;
196          if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
197            if (!dmap[v][k].found) next.push_back(v);
198            dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
199          }
200        }
201      }
202      process.swap(next);
203    }
204
205    /// \brief Processes one round of computing required path data
206    /// using \ref nodes vector instead of \ref process vector.
207    void processNextFullRound(int k) {
208      for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {
209        for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
210          Node v = graph.target(oe);
211          if (comp[v] != comp_cnt) continue;
212          if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
213            dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
214          }
215        }
216      }
217    }
218   
219    /// \brief Finds the minimum cycle mean value according to the path
220    /// data stored in \ref dmap.
221    ///
222    /// Finds the minimum cycle mean value according to the path data
223    /// stored in \ref dmap.
224    ///
225    /// \retval min_length The total length of the found cycle.
226    /// \retval min_size The number of edges in the found cycle.
227    /// \retval min_node A node for obtaining a critical cycle.
228    ///
229    /// \return \c true if a cycle exists in the graph.
230    bool findMinCycleMean(Length &min_length, int &min_size, Node &min_node) {
231      bool found_min = false;
232      for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
233        Length len;
234        int size;
235        bool found_one = false;
236        int n = nodes.size();
237        for (int k = 0; k < n; ++k) {
238          Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist;
239          int _size = n - k;
240          if ( dmap[*vi][n].found && dmap[*vi][k].found && (!found_one || len * _size < _len * size) ) {
241            found_one = true;
242            len = _len;
243            size = _size;
244          }
245        }
246        if (found_one && (!found_min || len * min_size < min_length * size)) {
247          found_min = true;
248          min_length = len;
249          min_size = size;
250          min_node = *vi;
251        }
252      }
253      return found_min;
254    }
255   
256    /// \brief Finds a critical (minimum mean) cycle according to the
257    /// path data stored in \ref dmap.
258    void findCycle(const Node &min_n) {
259      IntNodeMap reached(graph, -1);
260      int r = reached[min_n] = dmap[min_n].size() - 1;
261      Node u = graph.source(dmap[min_n][r].pred);
262      while (reached[u] < 0) {
263        reached[u] = --r;
264        u = graph.source(dmap[u][r].pred);
265      }
266      r = reached[u];
267      Edge ce = dmap[u][r].pred;
268      cycle_path->addFront(ce);
269      Node v;
270      while ((v = graph.source(ce)) != u) {
271        ce = dmap[v][--r].pred;
272        cycle_path->addFront(ce);
273      }
274    }
275   
276  public:
277
278    /// \brief Runs the algorithm.
279    ///
280    /// Runs the algorithm.
281    ///
282    /// \return \c true if a cycle exists in the graph.
283    bool run() {
284      init();
285      // Searching for the minimum mean cycle in all components
286      bool found_cycle = false;
287      Node cycle_node;
288      for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {
289     
290        initCurrent();
291        processRounds();
292       
293        Length min_length;
294        int min_size;
295        Node min_node;
296        bool found_min = findMinCycleMean(min_length, min_size, min_node);
297       
298        if ( found_min && (!found_cycle || min_length * cycle_size  < cycle_length * min_size) ) {
299          found_cycle = true;
300          cycle_length = min_length;
301          cycle_size = min_size;
302          cycle_node = min_node;
303        }
304      }
305      if (found_cycle) findCycle(cycle_node);
306      return found_cycle;
307    }
308   
309    /// \brief Returns the total length of the found critical cycle.
310    ///
311    /// Returns the total length of the found critical cycle.
312    ///
313    /// \pre \ref run() must be called before using this function.
314    Length cycleLength() const {
315      return cycle_length;
316    }
317   
318    /// \brief Returns the number of edges in the found critical
319    /// cycle.
320    ///
321    /// Returns the number of edges in the found critical cycle.
322    ///
323    /// \pre \ref run() must be called before using this function.
324    int cycleEdgeNum() const {
325      return cycle_size;
326    }
327   
328    /// \brief Returns the mean length of the found critical cycle.
329    ///
330    /// Returns the mean length of the found critical cycle.
331    ///
332    /// \pre \ref run() must be called before using this function.
333    ///
334    /// \warning LengthMap::Value must be convertible to double.
335    double minMean() const {
336      return (double)cycle_length / (double)cycle_size;
337    }
338
339    /// \brief Returns a const reference to the \ref lemon::Path "Path"
340    /// structure of the found flow.
341    ///
342    /// Returns a const reference to the \ref lemon::Path "Path"
343    /// structure of the found flow.
344    ///
345    /// \pre \ref run() must be called before using this function.
346    ///
347    /// \sa \ref cyclePath()
348    const Path &cycle() const {
349      return *cycle_path;
350    }
351   
352    /// \brief Sets the \ref lemon::Path "Path" structure storing the
353    /// found cycle.
354    ///
355    /// Sets the \ref lemon::Path "Path" structure storing the found
356    /// cycle. If you don't use this function before calling
357    /// \ref run(), it will allocate one. The destuctor deallocates
358    /// this automatically allocated map, of course.
359    ///
360    /// \note The algorithm calls only the \ref lemon::Path::addFront()
361    /// "addFront()" method of the given \ref lemon::Path "Path"
362    /// structure.
363    ///
364    /// \return \c (*this)
365    MinMeanCycle &cyclePath(Path& path) {
366      if (local_path) {
367        delete cycle_path;
368        local_path = false;
369      }
370      cycle_path = &path;
371      return *this;
372    }
373
374  }; //class MinMeanCycle
375
376  ///@}
377
378} //namespace lemon
379
380#endif //LEMON_MIN_MEAN_CYCLE_H
Note: See TracBrowser for help on using the repository browser.