COIN-OR::LEMON - Graph Library

Changeset 2555:a84e52e99f57 in lemon-0.x


Ignore:
Timestamp:
01/13/08 11:26:55 (12 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3436
Message:

Reimplemented MinMeanCycle? to be much more efficient.
The new version implements Howard's algorithm instead of Karp's algorithm and
it is at least 10-20 times faster on all the 40-50 random graphs we have tested.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/min_mean_cycle.h

    r2553 r2555  
    2323///
    2424/// \file
    25 /// \brief Karp's algorithm for finding a minimum mean (directed) cycle.
     25/// \brief Howard's algorithm for finding a minimum mean directed cycle.
    2626
    2727#include <vector>
     
    2929#include <lemon/topology.h>
    3030#include <lemon/path.h>
     31#include <lemon/tolerance.h>
    3132
    3233namespace lemon {
     
    3536  /// @{
    3637
    37   /// \brief Implementation of Karp's algorithm for finding a
    38   /// minimum mean (directed) cycle.
     38  /// \brief Implementation of Howard's algorithm for finding a minimum
     39  /// mean directed cycle.
    3940  ///
    40   /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's
    41   /// algorithm for finding a minimum mean (directed) cycle.
     41  /// \ref MinMeanCycle implements Howard's algorithm for finding a
     42  /// minimum mean directed cycle.
    4243  ///
    4344  /// \param Graph The directed graph type the algorithm runs on.
    4445  /// \param LengthMap The type of the length (cost) map.
    4546  ///
     47  /// \warning \c LengthMap::Value must be convertible to \c double.
     48  ///
    4649  /// \author Peter Kovacs
    4750
    48   template <typename Graph,
    49     typename LengthMap = typename Graph::template EdgeMap<int> >
     51  template < typename Graph,
     52             typename LengthMap = typename Graph::template EdgeMap<int> >
    5053  class MinMeanCycle
    5154  {
    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;
     55    GRAPH_TYPEDEFS(typename Graph);
    5756
    5857    typedef typename LengthMap::Value Length;
    59 
    60     typedef typename Graph::template NodeMap<int> IntNodeMap;
    61     typedef typename Graph::template NodeMap<Edge> PredNodeMap;
    6258    typedef Path<Graph> Path;
    63     typedef std::vector<Node> NodeVector;
    6459
    6560  protected:
    6661
    67     /// \brief Data structure for path data.
    68     struct PathData
    69     {
    70       bool found;
    71       Length dist;
    72       Edge pred;
    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) {}
    77     };
    78 
    79   private:
    80 
    81     typedef typename Graph::template NodeMap<std::vector<PathData> >
    82       PathDataNodeMap;
     62    typename Graph::template NodeMap<bool> _reached;
     63    typename Graph::template NodeMap<double> _dist;
     64    typename Graph::template NodeMap<Edge> _policy;
     65
     66    /// The directed graph the algorithm runs on.
     67    const Graph &_graph;
     68    /// The length of the edges.
     69    const LengthMap &_length;
     70
     71    /// The total length of the found cycle.
     72    Length _cycle_length;
     73    /// The number of edges on the found cycle.
     74    int _cycle_size;
     75    /// The found cycle.
     76    Path *_cycle_path;
     77
     78    bool _local_path;
     79    bool _cycle_found;
     80    Node _cycle_node;
     81
     82    typename Graph::template NodeMap<int> _component;
     83    int _component_num;
     84
     85    std::vector<Node> _nodes;
     86    std::vector<Edge> _edges;
     87    Tolerance<double> _tolerance;
     88
     89  public:
     90
     91    /// \brief The constructor of the class.
     92    ///
     93    /// The constructor of the class.
     94    ///
     95    /// \param graph The directed graph the algorithm runs on.
     96    /// \param length The length (cost) of the edges.
     97    MinMeanCycle( const Graph &graph,
     98                  const LengthMap &length ) :
     99      _graph(graph), _length(length), _dist(graph), _reached(graph),
     100      _policy(graph), _component(graph), _cycle_length(0),
     101      _cycle_size(-1), _cycle_path(NULL), _local_path(false)
     102    { }
     103
     104    /// The destructor of the class.
     105    ~MinMeanCycle() {
     106      if (_local_path) delete _cycle_path;
     107    }
    83108
    84109  protected:
    85110
    86     /// \brief Node map for storing path data.
    87     ///
    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.
    91     PathDataNodeMap dmap;
    92 
    93     /// \brief The directed graph the algorithm runs on.
    94     const Graph &graph;
    95     /// \brief The length of the edges.
    96     const LengthMap &length;
    97 
    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;
    102     /// \brief A node for obtaining a minimum mean cycle.
    103     Node cycle_node;
    104 
    105     /// \brief The found cycle.
    106     Path *cycle_path;
    107     /// \brief The algorithm uses local \ref lemon::Path "Path"
    108     /// structure to store 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), comp(_graph),
    133       cycle_length(0), cycle_size(-1), cycle_node(INVALID),
    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 for the current
    145     /// component.
    146     void initCurrent() {
    147       nodes.clear();
     111    // Initializes the internal data structures for the current strongly
     112    // connected component and creating the policy graph.
     113    // The policy graph can be represented by the _policy map because
     114    // the out degree of every node is 1.
     115    bool initCurrentComponent(int comp) {
    148116      // 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();
    154       for (int i = 0; i < n; ++i) {
    155         dmap[nodes[i]].resize(n + 1);
    156       }
    157     }
    158 
    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);
    163       process.clear();
    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);
    170       }
    171       // Processing other rounds
    172       int n = nodes.size(), k;
    173       for (k = 2; k <= n && process.size() < n; ++k)
    174         processNextBuildRound(k);
    175       for ( ; k <= n; ++k)
    176         processNextFullRound(k);
    177     }
    178 
    179     /// \brief Processes one round of computing required path data and
    180     /// rebuilds \ref process vector.
    181     void processNextBuildRound(int k) {
    182       NodeVector next;
    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) {
    188             next.push_back(v);
    189             dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e);
    190           }
    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);
    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) {
    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);
    209           }
    210         }
    211       }
    212     }
    213 
    214     /// \brief Finds the minimum cycle mean value in the current
    215     /// component.
    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;
    221         Length len;
    222         int size;
    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;
    227           int _size = n - k;
    228           if (!found_one || len * _size < _len * size) {
    229             found_one = true;
    230             len = _len;
    231             size = _size;
    232           }
    233         }
    234         if ( found_one &&
    235              (!found_min || len * min_size < min_length * size) ) {
    236           found_min = true;
    237           min_length = len;
    238           min_size = size;
    239           min_node = nodes[i];
    240         }
    241       }
    242       return found_min;
     117      _nodes.clear();
     118      for (NodeIt n(_graph); n != INVALID; ++n) {
     119        if (_component[n] == comp) _nodes.push_back(n);
     120      }
     121      if (_nodes.size() <= 1) return false;
     122      // Finding the edges of the current component
     123      _edges.clear();
     124      for (EdgeIt e(_graph); e != INVALID; ++e) {
     125        if ( _component[_graph.source(e)] == comp &&
     126             _component[_graph.target(e)] == comp )
     127          _edges.push_back(e);
     128      }
     129      // Initializing _reached, _dist, _policy maps
     130      for (int i = 0; i < _nodes.size(); ++i) {
     131        _reached[_nodes[i]] = false;
     132        _policy[_nodes[i]] = INVALID;
     133      }
     134      Node u; Edge e;
     135      for (int j = 0; j < _edges.size(); ++j) {
     136        e = _edges[j];
     137        u = _graph.source(e);
     138        if (!_reached[u] || _length[e] < _dist[u]) {
     139          _dist[u] = _length[e];
     140          _policy[u] = e;
     141          _reached[u] = true;
     142        }
     143      }
     144      return true;
     145    }
     146
     147    // Finds all cycles in the policy graph.
     148    // Sets _cycle_found to true if a cycle is found and sets
     149    // _cycle_length, _cycle_size, _cycle_node to represent the minimum
     150    // mean cycle in the policy graph.
     151    bool findPolicyCycles(int comp) {
     152      typename Graph::template NodeMap<int> level(_graph, -1);
     153      _cycle_found = false;
     154      Length clength;
     155      int csize;
     156      int path_cnt = 0;
     157      Node u, v;
     158      // Searching for cycles
     159      for (int i = 0; i < _nodes.size(); ++i) {
     160        if (level[_nodes[i]] < 0) {
     161          u = _nodes[i];
     162          level[u] = path_cnt;
     163          while (level[u = _graph.target(_policy[u])] < 0)
     164            level[u] = path_cnt;
     165          if (level[u] == path_cnt) {
     166            // A cycle is found
     167            clength = _length[_policy[u]];
     168            csize = 1;
     169            for (v = u; (v = _graph.target(_policy[v])) != u; ) {
     170              clength += _length[_policy[v]];
     171              ++csize;
     172            }
     173            if ( !_cycle_found ||
     174                 clength * _cycle_size < _cycle_length * csize ) {
     175              _cycle_found = true;
     176              _cycle_length = clength;
     177              _cycle_size = csize;
     178              _cycle_node = u;
     179            }
     180          }
     181          ++path_cnt;
     182        }
     183      }
     184      return _cycle_found;
     185    }
     186
     187    // Contracts the policy graph to be connected by cutting all cycles
     188    // except for the main cycle (i.e. the minimum mean cycle).
     189    void contractPolicyGraph(int comp) {
     190      // Finding the component of the main cycle using
     191      // reverse BFS search
     192      typename Graph::template NodeMap<int> found(_graph, false);
     193      std::deque<Node> queue;
     194      queue.push_back(_cycle_node);
     195      found[_cycle_node] = true;
     196      Node u, v;
     197      while (!queue.empty()) {
     198        v = queue.front(); queue.pop_front();
     199        for (InEdgeIt e(_graph, v); e != INVALID; ++e) {
     200          u = _graph.source(e);
     201          if (_component[u] == comp && !found[u] && _policy[u] == e) {
     202            found[u] = true;
     203            queue.push_back(u);
     204          }
     205        }
     206      }
     207      // Connecting all other nodes to this component using
     208      // reverse BFS search
     209      queue.clear();
     210      for (int i = 0; i < _nodes.size(); ++i)
     211        if (found[_nodes[i]]) queue.push_back(_nodes[i]);
     212      int found_cnt = queue.size();
     213      while (found_cnt < _nodes.size() && !queue.empty()) {
     214        v = queue.front(); queue.pop_front();
     215        for (InEdgeIt e(_graph, v); e != INVALID; ++e) {
     216          u = _graph.source(e);
     217          if (_component[u] == comp && !found[u]) {
     218            found[u] = true;
     219            ++found_cnt;
     220            _policy[u] = e;
     221            queue.push_back(u);
     222          }
     223        }
     224      }
     225    }
     226
     227    // Computes node distances in the policy graph and updates the
     228    // policy graph if the node distances can be improved.
     229    bool computeNodeDistances(int comp) {
     230      // Computing node distances using reverse BFS search
     231      double cycle_mean = (double)_cycle_length / _cycle_size;
     232      typename Graph::template NodeMap<int> found(_graph, false);
     233      std::deque<Node> queue;
     234      queue.push_back(_cycle_node);
     235      found[_cycle_node] = true;
     236      Node u, v;
     237      while (!queue.empty()) {
     238        v = queue.front(); queue.pop_front();
     239        for (InEdgeIt e(_graph, v); e != INVALID; ++e) {
     240          u = _graph.source(e);
     241          if (_component[u] == comp && !found[u] && _policy[u] == e) {
     242            found[u] = true;
     243            _dist[u] = _dist[v] + _length[e] - cycle_mean;
     244            queue.push_back(u);
     245          }
     246        }
     247      }
     248      // Improving node distances
     249      bool improved = false;
     250      for (int j = 0; j < _edges.size(); ++j) {
     251        Edge e = _edges[j];
     252        u = _graph.source(e); v = _graph.target(e);
     253        double delta = _dist[v] + _length[e] - cycle_mean;
     254        if (_tolerance.less(delta, _dist[u])) {
     255          improved = true;
     256          _dist[u] = delta;
     257          _policy[u] = e;
     258        }
     259      }
     260      return improved;
    243261    }
    244262
     
    249267    /// Runs the algorithm.
    250268    ///
    251     /// \return \c true if a cycle exists in the graph.
    252     ///
    253     /// \note Apart from the return value, <tt>m.run()</tt> is just a
     269    /// \return Returns \c true if a directed cycle exists in the graph.
     270    ///
     271    /// \note Apart from the return value, <tt>mmc.run()</tt> is just a
    254272    /// shortcut of the following code.
    255273    /// \code
    256     ///   m.init();
    257     ///   m.findMinMean();
    258     ///   m.findCycle();
     274    ///   mmc.init();
     275    ///   mmc.findMinMean();
     276    ///   mmc.findCycle();
    259277    /// \endcode
    260278    bool run() {
    261279      init();
    262       findMinMean();
    263       return findCycle();
     280      return findMinMean() && findCycle();
    264281    }
    265282
     
    270287    /// \sa reset()
    271288    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.
     289      _tolerance.epsilon(1e-8);
     290      if (!_cycle_path) {
     291        _local_path = true;
     292        _cycle_path = new Path;
     293      }
     294      _cycle_found = false;
     295      _component_num = stronglyConnectedComponents(_graph, _component);
     296    }
     297
     298    /// \brief Resets the internal data structures.
     299    ///
     300    /// Resets the internal data structures so that \ref findMinMean()
     301    /// and \ref findCycle() can be called again (e.g. when the
     302    /// underlaying graph has been modified).
     303    ///
     304    /// \sa init()
     305    void reset() {
     306      if (_cycle_path) _cycle_path->clear();
     307      _cycle_found = false;
     308      _component_num = stronglyConnectedComponents(_graph, _component);
     309    }
     310
     311    /// \brief Finds the minimum cycle mean length in the graph.
     312    ///
     313    /// Computes all the required data and finds the minimum cycle mean
     314    /// length in the graph.
     315    ///
     316    /// \return Returns \c true if a directed cycle exists in the graph.
    285317    ///
    286318    /// \pre \ref init() must be called before using this function.
    287319    bool findMinMean() {
    288       cycle_node = INVALID;
    289       for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {
    290         initCurrent();
    291         processRounds();
    292 
    293         Length min_length;
    294         int min_size;
    295         Node min_node;
    296         bool found_min = findCurrentMin(min_length, min_size, min_node);
    297 
    298         if ( found_min && (cycle_node == INVALID ||
    299              min_length * cycle_size < cycle_length * min_size) ) {
    300           cycle_length = min_length;
    301           cycle_size = min_size;
    302           cycle_node = min_node;
    303         }
    304       }
    305       return (cycle_node != INVALID);
    306     }
    307 
    308     /// \brief Finds a critical (minimum mean) cycle.
    309     ///
    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.
     320      // Finding the minimum mean cycle in the components
     321      for (int comp = 0; comp < _component_num; ++comp) {
     322        if (!initCurrentComponent(comp)) continue;
     323        while (true) {
     324          if (!findPolicyCycles(comp)) return false;
     325          contractPolicyGraph(comp);
     326          if (!computeNodeDistances(comp)) return true;
     327        }
     328      }
     329    }
     330
     331    /// \brief Finds a critical (minimum mean) directed cycle.
     332    ///
     333    /// Finds a critical (minimum mean) directed cycle using the data
     334    /// computed in the \ref findMinMean() function.
     335    ///
     336    /// \return Returns \c true if a directed cycle exists in the graph.
    314337    ///
    315338    /// \pre \ref init() and \ref findMinMean() must be called before
    316339    /// using this function.
    317340    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;
     341      if (!_cycle_found) return false;
     342      _cycle_path->addBack(_policy[_cycle_node]);
     343      for ( Node v = _cycle_node;
     344            (v = _graph.target(_policy[v])) != _cycle_node; ) {
     345        _cycle_path->addBack(_policy[v]);
    339346      }
    340347      return true;
    341348    }
    342349
    343     /// \brief Resets the internal data structures.
    344     ///
    345     /// Resets the internal data structures so that \ref findMinMean()
    346     /// and \ref findCycle() can be called again (e.g. when the
    347     /// underlaying graph has been modified).
    348     ///
    349     /// \sa init()
    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     }
    357 
    358350    /// \brief Returns the total length of the found cycle.
    359351    ///
    360352    /// Returns the total length of the found cycle.
    361     ///
    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.
    365     Length cycleLength() const {
    366       return cycle_length;
    367     }
    368 
    369     /// \brief Returns the number of edges in the found cycle.
    370     ///
    371     /// Returns the number of edges in the found cycle.
    372     ///
    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.
    376     int cycleEdgeNum() const {
    377       return cycle_size;
    378     }
    379 
    380     /// \brief Returns the mean length of the found cycle.
    381     ///
    382     /// Returns the mean length of the found cycle.
    383353    ///
    384354    /// \pre \ref run() or \ref findMinMean() must be called before
    385355    /// using this function.
    386     ///
    387     /// \warning LengthMap::Value must be convertible to double.
    388     ///
    389     /// \note <tt>m.minMean()</tt> is just a shortcut of the following
    390     /// code.
     356    Length cycleLength() const {
     357      return _cycle_length;
     358    }
     359
     360    /// \brief Returns the number of edges on the found cycle.
     361    ///
     362    /// Returns the number of edges on the found cycle.
     363    ///
     364    /// \pre \ref run() or \ref findMinMean() must be called before
     365    /// using this function.
     366    int cycleEdgeNum() const {
     367      return _cycle_size;
     368    }
     369
     370    /// \brief Returns the mean length of the found cycle.
     371    ///
     372    /// Returns the mean length of the found cycle.
     373    ///
     374    /// \pre \ref run() or \ref findMinMean() must be called before
     375    /// using this function.
     376    ///
     377    /// \note <tt>mmc.cycleMean()</tt> is just a shortcut of the
     378    /// following code.
    391379    /// \code
    392     ///   return m.cycleLength() / double(m.cycleEdgeNum());
     380    ///   return double(mmc.cycleLength()) / mmc.cycleEdgeNum();
    393381    /// \endcode
    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.
    397     double minMean() const {
    398       return cycle_length / (double)cycle_size;
    399     }
    400 
    401     /// \brief Returns a const reference to the \ref lemon::Path "Path"
    402     /// structure of the found cycle.
    403     ///
    404     /// Returns a const reference to the \ref lemon::Path "Path"
    405     /// structure of the found cycle.
    406     ///
    407     /// \pre \ref run() must be called before using this function.
    408     ///
    409     /// \sa \ref cyclePath()
     382    double cycleMean() const {
     383      return (double)_cycle_length / _cycle_size;
     384    }
     385
     386    /// \brief Returns a const reference to the \ref Path "path"
     387    /// structure storing the found cycle.
     388    ///
     389    /// Returns a const reference to the \ref Path "path"
     390    /// structure storing the found cycle.
     391    ///
     392    /// \pre \ref run() or \ref findCycle() must be called before using
     393    /// this function.
     394    ///
     395    /// \sa cyclePath()
    410396    const Path& cycle() const {
    411       return *cycle_path;
    412     }
    413 
    414     /// \brief Sets the \ref lemon::Path "Path" structure storing the
     397      return *_cycle_path;
     398    }
     399
     400    /// \brief Sets the \ref Path "path" structure for storing the found
     401    /// cycle.
     402    ///
     403    /// Sets an external \ref Path "path" structure for storing the
    415404    /// found cycle.
    416405    ///
    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
    420     /// this automatically allocated map, of course.
    421     ///
    422     /// \note The algorithm calls only the \ref lemon::Path::addFront()
    423     /// "addFront()" method of the given \ref lemon::Path "Path"
     406    /// If you don't call this function before calling \ref run() or
     407    /// \ref init(), it will allocate a local \ref Path "path"
    424408    /// structure.
    425     ///
    426     /// \return \c (*this)
     409    /// The destuctor deallocates this automatically allocated map,
     410    /// of course.
     411    ///
     412    /// \note The algorithm calls only the \ref lemon::Path::addBack()
     413    /// "addBack()" function of the given \ref Path "path" structure.
     414    ///
     415    /// \return <tt>(*this)</tt>
     416    ///
     417    /// \sa cycle()
    427418    MinMeanCycle& cyclePath(Path &path) {
    428       if (local_path) {
    429         delete cycle_path;
    430         local_path = false;
    431       }
    432       cycle_path = &path;
     419      if (_local_path) {
     420        delete _cycle_path;
     421        _local_path = false;
     422      }
     423      _cycle_path = &path;
    433424      return *this;
    434425    }
Note: See TracChangeset for help on using the changeset viewer.