diff -r e9c203fb003d -r 994c7df296c9 lemon/bfs.h
--- a/lemon/bfs.h	Fri Nov 13 12:33:33 2009 +0100
+++ b/lemon/bfs.h	Thu Dec 10 17:05:35 2009 +0100
@@ -2,7 +2,7 @@
  *
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
  *
@@ -49,11 +49,11 @@
     ///arcs of the shortest paths.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
-    ///Instantiates a PredMap.
+    ///Instantiates a \c PredMap.
 
-    ///This function instantiates a PredMap.
+    ///This function instantiates a \ref PredMap.
     ///\param g is the digraph, to which we would like to define the
-    ///PredMap.
+    ///\ref PredMap.
     static PredMap *createPredMap(const Digraph &g)
     {
       return new PredMap(g);
@@ -64,11 +64,11 @@
     ///The type of the map that indicates which nodes are processed.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
-    ///Instantiates a ProcessedMap.
+    ///Instantiates a \c ProcessedMap.
 
-    ///This function instantiates a ProcessedMap.
+    ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
-    ///we would like to define the ProcessedMap
+    ///we would like to define the \ref ProcessedMap
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const Digraph &g)
 #else
@@ -83,11 +83,11 @@
     ///The type of the map that indicates which nodes are reached.
     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
-    ///Instantiates a ReachedMap.
+    ///Instantiates a \c ReachedMap.
 
-    ///This function instantiates a ReachedMap.
+    ///This function instantiates a \ref ReachedMap.
     ///\param g is the digraph, to which
-    ///we would like to define the ReachedMap.
+    ///we would like to define the \ref ReachedMap.
     static ReachedMap *createReachedMap(const Digraph &g)
     {
       return new ReachedMap(g);
@@ -98,11 +98,11 @@
     ///The type of the map that stores the distances of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
-    ///Instantiates a DistMap.
+    ///Instantiates a \c DistMap.
 
-    ///This function instantiates a DistMap.
+    ///This function instantiates a \ref DistMap.
     ///\param g is the digraph, to which we would like to define the
-    ///DistMap.
+    ///\ref DistMap.
     static DistMap *createDistMap(const Digraph &g)
     {
       return new DistMap(g);
@@ -119,13 +119,7 @@
   ///used easier.
   ///
   ///\tparam GR The type of the digraph the algorithm runs on.
-  ///The default value is \ref ListDigraph. The value of GR is not used
-  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
-  ///\tparam TR Traits class to set various data types used by the algorithm.
-  ///The default traits class is
-  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
-  ///See \ref BfsDefaultTraits for the documentation of
-  ///a Bfs traits class.
+  ///The default type is \ref ListDigraph.
 #ifdef DOXYGEN
   template <typename GR,
             typename TR>
@@ -151,7 +145,7 @@
     ///The type of the paths.
     typedef PredMapPath<Digraph, PredMap> Path;
 
-    ///The traits class.
+    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     typedef TR Traits;
 
   private:
@@ -213,7 +207,7 @@
 
     typedef Bfs Create;
 
-    ///\name Named template parameters
+    ///\name Named Template Parameters
 
     ///@{
 
@@ -227,10 +221,11 @@
       }
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///PredMap type.
+    ///\c PredMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///PredMap type.
+    ///\c PredMap type.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
       typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
@@ -246,10 +241,11 @@
       }
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///DistMap type.
+    ///\c DistMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///DistMap type.
+    ///\c DistMap type.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
       typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
@@ -265,10 +261,11 @@
       }
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ReachedMap type.
+    ///\c ReachedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ReachedMap type.
+    ///\c ReachedMap type.
+    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     template <class T>
     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
       typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
@@ -284,10 +281,11 @@
       }
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type.
+    ///\c ProcessedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type.
+    ///\c ProcessedMap type.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
       typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
@@ -302,10 +300,10 @@
       }
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///If you don't set it explicitly, it will be automatically allocated.
     struct SetStandardProcessedMap :
       public Bfs< Digraph, SetStandardProcessedMapTraits > {
@@ -340,9 +338,10 @@
     ///Sets the map that stores the predecessor arcs.
 
     ///Sets the map that stores the predecessor arcs.
-    ///If you don't use this function before calling \ref run(),
-    ///it will allocate one. The destructor deallocates this
-    ///automatically allocated map, of course.
+    ///If you don't use this function before calling \ref run(Node) "run()"
+    ///or \ref init(), an instance will be allocated automatically.
+    ///The destructor deallocates this automatically allocated map,
+    ///of course.
     ///\return <tt> (*this) </tt>
     Bfs &predMap(PredMap &m)
     {
@@ -357,9 +356,10 @@
     ///Sets the map that indicates which nodes are reached.
 
     ///Sets the map that indicates which nodes are reached.
-    ///If you don't use this function before calling \ref run(),
-    ///it will allocate one. The destructor deallocates this
-    ///automatically allocated map, of course.
+    ///If you don't use this function before calling \ref run(Node) "run()"
+    ///or \ref init(), an instance will be allocated automatically.
+    ///The destructor deallocates this automatically allocated map,
+    ///of course.
     ///\return <tt> (*this) </tt>
     Bfs &reachedMap(ReachedMap &m)
     {
@@ -374,9 +374,10 @@
     ///Sets the map that indicates which nodes are processed.
 
     ///Sets the map that indicates which nodes are processed.
-    ///If you don't use this function before calling \ref run(),
-    ///it will allocate one. The destructor deallocates this
-    ///automatically allocated map, of course.
+    ///If you don't use this function before calling \ref run(Node) "run()"
+    ///or \ref init(), an instance will be allocated automatically.
+    ///The destructor deallocates this automatically allocated map,
+    ///of course.
     ///\return <tt> (*this) </tt>
     Bfs &processedMap(ProcessedMap &m)
     {
@@ -392,9 +393,10 @@
 
     ///Sets the map that stores the distances of the nodes calculated by
     ///the algorithm.
-    ///If you don't use this function before calling \ref run(),
-    ///it will allocate one. The destructor deallocates this
-    ///automatically allocated map, of course.
+    ///If you don't use this function before calling \ref run(Node) "run()"
+    ///or \ref init(), an instance will be allocated automatically.
+    ///The destructor deallocates this automatically allocated map,
+    ///of course.
     ///\return <tt> (*this) </tt>
     Bfs &distMap(DistMap &m)
     {
@@ -408,22 +410,19 @@
 
   public:
 
-    ///\name Execution control
-    ///The simplest way to execute the algorithm is to use
-    ///one of the member functions called \ref lemon::Bfs::run() "run()".
-    ///\n
-    ///If you need more control on the execution, first you must call
-    ///\ref lemon::Bfs::init() "init()", then you can add several source
-    ///nodes with \ref lemon::Bfs::addSource() "addSource()".
-    ///Finally \ref lemon::Bfs::start() "start()" will perform the
-    ///actual path computation.
+    ///\name Execution Control
+    ///The simplest way to execute the BFS algorithm is to use one of the
+    ///member functions called \ref run(Node) "run()".\n
+    ///If you need more control on the execution, first you have to call
+    ///\ref init(), then you can add several source nodes with
+    ///\ref addSource(). Finally the actual path computation can be
+    ///performed with one of the \ref start() functions.
 
     ///@{
 
+    ///\brief Initializes the internal data structures.
+    ///
     ///Initializes the internal data structures.
-
-    ///Initializes the internal data structures.
-    ///
     void init()
     {
       create_maps();
@@ -557,16 +556,16 @@
       return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
     }
 
-    ///\brief Returns \c false if there are nodes
-    ///to be processed.
-    ///
-    ///Returns \c false if there are nodes
-    ///to be processed in the queue.
+    ///Returns \c false if there are nodes to be processed.
+
+    ///Returns \c false if there are nodes to be processed
+    ///in the queue.
     bool emptyQueue() const { return _queue_tail==_queue_head; }
 
     ///Returns the number of the nodes to be processed.
 
-    ///Returns the number of the nodes to be processed in the queue.
+    ///Returns the number of the nodes to be processed
+    ///in the queue.
     int queueSize() const { return _queue_head-_queue_tail; }
 
     ///Executes the algorithm.
@@ -731,10 +730,10 @@
     ///@}
 
     ///\name Query Functions
-    ///The result of the %BFS algorithm can be obtained using these
+    ///The results of the BFS algorithm can be obtained using these
     ///functions.\n
-    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
-    ///"start()" must be called before using them.
+    ///Either \ref run(Node) "run()" or \ref start() should be called
+    ///before using them.
 
     ///@{
 
@@ -742,49 +741,49 @@
 
     ///Returns the shortest path to a node.
     ///
-    ///\warning \c t should be reachable from the root(s).
+    ///\warning \c t should be reached from the root(s).
     ///
-    ///\pre Either \ref run() or \ref start() must be called before
-    ///using this function.
+    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///must be called before using this function.
     Path path(Node t) const { return Path(*G, *_pred, t); }
 
     ///The distance of a node from the root(s).
 
     ///Returns the distance of a node from the root(s).
     ///
-    ///\warning If node \c v is not reachable from the root(s), then
+    ///\warning If node \c v is not reached from the root(s), then
     ///the return value of this function is undefined.
     ///
-    ///\pre Either \ref run() or \ref start() must be called before
-    ///using this function.
+    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///must be called before using this function.
     int dist(Node v) const { return (*_dist)[v]; }
 
     ///Returns the 'previous arc' of the shortest path tree for a node.
 
     ///This function returns the 'previous arc' of the shortest path
     ///tree for the node \c v, i.e. it returns the last arc of a
-    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
-    ///is not reachable from the root(s) or if \c v is a root.
+    ///shortest path from a root to \c v. It is \c INVALID if \c v
+    ///is not reached from the root(s) or if \c v is a root.
     ///
     ///The shortest path tree used here is equal to the shortest path
     ///tree used in \ref predNode().
     ///
-    ///\pre Either \ref run() or \ref start() must be called before
-    ///using this function.
+    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///must be called before using this function.
     Arc predArc(Node v) const { return (*_pred)[v];}
 
     ///Returns the 'previous node' of the shortest path tree for a node.
 
     ///This function returns the 'previous node' of the shortest path
     ///tree for the node \c v, i.e. it returns the last but one node
-    ///from a shortest path from the root(s) to \c v. It is \c INVALID
-    ///if \c v is not reachable from the root(s) or if \c v is a root.
+    ///from a shortest path from a root to \c v. It is \c INVALID
+    ///if \c v is not reached from the root(s) or if \c v is a root.
     ///
     ///The shortest path tree used here is equal to the shortest path
     ///tree used in \ref predArc().
     ///
-    ///\pre Either \ref run() or \ref start() must be called before
-    ///using this function.
+    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///must be called before using this function.
     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
                                   G->source((*_pred)[v]); }
 
@@ -794,7 +793,7 @@
     ///Returns a const reference to the node map that stores the distances
     ///of the nodes calculated by the algorithm.
     ///
-    ///\pre Either \ref run() or \ref init()
+    ///\pre Either \ref run(Node) "run()" or \ref init()
     ///must be called before using this function.
     const DistMap &distMap() const { return *_dist;}
 
@@ -804,14 +803,15 @@
     ///Returns a const reference to the node map that stores the predecessor
     ///arcs, which form the shortest path tree.
     ///
-    ///\pre Either \ref run() or \ref init()
+    ///\pre Either \ref run(Node) "run()" or \ref init()
     ///must be called before using this function.
     const PredMap &predMap() const { return *_pred;}
 
-    ///Checks if a node is reachable from the root(s).
+    ///Checks if a node is reached from the root(s).
 
-    ///Returns \c true if \c v is reachable from the root(s).
-    ///\pre Either \ref run() or \ref start()
+    ///Returns \c true if \c v is reached from the root(s).
+    ///
+    ///\pre Either \ref run(Node) "run()" or \ref init()
     ///must be called before using this function.
     bool reached(Node v) const { return (*_reached)[v]; }
 
@@ -957,8 +957,8 @@
 
   /// This auxiliary class is created to implement the
   /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
-  /// It does not have own \ref run() method, it uses the functions
-  /// and features of the plain \ref Bfs.
+  /// It does not have own \ref run(Node) "run()" method, it uses the
+  /// functions and features of the plain \ref Bfs.
   ///
   /// This class should only be used through the \ref bfs() function,
   /// which makes it easier to use the algorithm.
@@ -1178,7 +1178,7 @@
   ///  // Compute shortest path from s to t
   ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
   ///\endcode
-  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
+  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
   ///to the end of the parameter list.
   ///\sa BfsWizard
   ///\sa Bfs
@@ -1194,9 +1194,9 @@
   ///
   /// This class defines the interface of the BfsVisit events, and
   /// it could be the base of a real visitor class.
-  template <typename _Digraph>
+  template <typename GR>
   struct BfsVisitor {
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
     /// \brief Called for the source node(s) of the BFS.
@@ -1224,9 +1224,9 @@
     void examine(const Arc& arc) {}
   };
 #else
-  template <typename _Digraph>
+  template <typename GR>
   struct BfsVisitor {
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
     void start(const Node&) {}
@@ -1254,12 +1254,12 @@
   /// \brief Default traits class of BfsVisit class.
   ///
   /// Default traits class of BfsVisit class.
-  /// \tparam _Digraph The type of the digraph the algorithm runs on.
-  template<class _Digraph>
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  template<class GR>
   struct BfsVisitDefaultTraits {
 
     /// \brief The type of the digraph the algorithm runs on.
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
 
     /// \brief The type of the map that indicates which nodes are reached.
     ///
@@ -1280,12 +1280,12 @@
 
   /// \ingroup search
   ///
-  /// \brief %BFS algorithm class with visitor interface.
+  /// \brief BFS algorithm class with visitor interface.
   ///
-  /// This class provides an efficient implementation of the %BFS algorithm
+  /// This class provides an efficient implementation of the BFS algorithm
   /// with visitor interface.
   ///
-  /// The %BfsVisit class provides an alternative interface to the Bfs
+  /// The BfsVisit class provides an alternative interface to the Bfs
   /// class. It works with callback mechanism, the BfsVisit object calls
   /// the member functions of the \c Visitor class on every BFS event.
   ///
@@ -1294,37 +1294,37 @@
   /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
   /// instead.
   ///
-  /// \tparam _Digraph The type of the digraph the algorithm runs on.
-  /// The default value is
-  /// \ref ListDigraph. The value of _Digraph is not used directly by
-  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
-  /// \tparam _Visitor The Visitor type that is used by the algorithm.
-  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  /// The default type is \ref ListDigraph.
+  /// The value of GR is not used directly by \ref BfsVisit,
+  /// it is only passed to \ref BfsVisitDefaultTraits.
+  /// \tparam VS The Visitor type that is used by the algorithm.
+  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
   /// does not observe the BFS events. If you want to observe the BFS
   /// events, you should implement your own visitor class.
-  /// \tparam _Traits Traits class to set various data types used by the
+  /// \tparam TR Traits class to set various data types used by the
   /// algorithm. The default traits class is
-  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
+  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
   /// See \ref BfsVisitDefaultTraits for the documentation of
   /// a BFS visit traits class.
 #ifdef DOXYGEN
-  template <typename _Digraph, typename _Visitor, typename _Traits>
+  template <typename GR, typename VS, typename TR>
 #else
-  template <typename _Digraph = ListDigraph,
-            typename _Visitor = BfsVisitor<_Digraph>,
-            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
+  template <typename GR = ListDigraph,
+            typename VS = BfsVisitor<GR>,
+            typename TR = BfsVisitDefaultTraits<GR> >
 #endif
   class BfsVisit {
   public:
 
     ///The traits class.
-    typedef _Traits Traits;
+    typedef TR Traits;
 
     ///The type of the digraph the algorithm runs on.
     typedef typename Traits::Digraph Digraph;
 
     ///The visitor type used by the algorithm.
-    typedef _Visitor Visitor;
+    typedef VS Visitor;
 
     ///The type of the map that indicates which nodes are reached.
     typedef typename Traits::ReachedMap ReachedMap;
@@ -1364,7 +1364,7 @@
 
     typedef BfsVisit Create;
 
-    /// \name Named template parameters
+    /// \name Named Template Parameters
 
     ///@{
     template <class T>
@@ -1406,9 +1406,10 @@
     /// \brief Sets the map that indicates which nodes are reached.
     ///
     /// Sets the map that indicates which nodes are reached.
-    /// If you don't use this function before calling \ref run(),
-    /// it will allocate one. The destructor deallocates this
-    /// automatically allocated map, of course.
+    /// If you don't use this function before calling \ref run(Node) "run()"
+    /// or \ref init(), an instance will be allocated automatically.
+    /// The destructor deallocates this automatically allocated map,
+    /// of course.
     /// \return <tt> (*this) </tt>
     BfsVisit &reachedMap(ReachedMap &m) {
       if(local_reached) {
@@ -1421,16 +1422,13 @@
 
   public:
 
-    /// \name Execution control
-    /// The simplest way to execute the algorithm is to use
-    /// one of the member functions called \ref lemon::BfsVisit::run()
-    /// "run()".
-    /// \n
-    /// If you need more control on the execution, first you must call
-    /// \ref lemon::BfsVisit::init() "init()", then you can add several
-    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
-    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
-    /// actual path computation.
+    /// \name Execution Control
+    /// The simplest way to execute the BFS algorithm is to use one of the
+    /// member functions called \ref run(Node) "run()".\n
+    /// If you need more control on the execution, first you have to call
+    /// \ref init(), then you can add several source nodes with
+    /// \ref addSource(). Finally the actual path computation can be
+    /// performed with one of the \ref start() functions.
 
     /// @{
 
@@ -1730,19 +1728,20 @@
     ///@}
 
     /// \name Query Functions
-    /// The result of the %BFS algorithm can be obtained using these
+    /// The results of the BFS algorithm can be obtained using these
     /// functions.\n
-    /// Either \ref lemon::BfsVisit::run() "run()" or
-    /// \ref lemon::BfsVisit::start() "start()" must be called before
-    /// using them.
+    /// Either \ref run(Node) "run()" or \ref start() should be called
+    /// before using them.
+
     ///@{
 
-    /// \brief Checks if a node is reachable from the root(s).
+    /// \brief Checks if a node is reached from the root(s).
     ///
-    /// Returns \c true if \c v is reachable from the root(s).
-    /// \pre Either \ref run() or \ref start()
+    /// Returns \c true if \c v is reached from the root(s).
+    ///
+    /// \pre Either \ref run(Node) "run()" or \ref init()
     /// must be called before using this function.
-    bool reached(Node v) { return (*_reached)[v]; }
+    bool reached(Node v) const { return (*_reached)[v]; }
 
     ///@}