LEMON/LEMON-official Changeset - r287:bb40b6db0a58

Repositories » LEMON » LEMON-official

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

Changeset - r287:bb40b6db0a58

« 285:d8dc5a
« 286:da4149

290:f68999 »
288:47b3a3 »

r287:bb40b6db0a58

Sat, 27 Sep 2008 14:33:28

[Not Reviewed]

0 comments (0 inline)

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

Merge

0 18 0

merge default

3 files changed:

lemon/bfs.h

lemon/bits/base_extender.h

lemon/bits/vector_map.h

lemon/concept_check.h

lemon/concepts/path.h

lemon/core.h

325

309

lemon/dfs.h

Changeset was too big and was cut off... Show full diff

↑ Collapse diff ↑

lemon/bfs.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_BFS_H
 		#define LEMON_BFS_H
 		///\ingroup search
 		///\file
 		///\brief BFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///Default traits class of Bfs class.
 		  ///Default traits class of Bfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsDefaultTraits
+		  {
 		    ///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).
 		    //Creates the maps if necessary.
 		    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 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 SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 		      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    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 SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    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 SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    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 SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    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.
 		    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)
 		        if(!(*_reached)[m=G->target(e)]) {
 		          _queue[_queue_head++]=m;
 		          _reached->set(m,true);
 		          _pred->set(m,e);
 		          _dist->set(m,_curr_dist);
 		          reach = reach || (target == m);
+		        }
 		      return n;
+		    }
 		    ///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<class NM>
 		    Node processNextNode(const NM& nm, Node& rnode)
+		    {
 		      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);
 		          if (nm[m] && rnode == INVALID) rnode = m;
+		        }
 		      return n;
+		    }
 		    ///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 _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
+		    }
 		    ///\brief Returns \c false if there are nodes
 		    ///to be processed.
 		    ///
 		    ///Returns \c false if there are nodes
 		    ///to be processed in the queue.
 		    bool emptyQueue() const { return _queue_tail==_queue_head; }
 		    ///Returns the number of the nodes to be processed.
 		    ///Returns the number of the nodes to be processed in the queue.
 		    int queueSize() const { return _queue_head-_queue_tail; }
 		    ///Executes the algorithm.
 		    ///Executes the algorithm.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s)
 		    ///in order to compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree (forest),
 		    ///- the distance of each node from the root(s).
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>b.start()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  while ( !b.emptyQueue() ) {
 		    ///    b.processNextNode();
 		    ///  }
 		    ///\endcode
 		    void start()
+		    {
 		      while ( !emptyQueue() ) processNextNode();
+		    }
 		    ///Executes the algorithm until the given target node is reached.
 		    ///Executes the algorithm until the given target node is reached.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s)
 		    ///in order to compute the shortest path to \c t.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path to \c t,
 		    ///- the distance of \c t from the root(s).
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  bool reach = false;
 		    ///  while ( !b.emptyQueue() && !reach ) {
 		    ///    b.processNextNode(t, reach);
 		    ///  }
 		    ///\endcode
 		    void start(Node t)
+		    {
 		      bool reach = false;
 		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
 		    ///Executes the algorithm until a condition is met.
 		    ///Executes the algorithm until a condition is met.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s) in
 		    ///order to compute the shortest path to a node \c v with
 		    /// <tt>nm[v]</tt> true, if such a node can be found.
 		    ///
 		    ///\param nm A \c bool (or convertible) node map. The algorithm
 		    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
 		    ///
 		    ///\return The reached node \c v with <tt>nm[v]</tt> true or
 		    ///\c INVALID if no such node was found.
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  Node rnode = INVALID;
 		    ///  while ( !b.emptyQueue() && rnode == INVALID ) {
 		    ///    b.processNextNode(nm, rnode);
 		    ///  }
 		    ///  return rnode;
 		    ///\endcode
 		    template<class NodeBoolMap>
 		    Node start(const NodeBoolMap &nm)
+		    {
 		      Node rnode = INVALID;
 		      while ( !emptyQueue() && rnode == INVALID ) {
 		        processNextNode(nm, rnode);
+		      }
 		      return rnode;
+		    }
 		    ///Runs the algorithm from the given source node.
 		    ///This method runs the %BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree,
 		    ///- the distance of each node from the root.
 		    ///
 		    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  b.addSource(s);
 		    ///  b.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs the %BFS algorithm from node \c s
 		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    ///
 		    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
 		    ///shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  b.addSource(s);
 		    ///  b.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    ///Runs the algorithm to visit all nodes in the digraph.
 		    ///This method runs the %BFS algorithm in order to
 		    ///compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree (forest),
 		    ///- the distance of each node from the root(s).
 		    ///
 		    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  for (NodeIt n(gr); n != INVALID; ++n) {
 		    ///    if (!b.reached(n)) {
 		    ///      b.addSource(n);
 		    ///      b.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt n(*G); n != INVALID; ++n) {
 		        if (!reached(n)) {
 		          addSource(n);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The result of the %BFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
 		    ///"start()" must be called before using them.
 		    ///@{
 		    ///The shortest path to a node.
 		    ///Returns the shortest path to a node.
 		    ///
 		    ///\warning \c t should be reachable from the root(s).
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///The distance of a node from the root(s).
 		    ///Returns the distance of a node from the root(s).
 		    ///
 		    ///\warning If node \c v is not reachable from the root(s), then
 		    ///the return value of this function is undefined.
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the shortest path tree for a node.
 		    ///This function returns the 'previous arc' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last arc of a
 		    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
 		    ///is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predNode().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///Returns the 'previous node' of the shortest path tree for a node.
 		    ///This function returns the 'previous node' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last but one node
 		    ///from a shortest path from the root(s) to \c v. It is \c INVALID
 		    ///if \c v is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predArc().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->source((*_pred)[v]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    /// distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the distances
 		    ///of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the shortest path tree.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if a node is reachable from the root(s).
 		    ///Returns \c true if \c v is reachable from the root(s).
 		    ///\pre Either \ref run() or \ref start()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of bfs() function.
 		  ///Default traits class of bfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsWizardDefaultTraits
+		  {
 		    ///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);
+		    }
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
 		    ///It must meet the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// 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 shortest path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    int *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to \c 0.
 		    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires one parameter,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    BfsWizardBase(const GR &g) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of BFS algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
 		  /// It does not have own \ref run() method, it uses the functions
 		  /// and features of the plain \ref Bfs.
 		  ///
 		  /// This class should only be used through the \ref bfs() function,
 		  /// which makes it easier to use the algorithm.
 		  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;
 		    ///The type of the shortest paths
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    BfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param g The digraph the algorithm runs on.
 		    BfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
 		    BfsWizard(const TR &b) : TR(b) {}
 		    ~BfsWizard() {}
 		    ///Runs BFS algorithm from the given source node.
 		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    void run(Node s)
+		    {
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if (s!=INVALID)
 		        alg.run(s);
 		      else
 		        alg.run();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)
+		    {
 		      if (s==INVALID || t==INVALID) throw UninitializedParameter();
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      alg.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
 		      if (Base::_di)
 		        *Base::_di = alg.dist(t);
 		      return alg.reached(t);
+		    }
 		    ///Runs BFS algorithm to visit all nodes in the digraph.
 		    ///This method runs BFS algorithm in order to compute
 		    ///the shortest path to each node.
 		    void run()
+		    {
 		      run(INVALID);
+		    }
 		    template<class T>
 		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    template<class T>
 		    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    template<class T>
 		    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    template<class T>
 		    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetDistMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    template<class T>
 		    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetPathBase : public Base {
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the shortest path to the target node.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the shortest path to the target node.
 		    template<class T>
 		    BfsWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetPathBase<T> >(*this);
+		    }
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the distance of the target node.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the distance of the target node.
 		    BfsWizard dist(const int &d)
+		    {
 		      Base::_di=const_cast<int*>(&d);
 		      return *this;
+		    }
 		  };
 		  ///Function-type interface for BFS algorithm.
 		  /// \ingroup search
 		  ///Function-type interface for BFS algorithm.
 		  ///
 		  ///This function also has several \ref named-func-param "named parameters",
 		  ///they are declared as the members of class \ref BfsWizard.
 		  ///The following examples show how to use these parameters.
 		  ///\code
 		  ///  // Compute shortest path from node s to each node
 		  ///  bfs(g).predMap(preds).distMap(dists).run(s);
 		  ///
 		  ///  // Compute shortest path from s to t
 		  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
 		  ///to the end of the parameter list.
 		  ///\sa BfsWizard
 		  ///\sa Bfs
 		  template<class GR>
 		  BfsWizard<BfsWizardBase<GR> >
 		  bfs(const GR &digraph)
+		  {
 		    return BfsWizard<BfsWizardBase<GR> >(digraph);
+		  }
 		#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).
 		    //Creates the maps if necessary.
 		    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 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 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)
 		    /// in order to compute the shortest path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree (forest),
 		    /// - the distance of each node from the root(s).
 		    ///
 		    /// \pre init() must be called and at least one root node should be added
 		    /// with addSource() before using this function.
 		    ///
 		    /// \note <tt>b.start()</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   while ( !b.emptyQueue() ) {
 		    ///     b.processNextNode();
 		    ///   }
 		    /// \endcode
 		    void start() {
 		      while ( !emptyQueue() ) processNextNode();
+		    }
 		    /// \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 %BFS algorithm from the root node(s)
 		    /// in order to compute the shortest path to \c t.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path to \c t,
 		    /// - the distance of \c t from the root(s).
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    ///
 		    /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   bool reach = false;
 		    ///   while ( !b.emptyQueue() && !reach ) {
 		    ///     b.processNextNode(t, reach);
 		    ///   }
 		    /// \endcode
 		    void start(Node t) {
 		      bool reach = false;
 		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
 		    /// \brief Executes the algorithm until a condition is met.
 		    ///
 		    /// Executes the algorithm until a condition is met.
 		    ///
 		    /// This method runs the %BFS algorithm from the root node(s) in
 		    /// order to compute the shortest path to a node \c v with
 		    /// <tt>nm[v]</tt> true, if such a node can be found.
 		    ///
 		    /// \param nm must be a bool (or convertible) node map. The
 		    /// algorithm will stop when it reaches a node \c v with
 		    /// <tt>nm[v]</tt> true.
 		    ///
 		    /// \return The reached node \c v with <tt>nm[v]</tt> true or
 		    /// \c INVALID if no such node was found.
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    ///
 		    /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   Node rnode = INVALID;
 		    ///   while ( !b.emptyQueue() && rnode == INVALID ) {
 		    ///     b.processNextNode(nm, rnode);
 		    ///   }
 		    ///   return rnode;
 		    /// \endcode
 		    template <typename NM>
 		    Node start(const NM &nm) {
 		      Node rnode = INVALID;
 		      while ( !emptyQueue() && rnode == INVALID ) {
 		        processNextNode(nm, rnode);
+		      }
 		      return rnode;
+		    }
 		    /// \brief Runs the algorithm from the given source node.
 		    ///
 		    /// This method runs the %BFS algorithm from node \c s
 		    /// in order to compute the shortest path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree,
 		    /// - the distance of each node from the root.
 		    ///
 		    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///   b.init();
 		    ///   b.addSource(s);
 		    ///   b.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    /// \brief Finds the shortest path between \c s and \c t.
 		    ///
 		    /// This method runs the %BFS algorithm from node \c s
 		    /// in order to compute the shortest path to node \c t
 		    /// (it stops searching when \c t is processed).
 		    ///
 		    /// \return \c true if \c t is reachable form \c s.
 		    ///
 		    /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
 		    /// shortcut of the following code.
 		    ///\code
 		    ///   b.init();
 		    ///   b.addSource(s);
 		    ///   b.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    /// \brief Runs the algorithm to visit all nodes in the digraph.
 		    ///
 		    /// This method runs the %BFS algorithm in order to
 		    /// compute the shortest path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree (forest),
 		    /// - the distance of each node from the root(s).
 		    ///
 		    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  for (NodeIt n(gr); n != INVALID; ++n) {
 		    ///    if (!b.reached(n)) {
 		    ///      b.addSource(n);
 		    ///      b.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt it(*_digraph); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    /// \name Query Functions
 		    /// The result of the %BFS algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either \ref lemon::BfsVisit::run() "run()" or
 		    /// \ref lemon::BfsVisit::start() "start()" must be called before
 		    /// using them.
 		    ///@{
 		    /// \brief Checks if a node is reachable from the root(s).
 		    ///
 		    /// Returns \c true if \c v is reachable from the root(s).
 		    /// \pre Either \ref run() or \ref start()
 		    /// must be called before using this function.
 		    bool reached(Node v) { return (*_reached)[v]; }
 		    ///@}
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif

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
      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);
    }

    /// Source of the given arc
    Node source(const Arc &e) const {
      return e.forward ? Parent::source(e) : Parent::target(e);
    }

    /// Second node of the edge
    Node v(const Edge &e) const {
      return Parent::target(e);
    }

    /// 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 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 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 &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;
      } else {
        Parent::firstFromBlue(arc, node);
        arc.forward = static_cast<Edge&>(arc) == INVALID;
      }
    }
    void nextOut(Arc& arc) const {
      if (arc.forward) {
        Parent::nextFromRed(arc);
      } else {
        Parent::nextFromBlue(arc);
        arc.forward = static_cast<Edge&>(arc) == INVALID;
      }
    }

    void firstIn(Arc& arc, const Node& node) const {
      if (Parent::blue(node)) {
        Parent::firstFromBlue(arc, node);
        arc.forward = true;
      } else {
        Parent::firstFromRed(arc, node);
        arc.forward = static_cast<Edge&>(arc) == INVALID;
      }
    }
    void nextIn(Arc& arc) const {
      if (arc.forward) {
        Parent::nextFromBlue(arc);
      } else {
        Parent::nextFromRed(arc);
        arc.forward = static_cast<Edge&>(arc) == INVALID;
      }
    }

    Node source(const Arc& arc) const {
      return arc.forward ? Parent::red(arc) : Parent::blue(arc);
    }
    Node target(const Arc& arc) const {
      return arc.forward ? Parent::blue(arc) : Parent::red(arc);
    }

    int id(const Arc& arc) const {
      return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
        (arc.forward ? 0 : 1);
    }
    Arc arcFromId(int ix) const {
      return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
    }
    int maxArcId() const {
      return (Parent::maxEdgeId() << 1) + 1;
    }

    bool direction(const Arc& arc) const {
      return arc.forward;
    }

    Arc direct(const Edge& arc, bool dir) const {
      return Arc(arc, dir);
    }

    int arcNum() const {
      return 2 * Parent::edgeNum();
    }

    int edgeNum() const {
      return Parent::edgeNum();
    }


  };
}

#endif

lemon/bits/vector_map.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_VECTOR_MAP_H
 		#define LEMON_BITS_VECTOR_MAP_H
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/core.h>
 		#include <lemon/bits/alteration_notifier.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		///\ingroup graphbits
 		///
 		///\file
 		///\brief Vector based graph maps.
 		namespace lemon {
 		  /// \ingroup graphbits
 		  ///
 		  /// \brief Graph map based on the std::vector storage.
 		  ///
 		  /// The VectorMap template class is graph map structure what
 		  /// automatically updates the map when a key is added to or erased from
 		  /// the map. This map type uses the std::vector to store the values.
 		  ///
-		  /// \tparam _Notifier The AlterationNotifier that will notify this map.
+		  /// \tparam _Graph The graph this map is attached to.
 		  /// \tparam _Item The item type of the graph items.
 		  /// \tparam _Value The value type of the map.
 		  /// \todo Fix the doc: there is _Graph parameter instead of _Notifier.
 		  template <typename _Graph, typename _Item, typename _Value>
 		  class VectorMap
 		    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
 		  private:
 		    /// The container type of the map.
 		    typedef std::vector<_Value> Container;
 		  public:
 		    /// The graph type of the map.
 		    typedef _Graph Graph;
 		    /// The item type of the map.
 		    typedef _Item Item;
 		    /// The reference map tag.
 		    typedef True ReferenceMapTag;
 		    /// The key type of the map.
 		    typedef _Item Key;
 		    /// The value type of the map.
 		    typedef _Value Value;
 		    /// The notifier type.
 		    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
 		    /// The map type.
 		    typedef VectorMap Map;
 		    /// The base class of the map.
 		    typedef typename Notifier::ObserverBase Parent;
 		    /// The reference type of the map;
 		    typedef typename Container::reference Reference;
 		    /// The const reference type of the map;
 		    typedef typename Container::const_reference ConstReference;
 		    /// \brief Constructor to attach the new map into the notifier.
 		    ///
 		    /// It constructs a map and attachs it into the notifier.
 		    /// It adds all the items of the graph to the map.
 		    VectorMap(const Graph& graph) {
 		      Parent::attach(graph.notifier(Item()));
 		      container.resize(Parent::notifier()->maxId() + 1);
+		    }
 		    /// \brief Constructor uses given value to initialize the map.
 		    ///
 		    /// It constructs a map uses a given value to initialize the map.
 		    /// It adds all the items of the graph to the map.
 		    VectorMap(const Graph& graph, const Value& value) {
 		      Parent::attach(graph.notifier(Item()));
 		      container.resize(Parent::notifier()->maxId() + 1, value);
+		    }
 		  private:
 		    /// \brief Copy constructor
 		    ///
 		    /// Copy constructor.
 		    VectorMap(const VectorMap& _copy) : Parent() {
 		      if (_copy.attached()) {
 		        Parent::attach(*_copy.notifier());
 		        container = _copy.container;
+		      }
+		    }
 		    /// \brief Assign operator.
 		    ///
 		    /// This operator assigns for each item in the map the
 		    /// value mapped to the same item in the copied map.
 		    /// The parameter map should be indiced with the same
 		    /// itemset because this assign operator does not change
 		    /// the container of the map.
 		    VectorMap& operator=(const VectorMap& cmap) {
 		      return operator=<VectorMap>(cmap);
+		    }
 		    /// \brief Template assign operator.
 		    ///
 		    /// The given parameter should be conform to the ReadMap
 		    /// concecpt and could be indiced by the current item set of
 		    /// the NodeMap. In this case the value for each item
 		    /// is assigned by the value of the given ReadMap.
 		    template <typename CMap>
 		    VectorMap& operator=(const CMap& cmap) {
 		      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
 		      const typename Parent::Notifier* nf = Parent::notifier();
 		      Item it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        set(it, cmap[it]);
+		      }
 		      return *this;
+		    }
 		  public:
 		    /// \brief The subcript operator.
 		    ///
 		    /// The subscript operator. The map can be subscripted by the
 		    /// actual items of the graph.
 		    Reference operator[](const Key& key) {
 		      return container[Parent::notifier()->id(key)];
+		    }
 		    /// \brief The const subcript operator.
 		    ///
 		    /// The const subscript operator. The map can be subscripted by the
 		    /// actual items of the graph.
 		    ConstReference operator[](const Key& key) const {
 		      return container[Parent::notifier()->id(key)];
+		    }
 		    /// \brief The setter function of the map.
 		    ///
 		    /// It the same as operator[](key) = value expression.
 		    void set(const Key& key, const Value& value) {
 		      (*this)[key] = value;
+		    }
 		  protected:
 		    /// \brief Adds a new key to the map.
 		    ///
 		    /// It adds a new key to the map. It called by the observer notifier
 		    /// and it overrides the add() member function of the observer base.
 		    virtual void add(const Key& key) {
 		      int id = Parent::notifier()->id(key);
 		      if (id >= int(container.size())) {
 		        container.resize(id + 1);
+		      }
+		    }
 		    /// \brief Adds more new keys to the map.
 		    ///
 		    /// It adds more new keys to the map. It called by the observer notifier
 		    /// and it overrides the add() member function of the observer base.
 		    virtual void add(const std::vector<Key>& keys) {
 		      int max = container.size() - 1;
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        int id = Parent::notifier()->id(keys[i]);
 		        if (id >= max) {
 		          max = id;
+		        }
+		      }
 		      container.resize(max + 1);
+		    }
 		    /// \brief Erase a key from the map.
 		    ///
 		    /// Erase a key from the map. It called by the observer notifier
 		    /// and it overrides the erase() member function of the observer base.
 		    virtual void erase(const Key& key) {
 		      container[Parent::notifier()->id(key)] = Value();
+		    }
 		    /// \brief Erase more keys from the map.
 		    ///
 		    /// Erase more keys from the map. It called by the observer notifier
 		    /// and it overrides the erase() member function of the observer base.
 		    virtual void erase(const std::vector<Key>& keys) {
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        container[Parent::notifier()->id(keys[i])] = Value();
+		      }
+		    }
 		    /// \brief Buildes the map.
 		    ///
 		    /// It buildes the map. It called by the observer notifier
 		    /// and it overrides the build() member function of the observer base.
 		    virtual void build() {
 		      int size = Parent::notifier()->maxId() + 1;
 		      container.reserve(size);
 		      container.resize(size);
+		    }
 		    /// \brief Clear the map.
 		    ///
 		    /// It erase all items from the map. It called by the observer notifier
 		    /// and it overrides the clear() member function of the observer base.
 		    virtual void clear() {
 		      container.clear();
+		    }
 		  private:
 		    Container container;
 		  };
+		}
 		#endif

lemon/concept_check.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.
+		 *
 		 */
 		// This file contains a modified version of the concept checking
 		// utility from BOOST.
 		// See the appropriate copyright notice below.
 		// (C) Copyright Jeremy Siek 2000.
 		// Distributed under the Boost Software License, Version 1.0. (See
 		// accompanying file LICENSE_1_0.txt or copy at
 		// http://www.boost.org/LICENSE_1_0.txt)
 		//
 		// Revision History:
 		//   05 May   2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
 		//   02 April 2001: Removed limits header altogether. (Jeremy Siek)
 		//   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
 		//
 		// See http://www.boost.org/libs/concept_check for documentation.
 		// The contents of this file was inspired by the concept checking
 		// utility of the BOOST library (http://www.boost.org).
 		///\file
 		///\brief Basic utilities for concept checking.
 		///
 		///\todo Are we still using BOOST concept checking utility?
 		///Is the BOOST copyright notice necessary?
 		#ifndef LEMON_CONCEPT_CHECK_H
 		#define LEMON_CONCEPT_CHECK_H
 		namespace lemon {
 		  /*
 		    "inline" is used for ignore_unused_variable_warning()
 		    and function_requires() to make sure there is no
 		    overtarget with g++.
 		  */
 		  template <class T> inline void ignore_unused_variable_warning(const T&) { }
 		  ///\e
 		  template <class Concept>
 		  inline void function_requires()
+		  {
 		#if !defined(NDEBUG)
 		    void (Concept::*x)() = & Concept::constraints;
 		    ignore_unused_variable_warning(x);
 		#endif
+		  }
 		  ///\e
 		  template <typename Concept, typename Type>
 		  inline void checkConcept() {
 		#if !defined(NDEBUG)
 		    typedef typename Concept::template Constraints<Type> ConceptCheck;
 		    void (ConceptCheck::*x)() = & ConceptCheck::constraints;
 		    ignore_unused_variable_warning(x);
 		#endif
+		  }
 		} // namespace lemon
 		#endif // LEMON_CONCEPT_CHECK_H

lemon/concepts/path.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.
+		 *
 		 */
 		///\ingroup concept
 		///\file
 		///\brief Classes for representing paths in digraphs.
 		///
 		///\todo Iterators have obsolete style
 		#ifndef LEMON_CONCEPT_PATH_H
 		#define LEMON_CONCEPT_PATH_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief A skeleton structure for representing directed paths in
 		    /// a digraph.
 		    ///
 		    /// A skeleton structure for representing directed paths in a
 		    /// digraph.
 		    /// \tparam _Digraph The digraph type in which the path is.
 		    ///
 		    /// In a sense, the path can be treated as a list of arcs. The
 		    /// lemon path type stores just this list. As a consequence it
 		    /// cannot enumerate the nodes in the path and the zero length
 		    /// paths cannot store the source.
 		    ///
 		    template <typename _Digraph>
 		    class Path {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef _Digraph Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
 		      class ArcIt;
 		      /// \brief Default constructor
 		      Path() {}
 		      /// \brief Template constructor
 		      template <typename CPath>
 		      Path(const CPath& cpath) {}
 		      /// \brief Template assigment
 		      template <typename CPath>
 		      Path& operator=(const CPath& cpath) {
 		        ignore_unused_variable_warning(cpath);
 		        return *this;
+		      }
 		      /// Length of the path ie. the number of arcs in the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// Resets the path to an empty path.
 		      void clear() {}
 		      /// \brief LEMON style iterator for path arcs
 		      ///
 		      /// This class is used to iterate on the arcs of the paths.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
 		        /// Constructor for first arc
 		        ArcIt(const Path &) {}
 		        /// Conversion to Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          Path<Digraph> pc;
 		          _Path p, pp(pc);
 		          int l = p.length();
 		          int e = p.empty();
 		          p.clear();
 		          p = pc;
 		          typename _Path::ArcIt id, ii(INVALID), i(p);
 		          ++i;
 		          typename Digraph::Arc ed = i;
 		          e = (i == ii);
 		          e = (i != ii);
 		          e = (i < ii);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(pp);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ii);
 		          ignore_unused_variable_warning(ed);
+		        }
 		      };
 		    };
 		    namespace _path_bits {
 		      template <typename _Digraph, typename _Path, typename RevPathTag = void>
 		      struct PathDumperConstraints {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::ArcIt id, i(p);
 		          ++i;
 		          typename _Digraph::Arc ed = i;
 		          e = (i == INVALID);
 		          e = (i != INVALID);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ed);
+		        }
 		        _Path& p;
 		      };
 		      template <typename _Digraph, typename _Path>
 		      struct PathDumperConstraints<
 		        _Digraph, _Path,
 		        typename enable_if<typename _Path::RevPathTag, void>::type
 		      > {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::RevArcIt id, i(p);
 		          ++i;
 		          typename _Digraph::Arc ed = i;
 		          e = (i == INVALID);
 		          e = (i != INVALID);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ed);
+		        }
 		        _Path& p;
 		      };
+		    }
 		    /// \brief A skeleton structure for path dumpers.
 		    ///
 		    /// A skeleton structure for path dumpers. The path dumpers are
 		    /// the generalization of the paths. The path dumpers can
 		    /// enumerate the arcs of the path wheter in forward or in
 		    /// backward order.  In most time these classes are not used
 		    /// directly rather it used to assign a dumped class to a real
 		    /// path type.
 		    ///
 		    /// The main purpose of this concept is that the shortest path
 		    /// algorithms can enumerate easily the arcs in reverse order.
 		    /// If we would like to give back a real path from these
 		    /// algorithms then we should create a temporarly path object. In
 		    /// LEMON such algorithms gives back a path dumper what can
 		    /// assigned to a real path and the dumpers can be implemented as
 		    /// an adaptor class to the predecessor map.
 		    /// \tparam _Digraph  The digraph type in which the path is.
 		    ///
 		    /// The paths can be constructed from any path type by a
 		    /// template constructor or a template assignment operator.
 		    ///
 		    template <typename _Digraph>
 		    class PathDumper {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef _Digraph Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
 		      /// Length of the path ie. the number of arcs in the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// \brief Forward or reverse dumping
 		      ///
 		      /// If the RevPathTag is defined and true then reverse dumping
 		      /// is provided in the path dumper. In this case instead of the
 		      /// ArcIt the RevArcIt iterator should be implemented in the
 		      /// dumper.
 		      typedef False RevPathTag;
 		      /// \brief LEMON style iterator for path arcs
 		      ///
 		      /// This class is used to iterate on the arcs of the paths.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
 		        /// Constructor for first arc
 		        ArcIt(const PathDumper&) {}
 		        /// Conversion to Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
 		      /// \brief LEMON style iterator for path arcs
 		      ///
 		      /// This class is used to iterate on the arcs of the paths in
 		      /// reverse direction.
 		      class RevArcIt {
 		      public:
 		        /// Default constructor
 		        RevArcIt() {}
 		        /// Invalid constructor
 		        RevArcIt(Invalid) {}
 		        /// Constructor for first arc
 		        RevArcIt(const PathDumper &) {}
 		        /// Conversion to Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        RevArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const RevArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const RevArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const RevArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          function_requires<_path_bits::
 		            PathDumperConstraints<Digraph, _Path> >();
+		        }
 		      };
 		    };
 		    ///@}
+		  }
 		} // namespace lemon
 		#endif // LEMON_CONCEPT_PATH_H

lemon/core.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_CORE_H
 		#define LEMON_CORE_H
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/bits/enable_if.h>
 		#include <lemon/bits/traits.h>
 		///\file
 		///\brief LEMON core utilities.
 		///
 		///This header file contains core utilities for LEMON.
 		///It is automatically included by all graph types, therefore it usually
 		///do not have to be included directly.
 		namespace lemon {
 		  /// \brief Dummy type to make it easier to create invalid iterators.
 		  ///
 		  /// Dummy type to make it easier to create invalid iterators.
 		  /// See \ref INVALID for the usage.
 		  struct Invalid {
 		  public:
 		    bool operator==(Invalid) { return true;  }
 		    bool operator!=(Invalid) { return false; }
 		    bool operator< (Invalid) { return false; }
 		  };
 		  /// \brief Invalid iterators.
 		  ///
 		  /// \ref Invalid is a global type that converts to each iterator
 		  /// in such a way that the value of the target iterator will be invalid.
 		#ifdef LEMON_ONLY_TEMPLATES
 		  const Invalid INVALID = Invalid();
 		#else
 		  extern const Invalid INVALID;
 		#endif
 		  /// \addtogroup gutils
 		  /// @{
-		  ///Creates convenience typedefs for the digraph types and iterators
+		  ///Create convenient typedefs for the digraph types and iterators
 		  ///This \c \#define creates convenience typedefs for the following types
 		  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
 		  ///This \c \#define creates convenient type definitions for the following
 		  ///types of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
 		  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
 		  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
 		  ///
 		  ///\note If the graph type is a dependent type, ie. the graph type depend
 		  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
 		  ///macro.
 		#define DIGRAPH_TYPEDEFS(Digraph)                                       \
 		  typedef Digraph::Node Node;                                           \
 		  typedef Digraph::NodeIt NodeIt;                                       \
 		  typedef Digraph::Arc Arc;                                             \
 		  typedef Digraph::ArcIt ArcIt;                                         \
 		  typedef Digraph::InArcIt InArcIt;                                     \
 		  typedef Digraph::OutArcIt OutArcIt;                                   \
 		  typedef Digraph::NodeMap<bool> BoolNodeMap;                           \
 		  typedef Digraph::NodeMap<int> IntNodeMap;                             \
 		  typedef Digraph::NodeMap<double> DoubleNodeMap;                       \
 		  typedef Digraph::ArcMap<bool> BoolArcMap;                             \
 		  typedef Digraph::ArcMap<int> IntArcMap;                               \
 		  typedef Digraph::ArcMap<double> DoubleArcMap
+		  typedef Digraph::ArcMap<double> DoubleArcMap;
-		  ///Creates convenience typedefs for the digraph types and iterators
+		  ///Create convenient typedefs for the digraph types and iterators
 		  ///\see DIGRAPH_TYPEDEFS
 		  ///
 		  ///\note Use this macro, if the graph type is a dependent type,
 		  ///ie. the graph type depend on a template parameter.
 		#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \
 		  typedef typename Digraph::Node Node;                                  \
 		  typedef typename Digraph::NodeIt NodeIt;                              \
 		  typedef typename Digraph::Arc Arc;                                    \
 		  typedef typename Digraph::ArcIt ArcIt;                                \
 		  typedef typename Digraph::InArcIt InArcIt;                            \
 		  typedef typename Digraph::OutArcIt OutArcIt;                          \
 		  typedef typename Digraph::template NodeMap<bool> BoolNodeMap;         \
 		  typedef typename Digraph::template NodeMap<int> IntNodeMap;           \
 		  typedef typename Digraph::template NodeMap<double> DoubleNodeMap;     \
 		  typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \
 		  typedef typename Digraph::template ArcMap<int> IntArcMap;             \
 		  typedef typename Digraph::template ArcMap<double> DoubleArcMap
+		  typedef typename Digraph::template ArcMap<double> DoubleArcMap;
-		  ///Creates convenience typedefs for the graph types and iterators
+		  ///Create convenient typedefs for the graph types and iterators
-		  ///This \c \#define creates the same convenience typedefs as defined
+		  ///This \c \#define creates the same convenient type definitions as defined
 		  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
 		  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
 		  ///\c DoubleEdgeMap.
 		  ///
 		  ///\note If the graph type is a dependent type, ie. the graph type depend
-		  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
+		  ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
 		  ///macro.
 		#define GRAPH_TYPEDEFS(Graph)                                           \
 		  DIGRAPH_TYPEDEFS(Graph);                                              \
 		  typedef Graph::Edge Edge;                                             \
 		  typedef Graph::EdgeIt EdgeIt;                                         \
 		  typedef Graph::IncEdgeIt IncEdgeIt;                                   \
 		  typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \
 		  typedef Graph::EdgeMap<int> IntEdgeMap;                               \
 		  typedef Graph::EdgeMap<double> DoubleEdgeMap
+		  typedef Graph::EdgeMap<double> DoubleEdgeMap;
-		  ///Creates convenience typedefs for the graph types and iterators
+		  ///Create convenient typedefs for the graph types and iterators
 		  ///\see GRAPH_TYPEDEFS
 		  ///
 		  ///\note Use this macro, if the graph type is a dependent type,
 		  ///ie. the graph type depend on a template parameter.
 		#define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \
 		  typedef typename Graph::Edge Edge;                                    \
 		  typedef typename Graph::EdgeIt EdgeIt;                                \
 		  typedef typename Graph::IncEdgeIt IncEdgeIt;                          \
 		  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \
 		  typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \
 		  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
+		  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap;
-		  /// \brief Function to count the items in the graph.
+		  /// \brief Function to count the items in a graph.
 		  ///
 		  /// This function counts the items (nodes, arcs etc) in the graph.
 		  /// The complexity of the function is O(n) because
 		  /// This function counts the items (nodes, arcs etc.) in a graph.
 		  /// The complexity of the function is linear because
 		  /// it iterates on all of the items.
 		  template <typename Graph, typename Item>
 		  inline int countItems(const Graph& g) {
 		    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
 		    int num = 0;
 		    for (ItemIt it(g); it != INVALID; ++it) {
 		      ++num;
+		    }
 		    return num;
+		  }
 		  // Node counting:
 		  namespace _core_bits {
 		    template <typename Graph, typename Enable = void>
 		    struct CountNodesSelector {
 		      static int count(const Graph &g) {
 		        return countItems<Graph, typename Graph::Node>(g);
+		      }
 		    };
 		    template <typename Graph>
 		    struct CountNodesSelector<
 		      Graph, typename
 		      enable_if<typename Graph::NodeNumTag, void>::type>
+		    {
 		      static int count(const Graph &g) {
 		        return g.nodeNum();
+		      }
 		    };
+		  }
 		  /// \brief Function to count the nodes in the graph.
 		  ///
 		  /// This function counts the nodes in the graph.
 		  /// The complexity of the function is O(n) but for some
 		  /// graph structures it is specialized to run in O(1).
 		  /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
 		  /// graph structures it is specialized to run in <em>O</em>(1).
 		  ///
 		  /// If the graph contains a \e nodeNum() member function and a
 		  /// \e NodeNumTag tag then this function calls directly the member
 		  /// \note If the graph contains a \c nodeNum() member function and a
 		  /// \c NodeNumTag tag then this function calls directly the member
 		  /// function to query the cardinality of the node set.
 		  template <typename Graph>
 		  inline int countNodes(const Graph& g) {
 		    return _core_bits::CountNodesSelector<Graph>::count(g);
+		  }
 		  // Arc counting:
 		  namespace _core_bits {
 		    template <typename Graph, typename Enable = void>
 		    struct CountArcsSelector {
 		      static int count(const Graph &g) {
 		        return countItems<Graph, typename Graph::Arc>(g);
+		      }
 		    };
 		    template <typename Graph>
 		    struct CountArcsSelector<
 		      Graph,
 		      typename enable_if<typename Graph::ArcNumTag, void>::type>
+		    {
 		      static int count(const Graph &g) {
 		        return g.arcNum();
+		      }
 		    };
+		  }
 		  /// \brief Function to count the arcs in the graph.
 		  ///
 		  /// This function counts the arcs in the graph.
 		  /// The complexity of the function is O(e) but for some
 		  /// graph structures it is specialized to run in O(1).
 		  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
 		  /// graph structures it is specialized to run in <em>O</em>(1).
 		  ///
 		  /// If the graph contains a \e arcNum() member function and a
 		  /// \e EdgeNumTag tag then this function calls directly the member
 		  /// \note If the graph contains a \c arcNum() member function and a
 		  /// \c ArcNumTag tag then this function calls directly the member
 		  /// function to query the cardinality of the arc set.
 		  template <typename Graph>
 		  inline int countArcs(const Graph& g) {
 		    return _core_bits::CountArcsSelector<Graph>::count(g);
+		  }
 		  // Edge counting:
 		  namespace _core_bits {
 		    template <typename Graph, typename Enable = void>
 		    struct CountEdgesSelector {
 		      static int count(const Graph &g) {
 		        return countItems<Graph, typename Graph::Edge>(g);
+		      }
 		    };
 		    template <typename Graph>
 		    struct CountEdgesSelector<
 		      Graph,
 		      typename enable_if<typename Graph::EdgeNumTag, void>::type>
+		    {
 		      static int count(const Graph &g) {
 		        return g.edgeNum();
+		      }
 		    };
+		  }
 		  /// \brief Function to count the edges in the graph.
 		  ///
 		  /// This function counts the edges in the graph.
 		  /// The complexity of the function is O(m) but for some
 		  /// graph structures it is specialized to run in O(1).
 		  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
 		  /// graph structures it is specialized to run in <em>O</em>(1).
 		  ///
 		  /// If the graph contains a \e edgeNum() member function and a
 		  /// \e EdgeNumTag tag then this function calls directly the member
 		  /// \note If the graph contains a \c edgeNum() member function and a
 		  /// \c EdgeNumTag tag then this function calls directly the member
 		  /// function to query the cardinality of the edge set.
 		  template <typename Graph>
 		  inline int countEdges(const Graph& g) {
 		    return _core_bits::CountEdgesSelector<Graph>::count(g);
+		  }
 		  template <typename Graph, typename DegIt>
 		  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
 		    int num = 0;
 		    for (DegIt it(_g, _n); it != INVALID; ++it) {
 		      ++num;
+		    }
 		    return num;
+		  }
 		  /// \brief Function to count the number of the out-arcs from node \c n.
 		  ///
 		  /// This function counts the number of the out-arcs from node \c n
 		  /// in the graph.
+		  /// in the graph \c g.
 		  template <typename Graph>
 		  inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) {
 		    return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
 		  inline int countOutArcs(const Graph& g,  const typename Graph::Node& n) {
 		    return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
+		  }
 		  /// \brief Function to count the number of the in-arcs to node \c n.
 		  ///
 		  /// This function counts the number of the in-arcs to node \c n
 		  /// in the graph.
+		  /// in the graph \c g.
 		  template <typename Graph>
 		  inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) {
 		    return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
 		  inline int countInArcs(const Graph& g,  const typename Graph::Node& n) {
 		    return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
+		  }
 		  /// \brief Function to count the number of the inc-edges to node \c n.
 		  ///
 		  /// This function counts the number of the inc-edges to node \c n
 		  /// in the graph.
+		  /// in the undirected graph \c g.
 		  template <typename Graph>
 		  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
 		    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
 		  inline int countIncEdges(const Graph& g,  const typename Graph::Node& n) {
 		    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
+		  }
 		  namespace _core_bits {
 		    template <typename Digraph, typename Item, typename RefMap>
 		    class MapCopyBase {
 		    public:
 		      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
 		      virtual ~MapCopyBase() {}
 		    };
 		    template <typename Digraph, typename Item, typename RefMap,
-		              typename ToMap, typename FromMap>
+		              typename FromMap, typename ToMap>
 		    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
 		    public:
 		      MapCopy(ToMap& tmap, const FromMap& map)
 		        : _tmap(tmap), _map(map) {}
 		      MapCopy(const FromMap& map, ToMap& tmap)
 		        : _map(map), _tmap(tmap) {}
 		      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
 		        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
 		        for (ItemIt it(digraph); it != INVALID; ++it) {
 		          _tmap.set(refMap[it], _map[it]);
+		        }
+		      }
 		    private:
 		      const FromMap& _map;
 		      ToMap& _tmap;
 		      const FromMap& _map;
 		    };
 		    template <typename Digraph, typename Item, typename RefMap, typename It>
 		    class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
 		    public:
-		      ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
+		      ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
 		      virtual void copy(const Digraph&, const RefMap& refMap) {
 		        _it = refMap[_item];
+		      }
 		    private:
 		      Item _item;
 		      It& _it;
 		      Item _item;
 		    };
 		    template <typename Digraph, typename Item, typename RefMap, typename Ref>
 		    class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
 		    public:
 		      RefCopy(Ref& map) : _map(map) {}
 		      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
 		        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
 		        for (ItemIt it(digraph); it != INVALID; ++it) {
 		          _map.set(it, refMap[it]);
+		        }
+		      }
 		    private:
 		      Ref& _map;
 		    };
 		    template <typename Digraph, typename Item, typename RefMap,
 		              typename CrossRef>
 		    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
 		    public:
 		      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
 		      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
 		        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
 		        for (ItemIt it(digraph); it != INVALID; ++it) {
 		          _cmap.set(refMap[it], it);
+		        }
+		      }
 		    private:
 		      CrossRef& _cmap;
 		    };
 		    template <typename Digraph, typename Enable = void>
 		    struct DigraphCopySelector {
 		      template <typename From, typename NodeRefMap, typename ArcRefMap>
-		      static void copy(Digraph &to, const From& from,
+		      static void copy(const From& from, Digraph &to,
 		                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
 		        for (typename From::NodeIt it(from); it != INVALID; ++it) {
 		          nodeRefMap[it] = to.addNode();
+		        }
 		        for (typename From::ArcIt it(from); it != INVALID; ++it) {
 		          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
 		                                    nodeRefMap[from.target(it)]);
+		        }
+		      }
 		    };
 		    template <typename Digraph>
 		    struct DigraphCopySelector<
 		      Digraph,
 		      typename enable_if<typename Digraph::BuildTag, void>::type>
+		    {
 		      template <typename From, typename NodeRefMap, typename ArcRefMap>
-		      static void copy(Digraph &to, const From& from,
+		      static void copy(const From& from, Digraph &to,
 		                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
 		        to.build(from, nodeRefMap, arcRefMap);
+		      }
 		    };
 		    template <typename Graph, typename Enable = void>
 		    struct GraphCopySelector {
 		      template <typename From, typename NodeRefMap, typename EdgeRefMap>
-		      static void copy(Graph &to, const From& from,
+		      static void copy(const From& from, Graph &to,
 		                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
 		        for (typename From::NodeIt it(from); it != INVALID; ++it) {
 		          nodeRefMap[it] = to.addNode();
+		        }
 		        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
 		          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
 		                                      nodeRefMap[from.v(it)]);
+		        }
+		      }
 		    };
 		    template <typename Graph>
 		    struct GraphCopySelector<
 		      Graph,
 		      typename enable_if<typename Graph::BuildTag, void>::type>
+		    {
 		      template <typename From, typename NodeRefMap, typename EdgeRefMap>
-		      static void copy(Graph &to, const From& from,
+		      static void copy(const From& from, Graph &to,
 		                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
 		        to.build(from, nodeRefMap, edgeRefMap);
+		      }
 		    };
+		  }
 		  /// \brief Class to copy a digraph.
 		  ///
 		  /// Class to copy a digraph to another digraph (duplicate a digraph). The
-		  /// simplest way of using it is through the \c copyDigraph() function.
+		  /// simplest way of using it is through the \c digraphCopy() function.
 		  ///
-		  /// This class not just make a copy of a graph, but it can create
+		  /// This class not only make a copy of a digraph, but it can create
 		  /// references and cross references between the nodes and arcs of
 		  /// the two graphs, it can copy maps for use with the newly created
 		  /// graph and copy nodes and arcs.
 		  /// the two digraphs, and it can copy maps to use with the newly created
 		  /// digraph.
 		  ///
 		  /// To make a copy from a graph, first an instance of DigraphCopy
 		  /// should be created, then the data belongs to the graph should
 		  /// To make a copy from a digraph, first an instance of DigraphCopy
 		  /// should be created, then the data belongs to the digraph should
 		  /// assigned to copy. In the end, the \c run() member should be
 		  /// called.
 		  ///
-		  /// The next code copies a graph with several data:
+		  /// The next code copies a digraph with several data:
 		  ///\code
 		  ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
 		  ///  // create a reference for the nodes
 		  ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
 		  ///  // Create references for the nodes
 		  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
 		  ///  dc.nodeRef(nr);
 		  ///  // create a cross reference (inverse) for the arcs
 		  ///  cg.nodeRef(nr);
 		  ///  // Create cross references (inverse) for the arcs
 		  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
 		  ///  dc.arcCrossRef(acr);
 		  ///  // copy an arc map
 		  ///  cg.arcCrossRef(acr);
 		  ///  // Copy an arc map
 		  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
 		  ///  NewGraph::ArcMap<double> namap(new_graph);
 		  ///  dc.arcMap(namap, oamap);
 		  ///  // copy a node
 		  ///  cg.arcMap(oamap, namap);
 		  ///  // Copy a node
 		  ///  OrigGraph::Node on;
 		  ///  NewGraph::Node nn;
 		  ///  dc.node(nn, on);
 		  ///  // Executions of copy
-		  ///  dc.run();
+		  ///  cg.node(on, nn);
 		  ///  // Execute copying
 		  ///  cg.run();
 		  ///\endcode
-		  template <typename To, typename From>
+		  template <typename From, typename To>
 		  class DigraphCopy {
 		  private:
 		    typedef typename From::Node Node;
 		    typedef typename From::NodeIt NodeIt;
 		    typedef typename From::Arc Arc;
 		    typedef typename From::ArcIt ArcIt;
 		    typedef typename To::Node TNode;
 		    typedef typename To::Arc TArc;
 		    typedef typename From::template NodeMap<TNode> NodeRefMap;
 		    typedef typename From::template ArcMap<TArc> ArcRefMap;
 		  public:
 		    /// \brief Constructor for the DigraphCopy.
 		    /// \brief Constructor of DigraphCopy.
 		    ///
 		    /// It copies the content of the \c _from digraph into the
 		    /// \c _to digraph.
-		    DigraphCopy(To& to, const From& from)
+		    /// Constructor of DigraphCopy for copying the content of the
 		    /// \c from digraph into the \c to digraph.
 		    DigraphCopy(const From& from, To& to)
 		      : _from(from), _to(to) {}
-		    /// \brief Destructor of the DigraphCopy
 		    /// \brief Destructor of DigraphCopy
 		    ///
-		    /// Destructor of the DigraphCopy
+		    /// Destructor of DigraphCopy.
 		    ~DigraphCopy() {
 		      for (int i = 0; i < int(_node_maps.size()); ++i) {
 		        delete _node_maps[i];
+		      }
 		      for (int i = 0; i < int(_arc_maps.size()); ++i) {
 		        delete _arc_maps[i];
+		      }
+		    }
-		    /// \brief Copies the node references into the given map.
+		    /// \brief Copy the node references into the given map.
 		    ///
 		    /// Copies the node references into the given map. The parameter
 		    /// should be a map, which key type is the Node type of the source
 		    /// graph, while the value type is the Node type of the
 		    /// destination graph.
 		    /// This function copies the node references into the given map.
 		    /// The parameter should be a map, whose key type is the Node type of
 		    /// the source digraph, while the value type is the Node type of the
 		    /// destination digraph.
 		    template <typename NodeRef>
 		    DigraphCopy& nodeRef(NodeRef& map) {
 		      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
 		                           NodeRefMap, NodeRef>(map));
 		      return *this;
+		    }
-		    /// \brief Copies the node cross references into the given map.
+		    /// \brief Copy the node cross references into the given map.
 		    ///
 		    ///  Copies the node cross references (reverse references) into
 		    ///  the given map. The parameter should be a map, which key type
 		    ///  is the Node type of the destination graph, while the value type is
 		    ///  the Node type of the source graph.
 		    /// This function copies the node cross references (reverse references)
 		    /// into the given map. The parameter should be a map, whose key type
 		    /// is the Node type of the destination digraph, while the value type is
 		    /// the Node type of the source digraph.
 		    template <typename NodeCrossRef>
 		    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
 		      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
 		                           NodeRefMap, NodeCrossRef>(map));
 		      return *this;
+		    }
 		    /// \brief Make copy of the given map.
+		    /// \brief Make a copy of the given node map.
 		    ///
 		    /// Makes copy of the given map for the newly created digraph.
 		    /// The new map's key type is the destination graph's node type,
 		    /// and the copied map's key type is the source graph's node type.
 		    template <typename ToMap, typename FromMap>
-		    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
+		    /// This function makes a copy of the given node map for the newly
 		    /// created digraph.
 		    /// The key type of the new map \c tmap should be the Node type of the
 		    /// destination digraph, and the key type of the original map \c map
 		    /// should be the Node type of the source digraph.
 		    template <typename FromMap, typename ToMap>
 		    DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
 		      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
-		                           NodeRefMap, ToMap, FromMap>(tmap, map));
+		                           NodeRefMap, FromMap, ToMap>(map, tmap));
 		      return *this;
+		    }
 		    /// \brief Make a copy of the given node.
 		    ///
 		    /// Make a copy of the given node.
 		    DigraphCopy& node(TNode& tnode, const Node& snode) {
 		    /// This function makes a copy of the given node.
 		    DigraphCopy& node(const Node& node, TNode& tnode) {
 		      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
-		                           NodeRefMap, TNode>(tnode, snode));
+		                           NodeRefMap, TNode>(node, tnode));
 		      return *this;
+		    }
-		    /// \brief Copies the arc references into the given map.
+		    /// \brief Copy the arc references into the given map.
 		    ///
-		    /// Copies the arc references into the given map.
+		    /// This function copies the arc references into the given map.
 		    /// The parameter should be a map, whose key type is the Arc type of
 		    /// the source digraph, while the value type is the Arc type of the
 		    /// destination digraph.
 		    template <typename ArcRef>
 		    DigraphCopy& arcRef(ArcRef& map) {
 		      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
 		                          ArcRefMap, ArcRef>(map));
 		      return *this;
+		    }
-		    /// \brief Copies the arc cross references into the given map.
+		    /// \brief Copy the arc cross references into the given map.
 		    ///
 		    ///  Copies the arc cross references (reverse references) into
 		    ///  the given map.
 		    /// This function copies the arc cross references (reverse references)
 		    /// into the given map. The parameter should be a map, whose key type
 		    /// is the Arc type of the destination digraph, while the value type is
 		    /// the Arc type of the source digraph.
 		    template <typename ArcCrossRef>
 		    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
 		      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
 		                          ArcRefMap, ArcCrossRef>(map));
 		      return *this;
+		    }
 		    /// \brief Make copy of the given map.
+		    /// \brief Make a copy of the given arc map.
 		    ///
 		    /// Makes copy of the given map for the newly created digraph.
 		    /// The new map's key type is the to digraph's arc type,
 		    /// and the copied map's key type is the from digraph's arc
 		    /// type.
 		    template <typename ToMap, typename FromMap>
 		    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
 		    /// This function makes a copy of the given arc map for the newly
 		    /// created digraph.
 		    /// The key type of the new map \c tmap should be the Arc type of the
 		    /// destination digraph, and the key type of the original map \c map
 		    /// should be the Arc type of the source digraph.
 		    template <typename FromMap, typename ToMap>
 		    DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
 		      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
-		                          ArcRefMap, ToMap, FromMap>(tmap, map));
+		                          ArcRefMap, FromMap, ToMap>(map, tmap));
 		      return *this;
+		    }
 		    /// \brief Make a copy of the given arc.
 		    ///
 		    /// Make a copy of the given arc.
 		    DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
 		    /// This function makes a copy of the given arc.
 		    DigraphCopy& arc(const Arc& arc, TArc& tarc) {
 		      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
-		                          ArcRefMap, TArc>(tarc, sarc));
+		                          ArcRefMap, TArc>(arc, tarc));
 		      return *this;
+		    }
-		    /// \brief Executes the copies.
+		    /// \brief Execute copying.
 		    ///
-		    /// Executes the copies.
+		    /// This function executes the copying of the digraph along with the
 		    /// copying of the assigned data.
 		    void run() {
 		      NodeRefMap nodeRefMap(_from);
 		      ArcRefMap arcRefMap(_from);
 		      _core_bits::DigraphCopySelector<To>::
-		        copy(_to, _from, nodeRefMap, arcRefMap);
+		        copy(_from, _to, nodeRefMap, arcRefMap);
 		      for (int i = 0; i < int(_node_maps.size()); ++i) {
 		        _node_maps[i]->copy(_from, nodeRefMap);
+		      }
 		      for (int i = 0; i < int(_arc_maps.size()); ++i) {
 		        _arc_maps[i]->copy(_from, arcRefMap);
+		      }
+		    }
 		  protected:
 		    const From& _from;
 		    To& _to;
 		    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
 		    _node_maps;
+		      _node_maps;
 		    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
 		    _arc_maps;
+		      _arc_maps;
 		  };
 		  /// \brief Copy a digraph to another digraph.
 		  ///
 		  /// Copy a digraph to another digraph. The complete usage of the
 		  /// function is detailed in the DigraphCopy class, but a short
-		  /// example shows a basic work:
+		  /// This function copies a digraph to another digraph.
 		  /// The complete usage of it is detailed in the DigraphCopy class, but
 		  /// a short example shows a basic work:
 		  ///\code
-		  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
+		  /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
 		  ///\endcode
 		  ///
 		  /// After the copy the \c nr map will contain the mapping from the
 		  /// nodes of the \c from digraph to the nodes of the \c to digraph and
-		  /// \c ecr will contain the mapping from the arcs of the \c to digraph
+		  /// \c acr will contain the mapping from the arcs of the \c to digraph
 		  /// to the arcs of the \c from digraph.
 		  ///
 		  /// \see DigraphCopy
 		  template <typename To, typename From>
 		  DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
-		    return DigraphCopy<To, From>(to, from);
+		  template <typename From, typename To>
 		  DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
 		    return DigraphCopy<From, To>(from, to);
+		  }
 		  /// \brief Class to copy a graph.
 		  ///
 		  /// Class to copy a graph to another graph (duplicate a graph). The
-		  /// simplest way of using it is through the \c copyGraph() function.
+		  /// simplest way of using it is through the \c graphCopy() function.
 		  ///
-		  /// This class not just make a copy of a graph, but it can create
+		  /// This class not only make a copy of a graph, but it can create
 		  /// references and cross references between the nodes, edges and arcs of
 		  /// the two graphs, it can copy maps for use with the newly created
 		  /// graph and copy nodes, edges and arcs.
 		  /// the two graphs, and it can copy maps for using with the newly created
 		  /// graph.
 		  ///
 		  /// To make a copy from a graph, first an instance of GraphCopy
 		  /// should be created, then the data belongs to the graph should
 		  /// assigned to copy. In the end, the \c run() member should be
 		  /// called.
 		  ///
 		  /// The next code copies a graph with several data:
 		  ///\code
 		  ///  GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
 		  ///  // create a reference for the nodes
 		  ///  GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
 		  ///  // Create references for the nodes
 		  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
 		  ///  dc.nodeRef(nr);
 		  ///  // create a cross reference (inverse) for the edges
 		  ///  NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
 		  ///  dc.edgeCrossRef(ecr);
 		  ///  // copy an arc map
 		  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
 		  ///  NewGraph::ArcMap<double> namap(new_graph);
 		  ///  dc.arcMap(namap, oamap);
-		  ///  // copy a node
+		  ///  cg.nodeRef(nr);
 		  ///  // Create cross references (inverse) for the edges
 		  ///  NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
 		  ///  cg.edgeCrossRef(ecr);
 		  ///  // Copy an edge map
 		  ///  OrigGraph::EdgeMap<double> oemap(orig_graph);
 		  ///  NewGraph::EdgeMap<double> nemap(new_graph);
 		  ///  cg.edgeMap(oemap, nemap);
 		  ///  // Copy a node
 		  ///  OrigGraph::Node on;
 		  ///  NewGraph::Node nn;
 		  ///  dc.node(nn, on);
 		  ///  // Executions of copy
-		  ///  dc.run();
+		  ///  cg.node(on, nn);
 		  ///  // Execute copying
 		  ///  cg.run();
 		  ///\endcode
-		  template <typename To, typename From>
+		  template <typename From, typename To>
 		  class GraphCopy {
 		  private:
 		    typedef typename From::Node Node;
 		    typedef typename From::NodeIt NodeIt;
 		    typedef typename From::Arc Arc;
 		    typedef typename From::ArcIt ArcIt;
 		    typedef typename From::Edge Edge;
 		    typedef typename From::EdgeIt EdgeIt;
 		    typedef typename To::Node TNode;
 		    typedef typename To::Arc TArc;
 		    typedef typename To::Edge TEdge;
 		    typedef typename From::template NodeMap<TNode> NodeRefMap;
 		    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
 		    struct ArcRefMap {
-		      ArcRefMap(const To& to, const From& from,
+		      ArcRefMap(const From& from, const To& to,
 		                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
-		        : _to(to), _from(from),
+		        : _from(from), _to(to),
 		          _edge_ref(edge_ref), _node_ref(node_ref) {}
 		      typedef typename From::Arc Key;
 		      typedef typename To::Arc Value;
 		      Value operator[](const Key& key) const {
 		        bool forward = _from.u(key) != _from.v(key) ?
 		          _node_ref[_from.source(key)] ==
 		          _to.source(_to.direct(_edge_ref[key], true)) :
 		          _from.direction(key);
 		        return _to.direct(_edge_ref[key], forward);
+		      }
 		      const From& _from;
 		      const To& _to;
 		      const From& _from;
 		      const EdgeRefMap& _edge_ref;
 		      const NodeRefMap& _node_ref;
 		    };
 		  public:
 		    /// \brief Constructor for the GraphCopy.
 		    /// \brief Constructor of GraphCopy.
 		    ///
 		    /// It copies the content of the \c _from graph into the
 		    /// \c _to graph.
-		    GraphCopy(To& to, const From& from)
+		    /// Constructor of GraphCopy for copying the content of the
 		    /// \c from graph into the \c to graph.
 		    GraphCopy(const From& from, To& to)
 		      : _from(from), _to(to) {}
-		    /// \brief Destructor of the GraphCopy
 		    /// \brief Destructor of GraphCopy
 		    ///
-		    /// Destructor of the GraphCopy
+		    /// Destructor of GraphCopy.
 		    ~GraphCopy() {
 		      for (int i = 0; i < int(_node_maps.size()); ++i) {
 		        delete _node_maps[i];
+		      }
 		      for (int i = 0; i < int(_arc_maps.size()); ++i) {
 		        delete _arc_maps[i];
+		      }
 		      for (int i = 0; i < int(_edge_maps.size()); ++i) {
 		        delete _edge_maps[i];
+		      }
+		    }
-		    /// \brief Copies the node references into the given map.
+		    /// \brief Copy the node references into the given map.
 		    ///
-		    /// Copies the node references into the given map.
+		    /// This function copies the node references into the given map.
 		    /// The parameter should be a map, whose key type is the Node type of
 		    /// the source graph, while the value type is the Node type of the
 		    /// destination graph.
 		    template <typename NodeRef>
 		    GraphCopy& nodeRef(NodeRef& map) {
 		      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
 		                           NodeRefMap, NodeRef>(map));
 		      return *this;
+		    }
-		    /// \brief Copies the node cross references into the given map.
+		    /// \brief Copy the node cross references into the given map.
 		    ///
 		    ///  Copies the node cross references (reverse references) into
 		    ///  the given map.
 		    /// This function copies the node cross references (reverse references)
 		    /// into the given map. The parameter should be a map, whose key type
 		    /// is the Node type of the destination graph, while the value type is
 		    /// the Node type of the source graph.
 		    template <typename NodeCrossRef>
 		    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
 		      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
 		                           NodeRefMap, NodeCrossRef>(map));
 		      return *this;
+		    }
 		    /// \brief Make copy of the given map.
+		    /// \brief Make a copy of the given node map.
 		    ///
 		    /// Makes copy of the given map for the newly created graph.
 		    /// The new map's key type is the to graph's node type,
 		    /// and the copied map's key type is the from graph's node
 		    /// type.
 		    template <typename ToMap, typename FromMap>
 		    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
 		    /// This function makes a copy of the given node map for the newly
 		    /// created graph.
 		    /// The key type of the new map \c tmap should be the Node type of the
 		    /// destination graph, and the key type of the original map \c map
 		    /// should be the Node type of the source graph.
 		    template <typename FromMap, typename ToMap>
 		    GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
 		      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
-		                           NodeRefMap, ToMap, FromMap>(tmap, map));
+		                           NodeRefMap, FromMap, ToMap>(map, tmap));
 		      return *this;
+		    }
 		    /// \brief Make a copy of the given node.
 		    ///
 		    /// Make a copy of the given node.
 		    GraphCopy& node(TNode& tnode, const Node& snode) {
 		    /// This function makes a copy of the given node.
 		    GraphCopy& node(const Node& node, TNode& tnode) {
 		      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
-		                           NodeRefMap, TNode>(tnode, snode));
+		                           NodeRefMap, TNode>(node, tnode));
 		      return *this;
+		    }
-		    /// \brief Copies the arc references into the given map.
+		    /// \brief Copy the arc references into the given map.
 		    ///
-		    /// Copies the arc references into the given map.
+		    /// This function copies the arc references into the given map.
 		    /// The parameter should be a map, whose key type is the Arc type of
 		    /// the source graph, while the value type is the Arc type of the
 		    /// destination graph.
 		    template <typename ArcRef>
 		    GraphCopy& arcRef(ArcRef& map) {
 		      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
 		                          ArcRefMap, ArcRef>(map));
 		      return *this;
+		    }
-		    /// \brief Copies the arc cross references into the given map.
+		    /// \brief Copy the arc cross references into the given map.
 		    ///
 		    ///  Copies the arc cross references (reverse references) into
 		    ///  the given map.
 		    /// This function copies the arc cross references (reverse references)
 		    /// into the given map. The parameter should be a map, whose key type
 		    /// is the Arc type of the destination graph, while the value type is
 		    /// the Arc type of the source graph.
 		    template <typename ArcCrossRef>
 		    GraphCopy& arcCrossRef(ArcCrossRef& map) {
 		      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
 		                          ArcRefMap, ArcCrossRef>(map));
 		      return *this;
+		    }
 		    /// \brief Make copy of the given map.
+		    /// \brief Make a copy of the given arc map.
 		    ///
 		    /// Makes copy of the given map for the newly created graph.
 		    /// The new map's key type is the to graph's arc type,
 		    /// and the copied map's key type is the from graph's arc
 		    /// type.
 		    template <typename ToMap, typename FromMap>
 		    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
 		    /// This function makes a copy of the given arc map for the newly
 		    /// created graph.
 		    /// The key type of the new map \c tmap should be the Arc type of the
 		    /// destination graph, and the key type of the original map \c map
 		    /// should be the Arc type of the source graph.
 		    template <typename FromMap, typename ToMap>
 		    GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
 		      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
-		                          ArcRefMap, ToMap, FromMap>(tmap, map));
+		                          ArcRefMap, FromMap, ToMap>(map, tmap));
 		      return *this;
+		    }
 		    /// \brief Make a copy of the given arc.
 		    ///
 		    /// Make a copy of the given arc.
 		    GraphCopy& arc(TArc& tarc, const Arc& sarc) {
 		    /// This function makes a copy of the given arc.
 		    GraphCopy& arc(const Arc& arc, TArc& tarc) {
 		      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
-		                          ArcRefMap, TArc>(tarc, sarc));
+		                          ArcRefMap, TArc>(arc, tarc));
 		      return *this;
+		    }
-		    /// \brief Copies the edge references into the given map.
+		    /// \brief Copy the edge references into the given map.
 		    ///
-		    /// Copies the edge references into the given map.
+		    /// This function copies the edge references into the given map.
 		    /// The parameter should be a map, whose key type is the Edge type of
 		    /// the source graph, while the value type is the Edge type of the
 		    /// destination graph.
 		    template <typename EdgeRef>
 		    GraphCopy& edgeRef(EdgeRef& map) {
 		      _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
 		                           EdgeRefMap, EdgeRef>(map));
 		      return *this;
+		    }
-		    /// \brief Copies the edge cross references into the given map.
+		    /// \brief Copy the edge cross references into the given map.
 		    ///
 		    /// Copies the edge cross references (reverse
 		    /// references) into the given map.
 		    /// This function copies the edge cross references (reverse references)
 		    /// into the given map. The parameter should be a map, whose key type
 		    /// is the Edge type of the destination graph, while the value type is
 		    /// the Edge type of the source graph.
 		    template <typename EdgeCrossRef>
 		    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
 		      _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
 		                           Edge, EdgeRefMap, EdgeCrossRef>(map));
 		      return *this;
+		    }
 		    /// \brief Make copy of the given map.
+		    /// \brief Make a copy of the given edge map.
 		    ///
 		    /// Makes copy of the given map for the newly created graph.
 		    /// The new map's key type is the to graph's edge type,
 		    /// and the copied map's key type is the from graph's edge
 		    /// type.
 		    template <typename ToMap, typename FromMap>
 		    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
 		    /// This function makes a copy of the given edge map for the newly
 		    /// created graph.
 		    /// The key type of the new map \c tmap should be the Edge type of the
 		    /// destination graph, and the key type of the original map \c map
 		    /// should be the Edge type of the source graph.
 		    template <typename FromMap, typename ToMap>
 		    GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
 		      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
-		                           EdgeRefMap, ToMap, FromMap>(tmap, map));
+		                           EdgeRefMap, FromMap, ToMap>(map, tmap));
 		      return *this;
+		    }
 		    /// \brief Make a copy of the given edge.
 		    ///
 		    /// Make a copy of the given edge.
 		    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
 		    /// This function makes a copy of the given edge.
 		    GraphCopy& edge(const Edge& edge, TEdge& tedge) {
 		      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
-		                           EdgeRefMap, TEdge>(tedge, sedge));
+		                           EdgeRefMap, TEdge>(edge, tedge));
 		      return *this;
+		    }
-		    /// \brief Executes the copies.
+		    /// \brief Execute copying.
 		    ///
-		    /// Executes the copies.
+		    /// This function executes the copying of the graph along with the
 		    /// copying of the assigned data.
 		    void run() {
 		      NodeRefMap nodeRefMap(_from);
 		      EdgeRefMap edgeRefMap(_from);
-		      ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
+		      ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
 		      _core_bits::GraphCopySelector<To>::
-		        copy(_to, _from, nodeRefMap, edgeRefMap);
+		        copy(_from, _to, nodeRefMap, edgeRefMap);
 		      for (int i = 0; i < int(_node_maps.size()); ++i) {
 		        _node_maps[i]->copy(_from, nodeRefMap);
+		      }
 		      for (int i = 0; i < int(_edge_maps.size()); ++i) {
 		        _edge_maps[i]->copy(_from, edgeRefMap);
+		      }
 		      for (int i = 0; i < int(_arc_maps.size()); ++i) {
 		        _arc_maps[i]->copy(_from, arcRefMap);
+		      }
+		    }
 		  private:
 		    const From& _from;
 		    To& _to;
 		    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
 		    _node_maps;
+		      _node_maps;
 		    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
 		    _arc_maps;
+		      _arc_maps;
 		    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
 		    _edge_maps;
+		      _edge_maps;
 		  };
 		  /// \brief Copy a graph to another graph.
 		  ///
 		  /// Copy a graph to another graph. The complete usage of the
 		  /// function is detailed in the GraphCopy class, but a short
-		  /// example shows a basic work:
+		  /// This function copies a graph to another graph.
 		  /// The complete usage of it is detailed in the GraphCopy class,
 		  /// but a short example shows a basic work:
 		  ///\code
-		  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
+		  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
 		  ///\endcode
 		  ///
 		  /// After the copy the \c nr map will contain the mapping from the
 		  /// nodes of the \c from graph to the nodes of the \c to graph and
 		  /// \c ecr will contain the mapping from the arcs of the \c to graph
 		  /// to the arcs of the \c from graph.
 		  /// \c ecr will contain the mapping from the edges of the \c to graph
 		  /// to the edges of the \c from graph.
 		  ///
 		  /// \see GraphCopy
 		  template <typename To, typename From>
 		  GraphCopy<To, From>
 		  copyGraph(To& to, const From& from) {
 		    return GraphCopy<To, From>(to, from);
 		  template <typename From, typename To>
 		  GraphCopy<From, To>
 		  graphCopy(const From& from, To& to) {
 		    return GraphCopy<From, To>(from, to);
+		  }
 		  namespace _core_bits {
 		    template <typename Graph, typename Enable = void>
 		    struct FindArcSelector {
 		      typedef typename Graph::Node Node;
 		      typedef typename Graph::Arc Arc;
 		      static Arc find(const Graph &g, Node u, Node v, Arc e) {
 		        if (e == INVALID) {
 		          g.firstOut(e, u);
 		        } else {
 		          g.nextOut(e);
+		        }
 		        while (e != INVALID && g.target(e) != v) {
 		          g.nextOut(e);
+		        }
 		        return e;
+		      }
 		    };
 		    template <typename Graph>
 		    struct FindArcSelector<
 		      Graph,
-		      typename enable_if<typename Graph::FindEdgeTag, void>::type>
+		      typename enable_if<typename Graph::FindArcTag, void>::type>
+		    {
 		      typedef typename Graph::Node Node;
 		      typedef typename Graph::Arc Arc;
 		      static Arc find(const Graph &g, Node u, Node v, Arc prev) {
 		        return g.findArc(u, v, prev);
+		      }
 		    };
+		  }
-		  /// \brief Finds an arc between two nodes of a graph.
+		  /// \brief Find an arc between two nodes of a digraph.
 		  ///
-		  /// Finds an arc from node \c u to node \c v in graph \c g.
+		  /// This function finds an arc from node \c u to node \c v in the
 		  /// digraph \c g.
 		  ///
 		  /// If \c prev is \ref INVALID (this is the default value), then
 		  /// it finds the first arc from \c u to \c v. Otherwise it looks for
 		  /// the next arc from \c u to \c v after \c prev.
 		  /// \return The found arc or \ref INVALID if there is no such an arc.
 		  ///
 		  /// Thus you can iterate through each arc from \c u to \c v as it follows.
 		  ///\code
 		  /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
+		  /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
 		  ///   ...
 		  /// }
 		  ///\endcode
 		  ///
 		  ///\sa ArcLookUp
 		  ///\sa AllArcLookUp
-		  ///\sa DynArcLookUp
+		  /// \note \ref ConArcIt provides iterator interface for the same
 		  /// functionality.
 		  ///
 		  ///\sa ConArcIt
 		  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
 		  template <typename Graph>
 		  inline typename Graph::Arc
 		  findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
 		          typename Graph::Arc prev = INVALID) {
 		    return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
+		  }
-		  /// \brief Iterator for iterating on arcs connected the same nodes.
+		  /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
 		  ///
 		  /// Iterator for iterating on arcs connected the same nodes. It is
 		  /// higher level interface for the findArc() function. You can
 		  /// Iterator for iterating on parallel arcs connecting the same nodes. It is
 		  /// a higher level interface for the \ref findArc() function. You can
 		  /// use it the following way:
 		  ///\code
 		  /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
 		  ///   ...
 		  /// }
 		  ///\endcode
 		  ///
 		  ///\sa findArc()
 		  ///\sa ArcLookUp
 		  ///\sa AllArcLookUp
 		  ///\sa DynArcLookUp
+		  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
 		  template <typename _Graph>
 		  class ConArcIt : public _Graph::Arc {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Arc Parent;
 		    typedef typename Graph::Arc Arc;
 		    typedef typename Graph::Node Node;
 		    /// \brief Constructor.
 		    ///
 		    /// Construct a new ConArcIt iterating on the arcs which
 		    /// connects the \c u and \c v node.
 		    /// Construct a new ConArcIt iterating on the arcs that
 		    /// connects nodes \c u and \c v.
 		    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
 		      Parent::operator=(findArc(_graph, u, v));
+		    }
 		    /// \brief Constructor.
 		    ///
 		    /// Construct a new ConArcIt which continues the iterating from
 		    /// the \c e arc.
 		    /// Construct a new ConArcIt that continues the iterating from arc \c a.
 		    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
 		    /// \brief Increment operator.
 		    ///
 		    /// It increments the iterator and gives back the next arc.
 		    ConArcIt& operator++() {
 		      Parent::operator=(findArc(_graph, _graph.source(*this),
 		                                _graph.target(*this), *this));
 		      return *this;
+		    }
 		  private:
 		    const Graph& _graph;
 		  };
 		  namespace _core_bits {
 		    template <typename Graph, typename Enable = void>
 		    struct FindEdgeSelector {
 		      typedef typename Graph::Node Node;
 		      typedef typename Graph::Edge Edge;
 		      static Edge find(const Graph &g, Node u, Node v, Edge e) {
 		        bool b;
 		        if (u != v) {
 		          if (e == INVALID) {
 		            g.firstInc(e, b, u);
 		          } else {
 		            b = g.u(e) == u;
 		            g.nextInc(e, b);
+		          }
 		          while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
 		            g.nextInc(e, b);
+		          }
 		        } else {
 		          if (e == INVALID) {
 		            g.firstInc(e, b, u);
 		          } else {
 		            b = true;
 		            g.nextInc(e, b);
+		          }
 		          while (e != INVALID && (!b || g.v(e) != v)) {
 		            g.nextInc(e, b);
+		          }
+		        }
 		        return e;
+		      }
 		    };
 		    template <typename Graph>
 		    struct FindEdgeSelector<
 		      Graph,
 		      typename enable_if<typename Graph::FindEdgeTag, void>::type>
+		    {
 		      typedef typename Graph::Node Node;
 		      typedef typename Graph::Edge Edge;
 		      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
 		        return g.findEdge(u, v, prev);
+		      }
 		    };
+		  }
-		  /// \brief Finds an edge between two nodes of a graph.
+		  /// \brief Find an edge between two nodes of a graph.
 		  ///
 		  /// Finds an edge from node \c u to node \c v in graph \c g.
 		  /// If the node \c u and node \c v is equal then each loop edge
 		  /// This function finds an edge from node \c u to node \c v in graph \c g.
 		  /// If node \c u and node \c v is equal then each loop edge
 		  /// will be enumerated once.
 		  ///
 		  /// If \c prev is \ref INVALID (this is the default value), then
 		  /// it finds the first arc from \c u to \c v. Otherwise it looks for
 		  /// the next arc from \c u to \c v after \c prev.
-		  /// \return The found arc or \ref INVALID if there is no such an arc.
+		  /// it finds the first edge from \c u to \c v. Otherwise it looks for
 		  /// the next edge from \c u to \c v after \c prev.
 		  /// \return The found edge or \ref INVALID if there is no such an edge.
 		  ///
-		  /// Thus you can iterate through each arc from \c u to \c v as it follows.
+		  /// Thus you can iterate through each edge between \c u and \c v
 		  /// as it follows.
 		  ///\code
 		  /// for(Edge e = findEdge(g,u,v); e != INVALID;
 		  ///     e = findEdge(g,u,v,e)) {
 		  /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
 		  ///   ...
 		  /// }
 		  ///\endcode
 		  ///
 		  /// \note \ref ConEdgeIt provides iterator interface for the same
 		  /// functionality.
 		  ///
 		  ///\sa ConEdgeIt
 		  template <typename Graph>
 		  inline typename Graph::Edge
 		  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
 		            typename Graph::Edge p = INVALID) {
 		    return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
+		  }
-		  /// \brief Iterator for iterating on edges connected the same nodes.
+		  /// \brief Iterator for iterating on parallel edges connecting the same nodes.
 		  ///
 		  /// Iterator for iterating on edges connected the same nodes. It is
 		  /// higher level interface for the findEdge() function. You can
 		  /// Iterator for iterating on parallel edges connecting the same nodes.
 		  /// It is a higher level interface for the findEdge() function. You can
 		  /// use it the following way:
 		  ///\code
-		  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
+		  /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
 		  ///   ...
 		  /// }
 		  ///\endcode
 		  ///
 		  ///\sa findEdge()
 		  template <typename _Graph>
 		  class ConEdgeIt : public _Graph::Edge {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Edge Parent;
 		    typedef typename Graph::Edge Edge;
 		    typedef typename Graph::Node Node;
 		    /// \brief Constructor.
 		    ///
 		    /// Construct a new ConEdgeIt iterating on the edges which
 		    /// connects the \c u and \c v node.
 		    /// Construct a new ConEdgeIt iterating on the edges that
 		    /// connects nodes \c u and \c v.
 		    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
 		      Parent::operator=(findEdge(_graph, u, v));
+		    }
 		    /// \brief Constructor.
 		    ///
 		    /// Construct a new ConEdgeIt which continues the iterating from
 		    /// the \c e edge.
 		    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
 		    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
 		    /// \brief Increment operator.
 		    ///
 		    /// It increments the iterator and gives back the next edge.
 		    ConEdgeIt& operator++() {
 		      Parent::operator=(findEdge(_graph, _graph.u(*this),
 		                                 _graph.v(*this), *this));
 		      return *this;
+		    }
 		  private:
 		    const Graph& _graph;
 		  };
-		  ///Dynamic arc look up between given endpoints.
+		  ///Dynamic arc look-up between given endpoints.
 		  ///Using this class, you can find an arc in a digraph from a given
-		  ///source to a given target in amortized time <em>O(log</em>d<em>)</em>,
+		  ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
 		  ///where <em>d</em> is the out-degree of the source node.
 		  ///
 		  ///It is possible to find \e all parallel arcs between two nodes with
 		  ///the \c operator() member.
 		  ///
 		  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
 		  ///digraph is not changed so frequently.
 		  ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
 		  ///\ref AllArcLookUp if your digraph is not changed so frequently.
 		  ///
 		  ///This class uses a self-adjusting binary search tree, Sleator's
 		  ///and Tarjan's Splay tree for guarantee the logarithmic amortized
-		  ///time bound for arc lookups. This class also guarantees the
+		  ///This class uses a self-adjusting binary search tree, the Splay tree
 		  ///of Sleator and Tarjan to guarantee the logarithmic amortized
 		  ///time bound for arc look-ups. This class also guarantees the
 		  ///optimal time bound in a constant factor for any distribution of
 		  ///queries.
 		  ///
 		  ///\tparam G The type of the underlying digraph.
 		  ///
 		  ///\sa ArcLookUp
 		  ///\sa AllArcLookUp
 		  template<class G>
 		  class DynArcLookUp
 		    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
+		  {
 		  public:
 		    typedef typename ItemSetTraits<G, typename G::Arc>
 		    ::ItemNotifier::ObserverBase Parent;
 		    TEMPLATE_DIGRAPH_TYPEDEFS(G);
 		    typedef G Digraph;
 		  protected:
 		    class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
 		    public:
 		      typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
 		      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
 		      virtual void add(const Node& node) {
 		        Parent::add(node);
 		        Parent::set(node, INVALID);
+		      }
 		      virtual void add(const std::vector<Node>& nodes) {
 		        Parent::add(nodes);
 		        for (int i = 0; i < int(nodes.size()); ++i) {
 		          Parent::set(nodes[i], INVALID);
+		        }
+		      }
 		      virtual void build() {
 		        Parent::build();
 		        Node it;
 		        typename Parent::Notifier* nf = Parent::notifier();
 		        for (nf->first(it); it != INVALID; nf->next(it)) {
 		          Parent::set(it, INVALID);
+		        }
+		      }
 		    };
 		    const Digraph &_g;
 		    AutoNodeMap _head;
 		    typename Digraph::template ArcMap<Arc> _parent;
 		    typename Digraph::template ArcMap<Arc> _left;
 		    typename Digraph::template ArcMap<Arc> _right;
 		    class ArcLess {
 		      const Digraph &g;
 		    public:
 		      ArcLess(const Digraph &_g) : g(_g) {}
 		      bool operator()(Arc a,Arc b) const
+		      {
 		        return g.target(a)<g.target(b);
+		      }
 		    };
 		  public:
 		    ///Constructor
 		    ///Constructor.
 		    ///
 		    ///It builds up the search database.
 		    DynArcLookUp(const Digraph &g)
 		      : _g(g),_head(g),_parent(g),_left(g),_right(g)
+		    {
 		      Parent::attach(_g.notifier(typename Digraph::Arc()));
 		      refresh();
+		    }
 		  protected:
 		    virtual void add(const Arc& arc) {
 		      insert(arc);
+		    }
 		    virtual void add(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        insert(arcs[i]);
+		      }
+		    }
 		    virtual void erase(const Arc& arc) {
 		      remove(arc);
+		    }
 		    virtual void erase(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        remove(arcs[i]);
+		      }
+		    }
 		    virtual void build() {
 		      refresh();
+		    }
 		    virtual void clear() {
 		      for(NodeIt n(_g);n!=INVALID;++n) {
 		        _head.set(n, INVALID);
+		      }
+		    }
 		    void insert(Arc arc) {
 		      Node s = _g.source(arc);
 		      Node t = _g.target(arc);
 		      _left.set(arc, INVALID);
 		      _right.set(arc, INVALID);
 		      Arc e = _head[s];
 		      if (e == INVALID) {
 		        _head.set(s, arc);
 		        _parent.set(arc, INVALID);
 		        return;
+		      }
 		      while (true) {
 		        if (t < _g.target(e)) {
 		          if (_left[e] == INVALID) {
 		            _left.set(e, arc);
 		            _parent.set(arc, e);
 		            splay(arc);
 		            return;
 		          } else {
 		            e = _left[e];
+		          }
 		        } else {
 		          if (_right[e] == INVALID) {
 		            _right.set(e, arc);
 		            _parent.set(arc, e);
 		            splay(arc);
 		            return;
 		          } else {
 		            e = _right[e];
+		          }
+		        }
+		      }
+		    }
 		    void remove(Arc arc) {
 		      if (_left[arc] == INVALID) {
 		        if (_right[arc] != INVALID) {
 		          _parent.set(_right[arc], _parent[arc]);
+		        }
 		        if (_parent[arc] != INVALID) {
 		          if (_left[_parent[arc]] == arc) {
 		            _left.set(_parent[arc], _right[arc]);
 		          } else {
 		            _right.set(_parent[arc], _right[arc]);
+		          }
 		        } else {
 		          _head.set(_g.source(arc), _right[arc]);
+		        }
 		      } else if (_right[arc] == INVALID) {
 		        _parent.set(_left[arc], _parent[arc]);
 		        if (_parent[arc] != INVALID) {
 		          if (_left[_parent[arc]] == arc) {
 		            _left.set(_parent[arc], _left[arc]);
 		          } else {
 		            _right.set(_parent[arc], _left[arc]);
+		          }
 		        } else {
 		          _head.set(_g.source(arc), _left[arc]);
+		        }
 		      } else {
 		        Arc e = _left[arc];
 		        if (_right[e] != INVALID) {
 		          e = _right[e];
 		          while (_right[e] != INVALID) {
 		            e = _right[e];
+		          }
 		          Arc s = _parent[e];
 		          _right.set(_parent[e], _left[e]);
 		          if (_left[e] != INVALID) {
 		            _parent.set(_left[e], _parent[e]);
+		          }
 		          _left.set(e, _left[arc]);
 		          _parent.set(_left[arc], e);
 		          _right.set(e, _right[arc]);
 		          _parent.set(_right[arc], e);
 		          _parent.set(e, _parent[arc]);
 		          if (_parent[arc] != INVALID) {
 		            if (_left[_parent[arc]] == arc) {
 		              _left.set(_parent[arc], e);
 		            } else {
 		              _right.set(_parent[arc], e);
+		            }
+		          }
 		          splay(s);
 		        } else {
 		          _right.set(e, _right[arc]);
 		          _parent.set(_right[arc], e);
 		          _parent.set(e, _parent[arc]);
 		          if (_parent[arc] != INVALID) {
 		            if (_left[_parent[arc]] == arc) {
 		              _left.set(_parent[arc], e);
 		            } else {
 		              _right.set(_parent[arc], e);
+		            }
 		          } else {
 		            _head.set(_g.source(arc), e);
+		          }
+		        }
+		      }
+		    }
 		    Arc refreshRec(std::vector<Arc> &v,int a,int b)
+		    {
 		      int m=(a+b)/2;
 		      Arc me=v[m];
 		      if (a < m) {
 		        Arc left = refreshRec(v,a,m-1);
 		        _left.set(me, left);
 		        _parent.set(left, me);
 		      } else {
 		        _left.set(me, INVALID);
+		      }
 		      if (m < b) {
 		        Arc right = refreshRec(v,m+1,b);
 		        _right.set(me, right);
 		        _parent.set(right, me);
 		      } else {
 		        _right.set(me, INVALID);
+		      }
 		      return me;
+		    }
 		    void refresh() {
 		      for(NodeIt n(_g);n!=INVALID;++n) {
 		        std::vector<Arc> v;
 		        for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
 		        if (!v.empty()) {
 		          std::sort(v.begin(),v.end(),ArcLess(_g));
 		          Arc head = refreshRec(v,0,v.size()-1);
 		          _head.set(n, head);
 		          _parent.set(head, INVALID);
+		        }
 		        else _head.set(n, INVALID);
+		      }
+		    }
 		    void zig(Arc v) {
 		      Arc w = _parent[v];
 		      _parent.set(v, _parent[w]);
 		      _parent.set(w, v);
 		      _left.set(w, _right[v]);
 		      _right.set(v, w);
 		      if (_parent[v] != INVALID) {
 		        if (_right[_parent[v]] == w) {
 		          _right.set(_parent[v], v);
 		        } else {
 		          _left.set(_parent[v], v);
+		        }
+		      }
 		      if (_left[w] != INVALID){
 		        _parent.set(_left[w], w);
+		      }
+		    }
 		    void zag(Arc v) {
 		      Arc w = _parent[v];
 		      _parent.set(v, _parent[w]);
 		      _parent.set(w, v);
 		      _right.set(w, _left[v]);
 		      _left.set(v, w);
 		      if (_parent[v] != INVALID){
 		        if (_left[_parent[v]] == w) {
 		          _left.set(_parent[v], v);
 		        } else {
 		          _right.set(_parent[v], v);
+		        }
+		      }
 		      if (_right[w] != INVALID){
 		        _parent.set(_right[w], w);
+		      }
+		    }
 		    void splay(Arc v) {
 		      while (_parent[v] != INVALID) {
 		        if (v == _left[_parent[v]]) {
 		          if (_parent[_parent[v]] == INVALID) {
 		            zig(v);
 		          } else {
 		            if (_parent[v] == _left[_parent[_parent[v]]]) {
 		              zig(_parent[v]);
 		              zig(v);
 		            } else {
 		              zig(v);
 		              zag(v);
+		            }
+		          }
 		        } else {
 		          if (_parent[_parent[v]] == INVALID) {
 		            zag(v);
 		          } else {
 		            if (_parent[v] == _left[_parent[_parent[v]]]) {
 		              zag(v);
 		              zig(v);
 		            } else {
 		              zag(_parent[v]);
 		              zag(v);
+		            }
+		          }
+		        }
+		      }
 		      _head[_g.source(v)] = v;
+		    }
 		  public:
 		    ///Find an arc between two nodes.
 		    ///Find an arc between two nodes.
 		    ///\param s The source node
 		    ///\param t The target node
 		    ///\param s The source node.
 		    ///\param t The target node.
 		    ///\param p The previous arc between \c s and \c t. It it is INVALID or
 		    ///not given, the operator finds the first appropriate arc.
 		    ///\return An arc from \c s to \c t after \c p or
 		    ///\ref INVALID if there is no more.
 		    ///
 		    ///For example, you can count the number of arcs from \c u to \c v in the
 		    ///following way.
 		    ///\code
 		    ///DynArcLookUp<ListDigraph> ae(g);
 		    ///...
 		    ///int n=0;
 		    ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
 		    ///int n = 0;
 		    ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
 		    ///\endcode
 		    ///
-		    ///Finding the arcs take at most <em>O(</em>log<em>d)</em>
+		    ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
 		    ///amortized time, specifically, the time complexity of the lookups
 		    ///is equal to the optimal search tree implementation for the
 		    ///current query distribution in a constant factor.
 		    ///
 		    ///\note This is a dynamic data structure, therefore the data
 		    ///structure is updated after each graph alteration. However,
 		    ///theoretically this data structure is faster than \c ArcLookUp
-		    ///or AllEdgeLookup, but it often provides worse performance than
+		    ///structure is updated after each graph alteration. Thus although
 		    ///this data structure is theoretically faster than \ref ArcLookUp
 		    ///and \ref AllArcLookup, it often provides worse performance than
 		    ///them.
 		    ///
 		    Arc operator()(Node s, Node t, Arc p = INVALID) const  {
 		      if (p == INVALID) {
 		        Arc a = _head[s];
 		        if (a == INVALID) return INVALID;
 		        Arc r = INVALID;
 		        while (true) {
 		          if (_g.target(a) < t) {
 		            if (_right[a] == INVALID) {
 		              const_cast<DynArcLookUp&>(*this).splay(a);
 		              return r;
 		            } else {
 		              a = _right[a];
+		            }
 		          } else {
 		            if (_g.target(a) == t) {
 		              r = a;
+		            }
 		            if (_left[a] == INVALID) {
 		              const_cast<DynArcLookUp&>(*this).splay(a);
 		              return r;
 		            } else {
 		              a = _left[a];
+		            }
+		          }
+		        }
 		      } else {
 		        Arc a = p;
 		        if (_right[a] != INVALID) {
 		          a = _right[a];
 		          while (_left[a] != INVALID) {
 		            a = _left[a];
+		          }
 		          const_cast<DynArcLookUp&>(*this).splay(a);
 		        } else {
 		          while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
 		            a = _parent[a];
+		          }
 		          if (_parent[a] == INVALID) {
 		            return INVALID;
 		          } else {
 		            a = _parent[a];
 		            const_cast<DynArcLookUp&>(*this).splay(a);
+		          }
+		        }
 		        if (_g.target(a) == t) return a;
 		        else return INVALID;
+		      }
+		    }
 		  };
-		  ///Fast arc look up between given endpoints.
+		  ///Fast arc look-up between given endpoints.
 		  ///Using this class, you can find an arc in a digraph from a given
-		  ///source to a given target in time <em>O(log d)</em>,
+		  ///source to a given target in time <em>O</em>(log<em>d</em>),
 		  ///where <em>d</em> is the out-degree of the source node.
 		  ///
 		  ///It is not possible to find \e all parallel arcs between two nodes.
 		  ///Use \ref AllArcLookUp for this purpose.
 		  ///
 		  ///\warning This class is static, so you should refresh() (or at least
 		  ///refresh(Node)) this data structure
 		  ///whenever the digraph changes. This is a time consuming (superlinearly
 		  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
 		  ///\warning This class is static, so you should call refresh() (or at
 		  ///least refresh(Node)) to refresh this data structure whenever the
 		  ///digraph changes. This is a time consuming (superlinearly proportional
 		  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
 		  ///
 		  ///\tparam G The type of the underlying digraph.
 		  ///
 		  ///\sa DynArcLookUp
 		  ///\sa AllArcLookUp
 		  template<class G>
 		  class ArcLookUp
+		  {
 		  public:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(G);
 		    typedef G Digraph;
 		  protected:
 		    const Digraph &_g;
 		    typename Digraph::template NodeMap<Arc> _head;
 		    typename Digraph::template ArcMap<Arc> _left;
 		    typename Digraph::template ArcMap<Arc> _right;
 		    class ArcLess {
 		      const Digraph &g;
 		    public:
 		      ArcLess(const Digraph &_g) : g(_g) {}
 		      bool operator()(Arc a,Arc b) const
+		      {
 		        return g.target(a)<g.target(b);
+		      }
 		    };
 		  public:
 		    ///Constructor
 		    ///Constructor.
 		    ///
 		    ///It builds up the search database, which remains valid until the digraph
 		    ///changes.
 		    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
 		  private:
 		    Arc refreshRec(std::vector<Arc> &v,int a,int b)
+		    {
 		      int m=(a+b)/2;
 		      Arc me=v[m];
 		      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
 		      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
 		      return me;
+		    }
 		  public:
 		    ///Refresh the data structure at a node.
+		    ///Refresh the search data structure at a node.
 		    ///Build up the search database of node \c n.
 		    ///
 		    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
 		    ///the number of the outgoing arcs of \c n.
 		    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
 		    ///is the number of the outgoing arcs of \c n.
 		    void refresh(Node n)
+		    {
 		      std::vector<Arc> v;
 		      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
 		      if(v.size()) {
 		        std::sort(v.begin(),v.end(),ArcLess(_g));
 		        _head[n]=refreshRec(v,0,v.size()-1);
+		      }
 		      else _head[n]=INVALID;
+		    }
 		    ///Refresh the full data structure.
 		    ///Build up the full search database. In fact, it simply calls
 		    ///\ref refresh(Node) "refresh(n)" for each node \c n.
 		    ///
 		    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
 		    ///the number of the arcs of \c n and <em>D</em> is the maximum
 		    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
 		    ///the number of the arcs in the digraph and <em>D</em> is the maximum
 		    ///out-degree of the digraph.
 		    void refresh()
+		    {
 		      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
+		    }
 		    ///Find an arc between two nodes.
 		    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
 		    /// <em>d</em> is the number of outgoing arcs of \c s.
 		    ///\param s The source node
 		    ///\param t The target node
 		    ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>), where
 		    ///<em>d</em> is the number of outgoing arcs of \c s.
 		    ///\param s The source node.
 		    ///\param t The target node.
 		    ///\return An arc from \c s to \c t if there exists,
 		    ///\ref INVALID otherwise.
 		    ///
 		    ///\warning If you change the digraph, refresh() must be called before using
 		    ///this operator. If you change the outgoing arcs of
 		    ///a single node \c n, then
 		    ///\ref refresh(Node) "refresh(n)" is enough.
 		    ///
+		    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
 		    Arc operator()(Node s, Node t) const
+		    {
 		      Arc e;
 		      for(e=_head[s];
 		          e!=INVALID&&_g.target(e)!=t;
 		          e = t < _g.target(e)?_left[e]:_right[e]) ;
 		      return e;
+		    }
 		  };
-		  ///Fast look up of all arcs between given endpoints.
+		  ///Fast look-up of all arcs between given endpoints.
 		  ///This class is the same as \ref ArcLookUp, with the addition
-		  ///that it makes it possible to find all arcs between given endpoints.
+		  ///that it makes it possible to find all parallel arcs between given
 		  ///endpoints.
 		  ///
 		  ///\warning This class is static, so you should refresh() (or at least
 		  ///refresh(Node)) this data structure
 		  ///whenever the digraph changes. This is a time consuming (superlinearly
 		  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
 		  ///\warning This class is static, so you should call refresh() (or at
 		  ///least refresh(Node)) to refresh this data structure whenever the
 		  ///digraph changes. This is a time consuming (superlinearly proportional
 		  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
 		  ///
 		  ///\tparam G The type of the underlying digraph.
 		  ///
 		  ///\sa DynArcLookUp
 		  ///\sa ArcLookUp
 		  template<class G>
 		  class AllArcLookUp : public ArcLookUp<G>
+		  {
 		    using ArcLookUp<G>::_g;
 		    using ArcLookUp<G>::_right;
 		    using ArcLookUp<G>::_left;
 		    using ArcLookUp<G>::_head;
 		    TEMPLATE_DIGRAPH_TYPEDEFS(G);
 		    typedef G Digraph;
 		    typename Digraph::template ArcMap<Arc> _next;
 		    Arc refreshNext(Arc head,Arc next=INVALID)
+		    {
 		      if(head==INVALID) return next;
 		      else {
 		        next=refreshNext(_right[head],next);
 		//         _next[head]=next;
 		        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
 		          ? next : INVALID;
 		        return refreshNext(_left[head],head);
+		      }
+		    }
 		    void refreshNext()
+		    {
 		      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
+		    }
 		  public:
 		    ///Constructor
 		    ///Constructor.
 		    ///
 		    ///It builds up the search database, which remains valid until the digraph
 		    ///changes.
 		    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
 		    ///Refresh the data structure at a node.
 		    ///Build up the search database of node \c n.
 		    ///
-		    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
+		    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
 		    ///the number of the outgoing arcs of \c n.
 		    void refresh(Node n)
+		    {
 		      ArcLookUp<G>::refresh(n);
 		      refreshNext(_head[n]);
+		    }
 		    ///Refresh the full data structure.
 		    ///Build up the full search database. In fact, it simply calls
 		    ///\ref refresh(Node) "refresh(n)" for each node \c n.
 		    ///
 		    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
 		    ///the number of the arcs of \c n and <em>D</em> is the maximum
 		    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
 		    ///the number of the arcs in the digraph and <em>D</em> is the maximum
 		    ///out-degree of the digraph.
 		    void refresh()
+		    {
 		      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
+		    }
 		    ///Find an arc between two nodes.
 		    ///Find an arc between two nodes.
 		    ///\param s The source node
 		    ///\param t The target node
 		    ///\param s The source node.
 		    ///\param t The target node.
 		    ///\param prev The previous arc between \c s and \c t. It it is INVALID or
 		    ///not given, the operator finds the first appropriate arc.
 		    ///\return An arc from \c s to \c t after \c prev or
 		    ///\ref INVALID if there is no more.
 		    ///
 		    ///For example, you can count the number of arcs from \c u to \c v in the
 		    ///following way.
 		    ///\code
 		    ///AllArcLookUp<ListDigraph> ae(g);
 		    ///...
 		    ///int n=0;
 		    ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
 		    ///int n = 0;
 		    ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
 		    ///\endcode
 		    ///
 		    ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
 		    /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
 		    ///Finding the first arc take <em>O</em>(log<em>d</em>) time, where
 		    ///<em>d</em> is the number of outgoing arcs of \c s. Then, the
 		    ///consecutive arcs are found in constant time.
 		    ///
 		    ///\warning If you change the digraph, refresh() must be called before using
 		    ///this operator. If you change the outgoing arcs of
 		    ///a single node \c n, then
 		    ///\ref refresh(Node) "refresh(n)" is enough.
 		    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
 		    ///
 		#ifdef DOXYGEN
 		    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
 		#else
 		    using ArcLookUp<G>::operator() ;
 		    Arc operator()(Node s, Node t, Arc prev) const
+		    {
 		      return prev==INVALID?(*this)(s,t):_next[prev];
+		    }
 		#endif
 		  };
 		  /// @}
 		} //namespace lemon
 		#endif

lemon/dfs.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_DFS_H
 		#define LEMON_DFS_H
 		///\ingroup search
 		///\file
 		///\brief DFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/assert.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///Default traits class of Dfs class.
 		  ///Default traits class of Dfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsDefaultTraits
+		  {
 		    ///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).
 		    //Creates the maps if necessary.
 		    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 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 SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 		      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    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 SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    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 SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    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 SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    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.
 		    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
 		    ///is empty.
 		    OutArcIt 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; }
 		    ///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; }
 		    ///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();
+		    }
 		    ///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 t.
 		    ///
 		    ///The algorithm computes
 		    ///- the %DFS path to \c t,
 		    ///- the distance of \c t 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 t)
+		    {
 		      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
 		        processNextArc();
+		    }
 		    ///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
 		    ///until an arc \c a with <tt>am[a]</tt> true is found.
 		    ///
 		    ///\param am A \c bool (or convertible) arc map. The algorithm
 		    ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
 		    ///
 		    ///\return The reached arc \c a with <tt>am[a]</tt> true or
 		    ///\c INVALID if no such arc was found.
 		    ///
 		    ///\pre init() must be called and a root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
 		    ///not a node map.
 		    template<class ArcBoolMap>
 		    Arc start(const ArcBoolMap &am)
+		    {
 		      while ( !emptyQueue() && !am[_stack[_stack_head]] )
 		        processNextArc();
 		      return emptyQueue() ? INVALID : _stack[_stack_head];
+		    }
 		    ///Runs the algorithm from the given source node.
 		    ///This method runs the %DFS algorithm from node \c s
 		    ///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.
 		    ///
 		    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///Finds the %DFS path between \c s and \c t.
 		    ///This method runs the %DFS algorithm from node \c s
 		    ///in order to compute the DFS path to node \c t
 		    ///(it stops searching when \c t is processed)
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    ///
 		    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
 		    ///just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    ///Runs the algorithm to visit all nodes in the digraph.
 		    ///This method runs the %DFS algorithm 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.
 		    ///
 		    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  for (NodeIt n(digraph); n != INVALID; ++n) {
 		    ///    if (!d.reached(n)) {
 		    ///      d.addSource(n);
 		    ///      d.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt it(*G); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The result of the %DFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
 		    ///"start()" must be called before using them.
 		    ///@{
 		    ///The DFS path to a node.
 		    ///Returns the DFS path to a node.
 		    ///
 		    ///\warning \c t should be reachable from the root.
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///The distance of a node from the root.
 		    ///Returns the distance of a node from the root.
 		    ///
 		    ///\warning If node \c v is not reachable from the root, then
 		    ///the return value of this function is undefined.
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the %DFS tree for a node.
 		    ///This function returns the 'previous arc' of the %DFS tree for the
 		    ///node \c v, i.e. it returns the last arc of a %DFS path from the
 		    ///root to \c v. It is \c INVALID
 		    ///if \c v is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predNode().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before using
 		    ///this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///Returns the 'previous node' of the %DFS tree.
 		    ///This function returns the 'previous node' of the %DFS
 		    ///tree for the node \c v, i.e. it returns the last but one node
 		    ///from a %DFS path from the root to \c v. It is \c INVALID
 		    ///if \c v is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predArc().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->source((*_pred)[v]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the
 		    ///distances of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the DFS tree.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if a node is reachable from the root(s).
 		    ///Returns \c true if \c v is reachable from the root(s).
 		    ///\pre Either \ref run() or \ref start()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of dfs() function.
 		  ///Default traits class of dfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsWizardDefaultTraits
+		  {
 		    ///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);
+		    }
 		    ///The type of the DFS paths.
 		    ///The type of the DFS paths.
 		    ///It must meet the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// 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 DFS path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    int *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to \c 0.
 		    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires one parameter,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    DfsWizardBase(const GR &g) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of DFS algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
 		  /// It does not have own \ref run() method, it uses the functions
 		  /// and features of the plain \ref Dfs.
 		  ///
 		  /// This class should only be used through the \ref dfs() function,
 		  /// which makes it easier to use the algorithm.
 		  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 DFS 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;
 		    ///The type of the DFS paths
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    DfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param g The digraph the algorithm runs on.
 		    DfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
 		    DfsWizard(const TR &b) : TR(b) {}
 		    ~DfsWizard() {}
 		    ///Runs DFS algorithm from the given source node.
 		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS path to each node.
 		    void run(Node s)
+		    {
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if (s!=INVALID)
 		        alg.run(s);
 		      else
 		        alg.run();
+		    }
 		    ///Finds the DFS path between \c s and \c t.
 		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)
+		    {
 		      if (s==INVALID || t==INVALID) throw UninitializedParameter();
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      alg.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
 		      if (Base::_di)
 		        *Base::_di = alg.dist(t);
 		      return alg.reached(t);
+		      }
 		    ///Runs DFS algorithm to visit all nodes in the digraph.
 		    ///This method runs DFS algorithm in order to compute
 		    ///the DFS path to each node.
 		    void run()
+		    {
 		      run(INVALID);
+		    }
 		    template<class T>
 		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    template<class T>
 		    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref ReachedMap object.
 		    template<class T>
 		    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref DistMap object.
 		    template<class T>
 		    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetDistMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    template<class T>
 		    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetPathBase : public Base {
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the DFS path to the target node.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the DFS path to the target node.
 		    template<class T>
 		    DfsWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetPathBase<T> >(*this);
+		    }
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the distance of the target node.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the distance of the target node.
 		    DfsWizard dist(const int &d)
+		    {
 		      Base::_di=const_cast<int*>(&d);
 		      return *this;
+		    }
 		  };
 		  ///Function-type interface for DFS algorithm.
 		  ///\ingroup search
 		  ///Function-type interface for DFS algorithm.
 		  ///
 		  ///This function also has several \ref named-func-param "named parameters",
 		  ///they are declared as the members of class \ref DfsWizard.
 		  ///The following examples show how to use these parameters.
 		  ///\code
 		  ///  // Compute the DFS tree
 		  ///  dfs(g).predMap(preds).distMap(dists).run(s);
 		  ///
 		  ///  // Compute the DFS path from s to t
 		  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
 		  ///\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 &digraph)
+		  {
 		    return DfsWizard<DfsWizardBase<GR> >(digraph);
+		  }
 		#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).
 		    //Creates the maps if necessary.
 		    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 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 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 t.
 		    ///
 		    /// The algorithm computes
 		    /// - the %DFS path to \c t,
 		    /// - the distance of \c t 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 t) {
 		      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
 		        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
 		    /// until an arc \c a with <tt>am[a]</tt> true is found.
 		    ///
 		    /// \param am A \c bool (or convertible) arc map. The algorithm
 		    /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
 		    ///
 		    /// \return The reached arc \c a with <tt>am[a]</tt> true or
 		    /// \c INVALID if no such arc was found.
 		    ///
 		    /// \pre init() must be called and a root node should be added
 		    /// with addSource() before using this function.
 		    ///
 		    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
 		    /// not a node map.
 		    template <typename AM>
 		    Arc start(const AM &am) {
 		      while ( !emptyQueue() && !am[_stack[_stack_head]] )
 		        processNextArc();
 		      return emptyQueue() ? INVALID : _stack[_stack_head];
+		    }
 		    /// \brief Runs the algorithm from the given source node.
 		    ///
 		    /// This method runs the %DFS algorithm from node \c s.
 		    /// 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.
 		    ///
 		    /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///   d.init();
 		    ///   d.addSource(s);
 		    ///   d.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    /// \brief Finds the %DFS path between \c s and \c t.
 		    /// This method runs the %DFS algorithm from node \c s
 		    /// in order to compute the DFS path to node \c t
 		    /// (it stops searching when \c t is processed).
 		    ///
 		    /// \return \c true if \c t is reachable form \c s.
 		    ///
 		    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
 		    /// just a shortcut of the following code.
 		    ///\code
 		    ///   d.init();
 		    ///   d.addSource(s);
 		    ///   d.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    /// \brief Runs the algorithm to visit all nodes in the digraph.
 		    /// This method runs the %DFS algorithm 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.
 		    ///
 		    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///   d.init();
 		    ///   for (NodeIt n(digraph); n != INVALID; ++n) {
 		    ///     if (!d.reached(n)) {
 		    ///       d.addSource(n);
 		    ///       d.start();
 		    ///     }
 		    ///   }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt it(*_digraph); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    /// \name Query Functions
 		    /// The result of the %DFS algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either \ref lemon::DfsVisit::run() "run()" or
 		    /// \ref lemon::DfsVisit::start() "start()" must be called before
 		    /// using them.
 		    ///@{
 		    /// \brief Checks if a node is reachable from the root(s).
 		    ///
 		    /// Returns \c true if \c v is reachable from the root(s).
 		    /// \pre Either \ref run() or \ref start()
 		    /// must be called before using this function.
 		    bool reached(Node v) { return (*_reached)[v]; }
 		    ///@}
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif

Changeset was too big and was cut off... Show full diff

0 comments (0 inline)

RhodeCode

Login to your account

Changeset was too big and was cut off... Show full diff

Changeset was too big and was cut off... Show full diff

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#ifndef LEMON_BITS_BASE_EXTENDER_H
20	20	#define LEMON_BITS_BASE_EXTENDER_H
21	21
22	22	#include <lemon/core.h>
23	23	#include <lemon/error.h>
24	24
25	25	#include <lemon/bits/map_extender.h>
26	26	#include <lemon/bits/default_map.h>
27	27
28	28	#include <lemon/concept_check.h>
29	29	#include <lemon/concepts/maps.h>
30	30
31	31	///\ingroup digraphbits
32	32	///\file
33	33	///\brief Extenders for the digraph types
34	34	namespace lemon {
35	35
36	36	/// \ingroup digraphbits
37	37	///
38	38	/// \brief BaseDigraph to BaseGraph extender
39	39	template <typename Base>
40	40	class UndirDigraphExtender : public Base {
41	41
42	42	public:
43	43
44	44	typedef Base Parent;
45	45	typedef typename Parent::Arc Edge;
46	46	typedef typename Parent::Node Node;
47	47
48	48	typedef True UndirectedTag;
49	49
50	50	class Arc : public Edge {
51	51	friend class UndirDigraphExtender;
52	52
53	53	protected:
54	54	bool forward;
55	55
56	56	Arc(const Edge &ue, bool _forward) :
57	57	Edge(ue), forward(_forward) {}
58	58
59	59	public:
60	60	Arc() {}
61	61
62	62	// Invalid arc constructor
63	63	Arc(Invalid i) : Edge(i), forward(true) {}
64	64
65	65	bool operator==(const Arc &that) const {
66	66	return forward==that.forward && Edge(*this)==Edge(that);
67	67	}
68	68	bool operator!=(const Arc &that) const {
69	69	return forward!=that.forward \|\| Edge(*this)!=Edge(that);
70	70	}
71	71	bool operator<(const Arc &that) const {
72	72	return forward<that.forward \|\|
73	73	(!(that.forward<forward) && Edge(*this)<Edge(that));
74	74	}
75	75	};
76	76
77	77	/// First node of the edge
78	78	Node u(const Edge &e) const {
79	79	return Parent::source(e);
80	80	}
81	81
82	82	/// Source of the given arc
83	83	Node source(const Arc &e) const {
84	84	return e.forward ? Parent::source(e) : Parent::target(e);
85	85	}
86	86
87	87	/// Second node of the edge
88	88	Node v(const Edge &e) const {
89	89	return Parent::target(e);
90	90	}
91	91
92	92	/// Target of the given arc
93	93	Node target(const Arc &e) const {
94	94	return e.forward ? Parent::target(e) : Parent::source(e);
95	95	}
96	96
97	97	/// \brief Directed arc from an edge.
98	98	///
99	99	/// Returns a directed arc corresponding to the specified edge.
100	100	/// If the given bool is true, the first node of the given edge and
101	101	/// the source node of the returned arc are the same.
102	102	static Arc direct(const Edge &e, bool d) {
103	103	return Arc(e, d);
104	104	}
105	105
106	106	/// Returns whether the given directed arc has the same orientation
107	107	/// as the corresponding edge.
108		///
109		/// \todo reference to the corresponding point of the undirected digraph
110		/// concept. "What does the direction of an edge mean?"
111	108	static bool direction(const Arc &a) { return a.forward; }
112	109
113	110	using Parent::first;
114	111	using Parent::next;
115	112
116	113	void first(Arc &e) const {
117	114	Parent::first(e);
118	115	e.forward=true;
119	116	}
120	117
121	118	void next(Arc &e) const {
122	119	if( e.forward ) {
123	120	e.forward = false;
124	121	}
125	122	else {
126	123	Parent::next(e);
127	124	e.forward = true;
128	125	}
129	126	}
130	127
131	128	void firstOut(Arc &e, const Node &n) const {
132	129	Parent::firstIn(e,n);
133	130	if( Edge(e) != INVALID ) {
134	131	e.forward = false;
135	132	}
136	133	else {
137	134	Parent::firstOut(e,n);
138	135	e.forward = true;
139	136	}
140	137	}
141	138	void nextOut(Arc &e) const {
142	139	if( ! e.forward ) {
143	140	Node n = Parent::target(e);
144	141	Parent::nextIn(e);
145	142	if( Edge(e) == INVALID ) {
146	143	Parent::firstOut(e, n);
147	144	e.forward = true;
148	145	}
149	146	}
150	147	else {
151	148	Parent::nextOut(e);
152	149	}
153	150	}
154	151
155	152	void firstIn(Arc &e, const Node &n) const {
156	153	Parent::firstOut(e,n);
157	154	if( Edge(e) != INVALID ) {
158	155	e.forward = false;
159	156	}
160	157	else {
161	158	Parent::firstIn(e,n);
162	159	e.forward = true;
163	160	}
164	161	}
165	162	void nextIn(Arc &e) const {
166	163	if( ! e.forward ) {
167	164	Node n = Parent::source(e);
168	165	Parent::nextOut(e);
169	166	if( Edge(e) == INVALID ) {
170	167	Parent::firstIn(e, n);
171	168	e.forward = true;
172	169	}
173	170	}
174	171	else {
175	172	Parent::nextIn(e);
176	173	}
177	174	}
178	175
179	176	void firstInc(Edge &e, bool &d, const Node &n) const {
180	177	d = true;
181	178	Parent::firstOut(e, n);
182	179	if (e != INVALID) return;
183	180	d = false;
184	181	Parent::firstIn(e, n);
185	182	}
186	183
187	184	void nextInc(Edge &e, bool &d) const {
188	185	if (d) {
189	186	Node s = Parent::source(e);
190	187	Parent::nextOut(e);
191	188	if (e != INVALID) return;
192	189	d = false;
193	190	Parent::firstIn(e, s);
194	191	} else {
195	192	Parent::nextIn(e);
196	193	}
197	194	}
198	195
199	196	Node nodeFromId(int ix) const {
200	197	return Parent::nodeFromId(ix);
201	198	}
202	199
203	200	Arc arcFromId(int ix) const {
204	201	return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
205	202	}
206	203
207	204	Edge edgeFromId(int ix) const {
208	205	return Parent::arcFromId(ix);
209	206	}
210	207
211	208	int id(const Node &n) const {
212	209	return Parent::id(n);
213	210	}
214	211
215	212	int id(const Edge &e) const {
216	213	return Parent::id(e);
217	214	}
218	215
219	216	int id(const Arc &e) const {
220	217	return 2 * Parent::id(e) + int(e.forward);
221	218	}
222	219
223	220	int maxNodeId() const {
224	221	return Parent::maxNodeId();
225	222	}
226	223
227	224	int maxArcId() const {
228	225	return 2 * Parent::maxArcId() + 1;
229	226	}
230	227
231	228	int maxEdgeId() const {
232	229	return Parent::maxArcId();
233	230	}
234	231
235	232	int arcNum() const {
236	233	return 2 * Parent::arcNum();
237	234	}
238	235
239	236	int edgeNum() const {
240	237	return Parent::arcNum();
241	238	}
242	239
243	240	Arc findArc(Node s, Node t, Arc p = INVALID) const {
244	241	if (p == INVALID) {
245	242	Edge arc = Parent::findArc(s, t);
246	243	if (arc != INVALID) return direct(arc, true);
247	244	arc = Parent::findArc(t, s);
248	245	if (arc != INVALID) return direct(arc, false);
249	246	} else if (direction(p)) {
250	247	Edge arc = Parent::findArc(s, t, p);
251	248	if (arc != INVALID) return direct(arc, true);
252	249	arc = Parent::findArc(t, s);
253	250	if (arc != INVALID) return direct(arc, false);
254	251	} else {
255	252	Edge arc = Parent::findArc(t, s, p);
256	253	if (arc != INVALID) return direct(arc, false);
257	254	}
258	255	return INVALID;
259	256	}
260	257
261	258	Edge findEdge(Node s, Node t, Edge p = INVALID) const {
262	259	if (s != t) {
263	260	if (p == INVALID) {
264	261	Edge arc = Parent::findArc(s, t);
265	262	if (arc != INVALID) return arc;
266	263	arc = Parent::findArc(t, s);
267	264	if (arc != INVALID) return arc;
268	265	} else if (Parent::s(p) == s) {
269	266	Edge arc = Parent::findArc(s, t, p);
270	267	if (arc != INVALID) return arc;
271	268	arc = Parent::findArc(t, s);
272	269	if (arc != INVALID) return arc;
273	270	} else {
274	271	Edge arc = Parent::findArc(t, s, p);
275	272	if (arc != INVALID) return arc;
276	273	}
277	274	} else {
278	275	return Parent::findArc(s, t, p);
279	276	}
280	277	return INVALID;
281	278	}
282	279	};
283	280
284	281	template <typename Base>
285	282	class BidirBpGraphExtender : public Base {
286	283	public:
287	284	typedef Base Parent;
288	285	typedef BidirBpGraphExtender Digraph;
289	286
290	287	typedef typename Parent::Node Node;
291	288	typedef typename Parent::Edge Edge;
292	289
293	290
294	291	using Parent::first;
295	292	using Parent::next;
296	293
297	294	using Parent::id;
298	295
299	296	class Red : public Node {
300	297	friend class BidirBpGraphExtender;
301	298	public:
302	299	Red() {}
303	300	Red(const Node& node) : Node(node) {
304	301	LEMON_ASSERT(Parent::red(node) \|\| node == INVALID,
305	302	typename Parent::NodeSetError());
306	303	}
307	304	Red& operator=(const Node& node) {
308	305	LEMON_ASSERT(Parent::red(node) \|\| node == INVALID,
309	306	typename Parent::NodeSetError());
310	307	Node::operator=(node);
311	308	return *this;
312	309	}
313	310	Red(Invalid) : Node(INVALID) {}
314	311	Red& operator=(Invalid) {
315	312	Node::operator=(INVALID);
316	313	return *this;
317	314	}
318	315	};
319	316
320	317	void first(Red& node) const {
321	318	Parent::firstRed(static_cast<Node&>(node));
322	319	}
323	320	void next(Red& node) const {
324	321	Parent::nextRed(static_cast<Node&>(node));
325	322	}
326	323
327	324	int id(const Red& node) const {
328	325	return Parent::redId(node);
329	326	}
330	327
331	328	class Blue : public Node {
332	329	friend class BidirBpGraphExtender;
333	330	public:
334	331	Blue() {}
335	332	Blue(const Node& node) : Node(node) {
336	333	LEMON_ASSERT(Parent::blue(node) \|\| node == INVALID,
337	334	typename Parent::NodeSetError());
338	335	}
339	336	Blue& operator=(const Node& node) {
340	337	LEMON_ASSERT(Parent::blue(node) \|\| node == INVALID,
341	338	typename Parent::NodeSetError());
342	339	Node::operator=(node);
343	340	return *this;
344	341	}
345	342	Blue(Invalid) : Node(INVALID) {}
346	343	Blue& operator=(Invalid) {
347	344	Node::operator=(INVALID);
348	345	return *this;
349	346	}
350	347	};
351	348
352	349	void first(Blue& node) const {
353	350	Parent::firstBlue(static_cast<Node&>(node));
354	351	}
355	352	void next(Blue& node) const {
356	353	Parent::nextBlue(static_cast<Node&>(node));
357	354	}
358	355
359	356	int id(const Blue& node) const {
360	357	return Parent::redId(node);
361	358	}
362	359
363	360	Node source(const Edge& arc) const {
364	361	return red(arc);
365	362	}
366	363	Node target(const Edge& arc) const {
367	364	return blue(arc);
368	365	}
369	366
370	367	void firstInc(Edge& arc, bool& dir, const Node& node) const {
371	368	if (Parent::red(node)) {
372	369	Parent::firstFromRed(arc, node);
373	370	dir = true;
374	371	} else {
375	372	Parent::firstFromBlue(arc, node);
376	373	dir = static_cast<Edge&>(arc) == INVALID;
377	374	}
378	375	}
379	376	void nextInc(Edge& arc, bool& dir) const {
380	377	if (dir) {
381	378	Parent::nextFromRed(arc);
382	379	} else {
383	380	Parent::nextFromBlue(arc);
384	381	if (arc == INVALID) dir = true;
385	382	}
386	383	}
387	384
388	385	class Arc : public Edge {
389	386	friend class BidirBpGraphExtender;
390	387	protected:
391	388	bool forward;
392	389
393	390	Arc(const Edge& arc, bool _forward)
394	391	: Edge(arc), forward(_forward) {}
395	392
396	393	public:
397	394	Arc() {}
398	395	Arc (Invalid) : Edge(INVALID), forward(true) {}
399	396	bool operator==(const Arc& i) const {
400	397	return Edge::operator==(i) && forward == i.forward;
401	398	}
402	399	bool operator!=(const Arc& i) const {
403	400	return Edge::operator!=(i) \|\| forward != i.forward;
404	401	}
405	402	bool operator<(const Arc& i) const {
406	403	return Edge::operator<(i) \|\|
407	404	(!(i.forward<forward) && Edge(*this)<Edge(i));
408	405	}
409	406	};
410	407
411	408	void first(Arc& arc) const {
412	409	Parent::first(static_cast<Edge&>(arc));
413	410	arc.forward = true;
414	411	}
415	412
416	413	void next(Arc& arc) const {
417	414	if (!arc.forward) {
418	415	Parent::next(static_cast<Edge&>(arc));
419	416	}
420	417	arc.forward = !arc.forward;
421	418	}
422	419
423	420	void firstOut(Arc& arc, const Node& node) const {
424	421	if (Parent::red(node)) {
425	422	Parent::firstFromRed(arc, node);
426	423	arc.forward = true;
427	424	} else {
428	425	Parent::firstFromBlue(arc, node);
429	426	arc.forward = static_cast<Edge&>(arc) == INVALID;
430	427	}
431	428	}
432	429	void nextOut(Arc& arc) const {
433	430	if (arc.forward) {
434	431	Parent::nextFromRed(arc);
435	432	} else {
436	433	Parent::nextFromBlue(arc);
437	434	arc.forward = static_cast<Edge&>(arc) == INVALID;
438	435	}
439	436	}
440	437
441	438	void firstIn(Arc& arc, const Node& node) const {
442	439	if (Parent::blue(node)) {
443	440	Parent::firstFromBlue(arc, node);
444	441	arc.forward = true;
445	442	} else {
446	443	Parent::firstFromRed(arc, node);
447	444	arc.forward = static_cast<Edge&>(arc) == INVALID;
448	445	}
449	446	}
450	447	void nextIn(Arc& arc) const {
451	448	if (arc.forward) {
452	449	Parent::nextFromBlue(arc);
453	450	} else {
454	451	Parent::nextFromRed(arc);
455	452	arc.forward = static_cast<Edge&>(arc) == INVALID;
456	453	}
457	454	}
458	455
459	456	Node source(const Arc& arc) const {
460	457	return arc.forward ? Parent::red(arc) : Parent::blue(arc);
461	458	}
462	459	Node target(const Arc& arc) const {
463	460	return arc.forward ? Parent::blue(arc) : Parent::red(arc);
464	461	}
465	462
466	463	int id(const Arc& arc) const {
467	464	return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
468	465	(arc.forward ? 0 : 1);
469	466	}
470	467	Arc arcFromId(int ix) const {
471	468	return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
472	469	}
473	470	int maxArcId() const {
474	471	return (Parent::maxEdgeId() << 1) + 1;
475	472	}
476	473
477	474	bool direction(const Arc& arc) const {
478	475	return arc.forward;
479	476	}
480	477
481	478	Arc direct(const Edge& arc, bool dir) const {
482	479	return Arc(arc, dir);
483	480	}
484	481
485	482	int arcNum() const {
486	483	return 2 * Parent::edgeNum();
487	484	}
488	485
489	486	int edgeNum() const {
490	487	return Parent::edgeNum();
491	488	}
492	489
493	490
494	491	};
495	492	}
496	493
497	494	#endif