lemon-main: comparison lemon/suurballe.h

equal deleted inserted replaced

-:e8c3a05d4fac
+:5afe6771ab07
 namespace lemon {
 /// \addtogroup shortest_path
 /// @{
-/// \brief Implementation of an algorithm for finding arc-disjoint
+/// \brief Algorithm for finding arc-disjoint paths between two nodes
-/// paths between two nodes having minimum total length.
+/// having minimum total length.
 ///
 /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
 /// finding arc-disjoint paths having minimum total length (cost)
-/// from a given source node to a given target node in a directed
+/// from a given source node to a given target node in a digraph.
-/// digraph.
 ///
 /// In fact, this implementation is the specialization of the
 /// \ref CapacityScaling "successive shortest path" algorithm.
 ///
-/// \tparam Digraph The directed digraph type the algorithm runs on.
+/// \tparam Digraph The digraph type the algorithm runs on.
+/// The default value is \c ListDigraph.
 /// \tparam LengthMap The type of the length (cost) map.
+/// The default value is <tt>Digraph::ArcMap<int></tt>.
 ///
 /// \warning Length values should be \e non-negative \e integers.
 ///
 /// \note For finding node-disjoint paths this algorithm can be used
 /// with \ref SplitDigraphAdaptor.
-///
+#ifdef DOXYGEN
-/// \author Attila Bernath and Peter Kovacs
+template <typename Digraph, typename LengthMap>
+#else
-template < typename Digraph,
+template < typename Digraph = ListDigraph,
 typename LengthMap = typename Digraph::template ArcMap<int> >
+#endif
 class Suurballe
 {
 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 typedef typename LengthMap::Value Length;
 /// The type of the path structures.
 typedef SimplePath<Digraph> Path;
 private:
-/// \brief Special implementation of the \ref Dijkstra algorithm
+/// \brief Special implementation of the Dijkstra algorithm
 /// for finding shortest paths in the residual network.
 ///
 /// \ref ResidualDijkstra is a special implementation of the
 /// \ref Dijkstra algorithm for finding shortest paths in the
 /// residual network of the digraph with respect to the reduced arc
 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 typedef BinHeap<Length, HeapCrossRef> Heap;
 private:
-// The directed digraph the algorithm runs on
+// The digraph the algorithm runs on
 const Digraph &_graph;
 // The main maps
 const FlowMap &_flow;
 const LengthMap &_length;
 PredMap &pred,
 Node s, Node t ) :
 _graph(digraph), _flow(flow), _length(length), _potential(potential),
 _dist(digraph), _pred(pred), _s(s), _t(t) {}
-/// \brief Runs the algorithm. Returns \c true if a path is found
+/// \brief Run the algorithm. It returns \c true if a path is found
 /// from the source node to the target node.
 bool run() {
 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
 Heap heap(heap_cross_ref);
 heap.push(_s, 0);
 _pred[_s] = INVALID;
 _proc_nodes.clear();
-// Processing nodes
+// Process nodes
 while (!heap.empty() && heap.top() != _t) {
 Node u = heap.top(), v;
 Length d = heap.prio() + _potential[u], nd;
 _dist[u] = heap.prio();
 heap.pop();
 _proc_nodes.push_back(u);
-// Traversing outgoing arcs
+// Traverse outgoing arcs
 for (OutArcIt e(_graph, u); e != INVALID; ++e) {
 if (_flow[e] == 0) {
 v = _graph.target(e);
 switch(heap.state(v)) {
 case Heap::PRE_HEAP:
 break;
 }
 }
 }
-// Traversing incoming arcs
+// Traverse incoming arcs
 for (InArcIt e(_graph, u); e != INVALID; ++e) {
 if (_flow[e] == 1) {
 v = _graph.source(e);
 switch(heap.state(v)) {
 case Heap::PRE_HEAP:
 }
 }
 }
 if (heap.empty()) return false;
-// Updating potentials of processed nodes
+// Update potentials of processed nodes
 Length t_dist = heap.prio();
 for (int i = 0; i < int(_proc_nodes.size()); ++i)
 _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
 return true;
 }
 }; //class ResidualDijkstra
 private:
-// The directed digraph the algorithm runs on
+// The digraph the algorithm runs on
 const Digraph &_graph;
 // The length map
 const LengthMap &_length;
 // Arc map of the current flow
 /// \brief Constructor.
 ///
 /// Constructor.
 ///
-/// \param digraph The directed digraph the algorithm runs on.
+/// \param digraph The digraph the algorithm runs on.
 /// \param length The length (cost) values of the arcs.
 /// \param s The source node.
 /// \param t The target node.
 Suurballe( const Digraph &digraph,
 const LengthMap &length,
 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.
+/// This function sets the flow map.
 ///
 /// The found flow contains only 0 and 1 values. It is the union of
 /// the found arc-disjoint paths.
 ///
 /// \return \c (*this)
 }
 _flow = &map;
 return *this;
 }
-/// \brief Sets the potential map.
+/// \brief Set the potential map.
 ///
-/// Sets the potential map.
+/// This function sets the potential map.
 ///
 /// The potentials provide the dual solution of the underlying
 /// minimum cost flow problem.
 ///
 /// \return \c (*this)
 /// If you only need the flow that is the union of the found
 /// arc-disjoint paths, you may call init() and findFlow().
 /// @{
-/// \brief Runs the algorithm.
+/// \brief Run the algorithm.
 ///
-/// Runs the algorithm.
+/// This function runs the algorithm.
 ///
 /// \param k The number of paths to be found.
 ///
-/// \return \c k if there are at least \c k arc-disjoint paths
+/// \return \c k if there are at least \c k arc-disjoint paths from
-/// from \c s to \c t. Otherwise it returns the number of
+/// \c s to \c t in the digraph. Otherwise it returns the number of
 /// arc-disjoint paths found.
 ///
 /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
 /// shortcut of the following code.
 /// \code
 findFlow(k);
 findPaths();
 return _path_num;
 }
-/// \brief Initializes the algorithm.
+/// \brief Initialize the algorithm.
 ///
-/// Initializes the algorithm.
+/// This function initializes the algorithm.
 void init() {
-// Initializing maps
+// Initialize maps
 if (!_flow) {
 _flow = new FlowMap(_graph);
 _local_flow = true;
 }
 if (!_potential) {
 _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
 *_potential, _pred,
 _source, _target );
 }
-/// \brief Executes the successive shortest path algorithm to find
+/// \brief Execute the successive shortest path algorithm to find
 /// an optimal flow.
 ///
-/// Executes the successive shortest path algorithm to find a
+/// This function executes the successive shortest path algorithm to
-/// minimum cost flow, which is the union of \c k or less
+/// find a minimum cost flow, which is the union of \c k or less
 /// arc-disjoint paths.
 ///
-/// \return \c k if there are at least \c k arc-disjoint paths
+/// \return \c k if there are at least \c k arc-disjoint paths from
-/// from \c s to \c t. Otherwise it returns the number of
+/// \c s to \c t in the digraph. Otherwise it returns the number of
 /// arc-disjoint paths found.
 ///
 /// \pre \ref init() must be called before using this function.
 int findFlow(int k = 2) {
-// Finding shortest paths
+// Find shortest paths
 _path_num = 0;
 while (_path_num < k) {
-// Running Dijkstra
+// Run Dijkstra
 if (!_dijkstra->run()) break;
 ++_path_num;
-// Setting the flow along the found shortest path
+// Set the flow along the found shortest path
 Node u = _target;
 Arc e;
 while ((e = _pred[u]) != INVALID) {
 if (u == _graph.target(e)) {
 (*_flow)[e] = 1;
 }
 }
 return _path_num;
 }
-/// \brief Computes the paths from the flow.
+/// \brief Compute the paths from the flow.
 ///
-/// Computes the paths from the flow.
+/// This function computes the paths from the flow.
 ///
 /// \pre \ref init() and \ref findFlow() must be called before using
 /// this function.
 void findPaths() {
-// Creating the residual flow map (the union of the paths not
+// Create the residual flow map (the union of the paths not found
-// found so far)
+// so far)
 FlowMap res_flow(_graph);
-for(ArcIt a(_graph);a!=INVALID;++a) res_flow[a]=(*_flow)[a];
+for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
 paths.clear();
 paths.resize(_path_num);
 for (int i = 0; i < _path_num; ++i) {
 Node n = _source;
 }
 /// @}
 /// \name Query Functions
-/// The result of the algorithm can be obtained using these
+/// The results of the algorithm can be obtained using these
 /// functions.
 /// \n The algorithm should be executed before using them.
 /// @{
-/// \brief Returns a const reference to the arc map storing the
+/// \brief Return a const reference to the arc map storing the
 /// found flow.
 ///
-/// Returns a const reference to the arc map storing the flow that
+/// This function returns a const reference to the arc map storing
-/// is the union of the found arc-disjoint paths.
+/// the flow that is the union of the found arc-disjoint paths.
 ///
-/// \pre \ref run() or findFlow() must be called before using this
+/// \pre \ref run() or \ref findFlow() must be called before using
-/// function.
+/// 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
+/// This function returns a const reference to the node map storing
-/// potentials that provide the dual solution of the underlying
+/// the found potentials that provide the dual solution of the
-/// minimum cost flow problem.
+/// underlying minimum cost flow problem.
 ///
-/// \pre \ref run() or findFlow() must be called before using this
+/// \pre \ref run() or \ref findFlow() must be called before using
-/// function.
+/// this function.
 const PotentialMap& potentialMap() const {
 return *_potential;
 }
-/// \brief Returns the flow on the given arc.
+/// \brief Return the flow on the given arc.
 ///
-/// Returns the flow on the given arc.
+/// This function returns the flow on the given arc.
 /// It is \c 1 if the arc is involved in one of the found paths,
 /// otherwise it is \c 0.
 ///
-/// \pre \ref run() or findFlow() must be called before using this
+/// \pre \ref run() or \ref findFlow() must be called before using
-/// function.
+/// this function.
 int flow(const Arc& arc) const {
 return (*_flow)[arc];
 }
-/// \brief Returns the potential of the given node.
+/// \brief Return the potential of the given node.
 ///
-/// Returns the potential of the given node.
+/// This function returns the potential of the given node.
 ///
-/// \pre \ref run() or findFlow() must be called before using this
+/// \pre \ref run() or \ref findFlow() must be called before using
-/// function.
+/// this function.
 Length potential(const Node& node) const {
 return (*_potential)[node];
 }
-/// \brief Returns the total length (cost) of the found paths (flow).
+/// \brief Return the total length (cost) of the found paths (flow).
 ///
-/// Returns the total length (cost) of the found paths (flow).
+/// This function returns the total length (cost) of the found paths
-/// The complexity of the function is \f$ O(e) \f$.
+/// (flow). The complexity of the function is \f$ O(e) \f$.
 ///
-/// \pre \ref run() or findFlow() must be called before using this
+/// \pre \ref run() or \ref findFlow() must be called before using
-/// function.
+/// this function.
 Length totalLength() const {
 Length c = 0;
 for (ArcIt e(_graph); e != INVALID; ++e)
 c += (*_flow)[e] * _length[e];
 return c;
 }
-/// \brief Returns the number of the found paths.
+/// \brief Return the number of the found paths.
 ///
-/// Returns the number of the found paths.
+/// This function returns the number of the found paths.
 ///
-/// \pre \ref run() or findFlow() must be called before using this
+/// \pre \ref run() or \ref findFlow() must be called before using
-/// function.
+/// this function.
 int pathNum() const {
 return _path_num;
 }
-/// \brief Returns a const reference to the specified path.
+/// \brief Return a const reference to the specified path.
 ///
-/// Returns a const reference to the specified path.
+/// This function returns a const reference to the specified path.
 ///
 /// \param i The function returns the \c i-th path.
 /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
 ///
-/// \pre \ref run() or findPaths() must be called before using this
+/// \pre \ref run() or \ref findPaths() must be called before using
-/// function.
+/// this function.
 Path path(int i) const {
 return paths[i];
 }
 /// @}

changeset 402	235be9d4b6ab
parent 345	2f64c4a692a8
child 425	cace3206223b