COIN-OR::LEMON - Graph Library

Changeset 2437:02c7076bf894 in lemon-0.x


Ignore:
Timestamp:
05/07/07 10:47:38 (17 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3274
Message:

Small improvements in MinMeanCycle? class.

Patch from Peter Kovacs

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/min_mean_cycle.h

    r2413 r2437  
    2222/// \ingroup min_cost_flow
    2323///
    24 /// \file 
     24/// \file
    2525/// \brief Karp algorithm for finding a minimum mean cycle.
    2626
     
    4545  /// \author Peter Kovacs
    4646
    47 #ifdef DOXYGEN
    48   template <typename Graph, typename LengthMap>
    49 #else
    5047  template <typename Graph,
    5148    typename LengthMap = typename Graph::template EdgeMap<int> >
    52 #endif
    53 
    5449  class MinMeanCycle
    5550  {
     
    6661    typedef Path<Graph> Path;
    6762    typedef std::vector<Node> NodeVector;
    68     typedef typename NodeVector::iterator NodeVectorIt;
    6963
    7064  protected:
     
    9084
    9185    /// \brief Node map for storing path data.
    92     /// 
     86    ///
    9387    /// Node map for storing path data of all nodes in the current
    94     /// component. dmap[v][k] is the length of a shortest directed walk 
     88    /// component. dmap[v][k] is the length of a shortest directed walk
    9589    /// to node v from the starting node containing exactly k edges.
    9690    PathDataNodeMap dmap;
    97    
     91
    9892    /// \brief The directed graph the algorithm runs on.
    99     const Graph& graph;
     93    const Graph &graph;
    10094    /// \brief The length of the edges.
    101     const LengthMap& length;
    102    
     95    const LengthMap &length;
     96
    10397    /// \brief The total length of the found cycle.
    10498    Length cycle_length;
    10599    /// \brief The number of edges in the found cycle.
    106100    int cycle_size;
    107     /// \brief A node for obtaining a minimum mean cycle. 
     101    /// \brief A node for obtaining a minimum mean cycle.
    108102    Node cycle_node;
    109103
    110104    /// \brief The found cycle.
    111105    Path *cycle_path;
    112     /// \brief The algorithm uses local \ref lemon::Path "Path" 
     106    /// \brief The algorithm uses local \ref lemon::Path "Path"
    113107    /// structure to store the found cycle.
    114108    bool local_path;
    115    
     109
    116110    /// \brief Node map for identifying strongly connected components.
    117111    IntNodeMap comp;
     
    124118    /// \brief The processed nodes in the last round.
    125119    NodeVector process;
    126    
     120
    127121  public :
    128122
     
    133127    /// \param _graph The directed graph the algorithm runs on.
    134128    /// \param _length The length (cost) of the edges.
    135     MinMeanCycle( const Graph& _graph,
    136                   const LengthMap& _length ) :
     129    MinMeanCycle( const Graph &_graph,
     130                  const LengthMap &_length ) :
    137131      graph(_graph), length(_length), dmap(_graph), comp(_graph),
    138132      cycle_length(0), cycle_size(-1), cycle_node(INVALID),
     
    141135
    142136    /// \brief The destructor of the class.
    143     ~MinMeanCycle() { 
     137    ~MinMeanCycle() {
    144138      if (local_path) delete cycle_path;
    145139    }
     
    157151      // Creating vectors for all nodes
    158152      int n = nodes.size();
    159       for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
    160         dmap[*vi].resize(n + 1);
    161       }
    162     }
    163    
    164     /// \brief Processes all rounds of computing required path data for 
     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
    165159    /// the current component.
    166160    void processRounds() {
     
    174168        process.push_back(v);
    175169      }
    176       // Processing other rounds 
     170      // Processing other rounds
    177171      int n = nodes.size(), k;
    178       for (k = 2; k <= n && process.size() < n; ++k) {
     172      for (k = 2; k <= n && process.size() < n; ++k)
    179173        processNextBuildRound(k);
    180       }
    181       for ( ; k <= n; ++k) {
     174      for ( ; k <= n; ++k)
    182175        processNextFullRound(k);
    183       }
    184     }
    185    
     176    }
     177
    186178    /// \brief Processes one round of computing required path data and
    187179    /// rebuilds \ref process vector.
    188180    void processNextBuildRound(int k) {
    189181      NodeVector next;
    190       for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) {
    191         for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
     182      for (int i = 0; i < process.size(); ++i) {
     183        for (OutEdgeIt e(graph, process[i]); e != INVALID; ++e) {
    192184          Node v = graph.target(e);
    193185          if (comp[v] != comp_cnt) continue;
    194186          if (!dmap[v][k].found) {
    195187            next.push_back(v);
    196             dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
     188            dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e);
    197189          }
    198           else if (dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist) {
    199             dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
     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);
    200192          }
    201193        }
     
    207199    /// using \ref nodes vector instead of \ref process vector.
    208200    void processNextFullRound(int k) {
    209       for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {
    210         for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
     201      for (int i = 0; i < nodes.size(); ++i) {
     202        for (OutEdgeIt e(graph, nodes[i]); e != INVALID; ++e) {
    211203          Node v = graph.target(e);
    212204          if (comp[v] != comp_cnt) continue;
    213           if ( !dmap[v][k].found || 
    214                dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist ) {
    215             dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
     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);
    216208          }
    217209        }
    218210      }
    219211    }
    220    
    221     /// \brief Finds the minimum cycle mean value in the current 
     212
     213    /// \brief Finds the minimum cycle mean value in the current
    222214    /// component.
    223215    bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) {
    224216      bool found_min = false;
    225       for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
     217      for (int i = 0; i < nodes.size(); ++i) {
    226218        int n = nodes.size();
    227         if (!dmap[*vi][n].found) continue;
     219        if (!dmap[nodes[i]][n].found) continue;
    228220        Length len;
    229221        int size;
    230222        bool found_one = false;
    231223        for (int k = 0; k < n; ++k) {
    232           if (!dmap[*vi][k].found) continue;
    233           Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist;
    234           int _size = 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;
    235227          if (!found_one || len * _size < _len * size) {
    236228            found_one = true;
     
    239231          }
    240232        }
    241         if ( found_one && 
     233        if ( found_one &&
    242234             (!found_min || len * min_size < min_length * size) ) {
    243235          found_min = true;
    244236          min_length = len;
    245237          min_size = size;
    246           min_node = *vi;
     238          min_node = nodes[i];
    247239        }
    248240      }
    249241      return found_min;
    250242    }
    251    
    252   public: 
    253    
     243
     244  public:
     245
    254246    /// \brief Runs the algorithm.
    255247    ///
     
    258250    /// \return \c true if a cycle exists in the graph.
    259251    ///
    260     /// \note Apart from the return value, m.run() is just a shortcut 
     252    /// \note Apart from the return value, m.run() is just a shortcut
    261253    /// of the following code.
    262254    /// \code
     
    270262      return findCycle();
    271263    }
    272    
     264
    273265    /// \brief Initializes the internal data structures.
    274266    void init() {
     
    286278    ///
    287279    /// \return \c true if a cycle exists in the graph.
    288     /// 
     280    ///
    289281    /// \pre \ref init() must be called before using this function.
    290282    bool findMinMean() {
     
    293285        initCurrent();
    294286        processRounds();
    295        
     287
    296288        Length min_length;
    297289        int min_size;
    298290        Node min_node;
    299291        bool found_min = findCurrentMin(min_length, min_size, min_node);
    300        
    301         if ( found_min && (cycle_node == INVALID || 
     292
     293        if ( found_min && (cycle_node == INVALID ||
    302294             min_length * cycle_size < cycle_length * min_size) ) {
    303295          cycle_length = min_length;
     
    308300      return (cycle_node != INVALID);
    309301    }
    310    
     302
    311303    /// \brief Finds a critical (minimum mean) cycle.
    312304    ///
     
    315307    ///
    316308    /// \return \c true if a cycle exists in the graph.
    317     /// 
    318     /// \pre \ref init() and \ref findMinMean() must be called before 
     309    ///
     310    /// \pre \ref init() and \ref findMinMean() must be called before
    319311    /// using this function.
    320312    bool findCycle() {
     
    346338    /// \brief Resets the internal data structures.
    347339    ///
    348     /// Resets the internal data structures so that \ref findMinMean() 
    349     /// and \ref findCycle() can be called again (e.g. when the 
     340    /// Resets the internal data structures so that \ref findMinMean()
     341    /// and \ref findCycle() can be called again (e.g. when the
    350342    /// underlaying graph has been modified).
    351343    void reset() {
     
    356348      comp_num = stronglyConnectedComponents(graph, comp);
    357349    }
    358    
     350
    359351    /// \brief Returns the total length of the found cycle.
    360352    ///
     
    362354    ///
    363355    /// \pre \ref run() must be called before using this function.
    364     Length cycleLength() const { 
     356    Length cycleLength() const {
    365357      return cycle_length;
    366358    }
    367    
     359
    368360    /// \brief Returns the number of edges in the found cycle.
    369361    ///
     
    371363    ///
    372364    /// \pre \ref run() must be called before using this function.
    373     int cycleEdgeNum() const { 
     365    int cycleEdgeNum() const {
    374366      return cycle_size;
    375367    }
    376    
     368
    377369    /// \brief Returns the mean length of the found cycle.
    378370    ///
     
    387379    ///   return m.cycleEdgeNum() / double(m.cycleLength());
    388380    /// \endcode
    389     double minMean() const { 
     381    double minMean() const {
    390382      return cycle_length / (double)cycle_size;
    391383    }
     
    400392    ///
    401393    /// \sa \ref cyclePath()
    402     const Path &cycle() const {
     394    const Path& cycle() const {
    403395      return *cycle_path;
    404396    }
    405    
    406     /// \brief Sets the \ref lemon::Path "Path" structure storing the 
     397
     398    /// \brief Sets the \ref lemon::Path "Path" structure storing the
    407399    /// found cycle.
    408     /// 
    409     /// Sets the \ref lemon::Path "Path" structure storing the found 
    410     /// cycle. If you don't use this function before calling 
    411     /// \ref run(), it will allocate one. The destuctor deallocates 
     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
    412404    /// this automatically allocated map, of course.
    413405    ///
    414406    /// \note The algorithm calls only the \ref lemon::Path::addFront()
    415     /// "addFront()" method of the given \ref lemon::Path "Path" 
     407    /// "addFront()" method of the given \ref lemon::Path "Path"
    416408    /// structure.
    417     /// 
     409    ///
    418410    /// \return \c (*this)
    419     MinMeanCycle &cyclePath(Path& path) {
     411    MinMeanCycle& cyclePath(Path &path) {
    420412      if (local_path) {
    421413        delete cycle_path;
Note: See TracChangeset for help on using the changeset viewer.