lemon-0.x: comparison lemon/capacity

equal deleted inserted replaced

-:2e49ed97fe6a
+:e1233955ff09
 /// - Supply values should be \e signed \e integers.
 /// - The value types of the maps should be convertible to each other.
 /// - \c CostMap::Value must be signed type.
 ///
 /// \author Peter Kovacs
 template < typename Graph,
 typename LowerMap = typename Graph::template EdgeMap<int>,
 typename CapacityMap = typename Graph::template EdgeMap<int>,
 typename CostMap = typename Graph::template EdgeMap<int>,
 typename SupplyMap = typename Graph::template NodeMap<int> >
 _graph(graph), _flow(flow), _res_cap(res_cap), _cost(cost),
 _excess(excess), _potential(potential), _dist(graph),
 _pred(pred)
 {}
-/// Runs the algorithm from the given source node.
+/// Run the algorithm from the given source node.
 Node run(Node s, Capacity delta = 1) {
 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
 Heap heap(heap_cross_ref);
 heap.push(s, 0);
 _pred[s] = INVALID;
 if (_local_flow) delete _flow;
 if (_local_potential) delete _potential;
 delete _dijkstra;
 }
-/// \brief Sets the flow map.
+/// \brief Set the flow map.
 ///
-/// Sets the flow map.
+/// Set the flow map.
 ///
 /// \return \c (*this)
 CapacityScaling& flowMap(FlowMap &map) {
 if (_local_flow) {
 delete _flow;
 }
 _flow = &map;
 return *this;
 }
-/// \brief Sets the potential map.
+/// \brief Set the potential map.
 ///
-/// Sets the potential map.
+/// Set the potential map.
 ///
 /// \return \c (*this)
 CapacityScaling& potentialMap(PotentialMap &map) {
 if (_local_potential) {
 delete _potential;
 _potential = &map;
 return *this;
 }
 /// \name Execution control
-/// The only way to execute the algorithm is to call the run()
-/// function.
 /// @{
-/// \brief Runs the algorithm.
+/// \brief Run the algorithm.
 ///
-/// Runs the algorithm.
+/// This function runs the algorithm.
 ///
 /// \param scaling Enable or disable capacity scaling.
 /// If the maximum edge capacity and/or the amount of total supply
 /// is rather small, the algorithm could be slightly faster without
 /// scaling.
 }
 /// @}
 /// \name Query Functions
-/// The result of the algorithm can be obtained using these
+/// The results of the algorithm can be obtained using these
-/// functions.
+/// functions.\n
-/// \n run() must be called before using them.
+/// \ref lemon::CapacityScaling::run() "run()" must be called before
+/// using them.
 /// @{
-/// \brief Returns a const reference to the edge map storing the
+/// \brief Return a const reference to the edge map storing the
 /// found flow.
 ///
-/// Returns a const reference to the edge map storing the found flow.
+/// Return a const reference to the edge map storing the found flow.
 ///
 /// \pre \ref run() must be called before using this function.
 const FlowMap& flowMap() const {
 return *_flow;
 }
-/// \brief Returns a const reference to the node map storing the
+/// \brief Return a const reference to the node map storing the
 /// found potentials (the dual solution).
 ///
-/// Returns a const reference to the node map storing the found
+/// Return a const reference to the node map storing the found
 /// potentials (the dual solution).
 ///
 /// \pre \ref run() must be called before using this function.
 const PotentialMap& potentialMap() const {
 return *_potential;
 }
-/// \brief Returns the flow on the given edge.
+/// \brief Return the flow on the given edge.
 ///
-/// Returns the flow on the given edge.
+/// Return the flow on the given edge.
 ///
 /// \pre \ref run() must be called before using this function.
 Capacity flow(const Edge& edge) const {
 return (*_flow)[edge];
 }
-/// \brief Returns the potential of the given node.
+/// \brief Return the potential of the given node.
 ///
-/// Returns the potential of the given node.
+/// Return the potential of the given node.
 ///
 /// \pre \ref run() must be called before using this function.
 Cost potential(const Node& node) const {
 return (*_potential)[node];
 }
-/// \brief Returns the total cost of the found flow.
+/// \brief Return the total cost of the found flow.
 ///
-/// Returns the total cost of the found flow. The complexity of the
+/// Return the total cost of the found flow. The complexity of the
 /// function is \f$ O(e) \f$.
 ///
 /// \pre \ref run() must be called before using this function.
 Cost totalCost() const {
 Cost c = 0;
 /// @}
 private:
-/// Initializes the algorithm.
+/// Initialize the algorithm.
 bool init(bool scaling) {
 if (!_valid_supply) return false;
 // Initializing maps
 if (!_flow) {
 return startWithScaling();
 else
 return startWithoutScaling();
 }
-/// Executes the capacity scaling algorithm.
+/// Execute the capacity scaling algorithm.
 bool startWithScaling() {
 // Processing capacity scaling phases
 Node s, t;
 int phase_cnt = 0;
 int factor = 4;
 _deficit_nodes.clear();
 for (NodeIt n(_graph); n != INVALID; ++n) {
 if (_excess[n] >=  _delta) _excess_nodes.push_back(n);
 if (_excess[n] <= -_delta) _deficit_nodes.push_back(n);
 }
-int next_node = 0;
+int next_node = 0, next_def_node = 0;
 // Finding augmenting shortest paths
 while (next_node < int(_excess_nodes.size())) {
 // Checking deficit nodes
 if (_delta > 1) {
 bool delta_deficit = false;
-for (int i = 0; i < int(_deficit_nodes.size()); ++i) {
+for ( ; next_def_node < int(_deficit_nodes.size());
-if (_excess[_deficit_nodes[i]] <= -_delta) {
+++next_def_node ) {
+if (_excess[_deficit_nodes[next_def_node]] <= -_delta) {
 delta_deficit = true;
 break;
 }
 }
 if (!delta_deficit) break;
 (*_flow)[e] += (*_lower)[e];
 }
 return true;
 }
-/// Executes the successive shortest path algorithm.
+/// Execute the successive shortest path algorithm.
 bool startWithoutScaling() {
 // Finding excess nodes
 for (NodeIt n(_graph); n != INVALID; ++n)
 if (_excess[n] > 0) _excess_nodes.push_back(n);
 if (_excess_nodes.size() == 0) return true;

changeset 2622	fa2877651022
parent 2589	1bbb28acb8c9
child 2623	90defb96ee61