1.1 --- a/lemon/capacity_scaling.h Sun Oct 05 13:36:43 2008 +0000
1.2 +++ b/lemon/capacity_scaling.h Sun Oct 05 13:37:17 2008 +0000
1.3 @@ -52,7 +52,6 @@
1.4 /// - \c CostMap::Value must be signed type.
1.5 ///
1.6 /// \author Peter Kovacs
1.7 -
1.8 template < typename Graph,
1.9 typename LowerMap = typename Graph::template EdgeMap<int>,
1.10 typename CapacityMap = typename Graph::template EdgeMap<int>,
1.11 @@ -125,7 +124,7 @@
1.12 _pred(pred)
1.13 {}
1.14
1.15 - /// Runs the algorithm from the given source node.
1.16 + /// Run the algorithm from the given source node.
1.17 Node run(Node s, Capacity delta = 1) {
1.18 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
1.19 Heap heap(heap_cross_ref);
1.20 @@ -371,9 +370,9 @@
1.21 delete _dijkstra;
1.22 }
1.23
1.24 - /// \brief Sets the flow map.
1.25 + /// \brief Set the flow map.
1.26 ///
1.27 - /// Sets the flow map.
1.28 + /// Set the flow map.
1.29 ///
1.30 /// \return \c (*this)
1.31 CapacityScaling& flowMap(FlowMap &map) {
1.32 @@ -385,9 +384,9 @@
1.33 return *this;
1.34 }
1.35
1.36 - /// \brief Sets the potential map.
1.37 + /// \brief Set the potential map.
1.38 ///
1.39 - /// Sets the potential map.
1.40 + /// Set the potential map.
1.41 ///
1.42 /// \return \c (*this)
1.43 CapacityScaling& potentialMap(PotentialMap &map) {
1.44 @@ -400,14 +399,12 @@
1.45 }
1.46
1.47 /// \name Execution control
1.48 - /// The only way to execute the algorithm is to call the run()
1.49 - /// function.
1.50
1.51 /// @{
1.52
1.53 - /// \brief Runs the algorithm.
1.54 + /// \brief Run the algorithm.
1.55 ///
1.56 - /// Runs the algorithm.
1.57 + /// This function runs the algorithm.
1.58 ///
1.59 /// \param scaling Enable or disable capacity scaling.
1.60 /// If the maximum edge capacity and/or the amount of total supply
1.61 @@ -422,26 +419,27 @@
1.62 /// @}
1.63
1.64 /// \name Query Functions
1.65 - /// The result of the algorithm can be obtained using these
1.66 - /// functions.
1.67 - /// \n run() must be called before using them.
1.68 + /// The results of the algorithm can be obtained using these
1.69 + /// functions.\n
1.70 + /// \ref lemon::CapacityScaling::run() "run()" must be called before
1.71 + /// using them.
1.72
1.73 /// @{
1.74
1.75 - /// \brief Returns a const reference to the edge map storing the
1.76 + /// \brief Return a const reference to the edge map storing the
1.77 /// found flow.
1.78 ///
1.79 - /// Returns a const reference to the edge map storing the found flow.
1.80 + /// Return a const reference to the edge map storing the found flow.
1.81 ///
1.82 /// \pre \ref run() must be called before using this function.
1.83 const FlowMap& flowMap() const {
1.84 return *_flow;
1.85 }
1.86
1.87 - /// \brief Returns a const reference to the node map storing the
1.88 + /// \brief Return a const reference to the node map storing the
1.89 /// found potentials (the dual solution).
1.90 ///
1.91 - /// Returns a const reference to the node map storing the found
1.92 + /// Return a const reference to the node map storing the found
1.93 /// potentials (the dual solution).
1.94 ///
1.95 /// \pre \ref run() must be called before using this function.
1.96 @@ -449,27 +447,27 @@
1.97 return *_potential;
1.98 }
1.99
1.100 - /// \brief Returns the flow on the given edge.
1.101 + /// \brief Return the flow on the given edge.
1.102 ///
1.103 - /// Returns the flow on the given edge.
1.104 + /// Return the flow on the given edge.
1.105 ///
1.106 /// \pre \ref run() must be called before using this function.
1.107 Capacity flow(const Edge& edge) const {
1.108 return (*_flow)[edge];
1.109 }
1.110
1.111 - /// \brief Returns the potential of the given node.
1.112 + /// \brief Return the potential of the given node.
1.113 ///
1.114 - /// Returns the potential of the given node.
1.115 + /// Return the potential of the given node.
1.116 ///
1.117 /// \pre \ref run() must be called before using this function.
1.118 Cost potential(const Node& node) const {
1.119 return (*_potential)[node];
1.120 }
1.121
1.122 - /// \brief Returns the total cost of the found flow.
1.123 + /// \brief Return the total cost of the found flow.
1.124 ///
1.125 - /// Returns the total cost of the found flow. The complexity of the
1.126 + /// Return the total cost of the found flow. The complexity of the
1.127 /// function is \f$ O(e) \f$.
1.128 ///
1.129 /// \pre \ref run() must be called before using this function.
1.130 @@ -484,7 +482,7 @@
1.131
1.132 private:
1.133
1.134 - /// Initializes the algorithm.
1.135 + /// Initialize the algorithm.
1.136 bool init(bool scaling) {
1.137 if (!_valid_supply) return false;
1.138
1.139 @@ -535,7 +533,7 @@
1.140 return startWithoutScaling();
1.141 }
1.142
1.143 - /// Executes the capacity scaling algorithm.
1.144 + /// Execute the capacity scaling algorithm.
1.145 bool startWithScaling() {
1.146 // Processing capacity scaling phases
1.147 Node s, t;
1.148 @@ -567,15 +565,16 @@
1.149 if (_excess[n] >= _delta) _excess_nodes.push_back(n);
1.150 if (_excess[n] <= -_delta) _deficit_nodes.push_back(n);
1.151 }
1.152 - int next_node = 0;
1.153 + int next_node = 0, next_def_node = 0;
1.154
1.155 // Finding augmenting shortest paths
1.156 while (next_node < int(_excess_nodes.size())) {
1.157 // Checking deficit nodes
1.158 if (_delta > 1) {
1.159 bool delta_deficit = false;
1.160 - for (int i = 0; i < int(_deficit_nodes.size()); ++i) {
1.161 - if (_excess[_deficit_nodes[i]] <= -_delta) {
1.162 + for ( ; next_def_node < int(_deficit_nodes.size());
1.163 + ++next_def_node ) {
1.164 + if (_excess[_deficit_nodes[next_def_node]] <= -_delta) {
1.165 delta_deficit = true;
1.166 break;
1.167 }
1.168 @@ -641,7 +640,7 @@
1.169 return true;
1.170 }
1.171
1.172 - /// Executes the successive shortest path algorithm.
1.173 + /// Execute the successive shortest path algorithm.
1.174 bool startWithoutScaling() {
1.175 // Finding excess nodes
1.176 for (NodeIt n(_graph); n != INVALID; ++n)