LEMON/LEMON-official Changeset - r260:c691064dfd4f

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r260:c691064dfd4f

« 258:0310c8
« 259:362415

278:931190 »
272:e63a95 »
263:be8a86 »
262:0181b7 »
261:1c2ac7 »

r260:c691064dfd4f

Thu, 11 Sep 2008 12:10:44

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 5 0

merge default

0 files changed with 132 insertions and 133 deletions:

lemon/bfs.h

lemon/bits/base_extender.h

lemon/dfs.h

lemon/dijkstra.h

test/heap_test.cc

↑ Collapse diff ↑

lemon/bfs.h

Show inline comments

@@ -41,472 +41,471 @@
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///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 \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///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 \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///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 \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref DistMap.
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%BFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %BFS algorithm.
 		  ///
 		  ///There is also a \ref bfs() "function type interface" for the BFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///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.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=BfsDefaultTraits<GR> >
 		#endif
 		  class Bfs {
 		  public:
 		    ///\ref Exception for uninitialized parameters.
 		    ///This error represents problems in the initialization of the
 		    ///parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 		        return "lemon::Bfs::UninitializedParameter";
+		      }
 		    };
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The traits class.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::Node> _queue;
 		    int _queue_head,_queue_tail,_queue_next_dist;
 		    int _curr_dist;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Bfs() {}
 		  public:
 		    typedef Bfs Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
-		    struct DefPredMapTraits : public Traits {
+		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    template <class T>
 		    struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
 		      typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
 		    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 		      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
-		    struct DefDistMapTraits : public Traits {
+		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    template <class T>
 		    struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
 		      typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
 		    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
-		    struct DefReachedMapTraits : public Traits {
+		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    template <class T>
 		    struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
 		    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
-		    struct DefProcessedMapTraits : public Traits {
+		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    template <class T>
 		    struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
 		    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
-		    struct DefDigraphProcessedMapTraits : public Traits {
+		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    template <class T>
 		    struct DefProcessedMapToBeDefaultMap :
 		      public Bfs< Digraph, DefDigraphProcessedMapTraits> {
 		      typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
 		    struct SetStandardProcessedMap :
 		      public Bfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param g The digraph the algorithm runs on.
 		    Bfs(const Digraph &g) :
 		      G(&g),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _reached(NULL), local_reached(false),
 		      _processed(NULL), local_processed(false)
 		    { }
 		    ///Destructor.
 		    ~Bfs()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_reached) delete _reached;
 		      if(local_processed) delete _processed;
+		    }
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &reachedMap(ReachedMap &m)
+		    {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &processedMap(ProcessedMap &m)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
+		      }
 		      _processed = &m;
 		      return *this;
+		    }
 		    ///Sets the map that stores the distances of the nodes.
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &distMap(DistMap &m)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;
+		    }
 		  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.
 		    ///@{
 		    ///Initializes the internal data structures.
 		    ///Initializes the internal data structures.
 		    ///
 		    void init()
+		    {
 		      create_maps();
 		      _queue.resize(countNodes(*G));
 		      _queue_head=_queue_tail=0;
 		      _curr_dist=1;
 		      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 		        _pred->set(u,INVALID);
 		        _reached->set(u,false);
 		        _processed->set(u,false);
+		      }
+		    }
 		    ///Adds a new source node.
 		    ///Adds a new source node to the set of nodes to be processed.
 		    ///
 		    void addSource(Node s)
+		    {
 		      if(!(*_reached)[s])
+		        {
 		          _reached->set(s,true);
 		          _pred->set(s,INVALID);
 		          _dist->set(s,0);
 		          _queue[_queue_head++]=s;
 		          _queue_next_dist=_queue_head;
+		        }
+		    }
 		    ///Processes the next node.
 		    ///Processes the next node.
 		    ///
 		    ///\return The processed node.
 		    ///
 		    ///\pre The queue must not be empty.
 		    Node processNextNode()
+		    {
 		      if(_queue_tail==_queue_next_dist) {
 		        _curr_dist++;
 		        _queue_next_dist=_queue_head;
+		      }
 		      Node n=_queue[_queue_tail++];
 		      _processed->set(n,true);
 		      Node m;
 		      for(OutArcIt e(*G,n);e!=INVALID;++e)
 		        if(!(*_reached)[m=G->target(e)]) {
 		          _queue[_queue_head++]=m;
 		          _reached->set(m,true);
 		          _pred->set(m,e);
 		          _dist->set(m,_curr_dist);
+		        }
 		      return n;
+		    }
 		    ///Processes the next node.
 		    ///Processes the next node and checks if the given target node
 		    ///is reached. If the target node is reachable from the processed
 		    ///node, then the \c reach parameter will be set to \c true.
 		    ///
 		    ///\param target The target node.
 		    ///\retval reach Indicates if the target node is reached.
 		    ///It should be initially \c false.
 		    ///
 		    ///\return The processed node.
 		    ///
 		    ///\pre The queue must not be empty.
 		    Node processNextNode(Node target, bool& reach)
+		    {
 		      if(_queue_tail==_queue_next_dist) {
 		        _curr_dist++;
 		        _queue_next_dist=_queue_head;
+		      }
 		      Node n=_queue[_queue_tail++];
 		      _processed->set(n,true);
 		      Node m;
 		      for(OutArcIt e(*G,n);e!=INVALID;++e)
@@ -876,687 +875,687 @@
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///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 \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap<typename Digraph::Node,int> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const Digraph &g)
 		#else
 		    static DistMap *createDistMap(const Digraph &)
 		#endif
+		    {
 		      return new DistMap();
+		    }
 		  };
 		  /// Default traits class used by \ref BfsWizard
 		  /// To make it easier to use Bfs algorithm
 		  /// we have created a wizard class.
 		  /// This \ref BfsWizard class needs default traits,
 		  /// as well as the \ref Bfs class.
 		  /// The \ref BfsWizardBase is a class to be the default traits of the
 		  /// \ref BfsWizard class.
 		  template<class GR>
 		  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
+		  {
 		    typedef BfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the source node.
 		    Node _source;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to default values (0, INVALID).
 		    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _source(INVALID) {}
 		    /// Constructor.
 		    /// This constructor requires some parameters,
 		    /// listed in the parameters list.
 		    /// Others are initiated to 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param s The source node.
 		    BfsWizardBase(const GR &g, Node s=INVALID) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
 		  };
 		  /// Auxiliary class for the function type interface of BFS algorithm.
 		  /// This auxiliary class is created to implement the function type
 		  /// interface of \ref Bfs algorithm. It uses the functions and features
 		  /// of the plain \ref Bfs, but it is much simpler to use it.
 		  /// It should only be used through the \ref bfs() function, which makes
 		  /// it easier to use the algorithm.
 		  ///
 		  /// Simplicity means that the way to change the types defined
 		  /// in the traits class is based on functions that returns the new class
 		  /// and not on templatable built-in classes.
 		  /// When using the plain \ref Bfs
 		  /// the new class with the modified type comes from
 		  /// the original class by using the ::
 		  /// operator. In the case of \ref BfsWizard only
 		  /// a function have to be called, and it will
 		  /// return the needed class.
 		  ///
 		  /// It does not have own \ref run() method. When its \ref run() method
 		  /// is called, it initiates a plain \ref Bfs object, and calls the
 		  /// \ref Bfs::run() method of it.
 		  template<class TR>
 		  class BfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///\brief The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///\brief The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///\brief The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		  public:
 		    /// Constructor.
 		    BfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    BfsWizard(const Digraph &g, Node s=INVALID) :
 		      TR(g,s) {}
 		    ///Copy constructor
 		    BfsWizard(const TR &b) : TR(b) {}
 		    ~BfsWizard() {}
 		    ///Runs BFS algorithm from a source node.
 		    ///Runs BFS algorithm from a source node.
 		    ///The node can be given with the \ref source() function.
 		    void run()
+		    {
 		      if(Base::_source==INVALID) throw UninitializedParameter();
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if(Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if(Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if(Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if(Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      alg.run(Base::_source);
+		    }
 		    ///Runs BFS algorithm from the given node.
 		    ///Runs BFS algorithm from the given node.
 		    ///\param s is the given source.
 		    void run(Node s)
+		    {
 		      Base::_source=s;
 		      run();
+		    }
 		    /// Sets the source node, from which the Bfs algorithm runs.
 		    /// Sets the source node, from which the Bfs algorithm runs.
 		    /// \param s is the source node.
 		    BfsWizard<TR> &source(Node s)
+		    {
 		      Base::_source=s;
 		      return *this;
+		    }
 		    template<class T>
-		    struct DefPredMapBase : public Base {
+		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
-		      DefPredMapBase(const TR &b) : TR(b) {}
+		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    template<class T>
-		    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
+		    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return BfsWizard<DefPredMapBase<T> >(*this);
+		      return BfsWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
-		    struct DefReachedMapBase : public Base {
+		    struct SetReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
-		      DefReachedMapBase(const TR &b) : TR(b) {}
+		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    template<class T>
-		    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
+		    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return BfsWizard<DefReachedMapBase<T> >(*this);
+		      return BfsWizard<SetReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
-		    struct DefProcessedMapBase : public Base {
+		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
-		      DefProcessedMapBase(const TR &b) : TR(b) {}
+		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    template<class T>
-		    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
+		    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return BfsWizard<DefProcessedMapBase<T> >(*this);
+		      return BfsWizard<SetProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
-		    struct DefDistMapBase : public Base {
+		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
-		      DefDistMapBase(const TR &b) : TR(b) {}
+		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    template<class T>
-		    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
+		    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return BfsWizard<DefDistMapBase<T> >(*this);
+		      return BfsWizard<SetDistMapBase<T> >(*this);
+		    }
 		  };
 		  ///Function type interface for Bfs algorithm.
 		  /// \ingroup search
 		  ///Function type interface for Bfs algorithm.
 		  ///
 		  ///This function also has several
 		  ///\ref named-templ-func-param "named parameters",
 		  ///they are declared as the members of class \ref BfsWizard.
 		  ///The following
 		  ///example shows how to use these parameters.
 		  ///\code
 		  ///  bfs(g,source).predMap(preds).run();
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
 		  ///to the end of the parameter list.
 		  ///\sa BfsWizard
 		  ///\sa Bfs
 		  template<class GR>
 		  BfsWizard<BfsWizardBase<GR> >
 		  bfs(const GR &g,typename GR::Node s=INVALID)
+		  {
 		    return BfsWizard<BfsWizardBase<GR> >(g,s);
+		  }
 		#ifdef DOXYGEN
 		  /// \brief Visitor class for BFS.
 		  ///
 		  /// This class defines the interface of the BfsVisit events, and
 		  /// it could be the base of a real visitor class.
 		  template <typename _Digraph>
 		  struct BfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    /// \brief Called for the source node(s) of the BFS.
 		    ///
 		    /// This function is called for the source node(s) of the BFS.
 		    void start(const Node& node) {}
 		    /// \brief Called when a node is reached first time.
 		    ///
 		    /// This function is called when a node is reached first time.
 		    void reach(const Node& node) {}
 		    /// \brief Called when a node is processed.
 		    ///
 		    /// This function is called when a node is processed.
 		    void process(const Node& node) {}
 		    /// \brief Called when an arc reaches a new node.
 		    ///
 		    /// This function is called when the BFS finds an arc whose target node
 		    /// is not reached yet.
 		    void discover(const Arc& arc) {}
 		    /// \brief Called when an arc is examined but its target node is
 		    /// already discovered.
 		    ///
 		    /// This function is called when an arc is examined but its target node is
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		  };
 		#else
 		  template <typename _Digraph>
 		  struct BfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    void start(const Node&) {}
 		    void reach(const Node&) {}
 		    void process(const Node&) {}
 		    void discover(const Arc&) {}
 		    void examine(const Arc&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 		        Arc arc;
 		        Node node;
 		        visitor.start(node);
 		        visitor.reach(node);
 		        visitor.process(node);
 		        visitor.discover(arc);
 		        visitor.examine(arc);
+		      }
 		      _Visitor& visitor;
 		    };
 		  };
 		#endif
 		  /// \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>
 		  struct BfsVisitDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef _Digraph Digraph;
 		    /// \brief The type of the map that indicates which nodes are reached.
 		    ///
 		    /// 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;
 		    /// \brief Instantiates a \ref ReachedMap.
 		    ///
 		    /// This function instantiates a \ref ReachedMap.
 		    /// \param digraph is the digraph, to which
 		    /// we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &digraph) {
 		      return new ReachedMap(digraph);
+		    }
 		  };
 		  /// \ingroup search
 		  ///
 		  /// \brief %BFS algorithm class with visitor interface.
 		  ///
 		  /// This class provides an efficient implementation of the %BFS algorithm
 		  /// with visitor interface.
 		  ///
 		  /// 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.
 		  ///
 		  /// This interface of the BFS algorithm should be used in special cases
 		  /// when extra actions have to be performed in connection with certain
 		  /// 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
 		  /// 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
 		  /// algorithm. The default traits class is
 		  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
 		  /// See \ref BfsVisitDefaultTraits for the documentation of
 		  /// a BFS visit traits class.
 		#ifdef DOXYGEN
 		  template <typename _Digraph, typename _Visitor, typename _Traits>
 		#else
 		  template <typename _Digraph = ListDigraph,
 		            typename _Visitor = BfsVisitor<_Digraph>,
 		            typename _Traits = BfsDefaultTraits<_Digraph> >
 		#endif
 		  class BfsVisit {
 		  public:
 		    /// \brief \ref Exception for uninitialized parameters.
 		    ///
 		    /// This error represents problems in the initialization
 		    /// of the parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw()
+		      {
 		        return "lemon::BfsVisit::UninitializedParameter";
+		      }
 		    };
 		    ///The traits class.
 		    typedef _Traits 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;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename Traits::ReachedMap ReachedMap;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *_digraph;
 		    //Pointer to the visitor object.
 		    Visitor *_visitor;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Node> _list;
 		    int _list_front, _list_back;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    void create_maps() {
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*_digraph);
+		      }
+		    }
 		  protected:
 		    BfsVisit() {}
 		  public:
 		    typedef BfsVisit Create;
 		    /// \name Named template parameters
 		    ///@{
 		    template <class T>
-		    struct DefReachedMapTraits : public Traits {
+		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
 		    template <class T>
 		    struct DefReachedMap : public BfsVisit< Digraph, Visitor,
 		                                            DefReachedMapTraits<T> > {
-		      typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
+		    struct SetReachedMap : public BfsVisit< Digraph, Visitor,
 		                                            SetReachedMapTraits<T> > {
 		      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param visitor The visitor object of the algorithm.
 		    BfsVisit(const Digraph& digraph, Visitor& visitor)
 		      : _digraph(&digraph), _visitor(&visitor),
 		        _reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ~BfsVisit() {
 		      if(local_reached) delete _reached;
+		    }
 		    /// \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.
 		    /// \return <tt> (*this) </tt>
 		    BfsVisit &reachedMap(ReachedMap &m) {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached = false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  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.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    void init() {
 		      create_maps();
 		      _list.resize(countNodes(*_digraph));
 		      _list_front = _list_back = -1;
 		      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
 		        _reached->set(u, false);
+		      }
+		    }
 		    /// \brief Adds a new source node.
 		    ///
 		    /// Adds a new source node to the set of nodes to be processed.
 		    void addSource(Node s) {
 		      if(!(*_reached)[s]) {
 		          _reached->set(s,true);
 		          _visitor->start(s);
 		          _visitor->reach(s);
 		          _list[++_list_back] = s;
+		        }
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    Node processNextNode() {
 		      Node n = _list[++_list_front];
 		      _visitor->process(n);
 		      Arc e;
 		      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 		        Node m = _digraph->target(e);
 		        if (!(*_reached)[m]) {
 		          _visitor->discover(e);
 		          _visitor->reach(m);
 		          _reached->set(m, true);
 		          _list[++_list_back] = m;
 		        } else {
 		          _visitor->examine(e);
+		        }
+		      }
 		      return n;
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node and checks if the given target node
 		    /// is reached. If the target node is reachable from the processed
 		    /// node, then the \c reach parameter will be set to \c true.
 		    ///
 		    /// \param target The target node.
 		    /// \retval reach Indicates if the target node is reached.
 		    /// It should be initially \c false.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    Node processNextNode(Node target, bool& reach) {
 		      Node n = _list[++_list_front];
 		      _visitor->process(n);
 		      Arc e;
 		      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 		        Node m = _digraph->target(e);
 		        if (!(*_reached)[m]) {
 		          _visitor->discover(e);
 		          _visitor->reach(m);
 		          _reached->set(m, true);
 		          _list[++_list_back] = m;
 		          reach = reach || (target == m);
 		        } else {
 		          _visitor->examine(e);
+		        }
+		      }
 		      return n;
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node and checks if at least one of reached
 		    /// nodes has \c true value in the \c nm node map. If one node
 		    /// with \c true value is reachable from the processed node, then the
 		    /// \c rnode parameter will be set to the first of such nodes.
 		    ///
 		    /// \param nm A \c bool (or convertible) node map that indicates the
 		    /// possible targets.
 		    /// \retval rnode The reached target node.
 		    /// It should be initially \c INVALID.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    template <typename NM>
 		    Node processNextNode(const NM& nm, Node& rnode) {
 		      Node n = _list[++_list_front];
 		      _visitor->process(n);
 		      Arc e;
 		      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 		        Node m = _digraph->target(e);
 		        if (!(*_reached)[m]) {
 		          _visitor->discover(e);
 		          _visitor->reach(m);
 		          _reached->set(m, true);
 		          _list[++_list_back] = m;
 		          if (nm[m] && rnode == INVALID) rnode = m;
 		        } else {
 		          _visitor->examine(e);
+		        }
+		      }
 		      return n;
+		    }
 		    /// \brief The next node to be processed.
 		    ///
 		    /// Returns the next node to be processed or \c INVALID if the queue
 		    /// is empty.
 		    Node nextNode() const {
 		      return _list_front != _list_back ? _list[_list_front + 1] : 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.
 		    bool emptyQueue() const { return _list_front == _list_back; }
 		    /// \brief Returns the number of the nodes to be processed.
 		    ///
 		    /// Returns the number of the nodes to be processed in the queue.
 		    int queueSize() const { return _list_back - _list_front; }
 		    /// \brief Executes the algorithm.
 		    ///
 		    /// Executes the algorithm.
 		    ///
 		    /// This method runs the %BFS algorithm from the root node(s)

lemon/bits/base_extender.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_BASE_EXTENDER_H
 		#define LEMON_BITS_BASE_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/bits/map_extender.h>
 		#include <lemon/bits/default_map.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		///\ingroup digraphbits
 		///\file
 		///\brief Extenders for the digraph types
 		namespace lemon {
 		  /// \ingroup digraphbits
 		  ///
 		  /// \brief BaseDigraph to BaseGraph extender
 		  template <typename Base>
 		  class UndirDigraphExtender : public Base {
 		  public:
 		    typedef Base Parent;
 		    typedef typename Parent::Arc Edge;
 		    typedef typename Parent::Node Node;
 		    typedef True UndirectedTag;
 		    class Arc : public Edge {
 		      friend class UndirDigraphExtender;
 		    protected:
 		      bool forward;
 		      Arc(const Edge &ue, bool _forward) :
 		        Edge(ue), forward(_forward) {}
 		    public:
 		      Arc() {}
-		      /// Invalid arc constructor
 		      // Invalid arc constructor
 		      Arc(Invalid i) : Edge(i), forward(true) {}
 		      bool operator==(const Arc &that) const {
 		        return forward==that.forward && Edge(*this)==Edge(that);
+		      }
 		      bool operator!=(const Arc &that) const {
 		        return forward!=that.forward || Edge(*this)!=Edge(that);
+		      }
 		      bool operator<(const Arc &that) const {
 		        return forward<that.forward ||
 		          (!(that.forward<forward) && Edge(*this)<Edge(that));
+		      }
 		    };
 		    /// First node of the edge
 		    Node u(const Edge &e) const {
 		      return Parent::source(e);
+		    }
 		    using Parent::source;
 		    /// Source of the given Arc.
 		    /// Source of the given arc
 		    Node source(const Arc &e) const {
 		      return e.forward ? Parent::source(e) : Parent::target(e);
+		    }
-		    using Parent::target;
+		    /// Second node of the edge
 		    Node v(const Edge &e) const {
 		      return Parent::target(e);
+		    }
-		    /// Target of the given Arc.
+		    /// Target of the given arc
 		    Node target(const Arc &e) const {
 		      return e.forward ? Parent::target(e) : Parent::source(e);
+		    }
 		    /// \brief Directed arc from an edge.
 		    ///
 		    /// Returns a directed arc corresponding to the specified Edge.
 		    /// If the given bool is true the given edge and the
 		    /// returned arc have the same source node.
 		    static Arc direct(const Edge &ue, bool d) {
-		      return Arc(ue, d);
+		    /// Returns a directed arc corresponding to the specified edge.
 		    /// If the given bool is true, the first node of the given edge and
 		    /// the source node of the returned arc are the same.
 		    static Arc direct(const Edge &e, bool d) {
 		      return Arc(e, d);
+		    }
 		    /// Returns whether the given directed arc is same orientation as the
 		    /// corresponding edge.
 		    /// Returns whether the given directed arc has the same orientation
 		    /// as the corresponding edge.
 		    ///
 		    /// \todo reference to the corresponding point of the undirected digraph
 		    /// concept. "What does the direction of an edge mean?"
 		    static bool direction(const Arc &e) { return e.forward; }
 		    static bool direction(const Arc &a) { return a.forward; }
 		    using Parent::first;
 		    using Parent::next;
 		    void first(Arc &e) const {
 		      Parent::first(e);
 		      e.forward=true;
+		    }
 		    void next(Arc &e) const {
 		      if( e.forward ) {
 		        e.forward = false;
+		      }
 		      else {
 		        Parent::next(e);
 		        e.forward = true;
+		      }
+		    }
 		    void firstOut(Arc &e, const Node &n) const {
 		      Parent::firstIn(e,n);
 		      if( Edge(e) != INVALID ) {
 		        e.forward = false;
+		      }
 		      else {
 		        Parent::firstOut(e,n);
 		        e.forward = true;
+		      }
+		    }
 		    void nextOut(Arc &e) const {
 		      if( ! e.forward ) {
 		        Node n = Parent::target(e);
 		        Parent::nextIn(e);
 		        if( Edge(e) == INVALID ) {
 		          Parent::firstOut(e, n);
 		          e.forward = true;
+		        }
+		      }
 		      else {
 		        Parent::nextOut(e);
+		      }
+		    }
 		    void firstIn(Arc &e, const Node &n) const {
 		      Parent::firstOut(e,n);
 		      if( Edge(e) != INVALID ) {
 		        e.forward = false;
+		      }
 		      else {
 		        Parent::firstIn(e,n);
 		        e.forward = true;
+		      }
+		    }
 		    void nextIn(Arc &e) const {
 		      if( ! e.forward ) {
 		        Node n = Parent::source(e);
 		        Parent::nextOut(e);
 		        if( Edge(e) == INVALID ) {
 		          Parent::firstIn(e, n);
 		          e.forward = true;
+		        }
+		      }
 		      else {
 		        Parent::nextIn(e);
+		      }
+		    }
 		    void firstInc(Edge &e, bool &d, const Node &n) const {
 		      d = true;
 		      Parent::firstOut(e, n);
 		      if (e != INVALID) return;
 		      d = false;
 		      Parent::firstIn(e, n);
+		    }
 		    void nextInc(Edge &e, bool &d) const {
 		      if (d) {
 		        Node s = Parent::source(e);
 		        Parent::nextOut(e);
 		        if (e != INVALID) return;
 		        d = false;
 		        Parent::firstIn(e, s);
 		      } else {
 		        Parent::nextIn(e);
+		      }
+		    }
 		    Node nodeFromId(int ix) const {
 		      return Parent::nodeFromId(ix);
+		    }
 		    Arc arcFromId(int ix) const {
 		      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
+		    }
 		    Edge edgeFromId(int ix) const {
 		      return Parent::arcFromId(ix);
+		    }
 		    int id(const Node &n) const {
 		      return Parent::id(n);
+		    }
 		    int id(const Edge &e) const {
 		      return Parent::id(e);
+		    }
 		    int id(const Arc &e) const {
 		      return 2 * Parent::id(e) + int(e.forward);
+		    }
 		    int maxNodeId() const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxArcId() const {
 		      return 2 * Parent::maxArcId() + 1;
+		    }
 		    int maxEdgeId() const {
 		      return Parent::maxArcId();
+		    }
 		    int arcNum() const {
 		      return 2 * Parent::arcNum();
+		    }
 		    int edgeNum() const {
 		      return Parent::arcNum();
+		    }
 		    Arc findArc(Node s, Node t, Arc p = INVALID) const {
 		      if (p == INVALID) {
 		        Edge arc = Parent::findArc(s, t);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = Parent::findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else if (direction(p)) {
 		        Edge arc = Parent::findArc(s, t, p);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = Parent::findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else {
 		        Edge arc = Parent::findArc(t, s, p);
 		        if (arc != INVALID) return direct(arc, false);
+		      }
 		      return INVALID;
+		    }
 		    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
 		      if (s != t) {
 		        if (p == INVALID) {
 		          Edge arc = Parent::findArc(s, t);
 		          if (arc != INVALID) return arc;
 		          arc = Parent::findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else if (Parent::s(p) == s) {
 		          Edge arc = Parent::findArc(s, t, p);
 		          if (arc != INVALID) return arc;
 		          arc = Parent::findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else {
 		          Edge arc = Parent::findArc(t, s, p);
 		          if (arc != INVALID) return arc;
+		        }
 		      } else {
 		        return Parent::findArc(s, t, p);
+		      }
 		      return INVALID;
+		    }
 		  };
 		  template <typename Base>
 		  class BidirBpGraphExtender : public Base {
 		  public:
 		    typedef Base Parent;
 		    typedef BidirBpGraphExtender Digraph;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Edge Edge;
 		    using Parent::first;
 		    using Parent::next;
 		    using Parent::id;
 		    class Red : public Node {
 		      friend class BidirBpGraphExtender;
 		    public:
 		      Red() {}
 		      Red(const Node& node) : Node(node) {
 		        LEMON_ASSERT(Parent::red(node) || node == INVALID,
 		                     typename Parent::NodeSetError());
+		      }
 		      Red& operator=(const Node& node) {
 		        LEMON_ASSERT(Parent::red(node) || node == INVALID,
 		                     typename Parent::NodeSetError());
 		        Node::operator=(node);
 		        return *this;
+		      }
 		      Red(Invalid) : Node(INVALID) {}
 		      Red& operator=(Invalid) {
 		        Node::operator=(INVALID);
 		        return *this;
+		      }
 		    };
 		    void first(Red& node) const {
 		      Parent::firstRed(static_cast<Node&>(node));
+		    }
 		    void next(Red& node) const {
 		      Parent::nextRed(static_cast<Node&>(node));
+		    }
 		    int id(const Red& node) const {
 		      return Parent::redId(node);
+		    }
 		    class Blue : public Node {
 		      friend class BidirBpGraphExtender;
 		    public:
 		      Blue() {}
 		      Blue(const Node& node) : Node(node) {
 		        LEMON_ASSERT(Parent::blue(node) || node == INVALID,
 		                     typename Parent::NodeSetError());
+		      }
 		      Blue& operator=(const Node& node) {
 		        LEMON_ASSERT(Parent::blue(node) || node == INVALID,
 		                     typename Parent::NodeSetError());
 		        Node::operator=(node);
 		        return *this;
+		      }
 		      Blue(Invalid) : Node(INVALID) {}
 		      Blue& operator=(Invalid) {
 		        Node::operator=(INVALID);
 		        return *this;
+		      }
 		    };
 		    void first(Blue& node) const {
 		      Parent::firstBlue(static_cast<Node&>(node));
+		    }
 		    void next(Blue& node) const {
 		      Parent::nextBlue(static_cast<Node&>(node));
+		    }
 		    int id(const Blue& node) const {
 		      return Parent::redId(node);
+		    }
 		    Node source(const Edge& arc) const {
 		      return red(arc);
+		    }
 		    Node target(const Edge& arc) const {
 		      return blue(arc);
+		    }
 		    void firstInc(Edge& arc, bool& dir, const Node& node) const {
 		      if (Parent::red(node)) {
 		        Parent::firstFromRed(arc, node);
 		        dir = true;
 		      } else {
 		        Parent::firstFromBlue(arc, node);
 		        dir = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    void nextInc(Edge& arc, bool& dir) const {
 		      if (dir) {
 		        Parent::nextFromRed(arc);
 		      } else {
 		        Parent::nextFromBlue(arc);
 		        if (arc == INVALID) dir = true;
+		      }
+		    }
 		    class Arc : public Edge {
 		      friend class BidirBpGraphExtender;
 		    protected:
 		      bool forward;
 		      Arc(const Edge& arc, bool _forward)
 		        : Edge(arc), forward(_forward) {}
 		    public:
 		      Arc() {}
 		      Arc (Invalid) : Edge(INVALID), forward(true) {}
 		      bool operator==(const Arc& i) const {
 		        return Edge::operator==(i) && forward == i.forward;
+		      }
 		      bool operator!=(const Arc& i) const {
 		        return Edge::operator!=(i) || forward != i.forward;
+		      }
 		      bool operator<(const Arc& i) const {
 		        return Edge::operator<(i) ||
 		          (!(i.forward<forward) && Edge(*this)<Edge(i));
+		      }
 		    };
 		    void first(Arc& arc) const {
 		      Parent::first(static_cast<Edge&>(arc));
 		      arc.forward = true;
+		    }
 		    void next(Arc& arc) const {
 		      if (!arc.forward) {
 		        Parent::next(static_cast<Edge&>(arc));
+		      }
 		      arc.forward = !arc.forward;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      if (Parent::red(node)) {
 		        Parent::firstFromRed(arc, node);
 		        arc.forward = true;

lemon/dfs.h

Show inline comments

@@ -41,472 +41,471 @@
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///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 \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///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 \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref DistMap.
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%DFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %DFS algorithm.
 		  ///
 		  ///There is also a \ref dfs() "function type interface" for the DFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///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 Dfs, it is only passed to \ref DfsDefaultTraits.
 		  ///\tparam TR Traits class to set various data types used by the algorithm.
 		  ///The default traits class is
 		  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
 		  ///See \ref DfsDefaultTraits for the documentation of
 		  ///a Dfs traits class.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=DfsDefaultTraits<GR> >
 		#endif
 		  class Dfs {
 		  public:
 		    ///\ref Exception for uninitialized parameters.
 		    ///This error represents problems in the initialization of the
 		    ///parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 		        return "lemon::Dfs::UninitializedParameter";
+		      }
 		    };
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The traits class.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::OutArcIt> _stack;
 		    int _stack_head;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Dfs() {}
 		  public:
 		    typedef Dfs Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
-		    struct DefPredMapTraits : public Traits {
+		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    template <class T>
 		    struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
 		      typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
 		    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 		      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
-		    struct DefDistMapTraits : public Traits {
+		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    template <class T>
 		    struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
 		      typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
 		    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
-		    struct DefReachedMapTraits : public Traits {
+		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    template <class T>
 		    struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
 		    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
-		    struct DefProcessedMapTraits : public Traits {
+		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    template <class T>
 		    struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
 		    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
-		    struct DefDigraphProcessedMapTraits : public Traits {
+		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    template <class T>
 		    struct DefProcessedMapToBeDefaultMap :
 		      public Dfs< Digraph, DefDigraphProcessedMapTraits> {
 		      typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
 		    struct SetStandardProcessedMap :
 		      public Dfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param g The digraph the algorithm runs on.
 		    Dfs(const Digraph &g) :
 		      G(&g),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _reached(NULL), local_reached(false),
 		      _processed(NULL), local_processed(false)
 		    { }
 		    ///Destructor.
 		    ~Dfs()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_reached) delete _reached;
 		      if(local_processed) delete _processed;
+		    }
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &reachedMap(ReachedMap &m)
+		    {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &processedMap(ProcessedMap &m)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
+		      }
 		      _processed = &m;
 		      return *this;
+		    }
 		    ///Sets the map that stores the distances of the nodes.
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &distMap(DistMap &m)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;
+		    }
 		  public:
 		    ///\name Execution control
 		    ///The simplest way to execute the algorithm is to use
 		    ///one of the member functions called \ref lemon::Dfs::run() "run()".
 		    ///\n
 		    ///If you need more control on the execution, first you must call
 		    ///\ref lemon::Dfs::init() "init()", then you can add a source node
 		    ///with \ref lemon::Dfs::addSource() "addSource()".
 		    ///Finally \ref lemon::Dfs::start() "start()" will perform the
 		    ///actual path computation.
 		    ///@{
 		    ///Initializes the internal data structures.
 		    ///Initializes the internal data structures.
 		    ///
 		    void init()
+		    {
 		      create_maps();
 		      _stack.resize(countNodes(*G));
 		      _stack_head=-1;
 		      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 		        _pred->set(u,INVALID);
 		        _reached->set(u,false);
 		        _processed->set(u,false);
+		      }
+		    }
 		    ///Adds a new source node.
 		    ///Adds a new source node to the set of nodes to be processed.
 		    ///
 		    ///\pre The stack must be empty. (Otherwise the algorithm gives
 		    ///false results.)
 		    ///
 		    ///\warning Distances will be wrong (or at least strange) in case of
 		    ///multiple sources.
 		    void addSource(Node s)
+		    {
 		      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
 		      if(!(*_reached)[s])
+		        {
 		          _reached->set(s,true);
 		          _pred->set(s,INVALID);
 		          OutArcIt e(*G,s);
 		          if(e!=INVALID) {
 		            _stack[++_stack_head]=e;
 		            _dist->set(s,_stack_head);
+		          }
 		          else {
 		            _processed->set(s,true);
 		            _dist->set(s,0);
+		          }
+		        }
+		    }
 		    ///Processes the next arc.
 		    ///Processes the next arc.
 		    ///
 		    ///\return The processed arc.
 		    ///
 		    ///\pre The stack must not be empty.
 		    Arc processNextArc()
+		    {
 		      Node m;
 		      Arc e=_stack[_stack_head];
 		      if(!(*_reached)[m=G->target(e)]) {
 		        _pred->set(m,e);
 		        _reached->set(m,true);
 		        ++_stack_head;
 		        _stack[_stack_head] = OutArcIt(*G, m);
 		        _dist->set(m,_stack_head);
+		      }
 		      else {
 		        m=G->source(e);
 		        ++_stack[_stack_head];
+		      }
 		      while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
 		        _processed->set(m,true);
 		        --_stack_head;
 		        if(_stack_head>=0) {
 		          m=G->source(_stack[_stack_head]);
 		          ++_stack[_stack_head];
+		        }
+		      }
 		      return e;
+		    }
 		    ///Next arc to be processed.
 		    ///Next arc to be processed.
 		    ///
 		    ///\return The next arc to be processed or \c INVALID if the stack
@@ -811,699 +810,699 @@
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///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 \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap<typename Digraph::Node,int> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const Digraph &g)
 		#else
 		    static DistMap *createDistMap(const Digraph &)
 		#endif
+		    {
 		      return new DistMap();
+		    }
 		  };
 		  /// Default traits class used by \ref DfsWizard
 		  /// To make it easier to use Dfs algorithm
 		  /// we have created a wizard class.
 		  /// This \ref DfsWizard class needs default traits,
 		  /// as well as the \ref Dfs class.
 		  /// The \ref DfsWizardBase is a class to be the default traits of the
 		  /// \ref DfsWizard class.
 		  template<class GR>
 		  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
+		  {
 		    typedef DfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the source node.
 		    Node _source;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to default values (0, INVALID).
 		    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _source(INVALID) {}
 		    /// Constructor.
 		    /// This constructor requires some parameters,
 		    /// listed in the parameters list.
 		    /// Others are initiated to 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param s The source node.
 		    DfsWizardBase(const GR &g, Node s=INVALID) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
 		  };
 		  /// Auxiliary class for the function type interface of DFS algorithm.
 		  /// This auxiliary class is created to implement the function type
 		  /// interface of \ref Dfs algorithm. It uses the functions and features
 		  /// of the plain \ref Dfs, but it is much simpler to use it.
 		  /// It should only be used through the \ref dfs() function, which makes
 		  /// it easier to use the algorithm.
 		  ///
 		  /// Simplicity means that the way to change the types defined
 		  /// in the traits class is based on functions that returns the new class
 		  /// and not on templatable built-in classes.
 		  /// When using the plain \ref Dfs
 		  /// the new class with the modified type comes from
 		  /// the original class by using the ::
 		  /// operator. In the case of \ref DfsWizard only
 		  /// a function have to be called, and it will
 		  /// return the needed class.
 		  ///
 		  /// It does not have own \ref run() method. When its \ref run() method
 		  /// is called, it initiates a plain \ref Dfs object, and calls the
 		  /// \ref Dfs::run() method of it.
 		  template<class TR>
 		  class DfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///\brief The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///\brief The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///\brief The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		  public:
 		    /// Constructor.
 		    DfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    DfsWizard(const Digraph &g, Node s=INVALID) :
 		      TR(g,s) {}
 		    ///Copy constructor
 		    DfsWizard(const TR &b) : TR(b) {}
 		    ~DfsWizard() {}
 		    ///Runs DFS algorithm from a source node.
 		    ///Runs DFS algorithm from a source node.
 		    ///The node can be given with the \ref source() function.
 		    void run()
+		    {
 		      if(Base::_source==INVALID) throw UninitializedParameter();
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if(Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if(Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if(Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if(Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      alg.run(Base::_source);
+		    }
 		    ///Runs DFS algorithm from the given node.
 		    ///Runs DFS algorithm from the given node.
 		    ///\param s is the given source.
 		    void run(Node s)
+		    {
 		      Base::_source=s;
 		      run();
+		    }
 		    /// Sets the source node, from which the Dfs algorithm runs.
 		    /// Sets the source node, from which the Dfs algorithm runs.
 		    /// \param s is the source node.
 		    DfsWizard<TR> &source(Node s)
+		    {
 		      Base::_source=s;
 		      return *this;
+		    }
 		    template<class T>
-		    struct DefPredMapBase : public Base {
+		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
-		      DefPredMapBase(const TR &b) : TR(b) {}
+		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    template<class T>
-		    DfsWizard<DefPredMapBase<T> > predMap(const T &t)
+		    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return DfsWizard<DefPredMapBase<T> >(*this);
+		      return DfsWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
-		    struct DefReachedMapBase : public Base {
+		    struct SetReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
-		      DefReachedMapBase(const TR &b) : TR(b) {}
+		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    template<class T>
-		    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
+		    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return DfsWizard<DefReachedMapBase<T> >(*this);
+		      return DfsWizard<SetReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
-		    struct DefProcessedMapBase : public Base {
+		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
-		      DefProcessedMapBase(const TR &b) : TR(b) {}
+		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    template<class T>
-		    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
+		    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return DfsWizard<DefProcessedMapBase<T> >(*this);
+		      return DfsWizard<SetProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
-		    struct DefDistMapBase : public Base {
+		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
-		      DefDistMapBase(const TR &b) : TR(b) {}
+		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    template<class T>
-		    DfsWizard<DefDistMapBase<T> > distMap(const T &t)
+		    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return DfsWizard<DefDistMapBase<T> >(*this);
+		      return DfsWizard<SetDistMapBase<T> >(*this);
+		    }
 		  };
 		  ///Function type interface for Dfs algorithm.
 		  ///\ingroup search
 		  ///Function type interface for Dfs algorithm.
 		  ///
 		  ///This function also has several
 		  ///\ref named-templ-func-param "named parameters",
 		  ///they are declared as the members of class \ref DfsWizard.
 		  ///The following
 		  ///example shows how to use these parameters.
 		  ///\code
 		  ///  dfs(g,source).predMap(preds).run();
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
 		  ///to the end of the parameter list.
 		  ///\sa DfsWizard
 		  ///\sa Dfs
 		  template<class GR>
 		  DfsWizard<DfsWizardBase<GR> >
 		  dfs(const GR &g,typename GR::Node s=INVALID)
+		  {
 		    return DfsWizard<DfsWizardBase<GR> >(g,s);
+		  }
 		#ifdef DOXYGEN
 		  /// \brief Visitor class for DFS.
 		  ///
 		  /// This class defines the interface of the DfsVisit events, and
 		  /// it could be the base of a real visitor class.
 		  template <typename _Digraph>
 		  struct DfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    /// \brief Called for the source node of the DFS.
 		    ///
 		    /// This function is called for the source node of the DFS.
 		    void start(const Node& node) {}
 		    /// \brief Called when the source node is leaved.
 		    ///
 		    /// This function is called when the source node is leaved.
 		    void stop(const Node& node) {}
 		    /// \brief Called when a node is reached first time.
 		    ///
 		    /// This function is called when a node is reached first time.
 		    void reach(const Node& node) {}
 		    /// \brief Called when an arc reaches a new node.
 		    ///
 		    /// This function is called when the DFS finds an arc whose target node
 		    /// is not reached yet.
 		    void discover(const Arc& arc) {}
 		    /// \brief Called when an arc is examined but its target node is
 		    /// already discovered.
 		    ///
 		    /// This function is called when an arc is examined but its target node is
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		    /// \brief Called when the DFS steps back from a node.
 		    ///
 		    /// This function is called when the DFS steps back from a node.
 		    void leave(const Node& node) {}
 		    /// \brief Called when the DFS steps back on an arc.
 		    ///
 		    /// This function is called when the DFS steps back on an arc.
 		    void backtrack(const Arc& arc) {}
 		  };
 		#else
 		  template <typename _Digraph>
 		  struct DfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    void start(const Node&) {}
 		    void stop(const Node&) {}
 		    void reach(const Node&) {}
 		    void discover(const Arc&) {}
 		    void examine(const Arc&) {}
 		    void leave(const Node&) {}
 		    void backtrack(const Arc&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 		        Arc arc;
 		        Node node;
 		        visitor.start(node);
 		        visitor.stop(arc);
 		        visitor.reach(node);
 		        visitor.discover(arc);
 		        visitor.examine(arc);
 		        visitor.leave(node);
 		        visitor.backtrack(arc);
+		      }
 		      _Visitor& visitor;
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of DfsVisit class.
 		  ///
 		  /// Default traits class of DfsVisit class.
 		  /// \tparam _Digraph The type of the digraph the algorithm runs on.
 		  template<class _Digraph>
 		  struct DfsVisitDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef _Digraph Digraph;
 		    /// \brief The type of the map that indicates which nodes are reached.
 		    ///
 		    /// 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;
 		    /// \brief Instantiates a \ref ReachedMap.
 		    ///
 		    /// This function instantiates a \ref ReachedMap.
 		    /// \param digraph is the digraph, to which
 		    /// we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &digraph) {
 		      return new ReachedMap(digraph);
+		    }
 		  };
 		  /// \ingroup search
 		  ///
 		  /// \brief %DFS algorithm class with visitor interface.
 		  ///
 		  /// This class provides an efficient implementation of the %DFS algorithm
 		  /// with visitor interface.
 		  ///
 		  /// The %DfsVisit class provides an alternative interface to the Dfs
 		  /// class. It works with callback mechanism, the DfsVisit object calls
 		  /// the member functions of the \c Visitor class on every DFS event.
 		  ///
 		  /// This interface of the DFS algorithm should be used in special cases
 		  /// when extra actions have to be performed in connection with certain
 		  /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
 		  /// 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 DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
 		  /// \tparam _Visitor The Visitor type that is used by the algorithm.
 		  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
 		  /// does not observe the DFS events. If you want to observe the DFS
 		  /// events, you should implement your own visitor class.
 		  /// \tparam _Traits Traits class to set various data types used by the
 		  /// algorithm. The default traits class is
 		  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
 		  /// See \ref DfsVisitDefaultTraits for the documentation of
 		  /// a DFS visit traits class.
 		#ifdef DOXYGEN
 		  template <typename _Digraph, typename _Visitor, typename _Traits>
 		#else
 		  template <typename _Digraph = ListDigraph,
 		            typename _Visitor = DfsVisitor<_Digraph>,
 		            typename _Traits = DfsDefaultTraits<_Digraph> >
 		#endif
 		  class DfsVisit {
 		  public:
 		    /// \brief \ref Exception for uninitialized parameters.
 		    ///
 		    /// This error represents problems in the initialization
 		    /// of the parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw()
+		      {
 		        return "lemon::DfsVisit::UninitializedParameter";
+		      }
 		    };
 		    ///The traits class.
 		    typedef _Traits 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;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename Traits::ReachedMap ReachedMap;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *_digraph;
 		    //Pointer to the visitor object.
 		    Visitor *_visitor;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Arc> _stack;
 		    int _stack_head;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    void create_maps() {
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*_digraph);
+		      }
+		    }
 		  protected:
 		    DfsVisit() {}
 		  public:
 		    typedef DfsVisit Create;
 		    /// \name Named template parameters
 		    ///@{
 		    template <class T>
-		    struct DefReachedMapTraits : public Traits {
+		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
 		    template <class T>
 		    struct DefReachedMap : public DfsVisit< Digraph, Visitor,
 		                                            DefReachedMapTraits<T> > {
-		      typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
+		    struct SetReachedMap : public DfsVisit< Digraph, Visitor,
 		                                            SetReachedMapTraits<T> > {
 		      typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param visitor The visitor object of the algorithm.
 		    DfsVisit(const Digraph& digraph, Visitor& visitor)
 		      : _digraph(&digraph), _visitor(&visitor),
 		        _reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ~DfsVisit() {
 		      if(local_reached) delete _reached;
+		    }
 		    /// \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.
 		    /// \return <tt> (*this) </tt>
 		    DfsVisit &reachedMap(ReachedMap &m) {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  public:
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to use
 		    /// one of the member functions called \ref lemon::DfsVisit::run()
 		    /// "run()".
 		    /// \n
 		    /// If you need more control on the execution, first you must call
 		    /// \ref lemon::DfsVisit::init() "init()", then you can add several
 		    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
 		    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
 		    /// actual path computation.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    void init() {
 		      create_maps();
 		      _stack.resize(countNodes(*_digraph));
 		      _stack_head = -1;
 		      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
 		        _reached->set(u, false);
+		      }
+		    }
 		    ///Adds a new source node.
 		    ///Adds a new source node to the set of nodes to be processed.
 		    ///
 		    ///\pre The stack must be empty. (Otherwise the algorithm gives
 		    ///false results.)
 		    ///
 		    ///\warning Distances will be wrong (or at least strange) in case of
 		    ///multiple sources.
 		    void addSource(Node s)
+		    {
 		      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
 		      if(!(*_reached)[s]) {
 		          _reached->set(s,true);
 		          _visitor->start(s);
 		          _visitor->reach(s);
 		          Arc e;
 		          _digraph->firstOut(e, s);
 		          if (e != INVALID) {
 		            _stack[++_stack_head] = e;
 		          } else {
 		            _visitor->leave(s);
+		          }
+		        }
+		    }
 		    /// \brief Processes the next arc.
 		    ///
 		    /// Processes the next arc.
 		    ///
 		    /// \return The processed arc.
 		    ///
 		    /// \pre The stack must not be empty.
 		    Arc processNextArc() {
 		      Arc e = _stack[_stack_head];
 		      Node m = _digraph->target(e);
 		      if(!(*_reached)[m]) {
 		        _visitor->discover(e);
 		        _visitor->reach(m);
 		        _reached->set(m, true);
 		        _digraph->firstOut(_stack[++_stack_head], m);
 		      } else {
 		        _visitor->examine(e);
 		        m = _digraph->source(e);
 		        _digraph->nextOut(_stack[_stack_head]);
+		      }
 		      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
 		        _visitor->leave(m);
 		        --_stack_head;
 		        if (_stack_head >= 0) {
 		          _visitor->backtrack(_stack[_stack_head]);
 		          m = _digraph->source(_stack[_stack_head]);
 		          _digraph->nextOut(_stack[_stack_head]);
 		        } else {
 		          _visitor->stop(m);
+		        }
+		      }
 		      return e;
+		    }
 		    /// \brief Next arc to be processed.
 		    ///
 		    /// Next arc to be processed.
 		    ///
 		    /// \return The next arc to be processed or INVALID if the stack is
 		    /// empty.
 		    Arc nextArc() const {
 		      return _stack_head >= 0 ? _stack[_stack_head] : 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 (stack).
 		    bool emptyQueue() const { return _stack_head < 0; }
 		    /// \brief Returns the number of the nodes to be processed.
 		    ///
 		    /// Returns the number of the nodes to be processed in the queue (stack).
 		    int queueSize() const { return _stack_head + 1; }
 		    /// \brief Executes the algorithm.
 		    ///
 		    /// Executes the algorithm.
 		    ///
 		    /// This method runs the %DFS algorithm from the root node
 		    /// in order to compute the %DFS path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the %DFS tree,
 		    /// - the distance of each node from the root in the %DFS tree.
 		    ///
 		    /// \pre init() must be called and a root node should be
 		    /// added with addSource() before using this function.
 		    ///
 		    /// \note <tt>d.start()</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   while ( !d.emptyQueue() ) {
 		    ///     d.processNextArc();
 		    ///   }
 		    /// \endcode
 		    void start() {
 		      while ( !emptyQueue() ) processNextArc();
+		    }
 		    /// \brief Executes the algorithm until the given target node is reached.
 		    ///
 		    /// Executes the algorithm until the given target node is reached.
 		    ///
 		    /// This method runs the %DFS algorithm from the root node
 		    /// in order to compute the DFS path to \c dest.
 		    ///
 		    /// The algorithm computes
 		    /// - the %DFS path to \c dest,
 		    /// - the distance of \c dest from the root in the %DFS tree.
 		    ///
 		    /// \pre init() must be called and a root node should be added
 		    /// with addSource() before using this function.
 		    void start(Node dest) {
 		      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
 		        processNextArc();
+		    }
 		    /// \brief Executes the algorithm until a condition is met.
 		    ///
 		    /// Executes the algorithm until a condition is met.
 		    ///
 		    /// This method runs the %DFS algorithm from the root node

lemon/dijkstra.h

Show inline comments

@@ -142,523 +142,522 @@
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient for the initialization
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    ///\todo If it is set to a real map,
 		    ///Dijkstra::processed() should read this.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///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<typename LM::Value> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%Dijkstra algorithm class.
 		  /// \ingroup shortest_path
 		  ///This class provides an efficient implementation of the %Dijkstra algorithm.
 		  ///
 		  ///The arc lengths are passed to the algorithm using a
 		  ///\ref concepts::ReadMap "ReadMap",
 		  ///so it is easy to change it to any kind of length.
 		  ///The type of the length is determined by the
 		  ///\ref concepts::ReadMap::Value "Value" of the length map.
 		  ///It is also possible to change the underlying priority heap.
 		  ///
 		  ///There is also a \ref dijkstra() "function type interface" for the
 		  ///%Dijkstra algorithm, which is convenient in the simplier cases and
 		  ///it can be 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 Dijkstra, it is only
 		  ///passed to \ref DijkstraDefaultTraits.
 		  ///\tparam LM A readable arc map that determines the lengths of the
 		  ///arcs. It is read once for each arc, so the map may involve in
 		  ///relatively time consuming process to compute the arc lengths if
 		  ///it is necessary. The default map type is \ref
 		  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
 		  ///The value of LM is not used directly by \ref Dijkstra, it is only
 		  ///passed to \ref DijkstraDefaultTraits.
 		  ///\tparam TR Traits class to set various data types used by the algorithm.
 		  ///The default traits class is \ref DijkstraDefaultTraits
 		  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
 		  ///for the documentation of a Dijkstra traits class.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LM, typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename LM=typename GR::template ArcMap<int>,
 		            typename TR=DijkstraDefaultTraits<GR,LM> >
 		#endif
 		  class Dijkstra {
 		  public:
 		    ///\ref Exception for uninitialized parameters.
 		    ///This error represents problems in the initialization of the
 		    ///parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 		        return "lemon::Dijkstra::UninitializedParameter";
+		      }
 		    };
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///The type of the length of the arcs.
 		    typedef typename TR::LengthMap::Value Value;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The cross reference type used for the current heap.
 		    typedef typename TR::HeapCrossRef HeapCrossRef;
 		    ///The heap type used by the algorithm.
 		    typedef typename TR::Heap Heap;
 		    ///The operation traits class.
 		    typedef typename TR::OperationTraits OperationTraits;
 		    ///The traits class.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the length map.
 		    const LengthMap *length;
 		    //Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    //Pointer to the heap cross references.
 		    HeapCrossRef *_heap_cross_ref;
 		    //Indicates if _heap_cross_ref is locally allocated (true) or not.
 		    bool local_heap_cross_ref;
 		    //Pointer to the heap.
 		    Heap *_heap;
 		    //Indicates if _heap is locally allocated (true) or not.
 		    bool local_heap;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
 		      if (!_heap_cross_ref) {
 		        local_heap_cross_ref = true;
 		        _heap_cross_ref = Traits::createHeapCrossRef(*G);
+		      }
 		      if (!_heap) {
 		        local_heap = true;
 		        _heap = Traits::createHeap(*_heap_cross_ref);
+		      }
+		    }
 		  public:
 		    typedef Dijkstra Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
-		    struct DefPredMapTraits : public Traits {
+		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    template <class T>
 		    struct DefPredMap
 		      : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > {
-		      typedef Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > Create;
+		    struct SetPredMap
 		      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
-		    struct DefDistMapTraits : public Traits {
+		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    template <class T>
 		    struct DefDistMap
 		      : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
-		      typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create;
+		    struct SetDistMap
 		      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
-		    struct DefProcessedMapTraits : public Traits {
+		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    template <class T>
 		    struct DefProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > {
-		      typedef Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > Create;
+		    struct SetProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
 		    };
-		    struct DefDigraphProcessedMapTraits : public Traits {
+		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    template <class T>
 		    struct DefProcessedMapToBeDefaultMap
 		      : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
 		      typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits>
 		    struct SetStandardProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
 		      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
 		      Create;
 		    };
 		    template <class H, class CR>
-		    struct DefHeapTraits : public Traits {
+		    struct SetHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
 		        throw UninitializedParameter();
+		      }
 		      static Heap *createHeap(HeapCrossRef &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///heap and cross reference type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting heap and cross
 		    ///reference type.
 		    template <class H, class CR = typename Digraph::template NodeMap<int> >
 		    struct DefHeap
 		      : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > {
-		      typedef Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > Create;
+		    struct SetHeap
 		      : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
 		    };
 		    template <class H, class CR>
-		    struct DefStandardHeapTraits : public Traits {
+		    struct SetStandardHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
 		        return new HeapCrossRef(G);
+		      }
 		      static Heap *createHeap(HeapCrossRef &R)
+		      {
 		        return new Heap(R);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///heap and cross reference type with automatic allocation
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting heap and cross
 		    ///reference type. It can allocate the heap and the cross reference
 		    ///object if the cross reference's constructor waits for the digraph as
 		    ///parameter and the heap's constructor waits for the cross reference.
 		    template <class H, class CR = typename Digraph::template NodeMap<int> >
 		    struct DefStandardHeap
 		      : public Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > {
-		      typedef Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> >
+		    struct SetStandardHeap
 		      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
 		      Create;
 		    };
 		    template <class T>
-		    struct DefOperationTraitsTraits : public Traits {
+		    struct SetOperationTraitsTraits : public Traits {
 		      typedef T OperationTraits;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref OperationTraits type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref OperationTraits type.
 		    template <class T>
 		    struct DefOperationTraits
 		      : public Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > {
-		      typedef Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> >
+		    struct SetOperationTraits
 		      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
 		      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
 		      Create;
 		    };
 		    ///@}
 		  protected:
 		    Dijkstra() {}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param _g The digraph the algorithm runs on.
 		    ///\param _length The length map used by the algorithm.
 		    Dijkstra(const Digraph& _g, const LengthMap& _length) :
 		      G(&_g), length(&_length),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _processed(NULL), local_processed(false),
 		      _heap_cross_ref(NULL), local_heap_cross_ref(false),
 		      _heap(NULL), local_heap(false)
 		    { }
 		    ///Destructor.
 		    ~Dijkstra()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_processed) delete _processed;
 		      if(local_heap_cross_ref) delete _heap_cross_ref;
 		      if(local_heap) delete _heap;
+		    }
 		    ///Sets the length map.
 		    ///Sets the length map.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &lengthMap(const LengthMap &m)
+		    {
 		      length = &m;
 		      return *this;
+		    }
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &processedMap(ProcessedMap &m)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
+		      }
 		      _processed = &m;
 		      return *this;
+		    }
 		    ///Sets the map that stores the distances of the nodes.
 		    ///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.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &distMap(DistMap &m)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;
+		    }
 		    ///Sets the heap and the cross reference used by algorithm.
 		    ///Sets the heap and the cross reference used by algorithm.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated heap and cross reference, of course.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
+		    {
 		      if(local_heap_cross_ref) {
 		        delete _heap_cross_ref;
 		        local_heap_cross_ref=false;
+		      }
 		      _heap_cross_ref = &cr;
 		      if(local_heap) {
 		        delete _heap;
 		        local_heap=false;
+		      }
 		      _heap = &hp;
 		      return *this;
+		    }
 		  private:
 		    void finalizeNodeData(Node v,Value dst)
+		    {
 		      _processed->set(v,true);
 		      _dist->set(v, dst);
+		    }
 		  public:
 		    ///\name Execution control
 		    ///The simplest way to execute the algorithm is to use one of the
 		    ///member functions called \ref lemon::Dijkstra::run() "run()".
 		    ///\n
 		    ///If you need more control on the execution, first you must call
 		    ///\ref lemon::Dijkstra::init() "init()", then you can add several
 		    ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
 		    ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
 		    ///actual path computation.
 		    ///@{
 		    ///Initializes the internal data structures.
 		    ///Initializes the internal data structures.
 		    ///
 		    void init()
+		    {
 		      create_maps();
 		      _heap->clear();
 		      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 		        _pred->set(u,INVALID);
 		        _processed->set(u,false);
 		        _heap_cross_ref->set(u,Heap::PRE_HEAP);
+		      }
+		    }
 		    ///Adds a new source node.
 		    ///Adds a new source node to the priority heap.
 		    ///The optional second parameter is the initial distance of the node.
 		    ///
 		    ///The function checks if the node has already been added to the heap and
 		    ///it is pushed to the heap only if either it was not in the heap
 		    ///or the shortest path found till then is shorter than \c dst.
 		    void addSource(Node s,Value dst=OperationTraits::zero())
+		    {
 		      if(_heap->state(s) != Heap::IN_HEAP) {
 		        _heap->push(s,dst);
 		      } else if(OperationTraits::less((*_heap)[s], dst)) {
 		        _heap->set(s,dst);
 		        _pred->set(s,INVALID);
+		      }
+		    }
 		    ///Processes the next node in the priority heap
 		    ///Processes the next node in the priority heap.
 		    ///
 		    ///\return The processed node.
 		    ///
 		    ///\warning The priority heap must not be empty.
 		    Node processNextNode()
+		    {
 		      Node v=_heap->top();
 		      Value oldvalue=_heap->prio();
 		      _heap->pop();
 		      finalizeNodeData(v,oldvalue);
 		      for(OutArcIt e(*G,v); e!=INVALID; ++e) {
 		        Node w=G->target(e);
 		        switch(_heap->state(w)) {
 		        case Heap::PRE_HEAP:
@@ -1016,274 +1015,274 @@
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef NullMap<typename Digraph::Node,Value> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const Digraph &g)
 		#else
 		    static DistMap *createDistMap(const Digraph &)
 		#endif
+		    {
 		      return new DistMap();
+		    }
 		  };
 		  /// Default traits class used by \ref DijkstraWizard
 		  /// To make it easier to use Dijkstra algorithm
 		  /// we have created a wizard class.
 		  /// This \ref DijkstraWizard class needs default traits,
 		  /// as well as the \ref Dijkstra class.
 		  /// The \ref DijkstraWizardBase is a class to be the default traits of the
 		  /// \ref DijkstraWizard class.
 		  /// \todo More named parameters are required...
 		  template<class GR,class LM>
 		  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
+		  {
 		    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the length map
 		    void *_length;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the source node.
 		    Node _source;
 		  public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to default values (0, INVALID).
 		    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
 		                           _dist(0), _source(INVALID) {}
 		    /// Constructor.
 		    /// This constructor requires some parameters,
 		    /// listed in the parameters list.
 		    /// Others are initiated to 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param l The length map.
 		    /// \param s The source node.
 		    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
 		      _processed(0), _pred(0), _dist(0), _source(s) {}
 		  };
 		  /// Auxiliary class for the function type interface of Dijkstra algorithm.
 		  /// This auxiliary class is created to implement the function type
 		  /// interface of \ref Dijkstra algorithm. It uses the functions and features
 		  /// of the plain \ref Dijkstra, but it is much simpler to use it.
 		  /// It should only be used through the \ref dijkstra() function, which makes
 		  /// it easier to use the algorithm.
 		  ///
 		  /// Simplicity means that the way to change the types defined
 		  /// in the traits class is based on functions that returns the new class
 		  /// and not on templatable built-in classes.
 		  /// When using the plain \ref Dijkstra
 		  /// the new class with the modified type comes from
 		  /// the original class by using the ::
 		  /// operator. In the case of \ref DijkstraWizard only
 		  /// a function have to be called, and it will
 		  /// return the needed class.
 		  ///
 		  /// It does not have own \ref run() method. When its \ref run() method
 		  /// is called, it initiates a plain \ref Dijkstra object, and calls the
 		  /// \ref Dijkstra::run() method of it.
 		  template<class TR>
 		  class DijkstraWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    ///The type of the length of the arcs.
 		    typedef typename LengthMap::Value Value;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The heap type used by the dijkstra algorithm.
 		    typedef typename TR::Heap Heap;
 		  public:
 		    /// Constructor.
 		    DijkstraWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
 		      TR(g,l,s) {}
 		    ///Copy constructor
 		    DijkstraWizard(const TR &b) : TR(b) {}
 		    ~DijkstraWizard() {}
 		    ///Runs Dijkstra algorithm from a source node.
 		    ///Runs Dijkstra algorithm from a source node.
 		    ///The node can be given with the \ref source() function.
 		    void run()
+		    {
 		      if(Base::_source==INVALID) throw UninitializedParameter();
 		      Dijkstra<Digraph,LengthMap,TR>
 		        dij(*reinterpret_cast<const Digraph*>(Base::_g),
 		            *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if(Base::_processed)
 		        dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if(Base::_pred)
 		        dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if(Base::_dist)
 		        dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      dij.run(Base::_source);
+		    }
 		    ///Runs Dijkstra algorithm from the given node.
 		    ///Runs Dijkstra algorithm from the given node.
 		    ///\param s is the given source.
 		    void run(Node s)
+		    {
 		      Base::_source=s;
 		      run();
+		    }
 		    /// Sets the source node, from which the Dijkstra algorithm runs.
 		    /// Sets the source node, from which the Dijkstra algorithm runs.
 		    /// \param s is the source node.
 		    DijkstraWizard<TR> &source(Node s)
+		    {
 		      Base::_source=s;
 		      return *this;
+		    }
 		    template<class T>
-		    struct DefPredMapBase : public Base {
+		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
-		      DefPredMapBase(const TR &b) : TR(b) {}
+		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    template<class T>
-		    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
+		    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return DijkstraWizard<DefPredMapBase<T> >(*this);
+		      return DijkstraWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
-		    struct DefProcessedMapBase : public Base {
+		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
-		      DefProcessedMapBase(const TR &b) : TR(b) {}
+		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    template<class T>
-		    DijkstraWizard<DefProcessedMapBase<T> > processedMap(const T &t)
+		    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return DijkstraWizard<DefProcessedMapBase<T> >(*this);
+		      return DijkstraWizard<SetProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
-		    struct DefDistMapBase : public Base {
+		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
-		      DefDistMapBase(const TR &b) : TR(b) {}
+		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    template<class T>
-		    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
+		    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
-		      return DijkstraWizard<DefDistMapBase<T> >(*this);
+		      return DijkstraWizard<SetDistMapBase<T> >(*this);
+		    }
 		  };
 		  ///Function type interface for Dijkstra algorithm.
 		  /// \ingroup shortest_path
 		  ///Function type interface for Dijkstra algorithm.
 		  ///
 		  ///This function also has several
 		  ///\ref named-templ-func-param "named parameters",
 		  ///they are declared as the members of class \ref DijkstraWizard.
 		  ///The following
 		  ///example shows how to use these parameters.
 		  ///\code
 		  ///  dijkstra(g,length,source).predMap(preds).run();
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
 		  ///to the end of the parameter list.
 		  ///\sa DijkstraWizard
 		  ///\sa Dijkstra
 		  template<class GR, class LM>
 		  DijkstraWizard<DijkstraWizardBase<GR,LM> >
 		  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
+		  {
 		    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
+		  }
 		} //END OF NAMESPACE LEMON
 		#endif

test/heap_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <iostream>
 		#include <fstream>
 		#include <string>
 		#include <vector>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/heap.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/maps.h>
 		#include <lemon/bin_heap.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		typedef ListDigraph Digraph;
 		DIGRAPH_TYPEDEFS(Digraph);
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "6\n"
 		  "7\n"
 		  "8\n"
 		  "9\n"
 		  "@arcs\n"
 		  "                label   capacity\n"
 		  "0       5       0       94\n"
 		  "3       9       1       11\n"
 		  "8       7       2       83\n"
 		  "1       2       3       94\n"
 		  "5       7       4       35\n"
 		  "7       4       5       84\n"
 		  "9       5       6       38\n"
 		  "0       4       7       96\n"
 		  "6       7       8       6\n"
 		  "3       1       9       27\n"
 		  "5       2       10      77\n"
 		  "5       6       11      69\n"
 		  "6       5       12      41\n"
 		  "4       6       13      70\n"
 		  "3       2       14      45\n"
 		  "7       9       15      93\n"
 		  "5       9       16      50\n"
 		  "9       0       17      94\n"
 		  "9       6       18      67\n"
 		  "0       9       19      86\n"
 		  "@attributes\n"
 		  "source 3\n";
 		int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
 		int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
 		int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
 		template <typename Heap>
 		void heapSortTest() {
 		  RangeMap<int> map(test_len, -1);
 		  Heap heap(map);
 		  std::vector<int> v(test_len);
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] = test_seq[i];
 		    heap.push(i, v[i]);
+		  }
 		  std::sort(v.begin(), v.end());
 		  for (int i = 0; i < test_len; ++i) {
 		    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
 		    heap.pop();
+		  }
+		}
 		template <typename Heap>
 		void heapIncreaseTest() {
 		  RangeMap<int> map(test_len, -1);
 		  Heap heap(map);
 		  std::vector<int> v(test_len);
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] = test_seq[i];
 		    heap.push(i, v[i]);
+		  }
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] += test_inc[i];
 		    heap.increase(i, v[i]);
+		  }
 		  std::sort(v.begin(), v.end());
 		  for (int i = 0; i < test_len; ++i) {
 		    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
 		    heap.pop();
+		  }
+		}
 		template <typename Heap>
 		void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
 		                      Node source) {
-		  typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
+		  typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
 		    Create dijkstra(digraph, length);
 		  dijkstra.run(source);
 		  for(ArcIt a(digraph); a != INVALID; ++a) {
 		    Node s = digraph.source(a);
 		    Node t = digraph.target(a);
 		    if (dijkstra.reached(s)) {
 		      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
 		             "Error in a shortest path tree!");
+		    }
+		  }
 		  for(NodeIt n(digraph); n != INVALID; ++n) {
 		    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
 		      Arc a = dijkstra.predArc(n);
 		      Node s = digraph.source(a);
 		      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
 		             "Error in a shortest path tree!");
+		    }
+		  }
+		}
 		int main() {
 		  typedef int Item;
 		  typedef int Prio;
 		  typedef RangeMap<int> ItemIntMap;
 		  Digraph digraph;
 		  IntArcMap length(digraph);
 		  Node source;
 		  std::istringstream input(test_lgf);
 		  digraphReader(input, digraph).
 		    arcMap("capacity", length).
 		    node("source", source).
 		    run();
+		  {
 		    typedef BinHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account