COIN-OR::LEMON - Graph Library

Changeset 2583:7216b6a52ab9 in lemon-0.x


Ignore:
Timestamp:
02/28/08 03:57:36 (11 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3465
Message:

Small fixes and doc improvements in MinMeanCycle?.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/min_mean_cycle.h

    r2555 r2583  
    2727#include <vector>
    2828#include <lemon/graph_utils.h>
    29 #include <lemon/topology.h>
    3029#include <lemon/path.h>
    3130#include <lemon/tolerance.h>
     31#include <lemon/topology.h>
    3232
    3333namespace lemon {
     
    4242  /// minimum mean directed cycle.
    4343  ///
    44   /// \param Graph The directed graph type the algorithm runs on.
    45   /// \param LengthMap The type of the length (cost) map.
     44  /// \tparam Graph The directed graph type the algorithm runs on.
     45  /// \tparam LengthMap The type of the length (cost) map.
    4646  ///
    4747  /// \warning \c LengthMap::Value must be convertible to \c double.
     
    5858    typedef Path<Graph> Path;
    5959
    60   protected:
     60  private:
     61
     62    // The directed graph the algorithm runs on
     63    const Graph &_graph;
     64    // The length of the edges
     65    const LengthMap &_length;
     66
     67    // The total length of the found cycle
     68    Length _cycle_length;
     69    // The number of edges on the found cycle
     70    int _cycle_size;
     71    // The found cycle
     72    Path *_cycle_path;
     73
     74    bool _local_path;
     75    bool _cycle_found;
     76    Node _cycle_node;
    6177
    6278    typename Graph::template NodeMap<bool> _reached;
    6379    typename Graph::template NodeMap<double> _dist;
    6480    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;
    8181
    8282    typename Graph::template NodeMap<int> _component;
     
    9797    MinMeanCycle( const Graph &graph,
    9898                  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     { }
     99      _graph(graph), _length(length), _cycle_length(0), _cycle_size(-1),
     100      _cycle_path(NULL), _local_path(false), _reached(graph),
     101      _dist(graph), _policy(graph), _component(graph)
     102    {}
    103103
    104104    /// The destructor of the class.
     
    107107    }
    108108
    109   protected:
     109    /// \brief Sets the \ref Path "path" structure for storing the found
     110    /// cycle.
     111    ///
     112    /// Sets an external \ref Path "path" structure for storing the
     113    /// found cycle.
     114    ///
     115    /// If you don't call this function before calling \ref run() or
     116    /// \ref init(), it will allocate a local \ref Path "path"
     117    /// structure.
     118    /// The destuctor deallocates this automatically allocated map,
     119    /// of course.
     120    ///
     121    /// \note The algorithm calls only the \ref lemon::Path::addBack()
     122    /// "addBack()" function of the given \ref Path "path" structure.
     123    ///
     124    /// \return <tt>(*this)</tt>
     125    ///
     126    /// \sa cycle()
     127    MinMeanCycle& cyclePath(Path &path) {
     128      if (_local_path) {
     129        delete _cycle_path;
     130        _local_path = false;
     131      }
     132      _cycle_path = &path;
     133      return *this;
     134    }
     135
     136    /// \name Execution control
     137    /// The simplest way to execute the algorithm is to call run().
     138    /// \n
     139    /// If you only need the minimum mean value, you may call init()
     140    /// and findMinMean().
     141    /// \n
     142    /// If you would like to run the algorithm again (e.g. the
     143    /// underlaying graph and/or the edge costs were modified), you may
     144    /// not create a new instance of the class, rather call reset(),
     145    /// findMinMean(), and findCycle() instead.
     146
     147    /// @{
     148
     149    /// \brief Runs the algorithm.
     150    ///
     151    /// Runs the algorithm.
     152    ///
     153    /// \return Returns \c true if a directed cycle exists in the graph.
     154    ///
     155    /// \note Apart from the return value, <tt>mmc.run()</tt> is just a
     156    /// shortcut of the following code.
     157    /// \code
     158    ///   mmc.init();
     159    ///   mmc.findMinMean();
     160    ///   mmc.findCycle();
     161    /// \endcode
     162    bool run() {
     163      init();
     164      return findMinMean() && findCycle();
     165    }
     166
     167    /// \brief Initializes the internal data structures.
     168    ///
     169    /// Initializes the internal data structures.
     170    ///
     171    /// \sa reset()
     172    void init() {
     173      _tolerance.epsilon(1e-6);
     174      if (!_cycle_path) {
     175        _local_path = true;
     176        _cycle_path = new Path;
     177      }
     178      _cycle_found = false;
     179      _component_num = stronglyConnectedComponents(_graph, _component);
     180    }
     181
     182    /// \brief Resets the internal data structures.
     183    ///
     184    /// Resets the internal data structures so that \ref findMinMean()
     185    /// and \ref findCycle() can be called again (e.g. when the
     186    /// underlaying graph has been modified).
     187    ///
     188    /// \sa init()
     189    void reset() {
     190      if (_cycle_path) _cycle_path->clear();
     191      _cycle_found = false;
     192      _component_num = stronglyConnectedComponents(_graph, _component);
     193    }
     194
     195    /// \brief Finds the minimum cycle mean length in the graph.
     196    ///
     197    /// Computes all the required data and finds the minimum cycle mean
     198    /// length in the graph.
     199    ///
     200    /// \return Returns \c true if a directed cycle exists in the graph.
     201    ///
     202    /// \pre \ref init() must be called before using this function.
     203    bool findMinMean() {
     204      // Finding the minimum mean cycle in the components
     205      for (int comp = 0; comp < _component_num; ++comp) {
     206        if (!initCurrentComponent(comp)) continue;
     207        while (true) {
     208          if (!findPolicyCycles()) break;
     209          contractPolicyGraph(comp);
     210          if (!computeNodeDistances(comp)) break;
     211        }
     212      }
     213      return _cycle_found;
     214    }
     215
     216    /// \brief Finds a critical (minimum mean) directed cycle.
     217    ///
     218    /// Finds a critical (minimum mean) directed cycle using the data
     219    /// computed in the \ref findMinMean() function.
     220    ///
     221    /// \return Returns \c true if a directed cycle exists in the graph.
     222    ///
     223    /// \pre \ref init() and \ref findMinMean() must be called before
     224    /// using this function.
     225    bool findCycle() {
     226      if (!_cycle_found) return false;
     227      _cycle_path->addBack(_policy[_cycle_node]);
     228      for ( Node v = _cycle_node;
     229            (v = _graph.target(_policy[v])) != _cycle_node; ) {
     230        _cycle_path->addBack(_policy[v]);
     231      }
     232      return true;
     233    }
     234   
     235    /// @}
     236
     237    /// \name Query Functions
     238    /// The result of the algorithm can be obtained using these
     239    /// functions.
     240    /// \n run() must be called before using them.
     241
     242    /// @{
     243   
     244    /// \brief Returns the total length of the found cycle.
     245    ///
     246    /// Returns the total length of the found cycle.
     247    ///
     248    /// \pre \ref run() or \ref findMinMean() must be called before
     249    /// using this function.
     250    Length cycleLength() const {
     251      return _cycle_length;
     252    }
     253
     254    /// \brief Returns the number of edges on the found cycle.
     255    ///
     256    /// Returns the number of edges on the found cycle.
     257    ///
     258    /// \pre \ref run() or \ref findMinMean() must be called before
     259    /// using this function.
     260    int cycleEdgeNum() const {
     261      return _cycle_size;
     262    }
     263
     264    /// \brief Returns the mean length of the found cycle.
     265    ///
     266    /// Returns the mean length of the found cycle.
     267    ///
     268    /// \pre \ref run() or \ref findMinMean() must be called before
     269    /// using this function.
     270    ///
     271    /// \note <tt>mmc.cycleMean()</tt> is just a shortcut of the
     272    /// following code.
     273    /// \code
     274    ///   return double(mmc.cycleLength()) / mmc.cycleEdgeNum();
     275    /// \endcode
     276    double cycleMean() const {
     277      return double(_cycle_length) / _cycle_size;
     278    }
     279
     280    /// \brief Returns a const reference to the \ref Path "path"
     281    /// structure storing the found cycle.
     282    ///
     283    /// Returns a const reference to the \ref Path "path"
     284    /// structure storing the found cycle.
     285    ///
     286    /// \pre \ref run() or \ref findCycle() must be called before using
     287    /// this function.
     288    ///
     289    /// \sa cyclePath()
     290    const Path& cycle() const {
     291      return *_cycle_path;
     292    }
     293   
     294    ///@}
     295   
     296  private:
    110297
    111298    // Initializes the internal data structures for the current strongly
     
    128315      }
    129316      // Initializing _reached, _dist, _policy maps
    130       for (int i = 0; i < _nodes.size(); ++i) {
     317      for (int i = 0; i < int(_nodes.size()); ++i) {
    131318        _reached[_nodes[i]] = false;
    132319        _policy[_nodes[i]] = INVALID;
    133320      }
    134321      Node u; Edge e;
    135       for (int j = 0; j < _edges.size(); ++j) {
     322      for (int j = 0; j < int(_edges.size()); ++j) {
    136323        e = _edges[j];
    137324        u = _graph.source(e);
     
    149336    // _cycle_length, _cycle_size, _cycle_node to represent the minimum
    150337    // mean cycle in the policy graph.
    151     bool findPolicyCycles(int comp) {
     338    bool findPolicyCycles() {
    152339      typename Graph::template NodeMap<int> level(_graph, -1);
    153       _cycle_found = false;
     340      bool curr_cycle_found = false;
    154341      Length clength;
    155342      int csize;
     
    157344      Node u, v;
    158345      // Searching for cycles
    159       for (int i = 0; i < _nodes.size(); ++i) {
     346      for (int i = 0; i < int(_nodes.size()); ++i) {
    160347        if (level[_nodes[i]] < 0) {
    161348          u = _nodes[i];
     
    165352          if (level[u] == path_cnt) {
    166353            // A cycle is found
     354            curr_cycle_found = true;
    167355            clength = _length[_policy[u]];
    168356            csize = 1;
     
    182370        }
    183371      }
    184       return _cycle_found;
     372      return curr_cycle_found;
    185373    }
    186374
     
    208396      // reverse BFS search
    209397      queue.clear();
    210       for (int i = 0; i < _nodes.size(); ++i)
     398      for (int i = 0; i < int(_nodes.size()); ++i)
    211399        if (found[_nodes[i]]) queue.push_back(_nodes[i]);
    212400      int found_cnt = queue.size();
    213       while (found_cnt < _nodes.size() && !queue.empty()) {
     401      while (found_cnt < int(_nodes.size()) && !queue.empty()) {
    214402        v = queue.front(); queue.pop_front();
    215403        for (InEdgeIt e(_graph, v); e != INVALID; ++e) {
     
    229417    bool computeNodeDistances(int comp) {
    230418      // Computing node distances using reverse BFS search
    231       double cycle_mean = (double)_cycle_length / _cycle_size;
     419      double cycle_mean = double(_cycle_length) / _cycle_size;
    232420      typename Graph::template NodeMap<int> found(_graph, false);
    233421      std::deque<Node> queue;
    234422      queue.push_back(_cycle_node);
    235423      found[_cycle_node] = true;
     424      _dist[_cycle_node] = 0;
    236425      Node u, v;
    237426      while (!queue.empty()) {
     
    248437      // Improving node distances
    249438      bool improved = false;
    250       for (int j = 0; j < _edges.size(); ++j) {
     439      for (int j = 0; j < int(_edges.size()); ++j) {
    251440        Edge e = _edges[j];
    252441        u = _graph.source(e); v = _graph.target(e);
     
    261450    }
    262451
    263   public:
    264 
    265     /// \brief Runs the algorithm.
    266     ///
    267     /// Runs the algorithm.
    268     ///
    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
    272     /// shortcut of the following code.
    273     /// \code
    274     ///   mmc.init();
    275     ///   mmc.findMinMean();
    276     ///   mmc.findCycle();
    277     /// \endcode
    278     bool run() {
    279       init();
    280       return findMinMean() && findCycle();
    281     }
    282 
    283     /// \brief Initializes the internal data structures.
    284     ///
    285     /// Initializes the internal data structures.
    286     ///
    287     /// \sa reset()
    288     void init() {
    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.
    317     ///
    318     /// \pre \ref init() must be called before using this function.
    319     bool findMinMean() {
    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.
    337     ///
    338     /// \pre \ref init() and \ref findMinMean() must be called before
    339     /// using this function.
    340     bool findCycle() {
    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]);
    346       }
    347       return true;
    348     }
    349 
    350     /// \brief Returns the total length of the found cycle.
    351     ///
    352     /// Returns the total length of the found cycle.
    353     ///
    354     /// \pre \ref run() or \ref findMinMean() must be called before
    355     /// using this function.
    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.
    379     /// \code
    380     ///   return double(mmc.cycleLength()) / mmc.cycleEdgeNum();
    381     /// \endcode
    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()
    396     const Path& cycle() const {
    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
    404     /// found cycle.
    405     ///
    406     /// If you don't call this function before calling \ref run() or
    407     /// \ref init(), it will allocate a local \ref Path "path"
    408     /// structure.
    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()
    418     MinMeanCycle& cyclePath(Path &path) {
    419       if (_local_path) {
    420         delete _cycle_path;
    421         _local_path = false;
    422       }
    423       _cycle_path = &path;
    424       return *this;
    425     }
    426 
    427452  }; //class MinMeanCycle
    428453
Note: See TracChangeset for help on using the changeset viewer.