# HG changeset patch # User kpeter # Date 1223213837 0 # Node ID 8f41a31297460adf9d81416881ba719522f6115e # Parent 30fb4d68b0e8d4c6b552e91ee18b2160a77aabf3 Doc improvements diff -r 30fb4d68b0e8 -r 8f41a3129746 lemon/capacity_scaling.h --- a/lemon/capacity_scaling.h Sun Oct 05 13:36:43 2008 +0000 +++ b/lemon/capacity_scaling.h Sun Oct 05 13:37:17 2008 +0000 @@ -52,7 +52,6 @@ /// - \c CostMap::Value must be signed type. /// /// \author Peter Kovacs - template < typename Graph, typename LowerMap = typename Graph::template EdgeMap, typename CapacityMap = typename Graph::template EdgeMap, @@ -125,7 +124,7 @@ _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); @@ -371,9 +370,9 @@ 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) { @@ -385,9 +384,9 @@ 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) { @@ -400,14 +399,12 @@ } /// \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 @@ -422,26 +419,27 @@ /// @} /// \name Query Functions - /// The result of the algorithm can be obtained using these - /// functions. - /// \n run() must be called before using them. + /// The results of the algorithm can be obtained using these + /// functions.\n + /// \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. @@ -449,27 +447,27 @@ 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. @@ -484,7 +482,7 @@ private: - /// Initializes the algorithm. + /// Initialize the algorithm. bool init(bool scaling) { if (!_valid_supply) return false; @@ -535,7 +533,7 @@ return startWithoutScaling(); } - /// Executes the capacity scaling algorithm. + /// Execute the capacity scaling algorithm. bool startWithScaling() { // Processing capacity scaling phases Node s, t; @@ -567,15 +565,16 @@ 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) { - if (_excess[_deficit_nodes[i]] <= -_delta) { + for ( ; next_def_node < int(_deficit_nodes.size()); + ++next_def_node ) { + if (_excess[_deficit_nodes[next_def_node]] <= -_delta) { delta_deficit = true; break; } @@ -641,7 +640,7 @@ 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) diff -r 30fb4d68b0e8 -r 8f41a3129746 lemon/cost_scaling.h --- a/lemon/cost_scaling.h Sun Oct 05 13:36:43 2008 +0000 +++ b/lemon/cost_scaling.h Sun Oct 05 13:37:17 2008 +0000 @@ -64,7 +64,6 @@ /// long int in the inside computations. /// /// \author Peter Kovacs - template < typename Graph, typename LowerMap = typename Graph::template EdgeMap, typename CapacityMap = typename Graph::template EdgeMap, @@ -102,8 +101,7 @@ /// \brief Map adaptor class for handling residual edge costs. /// - /// \ref ResidualCostMap is a map adaptor class for handling - /// residual edge costs. + /// Map adaptor class for handling residual edge costs. template class ResidualCostMap : public MapBase { @@ -126,8 +124,7 @@ /// \brief Map adaptor class for handling reduced edge costs. /// - /// \ref ReducedCostMap is a map adaptor class for handling reduced - /// edge costs. + /// Map adaptor class for handling reduced edge costs. class ReducedCostMap : public MapBase { private: @@ -326,9 +323,9 @@ delete _red_cost; } - /// \brief Sets the flow map. + /// \brief Set the flow map. /// - /// Sets the flow map. + /// Set the flow map. /// /// \return \c (*this) CostScaling& flowMap(FlowMap &map) { @@ -340,9 +337,9 @@ return *this; } - /// \brief Sets the potential map. + /// \brief Set the potential map. /// - /// Sets the potential map. + /// Set the potential map. /// /// \return \c (*this) CostScaling& potentialMap(PotentialMap &map) { @@ -355,14 +352,12 @@ } /// \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. + /// Run the algorithm. /// /// \return \c true if a feasible flow can be found. bool run() { @@ -373,25 +368,26 @@ /// \name Query Functions /// The result of the algorithm can be obtained using these - /// functions. - /// \n run() must be called before using them. + /// functions.\n + /// \ref lemon::CostScaling::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. @@ -399,27 +395,27 @@ 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. @@ -434,7 +430,7 @@ private: - /// Initializes the algorithm. + /// Initialize the algorithm. bool init() { if (!_valid_supply) return false; @@ -469,7 +465,7 @@ } - /// Executes the algorithm. + /// Execute the algorithm. bool start() { std::deque active_nodes; typename Graph::template NodeMap hyper(_graph, false); diff -r 30fb4d68b0e8 -r 8f41a3129746 lemon/cycle_canceling.h --- a/lemon/cycle_canceling.h Sun Oct 05 13:36:43 2008 +0000 +++ b/lemon/cycle_canceling.h Sun Oct 05 13:37:17 2008 +0000 @@ -64,7 +64,6 @@ /// parameter. /// /// \author Peter Kovacs - template < typename Graph, typename LowerMap = typename Graph::template EdgeMap, typename CapacityMap = typename Graph::template EdgeMap, @@ -98,8 +97,7 @@ /// \brief Map adaptor class for handling residual edge costs. /// - /// \ref ResidualCostMap is a map adaptor class for handling - /// residual edge costs. + /// Map adaptor class for handling residual edge costs. class ResidualCostMap : public MapBase { private: @@ -278,9 +276,9 @@ delete _res_graph; } - /// \brief Sets the flow map. + /// \brief Set the flow map. /// - /// Sets the flow map. + /// Set the flow map. /// /// \return \c (*this) CycleCanceling& flowMap(FlowMap &map) { @@ -292,9 +290,9 @@ return *this; } - /// \brief Sets the potential map. + /// \brief Set the potential map. /// - /// Sets the potential map. + /// Set the potential map. /// /// \return \c (*this) CycleCanceling& potentialMap(PotentialMap &map) { @@ -307,14 +305,12 @@ } /// \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. + /// Run the algorithm. /// /// \param min_mean_cc Set this parameter to \c true to run the /// "Minimum Mean Cycle-Canceling" algorithm, which is strongly @@ -329,25 +325,26 @@ /// \name Query Functions /// The result of the algorithm can be obtained using these - /// functions. - /// \n run() must be called before using them. + /// functions.\n + /// \ref lemon::CycleCanceling::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. @@ -355,27 +352,27 @@ 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. @@ -390,7 +387,7 @@ private: - /// Initializes the algorithm. + /// Initialize the algorithm. bool init() { if (!_valid_supply) return false; @@ -428,9 +425,9 @@ return true; } - /// \brief Executes the algorithm using \ref BellmanFord. + /// \brief Execute the algorithm using \ref BellmanFord. /// - /// Executes the algorithm using the \ref BellmanFord + /// Execute the algorithm using the \ref BellmanFord /// "Bellman-Ford" algorithm for negative cycle detection with /// successively larger limit for the number of iterations. void start() { @@ -506,9 +503,9 @@ } } - /// \brief Executes the algorithm using \ref MinMeanCycle. + /// \brief Execute the algorithm using \ref MinMeanCycle. /// - /// Executes the algorithm using \ref MinMeanCycle for negative + /// Execute the algorithm using \ref MinMeanCycle for negative /// cycle detection. void startMinMean() { typedef Path ResPath; diff -r 30fb4d68b0e8 -r 8f41a3129746 lemon/min_cost_flow.h --- a/lemon/min_cost_flow.h Sun Oct 05 13:36:43 2008 +0000 +++ b/lemon/min_cost_flow.h Sun Oct 05 13:37:17 2008 +0000 @@ -62,7 +62,6 @@ /// - \c CostMap::Value must be signed type. /// /// \author Peter Kovacs - template < typename Graph, typename LowerMap = typename Graph::template EdgeMap, typename CapacityMap = typename Graph::template EdgeMap, diff -r 30fb4d68b0e8 -r 8f41a3129746 lemon/min_cost_max_flow.h --- a/lemon/min_cost_max_flow.h Sun Oct 05 13:36:43 2008 +0000 +++ b/lemon/min_cost_max_flow.h Sun Oct 05 13:37:17 2008 +0000 @@ -58,7 +58,6 @@ /// - \c CostMap::Value must be signed type. /// /// \author Peter Kovacs - template < typename Graph, typename CapacityMap = typename Graph::template EdgeMap, typename CostMap = typename Graph::template EdgeMap > @@ -127,9 +126,9 @@ if (_local_potential) delete _potential; } - /// \brief Sets the flow map. + /// \brief Set the flow map. /// - /// Sets the flow map. + /// Set the flow map. /// /// \return \c (*this) MinCostMaxFlow& flowMap(FlowMap &map) { @@ -141,9 +140,9 @@ return *this; } - /// \brief Sets the potential map. + /// \brief Set the potential map. /// - /// Sets the potential map. + /// Set the potential map. /// /// \return \c (*this) MinCostMaxFlow& potentialMap(PotentialMap &map) { @@ -156,14 +155,12 @@ } /// \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. + /// Run the algorithm. void run() { // Initializing maps if (!_flow) { @@ -186,26 +183,27 @@ /// @} /// \name Query Functions - /// The result of the algorithm can be obtained using these - /// functions. - /// \n run() must be called before using them. + /// The results of the algorithm can be obtained using these + /// functions.\n + /// \ref lemon::MinCostMaxFlow::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. @@ -213,27 +211,27 @@ 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. diff -r 30fb4d68b0e8 -r 8f41a3129746 lemon/min_mean_cycle.h --- a/lemon/min_mean_cycle.h Sun Oct 05 13:36:43 2008 +0000 +++ b/lemon/min_mean_cycle.h Sun Oct 05 13:37:17 2008 +0000 @@ -232,7 +232,7 @@ } return true; } - + /// @} /// \name Query Functions @@ -241,7 +241,7 @@ /// \n The algorithm should be executed before using them. /// @{ - + /// \brief Returns the total length of the found cycle. /// /// Returns the total length of the found cycle. @@ -291,9 +291,9 @@ const Path& cycle() const { return *_cycle_path; } - + ///@} - + private: // Initializes the internal data structures for the current strongly