COIN-OR::LEMON - Graph Library

Changeset 2620:8f41a3129746 in lemon-0.x for lemon/capacity_scaling.h


Ignore:
Timestamp:
10/05/08 15:37:17 (11 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3505
Message:

Doc improvements

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r2589 r2620  
    5353  ///
    5454  /// \author Peter Kovacs
    55 
    5655  template < typename Graph,
    5756             typename LowerMap = typename Graph::template EdgeMap<int>,
     
    126125      {}
    127126
    128       /// Runs the algorithm from the given source node.
     127      /// Run the algorithm from the given source node.
    129128      Node run(Node s, Capacity delta = 1) {
    130129        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
     
    372371    }
    373372
    374     /// \brief Sets the flow map.
    375     ///
    376     /// Sets the flow map.
     373    /// \brief Set the flow map.
     374    ///
     375    /// Set the flow map.
    377376    ///
    378377    /// \return \c (*this)
     
    386385    }
    387386
    388     /// \brief Sets the potential map.
    389     ///
    390     /// Sets the potential map.
     387    /// \brief Set the potential map.
     388    ///
     389    /// Set the potential map.
    391390    ///
    392391    /// \return \c (*this)
     
    401400
    402401    /// \name Execution control
    403     /// The only way to execute the algorithm is to call the run()
    404     /// function.
    405402
    406403    /// @{
    407404
    408     /// \brief Runs the algorithm.
    409     ///
    410     /// Runs the algorithm.
     405    /// \brief Run the algorithm.
     406    ///
     407    /// This function runs the algorithm.
    411408    ///
    412409    /// \param scaling Enable or disable capacity scaling.
     
    423420
    424421    /// \name Query Functions
    425     /// The result of the algorithm can be obtained using these
    426     /// functions.
    427     /// \n run() must be called before using them.
     422    /// The results of the algorithm can be obtained using these
     423    /// functions.\n
     424    /// \ref lemon::CapacityScaling::run() "run()" must be called before
     425    /// using them.
    428426
    429427    /// @{
    430428
    431     /// \brief Returns a const reference to the edge map storing the
     429    /// \brief Return a const reference to the edge map storing the
    432430    /// found flow.
    433431    ///
    434     /// Returns a const reference to the edge map storing the found flow.
     432    /// Return a const reference to the edge map storing the found flow.
    435433    ///
    436434    /// \pre \ref run() must be called before using this function.
     
    439437    }
    440438
    441     /// \brief Returns a const reference to the node map storing the
     439    /// \brief Return a const reference to the node map storing the
    442440    /// found potentials (the dual solution).
    443441    ///
    444     /// Returns a const reference to the node map storing the found
     442    /// Return a const reference to the node map storing the found
    445443    /// potentials (the dual solution).
    446444    ///
     
    450448    }
    451449
    452     /// \brief Returns the flow on the given edge.
    453     ///
    454     /// Returns the flow on the given edge.
     450    /// \brief Return the flow on the given edge.
     451    ///
     452    /// Return the flow on the given edge.
    455453    ///
    456454    /// \pre \ref run() must be called before using this function.
     
    459457    }
    460458
    461     /// \brief Returns the potential of the given node.
    462     ///
    463     /// Returns the potential of the given node.
     459    /// \brief Return the potential of the given node.
     460    ///
     461    /// Return the potential of the given node.
    464462    ///
    465463    /// \pre \ref run() must be called before using this function.
     
    468466    }
    469467
    470     /// \brief Returns the total cost of the found flow.
    471     ///
    472     /// Returns the total cost of the found flow. The complexity of the
     468    /// \brief Return the total cost of the found flow.
     469    ///
     470    /// Return the total cost of the found flow. The complexity of the
    473471    /// function is \f$ O(e) \f$.
    474472    ///
     
    485483  private:
    486484
    487     /// Initializes the algorithm.
     485    /// Initialize the algorithm.
    488486    bool init(bool scaling) {
    489487      if (!_valid_supply) return false;
     
    536534    }
    537535
    538     /// Executes the capacity scaling algorithm.
     536    /// Execute the capacity scaling algorithm.
    539537    bool startWithScaling() {
    540538      // Processing capacity scaling phases
     
    568566          if (_excess[n] <= -_delta) _deficit_nodes.push_back(n);
    569567        }
    570         int next_node = 0;
     568        int next_node = 0, next_def_node = 0;
    571569
    572570        // Finding augmenting shortest paths
     
    575573          if (_delta > 1) {
    576574            bool delta_deficit = false;
    577             for (int i = 0; i < int(_deficit_nodes.size()); ++i) {
    578               if (_excess[_deficit_nodes[i]] <= -_delta) {
     575            for ( ; next_def_node < int(_deficit_nodes.size());
     576                    ++next_def_node ) {
     577              if (_excess[_deficit_nodes[next_def_node]] <= -_delta) {
    579578                delta_deficit = true;
    580579                break;
     
    642641    }
    643642
    644     /// Executes the successive shortest path algorithm.
     643    /// Execute the successive shortest path algorithm.
    645644    bool startWithoutScaling() {
    646645      // Finding excess nodes
Note: See TracChangeset for help on using the changeset viewer.