LEMON/LEMON-official Changeset - r157:2ccc1afc2c52

Repositories » LEMON » LEMON-official

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

Changeset - r157:2ccc1afc2c52

« 156:e561aa

158:500f3c »

r157:2ccc1afc2c52

Sat, 24 May 2008 23:20:49

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Using \tparam commands + removing \author commands (ticket #29, #39)

0 14 0

default

14 files changed:

lemon/bfs.h

lemon/bin_heap.h

lemon/bits/alteration_notifier.h

lemon/bits/bezier.h

lemon/bits/vector_map.h

lemon/color.h

lemon/concepts/path.h

lemon/dfs.h

lemon/dijkstra.h

lemon/graph_to_eps.h

lemon/graph_utils.h

lemon/path.h

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

↑ Collapse diff ↑

lemon/bfs.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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/graph_utils.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/bits/invalid.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		namespace lemon {
 		  ///Default traits class of Bfs class.
 		  ///Default traits class of Bfs class.
-		  ///\param GR Digraph type.
+		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsDefaultTraits
+		  {
 		    ///The digraph type the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param G is the digraph, to which we would like to define the PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		    static PredMap *createPredMap(const GR &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.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a 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 GR &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const GR &)
 		#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::WriteMap "WriteMap" concept.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a 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 GR &G)
+		    {
 		      return new ReachedMap(G);
+		    }
 		    ///The type of the map that stores the dists of the nodes.
 		    ///The type of the map that stores the dists of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a 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 GR &G)
+		    {
 		      return new DistMap(G);
+		    }
 		  };
 		  ///%BFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %BFS algorithm.
 		  ///
-		  ///\param GR The digraph type the algorithm runs on. The default value is
+		  ///\tparam GR The digraph type the algorithm runs on. The default value is
 		  ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
 		  ///is only passed to \ref BfsDefaultTraits.
-		  ///\param TR Traits class to set various data types used by the algorithm.
+		  ///\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.
 		  ///
 		  ///\author Alpar Juttner
 		#ifdef DOXYGEN
 		  template <typename GR,
 			    typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 			    typename TR=BfsDefaultTraits<GR> >
 		#endif
 		  class Bfs {
 		  public:
 		    /**
 		     * \brief \ref Exception for uninitialized parameters.
+		     *
 		     * This error represents problems in the initialization
 		     * of the parameters of the algorithms.
 		     */
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 			return "lemon::Bfs::UninitializedParameter";
+		      }
 		    };
 		    typedef TR Traits;
 		    ///The type of the underlying digraph.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map indicating which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map indicating which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the map that stores the dists of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		  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 predecessors arcs.
 		    PredMap *_pred;
 		    ///Indicates if \ref _pred is locally allocated (\c true) or not.
 		    bool local_pred;
 		    ///Pointer to the map of distances.
 		    DistMap *_dist;
 		    ///Indicates if \ref _dist is locally allocated (\c true) or not.
 		    bool local_dist;
 		    ///Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    ///Indicates if \ref _reached is locally allocated (\c true) or not.
 		    bool local_reached;
 		    ///Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    ///Indicates if \ref _processed is locally allocated (\c true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::Node> _queue;
 		    int _queue_head,_queue_tail,_queue_next_dist;
 		    int _curr_dist;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    void create_maps()
+		    {
 		      if(!_pred) {
 			local_pred = true;
 			_pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 			local_dist = true;
 			_dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 			local_reached = true;
 			_reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 			local_processed = true;
 			_processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Bfs() {}
 		  public:
 		    typedef Bfs Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct DefPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///PredMap type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting PredMap type
 		    ///
 		    template <class T>
 		    struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
 		      typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct DefDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///DistMap type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting DistMap type
 		    ///
 		    template <class T>
 		    struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
 		      typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct DefReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ReachedMap type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
 		    ///
 		    template <class T>
 		    struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct DefProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
 		    ///
 		    template <class T>
 		    struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
 		    };
 		    struct DefDigraphProcessedMapTraits : 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 the ProcessedMap type to be Digraph::NodeMap<bool>.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    template <class T>
 		    struct DefProcessedMapToBeDefaultMap :
 		      public Bfs< Digraph, DefDigraphProcessedMapTraits> {
 		      typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
 		    };
@@ -567,385 +565,385 @@
 		    ///Returns the number of the nodes to be processed.
 		    ///Returns the number of the nodes to be processed in the queue.
 		    int queueSize() { return _queue_head-_queue_tail; }
 		    ///Executes the algorithm.
 		    ///Executes the algorithm.
 		    ///
 		    ///\pre init() must be called and at least one node should be added
 		    ///with addSource() before using this function.
 		    ///
 		    ///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.
 		    ///- The distance of each node from the root(s).
 		    void start()
+		    {
 		      while ( !emptyQueue() ) processNextNode();
+		    }
 		    ///Executes the algorithm until \c dest is reached.
 		    ///Executes the algorithm until \c dest is reached.
 		    ///
 		    ///\pre init() must be called and at least one node should be added
 		    ///with addSource() before using this function.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s)
 		    ///in order to compute the shortest path to \c dest.
 		    ///The algorithm computes
 		    ///- The shortest path to \c  dest.
 		    ///- The distance of \c dest from the root(s).
 		    void start(Node dest)
+		    {
 		      bool reach = false;
 		      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+		    }
 		    ///Executes the algorithm until a condition is met.
 		    ///Executes the algorithm until a condition is met.
 		    ///
 		    ///\pre init() must be called and at least one node should be added
 		    ///with addSource() before using this function.
 		    ///
 		    ///\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.
 		    template<class NM>
 		    Node start(const NM &nm)
+		    {
 		      Node rnode = INVALID;
 		      while ( !emptyQueue() && rnode == INVALID ) {
 			processNextNode(nm, rnode);
+		      }
 		      return rnode;
+		    }
 		    ///Runs %BFS algorithm from node \c s.
 		    ///This method runs the %BFS algorithm from a root 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 b.run(s) 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.
 		    ///Finds the shortest path between \c s and \c t.
 		    ///
 		    ///\return The length of the shortest s---t path if there exists one,
 		    ///0 otherwise.
 		    ///\note Apart from the return value, b.run(s) is
 		    ///just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  b.addSource(s);
 		    ///  b.start(t);
 		    ///\endcode
 		    int run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t) ? _curr_dist : 0;
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The result of the %BFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Before the use of these functions,
 		    ///either run() or start() must be calleb.
 		    ///@{
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///Gives back the shortest path.
 		    ///Gives back the shortest path.
 		    ///\pre The \c t should be reachable from the source.
 		    Path path(Node t)
+		    {
 		      return Path(*G, *_pred, t);
+		    }
 		    ///The distance of a node from the root(s).
 		    ///Returns the distance of a node from the root(s).
 		    ///\pre \ref run() must be called before using this function.
 		    ///\warning If node \c v in unreachable from the root(s) the return value
 		    ///of this function is undefined.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the shortest path tree.
 		    ///For a node \c v it returns the 'previous arc'
 		    ///of the shortest path tree,
 		    ///i.e. it returns the last arc of a shortest path from the root(s) to \c
 		    ///v. It is \ref INVALID
 		    ///if \c v is unreachable from the root(s) or \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 \c v it returns the 'previous node'
 		    ///of the shortest path tree,
 		    ///i.e. it returns the last but one node from a shortest path from the
 		    ///root(a) to \c /v.
 		    ///It is INVALID if \c v is unreachable from the root(s) or
 		    ///if \c v itself 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]); }
 		    ///Returns a reference to the NodeMap of distances.
 		    ///Returns a reference to the NodeMap of distances.
 		    ///\pre Either \ref run() or \ref init() must
 		    ///be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///Returns a reference to the shortest path tree map.
 		    ///Returns a reference to the NodeMap of the arcs of 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.
 		    ///Returns \c true if \c v is reachable from the root.
 		    ///\warning The source nodes are indicated as unreached.
 		    ///\pre Either \ref run() or \ref start()
 		    ///must be called before using this function.
 		    ///
 		    bool reached(Node v) { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of Bfs function.
 		  ///Default traits class of Bfs function.
-		  ///\param GR Digraph type.
+		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsWizardDefaultTraits
+		  {
 		    ///The digraph type the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const GR &g)
 		#else
 		    static PredMap *createPredMap(const GR &)
 		#endif
+		    {
 		      return new PredMap();
+		    }
 		    ///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.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a 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 GR &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const GR &)
 		#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::WriteMap "WriteMap" concept.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a 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 GR &G)
+		    {
 		      return new ReachedMap(G);
+		    }
 		    ///The type of the map that stores the dists of the nodes.
 		    ///The type of the map that stores the dists of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap<typename Digraph::Node,int> DistMap;
 		    ///Instantiates a DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const GR &g)
 		#else
 		    static DistMap *createDistMap(const GR &)
 		#endif
+		    {
 		      return new DistMap();
+		    }
 		  };
 		  /// Default traits 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:
 		    /// Type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    /// Pointer to the underlying digraph.
 		    void *_g;
 		    ///Pointer to the map of reached nodes.
 		    void *_reached;
 		    ///Pointer to the map of processed nodes.
 		    void *_processed;
 		    ///Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    ///Pointer to the map of distances.
 		    void *_dist;
 		    ///Pointer to the source node.
 		    Node _source;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to default values (0, INVALID).
 		    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 					   _dist(0), _source(INVALID) {}
 		    /// Constructor.
 		    /// This constructor requires some parameters,
 		    /// listed in the parameters list.
 		    /// Others are initiated to 0.
 		    /// \param g is the initial value of  \ref _g
 		    /// \param s is the initial value of  \ref _source
 		    BfsWizardBase(const GR &g, Node s=INVALID) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
 		  };
 		  /// A class to make the usage of Bfs algorithm easier
 		  /// This class is created to make it easier to use Bfs algorithm.
 		  /// It uses the functions and features of the plain \ref Bfs,
 		  /// but it is much simpler to use it.
 		  ///
 		  /// Simplicity means that the way to change the types defined
 		  /// in the traits class is based on functions that returns the new class
 		  /// and not on templatable built-in classes.
 		  /// When using the plain \ref Bfs
 		  /// the new class with the modified type comes from
 		  /// the original class by using the ::
 		  /// operator. In the case of \ref BfsWizard only
 		  /// a function have to be called and it will
 		  /// return the needed class.
 		  ///
 		  /// It does not have own \ref run method. When its \ref run method is called
 		  /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
 		  /// method of it.
 		  template<class TR>
 		  class BfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the underlying digraph.
 		    typedef typename TR::Digraph Digraph;
 		    //\e
 		    typedef typename Digraph::Node Node;
 		    //\e
 		    typedef typename Digraph::NodeIt NodeIt;
 		    //\e
 		    typedef typename Digraph::Arc Arc;
 		    //\e
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\brief The type of the map that stores
 		    ///the reached nodes
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///\brief The type of the map that stores
 		    ///the processed nodes
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the dists of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		  public:
 		    /// Constructor.
 		    BfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    BfsWizard(const Digraph &g, Node s=INVALID) :
 		      TR(g,s) {}
 		    ///Copy constructor
 		    BfsWizard(const TR &b) : TR(b) {}
@@ -976,434 +974,432 @@
 		    ///Runs Bfs algorithm from the given node.
 		    ///\param s is the given source.
 		    void run(Node s)
+		    {
 		      Base::_source=s;
 		      run();
+		    }
 		    template<class T>
 		    struct DefPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      DefPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///function for setting PredMap
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///function for setting PredMap
 		    ///
 		    template<class T>
 		    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<DefPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct DefReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      DefReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///function for setting ReachedMap
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///function for setting ReachedMap
 		    ///
 		    template<class T>
 		    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<DefReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct DefProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      DefProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///function for setting ProcessedMap
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///function for setting ProcessedMap
 		    ///
 		    template<class T>
 		    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<DefProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct DefDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      DefDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///function for setting DistMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///function for setting DistMap type
 		    ///
 		    template<class T>
 		    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<DefDistMapBase<T> >(*this);
+		    }
 		    /// Sets the source node, from which the Bfs algorithm runs.
 		    /// Sets the source node, from which the Bfs algorithm runs.
 		    /// \param s is the source node.
 		    BfsWizard<TR> &source(Node s)
+		    {
 		      Base::_source=s;
 		      return *this;
+		    }
 		  };
 		  ///Function type interface for Bfs algorithm.
 		  /// \ingroup search
 		  ///Function type interface for Bfs algorithm.
 		  ///
 		  ///This function also has several
 		  ///\ref named-templ-func-param "named parameters",
 		  ///they are declared as the members of class \ref BfsWizard.
 		  ///The following
 		  ///example shows how to use these parameters.
 		  ///\code
 		  ///  bfs(g,source).predMap(preds).run();
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
 		  ///to the end of the parameter list.
 		  ///\sa BfsWizard
 		  ///\sa Bfs
 		  template<class GR>
 		  BfsWizard<BfsWizardBase<GR> >
 		  bfs(const GR &g,typename GR::Node s=INVALID)
+		  {
 		    return BfsWizard<BfsWizardBase<GR> >(g,s);
+		  }
 		#ifdef DOXYGEN
 		  /// \brief Visitor class for bfs.
 		  ///
 		  /// This class defines the interface of the BfsVisit events, and
 		  /// it could be the base of a real Visitor class.
 		  template <typename _Digraph>
 		  struct BfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    /// \brief Called when the arc reach a node.
 		    ///
 		    /// It is called when the bfs find an arc which target is not
 		    /// reached yet.
 		    void discover(const Arc& arc) {}
 		    /// \brief Called when the node reached first time.
 		    ///
 		    /// It is Called when the node reached first time.
 		    void reach(const Node& node) {}
 		    /// \brief Called when the arc examined but target of the arc
 		    /// already discovered.
 		    ///
 		    /// It called when the arc examined but the target of the arc
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		    /// \brief Called for the source node of the bfs.
 		    ///
 		    /// It is called for the source node of the bfs.
 		    void start(const Node& node) {}
 		    /// \brief Called when the node processed.
 		    ///
 		    /// It is Called when the node processed.
 		    void process(const Node& node) {}
 		  };
 		#else
 		  template <typename _Digraph>
 		  struct BfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    void discover(const Arc&) {}
 		    void reach(const Node&) {}
 		    void examine(const Arc&) {}
 		    void start(const Node&) {}
 		    void process(const Node&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 			Arc arc;
 			Node node;
 			visitor.discover(arc);
 			visitor.reach(node);
 			visitor.examine(arc);
 			visitor.start(node);
 		        visitor.process(node);
+		      }
 		      _Visitor& visitor;
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of BfsVisit class.
 		  ///
 		  /// Default traits class of BfsVisit class.
-		  /// \param _Digraph Digraph type.
+		  /// \tparam _Digraph Digraph type.
 		  template<class _Digraph>
 		  struct BfsVisitDefaultTraits {
 		    /// \brief The digraph type 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::WriteMap "WriteMap" concept.
 		    /// \todo named parameter to set this type, function to read and write.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a 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 Visit algorithm class.
 		  ///
 		  /// 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
 		  /// on every bfs event the \c Visitor class member functions.
 		  ///
-		  /// \param _Digraph The digraph type the algorithm runs on. The default value is
+		  /// \tparam _Digraph The digraph type the algorithm runs on. The default value is
 		  /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
 		  /// is only passed to \ref BfsDefaultTraits.
-		  /// \param _Visitor The Visitor object for the algorithm. The
+		  /// \tparam _Visitor The Visitor object for the algorithm. The
 		  /// \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.
-		  /// \param _Traits Traits class to set various data types used by the
+		  /// \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.
 		  ///
 		  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
 		#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 algorithms.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw()
+		      {
 			return "lemon::BfsVisit::UninitializedParameter";
+		      }
 		    };
 		    typedef _Traits Traits;
 		    typedef typename Traits::Digraph Digraph;
 		    typedef _Visitor Visitor;
 		    ///The type of the map indicating 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 \ref _reached is locally allocated (\c true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Node> _list;
 		    int _list_front, _list_back;
 		    /// \brief Creates the maps if necessary.
 		    ///
 		    /// 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 DefReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 			throw UninitializedParameter();
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
 		    template <class T>
 		    struct DefReachedMap : public BfsVisit< Digraph, Visitor,
 							    DefReachedMapTraits<T> > {
 		      typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph the digraph the algorithm will run on.
 		    /// \param visitor The visitor of the algorithm.
 		    ///
 		    BfsVisit(const Digraph& digraph, Visitor& visitor)
 		      : _digraph(&digraph), _visitor(&visitor),
 			_reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ///
 		    /// Destructor.
 		    ~BfsVisit() {
 		      if(local_reached) delete _reached;
+		    }
 		    /// \brief Sets the map indicating if a node is reached.
 		    ///
 		    /// Sets the map indicating if a node is reached.
 		    /// If you don't use this function before calling \ref run(),
 		    /// it will allocate one. The destuctor 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 \c run(...).
 		    /// \n
 		    /// If you need more control on the execution,
 		    /// first you must call \ref init(), then you can adda source node
 		    /// with \ref addSource().
 		    /// Finally \ref 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 that the given target node
 		    /// is reached. If the target node is reachable from the processed
 		    /// node then the reached parameter will be set true. The reached

lemon/bin_heap.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_BIN_HEAP_H
 		#define LEMON_BIN_HEAP_H
 		///\ingroup auxdat
 		///\file
 		///\brief Binary Heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
 		  ///\ingroup auxdat
 		  ///
 		  ///\brief A Binary Heap implementation.
 		  ///
 		  ///This class implements the \e binary \e heap data structure. A \e heap
 		  ///is a data structure for storing items with specified values called \e
 		  ///priorities in such a way that finding the item with minimum priority is
 		  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
 		  ///one can change the priority of an item, add or erase an item, etc.
 		  ///
 		  ///\param _Prio Type of the priority of the items.
 		  ///\param _ItemIntMap A read and writable Item int map, used internally
 		  ///\tparam _Prio Type of the priority of the items.
 		  ///\tparam _ItemIntMap A read and writable Item int map, used internally
 		  ///to handle the cross references.
-		  ///\param _Compare A class for the ordering of the priorities. The
+		  ///\tparam _Compare A class for the ordering of the priorities. The
 		  ///default is \c std::less<_Prio>.
 		  ///
 		  ///\sa FibHeap
 		  ///\sa Dijkstra
 		  template <typename _Prio, typename _ItemIntMap,
 			    typename _Compare = std::less<_Prio> >
 		  class BinHeap {
 		  public:
 		    ///\e
 		    typedef _ItemIntMap ItemIntMap;
 		    ///\e
 		    typedef _Prio Prio;
 		    ///\e
 		    typedef typename ItemIntMap::Key Item;
 		    ///\e
 		    typedef std::pair<Item,Prio> Pair;
 		    ///\e
 		    typedef _Compare Compare;
 		    /// \brief Type to represent the items states.
 		    ///
 		    /// Each Item element have a state associated to it. It may be "in heap",
 		    /// "pre heap" or "post heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// The ItemIntMap \e should be initialized in such way that it maps
 		    /// PRE_HEAP (-1) to any element to be put in the heap...
 		    enum State {
 		      IN_HEAP = 0,
 		      PRE_HEAP = -1,
 		      POST_HEAP = -2
 		    };
 		  private:
 		    std::vector<Pair> data;
 		    Compare comp;
 		    ItemIntMap &iim;
 		  public:
 		    /// \brief The constructor.
 		    ///
 		    /// The constructor.
 		    /// \param _iim should be given to the constructor, since it is used
 		    /// internally to handle the cross references. The value of the map
 		    /// should be PRE_HEAP (-1) for each element.
 		    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
 		    /// \brief The constructor.
 		    ///
 		    /// The constructor.
 		    /// \param _iim should be given to the constructor, since it is used
 		    /// internally to handle the cross references. The value of the map
 		    /// should be PRE_HEAP (-1) for each element.
 		    ///
 		    /// \param _comp The comparator function object.
 		    BinHeap(ItemIntMap &_iim, const Compare &_comp)
 		      : iim(_iim), comp(_comp) {}
 		    /// The number of items stored in the heap.
 		    ///
 		    /// \brief Returns the number of items stored in the heap.
 		    int size() const { return data.size(); }
 		    /// \brief Checks if the heap stores no items.
 		    ///
 		    /// Returns \c true if and only if the heap stores no items.
 		    bool empty() const { return data.empty(); }
 		    /// \brief Make empty this heap.
 		    ///
 		    /// Make empty this heap. It does not change the cross reference map.
 		    /// If you want to reuse what is not surely empty you should first clear
 		    /// the heap and after that you should set the cross reference map for
 		    /// each item to \c PRE_HEAP.
 		    void clear() {
 		      data.clear();
+		    }
 		  private:
 		    static int parent(int i) { return (i-1)/2; }
 		    static int second_child(int i) { return 2*i+2; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return comp(p1.second, p2.second);
+		    }
 		    int bubble_up(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,data[par]) ) {
 			move(data[par],hole);
 			hole = par;
 			par = parent(hole);
+		      }
 		      move(p, hole);
 		      return hole;
+		    }
 		    int bubble_down(int hole, Pair p, int length) {
 		      int child = second_child(hole);
 		      while(child < length) {
 			if( less(data[child-1], data[child]) ) {
 			  --child;
+			}
 			if( !less(data[child], p) )
 			  goto ok;
 			move(data[child], hole);
 			hole = child;
 			child = second_child(hole);
+		      }
 		      child--;
 		      if( child<length && less(data[child], p) ) {
 			move(data[child], hole);
 			hole=child;
+		      }
 		    ok:
 		      move(p, hole);
 		      return hole;
+		    }
 		    void move(const Pair &p, int i) {
 		      data[i] = p;
 		      iim.set(p.first, i);
+		    }
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
 		    /// Adds \c p.first to the heap with priority \c p.second.
 		    /// \param p The pair to insert.
 		    void push(const Pair &p) {
 		      int n = data.size();
 		      data.resize(n+1);
 		      bubble_up(n, p);
+		    }
 		    /// \brief Insert an item into the heap with the given heap.
 		    ///
 		    /// Adds \c i to the heap with priority \c p.
 		    /// \param i The item to insert.
 		    /// \param p The priority of the item.
 		    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
 		    /// \brief Returns the item with minimum priority relative to \c Compare.
 		    ///
 		    /// This method returns the item with minimum priority relative to \c
 		    /// Compare.
 		    /// \pre The heap must be nonempty.
 		    Item top() const {
 		      return data[0].first;
+		    }
 		    /// \brief Returns the minimum priority relative to \c Compare.
 		    ///
 		    /// It returns the minimum priority relative to \c Compare.
 		    /// \pre The heap must be nonempty.
 		    Prio prio() const {
 		      return data[0].second;
+		    }
 		    /// \brief Deletes the item with minimum priority relative to \c Compare.
 		    ///
 		    /// This method deletes the item with minimum priority relative to \c
 		    /// Compare from the heap.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      int n = data.size()-1;
 		      iim.set(data[0].first, POST_HEAP);
 		      if (n > 0) {
 			bubble_down(0, data[n], n);
+		      }
 		      data.pop_back();
+		    }
 		    /// \brief Deletes \c i from the heap.
 		    ///
 		    /// This method deletes item \c i from the heap.
 		    /// \param i The item to erase.
 		    /// \pre The item should be in the heap.
 		    void erase(const Item &i) {
 		      int h = iim[i];
 		      int n = data.size()-1;
 		      iim.set(data[h].first, POST_HEAP);
 		      if( h < n ) {
 			if ( bubble_up(h, data[n]) == h) {
 			  bubble_down(h, data[n], n);
+			}
+		      }
 		      data.pop_back();
+		    }

lemon/bits/alteration_notifier.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_ALTERATION_NOTIFIER_H
 		#define LEMON_BITS_ALTERATION_NOTIFIER_H
 		#include <vector>
 		#include <list>
 		#include <lemon/bits/utility.h>
 		///\ingroup graphbits
 		///\file
 		///\brief Observer notifier for graph alteration observers.
 		namespace lemon {
 		  /// \ingroup graphbits
 		  ///
 		  /// \brief Notifier class to notify observes about alterations in
 		  /// a container.
 		  ///
 		  /// The simple graph's can be refered as two containers, one node container
 		  /// and one edge container. But they are not standard containers they
 		  /// does not store values directly they are just key continars for more
 		  /// value containers which are the node and edge maps.
 		  ///
 		  /// The graph's node and edge sets can be changed as we add or erase
 		  /// nodes and edges in the graph. Lemon would like to handle easily
 		  /// that the node and edge maps should contain values for all nodes or
 		  /// edges. If we want to check on every indicing if the map contains
 		  /// the current indicing key that cause a drawback in the performance
 		  /// in the library. We use another solution we notify all maps about
 		  /// an alteration in the graph, which cause only drawback on the
 		  /// alteration of the graph.
 		  ///
 		  /// This class provides an interface to the container. The \e first() and \e
 		  /// next() member functions make possible to iterate on the keys of the
 		  /// container. The \e id() function returns an integer id for each key.
 		  /// The \e maxId() function gives back an upper bound of the ids.
 		  ///
 		  /// For the proper functonality of this class, we should notify it
 		  /// about each alteration in the container. The alterations have four type
 		  /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
 		  /// \e erase() signals that only one or few items added or erased to or
 		  /// from the graph. If all items are erased from the graph or from an empty
 		  /// graph a new graph is builded then it can be signaled with the
 		  /// clear() and build() members. Important rule that if we erase items
 		  /// from graph we should first signal the alteration and after that erase
 		  /// them from the container, on the other way on item addition we should
 		  /// first extend the container and just after that signal the alteration.
 		  ///
 		  /// The alteration can be observed with a class inherited from the
 		  /// \e ObserverBase nested class. The signals can be handled with
 		  /// overriding the virtual functions defined in the base class.  The
 		  /// observer base can be attached to the notifier with the
 		  /// \e attach() member and can be detached with detach() function. The
 		  /// alteration handlers should not call any function which signals
 		  /// an other alteration in the same notifier and should not
 		  /// detach any observer from the notifier.
 		  ///
 		  /// Alteration observers try to be exception safe. If an \e add() or
 		  /// a \e clear() function throws an exception then the remaining
 		  /// observeres will not be notified and the fulfilled additions will
 		  /// be rolled back by calling the \e erase() or \e clear()
 		  /// functions. Thence the \e erase() and \e clear() should not throw
 		  /// exception. Actullay, it can be throw only
 		  /// \ref AlterationObserver::ImmediateDetach ImmediateDetach
 		  /// exception which detach the observer from the notifier.
 		  ///
 		  /// There are some place when the alteration observing is not completly
 		  /// reliable. If we want to carry out the node degree in the graph
 		  /// as in the \ref InDegMap and we use the reverseEdge that cause
 		  /// unreliable functionality. Because the alteration observing signals
 		  /// only erasing and adding but not the reversing it will stores bad
 		  /// degrees. The sub graph adaptors cannot signal the alterations because
 		  /// just a setting in the filter map can modify the graph and this cannot
 		  /// be watched in any way.
 		  ///
 		  /// \param _Container The container which is observed.
 		  /// \param _Item The item type which is obserbved.
 		  ///
 		  /// \author Balazs Dezso
 		  template <typename _Container, typename _Item>
 		  class AlterationNotifier {
 		  public:
 		    typedef True Notifier;
 		    typedef _Container Container;
 		    typedef _Item Item;
 		    /// \brief Exception which can be called from \e clear() and
 		    /// \e erase().
 		    ///
 		    /// From the \e clear() and \e erase() function only this
 		    /// exception is allowed to throw. The exception immediatly
 		    /// detaches the current observer from the notifier. Because the
 		    /// \e clear() and \e erase() should not throw other exceptions
 		    /// it can be used to invalidate the observer.
 		    struct ImmediateDetach {};
 		    /// \brief ObserverBase is the base class for the observers.
 		    ///
 		    /// ObserverBase is the abstract base class for the observers.
 		    /// It will be notified about an item was inserted into or
 		    /// erased from the graph.
 		    ///
 		    /// The observer interface contains some pure virtual functions
 		    /// to override. The add() and erase() functions are
 		    /// to notify the oberver when one item is added or
 		    /// erased.
 		    ///
 		    /// The build() and clear() members are to notify the observer
 		    /// about the container is built from an empty container or
 		    /// is cleared to an empty container.
 		    ///
 		    /// \author Balazs Dezso
 		    class ObserverBase {
 		    protected:
 		      typedef AlterationNotifier Notifier;
 		      friend class AlterationNotifier;
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor for ObserverBase.
 		      ///
 		      ObserverBase() : _notifier(0) {}
 		      /// \brief Constructor which attach the observer into notifier.
 		      ///
 		      /// Constructor which attach the observer into notifier.
 		      ObserverBase(AlterationNotifier& nf) {
 		        attach(nf);
+		      }
 		      /// \brief Constructor which attach the obserever to the same notifier.
 		      ///
 		      /// Constructor which attach the obserever to the same notifier as
 		      /// the other observer is attached to.
 		      ObserverBase(const ObserverBase& copy) {
 			if (copy.attached()) {
 		          attach(*copy.notifier());
+			}
+		      }
 		      /// \brief Destructor
 		      virtual ~ObserverBase() {
 		        if (attached()) {
 		          detach();
+		        }
+		      }
 		      /// \brief Attaches the observer into an AlterationNotifier.
 		      ///
 		      /// This member attaches the observer into an AlterationNotifier.
 		      ///
 		      void attach(AlterationNotifier& nf) {
 			nf.attach(*this);
+		      }
 		      /// \brief Detaches the observer into an AlterationNotifier.
 		      ///
 		      /// This member detaches the observer from an AlterationNotifier.
 		      ///
 		      void detach() {
 		        _notifier->detach(*this);
+		      }
 		      /// \brief Gives back a pointer to the notifier which the map
 		      /// attached into.
 		      ///
 		      /// This function gives back a pointer to the notifier which the map
 		      /// attached into.
 		      ///
 		      Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }
 		      /// Gives back true when the observer is attached into a notifier.
 		      bool attached() const { return _notifier != 0; }
 		    private:
 		      ObserverBase& operator=(const ObserverBase& copy);
 		    protected:
 		      Notifier* _notifier;
 		      typename std::list<ObserverBase*>::iterator _index;
 		      /// \brief The member function to notificate the observer about an
 		      /// item is added to the container.
 		      ///
 		      /// The add() member function notificates the observer about an item
 		      /// is added to the container. It have to be overrided in the
 		      /// subclasses.
 		      virtual void add(const Item&) = 0;
 		      /// \brief The member function to notificate the observer about
 		      /// more item is added to the container.
 		      ///
 		      /// The add() member function notificates the observer about more item
 		      /// is added to the container. It have to be overrided in the
 		      /// subclasses.
 		      virtual void add(const std::vector<Item>& items) = 0;
 		      /// \brief The member function to notificate the observer about an
 		      /// item is erased from the container.
 		      ///
 		      /// The erase() member function notificates the observer about an
 		      /// item is erased from the container. It have to be overrided in
 		      /// the subclasses.
 		      virtual void erase(const Item&) = 0;
 		      /// \brief The member function to notificate the observer about
 		      /// more item is erased from the container.
 		      ///
 		      /// The erase() member function notificates the observer about more item
 		      /// is erased from the container. It have to be overrided in the
 		      /// subclasses.
 		      virtual void erase(const std::vector<Item>& items) = 0;
 		      /// \brief The member function to notificate the observer about the
 		      /// container is built.
 		      ///
 		      /// The build() member function notificates the observer about the
 		      /// container is built from an empty container. It have to be
 		      /// overrided in the subclasses.
 		      virtual void build() = 0;
 		      /// \brief The member function to notificate the observer about all
 		      /// items are erased from the container.
 		      ///
 		      /// The clear() member function notificates the observer about all
 		      /// items are erased from the container. It have to be overrided in
 		      /// the subclasses.
 		      virtual void clear() = 0;
 		    };
 		  protected:
 		    const Container* container;
 		    typedef std::list<ObserverBase*> Observers;
 		    Observers _observers;
 		  public:
 		    /// \brief Default constructor.
 		    ///
 		    /// The default constructor of the AlterationNotifier.
 		    /// It creates an empty notifier.
 		    AlterationNotifier()
 		      : container(0) {}
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor with the observed container parameter.
 		    AlterationNotifier(const Container& _container)
 		      : container(&_container) {}
 		    /// \brief Copy Constructor of the AlterationNotifier.
 		    ///
 		    /// Copy constructor of the AlterationNotifier.
 		    /// It creates only an empty notifier because the copiable
 		    /// notifier's observers have to be registered still into that notifier.
 		    AlterationNotifier(const AlterationNotifier& _notifier)
 		      : container(_notifier.container) {}
 		    /// \brief Destructor.
 		    ///
 		    /// Destructor of the AlterationNotifier.
 		    ///
 		    ~AlterationNotifier() {
 		      typename Observers::iterator it;
 		      for (it = _observers.begin(); it != _observers.end(); ++it) {
 			(*it)->_notifier = 0;
+		      }
+		    }
 		    /// \brief Sets the container.
 		    ///
 		    /// Sets the container.
 		    void setContainer(const Container& _container) {
 		      container = &_container;
+		    }
 		  protected:
 		    AlterationNotifier& operator=(const AlterationNotifier&);
 		  public:
 		    /// \brief First item in the container.
 		    ///
 		    /// Returns the first item in the container. It is
 		    /// for start the iteration on the container.
 		    void first(Item& item) const {
 		      container->first(item);
+		    }
 		    /// \brief Next item in the container.
 		    ///
 		    /// Returns the next item in the container. It is

lemon/bits/bezier.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_BEZIER_H
 		#define LEMON_BEZIER_H
 		///\ingroup misc
 		///\file
 		///\brief Classes to compute with Bezier curves.
 		///
 		///Up to now this file is used internally by \ref graph_to_eps.h
 		///
 		///\author Alpar Juttner
 		#include<lemon/dim2.h>
 		namespace lemon {
 		  namespace dim2 {
 		class BezierBase {
 		public:
 		  typedef Point<double> Point;
 		protected:
 		  static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;}
 		};
 		class Bezier1 : public BezierBase
+		{
 		public:
 		  Point p1,p2;
 		  Bezier1() {}
 		  Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {}
 		  Point operator()(double t) const
+		  {
 		    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
 		    return conv(p1,p2,t);
+		  }
 		  Bezier1 before(double t) const
+		  {
 		    return Bezier1(p1,conv(p1,p2,t));
+		  }
 		  Bezier1 after(double t) const
+		  {
 		    return Bezier1(conv(p1,p2,t),p2);
+		  }
 		  Bezier1 revert() const { return Bezier1(p2,p1);}
 		  Bezier1 operator()(double a,double b) const { return before(b).after(a/b); }
 		  Point grad() const { return p2-p1; }
 		  Point norm() const { return rot90(p2-p1); }
 		  Point grad(double) const { return grad(); }
 		  Point norm(double t) const { return rot90(grad(t)); }
 		};
 		class Bezier2 : public BezierBase
+		{
 		public:
 		  Point p1,p2,p3;
 		  Bezier2() {}
 		  Bezier2(Point _p1, Point _p2, Point _p3) :p1(_p1), p2(_p2), p3(_p3) {}
 		  Bezier2(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,.5)), p3(b.p2) {}
 		  Point operator()(double t) const
+		  {
 		    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
 		    return ((1-t)*(1-t))*p1+(2*(1-t)*t)*p2+(t*t)*p3;
+		  }
 		  Bezier2 before(double t) const
+		  {
 		    Point q(conv(p1,p2,t));
 		    Point r(conv(p2,p3,t));
 		    return Bezier2(p1,q,conv(q,r,t));
+		  }
 		  Bezier2 after(double t) const
+		  {
 		    Point q(conv(p1,p2,t));
 		    Point r(conv(p2,p3,t));
 		    return Bezier2(conv(q,r,t),r,p3);
+		  }
 		  Bezier2 revert() const { return Bezier2(p3,p2,p1);}
 		  Bezier2 operator()(double a,double b) const { return before(b).after(a/b); }
 		  Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); }
 		  Bezier1 norm() const { return Bezier1(2.0*rot90(p2-p1),2.0*rot90(p3-p2)); }
 		  Point grad(double t) const { return grad()(t); }
 		  Point norm(double t) const { return rot90(grad(t)); }
 		};
 		class Bezier3 : public BezierBase
+		{
 		public:
 		  Point p1,p2,p3,p4;
 		  Bezier3() {}
 		  Bezier3(Point _p1, Point _p2, Point _p3, Point _p4)
 		    : p1(_p1), p2(_p2), p3(_p3), p4(_p4) {}
 		  Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)),
 					      p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {}
 		  Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)),
 					      p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {}
 		  Point operator()(double t) const
+		    {
 		      //    return Bezier2(conv(p1,p2,t),conv(p2,p3,t),conv(p3,p4,t))(t);
 		      return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+
 			(3*t*t*(1-t))*p3+(t*t*t)*p4;
+		    }
 		  Bezier3 before(double t) const
+		    {
 		      Point p(conv(p1,p2,t));
 		      Point q(conv(p2,p3,t));
 		      Point r(conv(p3,p4,t));
 		      Point a(conv(p,q,t));
 		      Point b(conv(q,r,t));
 		      Point c(conv(a,b,t));
 		      return Bezier3(p1,p,a,c);
+		    }
 		  Bezier3 after(double t) const
+		    {
 		      Point p(conv(p1,p2,t));
 		      Point q(conv(p2,p3,t));
 		      Point r(conv(p3,p4,t));
 		      Point a(conv(p,q,t));
 		      Point b(conv(q,r,t));
 		      Point c(conv(a,b,t));
 		      return Bezier3(c,b,r,p4);
+		    }
 		  Bezier3 revert() const { return Bezier3(p4,p3,p2,p1);}
 		  Bezier3 operator()(double a,double b) const { return before(b).after(a/b); }
 		  Bezier2 grad() const { return Bezier2(3.0*(p2-p1),3.0*(p3-p2),3.0*(p4-p3)); }
 		  Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1),
 .0*rot90(p3-p2),
 .0*rot90(p4-p3)); }
 		  Point grad(double t) const { return grad()(t); }
 		  Point norm(double t) const { return rot90(grad(t)); }
 		  template<class R,class F,class S,class D>
 		  R recSplit(F &_f,const S &_s,D _d) const
+		  {
 		    const Point a=(p1+p2)/2;
 		    const Point b=(p2+p3)/2;
 		    const Point c=(p3+p4)/2;
 		    const Point d=(a+b)/2;
 		    const Point e=(b+c)/2;
 		    const Point f=(d+e)/2;
 		    R f1=_f(Bezier3(p1,a,d,e),_d);
 		    R f2=_f(Bezier3(e,d,c,p4),_d);
 		    return _s(f1,f2);
+		  }
 		};
 		} //END OF NAMESPACE dim2
 		} //END OF NAMESPACE lemon
 		#endif // LEMON_BEZIER_H

lemon/bits/vector_map.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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/bits/traits.h>
 		#include <lemon/bits/utility.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.
 		  ///
 		  /// \param Notifier The AlterationNotifier that will notify this map.
 		  /// \param Item The item type of the graph items.
 		  /// \param Value The value type of the map.
 		  ///
-		  /// \author Balazs Dezso
+		  /// \tparam _Notifier The AlterationNotifier that will notify this map.
 		  /// \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);
+		    }
 		    /// \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/color.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_COLOR_H
 		#define LEMON_COLOR_H
 		#include<vector>
 		#include<lemon/math.h>
 		#include<lemon/maps.h>
 		///\ingroup misc
 		///\file
 		///\brief Tools to manage RGB colors.
 		///
 		///\author Alpar Juttner
 		namespace lemon {
 		  /// \addtogroup misc
 		  /// @{
 		  ///Data structure representing RGB colors.
 		  ///Data structure representing RGB colors.
 		  class Color
+		  {
 		    double _r,_g,_b;
 		  public:
 		    ///Default constructor
 		    Color() {}
 		    ///Constructor
 		    Color(double r,double g,double b) :_r(r),_g(g),_b(b) {};
 		    ///Set the red component
 		    double & red() {return _r;}
 		    ///Return the red component
 		    const double & red() const {return _r;}
 		    ///Set the green component
 		    double & green() {return _g;}
 		    ///Return the green component
 		    const double & green() const {return _g;}
 		    ///Set the blue component
 		    double & blue() {return _b;}
 		    ///Return the blue component
 		    const double & blue() const {return _b;}
 		    ///Set the color components
 		    void set(double r,double g,double b) { _r=r;_g=g;_b=b; };
 		  };
 		  /// White color constant
 		  extern const Color WHITE;
 		  /// Black color constant
 		  extern const Color BLACK;
 		  /// Red color constant
 		  extern const Color RED;
 		  /// Green color constant
 		  extern const Color GREEN;
 		  /// Blue color constant
 		  extern const Color BLUE;
 		  /// Yellow color constant
 		  extern const Color YELLOW;
 		  /// Magenta color constant
 		  extern const Color MAGENTA;
 		  /// Cyan color constant
 		  extern const Color CYAN;
 		  /// Grey color constant
 		  extern const Color GREY;
 		  /// Dark red color constant
 		  extern const Color DARK_RED;
 		  /// Dark green color constant
 		  extern const Color DARK_GREEN;
 		  /// Drak blue color constant
 		  extern const Color DARK_BLUE;
 		  /// Dark yellow color constant
 		  extern const Color DARK_YELLOW;
 		  /// Dark magenta color constant
 		  extern const Color DARK_MAGENTA;
 		  /// Dark cyan color constant
 		  extern const Color DARK_CYAN;
 		  ///Map <tt>int</tt>s to different \ref Color "Color"s
 		  ///This map assigns one of the predefined \ref Color "Color"s to
 		  ///each <tt>int</tt>. It is possible to change the colors as well as
 		  ///their number. The integer range is cyclically mapped to the
 		  ///provided set of colors.
 		  ///
 		  ///This is a true \ref concepts::ReferenceMap "reference map", so
 		  ///you can also change the actual colors.
 		  class Palette : public MapBase<int,Color>
+		  {
 		    std::vector<Color> colors;
 		  public:
 		    ///Constructor
 		    ///Constructor
 		    ///\param have_white indicates whether white is amongst the
 		    ///provided initial colors (\c true) or not (\c false). If it is true,
 		    ///white will be assigned to \c 0.
 		    ///\param num the number of the allocated colors. If it is \c -1,
 		    ///the default color configuration is set up (26 color plus optionaly the
 		    ///white).  If \c num is less then 26/27 then the default color
 		    ///list is cut. Otherwise the color list is filled repeatedly with
 		    ///the default color list.  (The colors can be changed later on.)
 		    Palette(bool have_white=false,int num=-1)
+		    {
 		      if (num==0) return;
 		      do {
 		        if(have_white) colors.push_back(Color(1,1,1));
 		        colors.push_back(Color(0,0,0));
 		        colors.push_back(Color(1,0,0));
 		        colors.push_back(Color(0,1,0));
 		        colors.push_back(Color(0,0,1));
 		        colors.push_back(Color(1,1,0));
 		        colors.push_back(Color(1,0,1));
 		        colors.push_back(Color(0,1,1));
 		        colors.push_back(Color(.5,0,0));
 		        colors.push_back(Color(0,.5,0));
 		        colors.push_back(Color(0,0,.5));
 		        colors.push_back(Color(.5,.5,0));
 		        colors.push_back(Color(.5,0,.5));
 		        colors.push_back(Color(0,.5,.5));
 		        colors.push_back(Color(.5,.5,.5));
 		        colors.push_back(Color(1,.5,.5));
 		        colors.push_back(Color(.5,1,.5));
 		        colors.push_back(Color(.5,.5,1));
 		        colors.push_back(Color(1,1,.5));
 		        colors.push_back(Color(1,.5,1));
 		        colors.push_back(Color(.5,1,1));
 		        colors.push_back(Color(1,.5,0));
 		        colors.push_back(Color(.5,1,0));
 		        colors.push_back(Color(1,0,.5));
 		        colors.push_back(Color(0,1,.5));
 		        colors.push_back(Color(0,.5,1));
 		        colors.push_back(Color(.5,0,1));
 		      } while(int(colors.size())<num);
 		      //    colors.push_back(Color(1,1,1));
 		      if(num>=0) colors.resize(num);
+		    }
 		    ///\e
 		    Color &operator[](int i)
+		    {
 		      return colors[i%colors.size()];
+		    }
 		    ///\e
 		    const Color &operator[](int i) const
+		    {
 		      return colors[i%colors.size()];
+		    }
 		    ///\e
 		    void set(int i,const Color &c)
+		    {
 		      colors[i%colors.size()]=c;
+		    }
 		    ///Add a new color to the end of the color list.
 		    void add(const Color &c)
+		    {
 		      colors.push_back(c);
+		    }
 		    ///Sets the number of the exiting colors.
 		    void resize(int s) { colors.resize(s);}
 		    ///Returns the number of the existing colors.
 		    int size() const { return int(colors.size());}
 		  };
 		  ///Returns a visibly distinct \ref Color
 		  ///Returns a \ref Color which is as different from the given parameter
 		  ///as it is possible.
 		  inline Color distantColor(const Color &c)
+		  {
 		    return Color(c.red()<.5?1:0,c.green()<.5?1:0,c.blue()<.5?1:0);
+		  }
 		  ///Returns black for light colors and white for the dark ones.
 		  ///Returns black for light colors and white for the dark ones.
 		  inline Color distantBW(const Color &c){
 		    return (.2125*c.red()+.7154*c.green()+.0721*c.blue())<.5 ? WHITE : BLACK;
+		  }
 		  /// @}
 		} //END OF NAMESPACE LEMON
 		#endif // LEMON_COLOR_H

lemon/concepts/path.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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/bits/invalid.h>
 		#include <lemon/bits/utility.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.
-		    /// \param _Digraph The digraph type in which the path is.
+		    /// \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) {}
 		      /// 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.
-		    /// \param _Digraph  The digraph type in which the path is.
+		    /// \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/dfs.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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/graph_utils.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/bits/invalid.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  ///Default traits class of Dfs class.
 		  ///Default traits class of Dfs class.
-		  ///\param GR Digraph type.
+		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsDefaultTraits
+		  {
 		    ///The digraph type the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the last
 		    ///arcs of the %DFS paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param G is the digraph, to which we would like to define the PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		    static PredMap *createPredMap(const GR &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.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a 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 GR &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const GR &)
 		#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::WriteMap "WriteMap" concept.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a 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 GR &G)
+		    {
 		      return new ReachedMap(G);
+		    }
 		    ///The type of the map that stores the dists of the nodes.
 		    ///The type of the map that stores the dists of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a 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 GR &G)
+		    {
 		      return new DistMap(G);
+		    }
 		  };
 		  ///%DFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %DFS algorithm.
 		  ///
-		  ///\param GR The digraph type the algorithm runs on. The default value is
+		  ///\tparam GR The digraph type the algorithm runs on. The default value is
 		  ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
 		  ///is only passed to \ref DfsDefaultTraits.
-		  ///\param TR Traits class to set various data types used by the algorithm.
+		  ///\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.
 		  ///
 		  ///\author Jacint Szabo and Alpar Juttner
 		#ifdef DOXYGEN
 		  template <typename GR,
 			    typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 			    typename TR=DfsDefaultTraits<GR> >
 		#endif
 		  class Dfs {
 		  public:
 		    /**
 		     * \brief \ref Exception for uninitialized parameters.
+		     *
 		     * This error represents problems in the initialization
 		     * of the parameters of the algorithms.
 		     */
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 			return "lemon::Dfs::UninitializedParameter";
+		      }
 		    };
 		    typedef TR Traits;
 		    ///The type of the underlying digraph.
 		    typedef typename TR::Digraph Digraph;
 		    ///\e
 		    typedef typename Digraph::Node Node;
 		    ///\e
 		    typedef typename Digraph::NodeIt NodeIt;
 		    ///\e
 		    typedef typename Digraph::Arc Arc;
 		    ///\e
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the %DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map indicating which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map indicating which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the map that stores the dists of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		  private:
 		    /// Pointer to the underlying digraph.
 		    const Digraph *G;
 		    ///Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    ///Indicates if \ref _pred is locally allocated (\c true) or not.
 		    bool local_pred;
 		    ///Pointer to the map of distances.
 		    DistMap *_dist;
 		    ///Indicates if \ref _dist is locally allocated (\c true) or not.
 		    bool local_dist;
 		    ///Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    ///Indicates if \ref _reached is locally allocated (\c true) or not.
 		    bool local_reached;
 		    ///Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    ///Indicates if \ref _processed is locally allocated (\c true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::OutArcIt> _stack;
 		    int _stack_head;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    void create_maps()
+		    {
 		      if(!_pred) {
 			local_pred = true;
 			_pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 			local_dist = true;
 			_dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 			local_reached = true;
 			_reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 			local_processed = true;
 			_processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Dfs() {}
 		  public:
 		    typedef Dfs Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct DefPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &G)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///PredMap type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting PredMap type
 		    ///
 		    template <class T>
 		    struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
 		      typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct DefDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///DistMap type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting DistMap
 		    ///type
 		    template <class T>
 		    struct DefDistMap {
 		      typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct DefReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ReachedMap type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
 		    ///
 		    template <class T>
 		    struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct DefProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
 		    ///
 		    template <class T>
 		    struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
 		    };
 		    struct DefDigraphProcessedMapTraits : 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 the ProcessedMap type to be Digraph::NodeMap<bool>.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
 		    ///If you don't set it explicitely, it will be automatically allocated.
 		    template <class T>
 		    class DefProcessedMapToBeDefaultMap :
 		      public Dfs< Digraph, DefDigraphProcessedMapTraits> {
 		      typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
 		    };
@@ -550,385 +548,385 @@
 		    ///This method runs the %DFS algorithm from the root node(s)
 		    ///in order to
 		    ///compute the
 		    ///%DFS path to \c dest. The algorithm computes
 		    ///- The %DFS path to \c  dest.
 		    ///- The distance of \c dest from the root(s) in the %DFS tree.
 		    ///
 		    void start(Node dest)
+		    {
 		      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
 			processNextArc();
+		    }
 		    ///Executes the algorithm until a condition is met.
 		    ///Executes the algorithm until a condition is met.
 		    ///
 		    ///\pre init() must be called and at least one node should be added
 		    ///with addSource() before using this function.
 		    ///
 		    ///\param em must be a bool (or convertible) arc map. The algorithm
 		    ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
 		    ///
 		    ///\return The reached arc \c e with <tt>em[e]</tt> true or
 		    ///\c INVALID if no such arc was found.
 		    ///
 		    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
 		    ///not a node map.
 		    template<class EM>
 		    Arc start(const EM &em)
+		    {
 		      while ( !emptyQueue() && !em[_stack[_stack_head]] )
 		        processNextArc();
 		      return emptyQueue() ? INVALID : _stack[_stack_head];
+		    }
 		    ///Runs %DFS 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 d.run() is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
 		    ///    if (!d.reached(it)) {
 		    ///      d.addSource(it);
 		    ///      d.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt it(*G); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///Runs %DFS algorithm from node \c s.
 		    ///This method runs the %DFS algorithm from a root 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 d.run(s) 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.
 		    ///Finds the %DFS path between \c s and \c t.
 		    ///
 		    ///\return The length of the %DFS s---t path if there exists one,
 		    ///0 otherwise.
 		    ///\note Apart from the return value, d.run(s,t) is
 		    ///just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start(t);
 		    ///\endcode
 		    int run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t)?_stack_head+1:0;
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The result of the %DFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Before the use of these functions,
 		    ///either run() or start() must be called.
 		    ///@{
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///Gives back the shortest path.
 		    ///Gives back the shortest path.
 		    ///\pre The \c t should be reachable from the source.
 		    Path path(Node t)
+		    {
 		      return Path(*G, *_pred, t);
+		    }
 		    ///The distance of a node from the root(s).
 		    ///Returns the distance of a node from the root(s).
 		    ///\pre \ref run() must be called before using this function.
 		    ///\warning If node \c v is unreachable from the root(s) then the return
 		    ///value of this funcion is undefined.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the %DFS tree.
 		    ///For a node \c v it returns the 'previous arc'
 		    ///of the %DFS path,
 		    ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
 		    ///v. It is \ref INVALID
 		    ///if \c v is unreachable from the root(s) or \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.
 		    ///For a node \c v it returns the 'previous node'
 		    ///of the %DFS tree,
 		    ///i.e. it returns the last but one node from a %DFS path from the
 		    ///root(s) to \c v.
 		    ///It is INVALID if \c v is unreachable from the root(s) or
 		    ///if \c v itself 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]); }
 		    ///Returns a reference to the NodeMap of distances.
 		    ///Returns a reference to the NodeMap of distances.
 		    ///\pre Either \ref run() or \ref init() must
 		    ///be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///Returns a reference to the %DFS arc-tree map.
 		    ///Returns a reference to the NodeMap of the arcs of 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.
 		    ///Returns \c true if \c v is reachable from the root(s).
 		    ///\warning The source nodes are inditated as unreachable.
 		    ///\pre Either \ref run() or \ref start()
 		    ///must be called before using this function.
 		    ///
 		    bool reached(Node v) { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of Dfs function.
 		  ///Default traits class of Dfs function.
-		  ///\param GR Digraph type.
+		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsWizardDefaultTraits
+		  {
 		    ///The digraph type the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the last
 		    ///arcs of the %DFS paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const GR &g)
 		#else
 		    static PredMap *createPredMap(const GR &)
 		#endif
+		    {
 		      return new PredMap();
+		    }
 		    ///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.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a 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 GR &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const GR &)
 		#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::WriteMap "WriteMap" concept.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a 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 GR &G)
+		    {
 		      return new ReachedMap(G);
+		    }
 		    ///The type of the map that stores the dists of the nodes.
 		    ///The type of the map that stores the dists of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap<typename Digraph::Node,int> DistMap;
 		    ///Instantiates a DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const GR &g)
 		#else
 		    static DistMap *createDistMap(const GR &)
 		#endif
+		    {
 		      return new DistMap();
+		    }
 		  };
 		  /// Default traits 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:
 		    /// Type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    /// Pointer to the underlying digraph.
 		    void *_g;
 		    ///Pointer to the map of reached nodes.
 		    void *_reached;
 		    ///Pointer to the map of processed nodes.
 		    void *_processed;
 		    ///Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    ///Pointer to the map of distances.
 		    void *_dist;
 		    ///Pointer to the source node.
 		    Node _source;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to default values (0, INVALID).
 		    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 					   _dist(0), _source(INVALID) {}
 		    /// Constructor.
 		    /// This constructor requires some parameters,
 		    /// listed in the parameters list.
 		    /// Others are initiated to 0.
 		    /// \param g is the initial value of  \ref _g
 		    /// \param s is the initial value of  \ref _source
 		    DfsWizardBase(const GR &g, Node s=INVALID) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
 		  };
 		  /// A class to make the usage of the Dfs algorithm easier
 		  /// This class is created to make it easier to use the Dfs algorithm.
 		  /// It uses the functions and features of the plain \ref Dfs,
 		  /// but it is much simpler to use it.
 		  ///
 		  /// Simplicity means that the way to change the types defined
 		  /// in the traits class is based on functions that returns the new class
 		  /// and not on templatable built-in classes.
 		  /// When using the plain \ref Dfs
 		  /// the new class with the modified type comes from
 		  /// the original class by using the ::
 		  /// operator. In the case of \ref DfsWizard only
 		  /// a function have to be called and it will
 		  /// return the needed class.
 		  ///
 		  /// It does not have own \ref run method. When its \ref run method is called
 		  /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
 		  /// method of it.
 		  template<class TR>
 		  class DfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the underlying digraph.
 		    typedef typename TR::Digraph Digraph;
 		    //\e
 		    typedef typename Digraph::Node Node;
 		    //\e
 		    typedef typename Digraph::NodeIt NodeIt;
 		    //\e
 		    typedef typename Digraph::Arc Arc;
 		    //\e
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\brief The type of the map that stores
 		    ///the reached nodes
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///\brief The type of the map that stores
 		    ///the processed nodes
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///\brief The type of the map that stores the last
 		    ///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;
 		  public:
 		    /// Constructor.
 		    DfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    DfsWizard(const Digraph &g, Node s=INVALID) :
 		      TR(g,s) {}
 		    ///Copy constructor
 		    DfsWizard(const TR &b) : TR(b) {}
@@ -971,427 +969,427 @@
 		      DefPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///function for setting PredMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///function for setting PredMap type
 		    ///
 		    template<class T>
 		    DfsWizard<DefPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<DefPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct DefReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      DefReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///function for setting ReachedMap
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///function for setting ReachedMap
 		    ///
 		    template<class T>
 		    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<DefReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct DefProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      DefProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///function for setting ProcessedMap
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///function for setting ProcessedMap
 		    ///
 		    template<class T>
 		    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<DefProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct DefDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      DefDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///function for setting DistMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///function for setting DistMap type
 		    ///
 		    template<class T>
 		    DfsWizard<DefDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<DefDistMapBase<T> >(*this);
+		    }
 		    /// Sets the source node, from which the Dfs algorithm runs.
 		    /// Sets the source node, from which the Dfs algorithm runs.
 		    /// \param s is the source node.
 		    DfsWizard<TR> &source(Node s)
+		    {
 		      Base::_source=s;
 		      return *this;
+		    }
 		  };
 		  ///Function type interface for Dfs algorithm.
 		  ///\ingroup search
 		  ///Function type interface for Dfs algorithm.
 		  ///
 		  ///This function also has several
 		  ///\ref named-templ-func-param "named parameters",
 		  ///they are declared as the members of class \ref DfsWizard.
 		  ///The following
 		  ///example shows how to use these parameters.
 		  ///\code
 		  ///  dfs(g,source).predMap(preds).run();
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
 		  ///to the end of the parameter list.
 		  ///\sa DfsWizard
 		  ///\sa Dfs
 		  template<class GR>
 		  DfsWizard<DfsWizardBase<GR> >
 		  dfs(const GR &g,typename GR::Node s=INVALID)
+		  {
 		    return DfsWizard<DfsWizardBase<GR> >(g,s);
+		  }
 		#ifdef DOXYGEN
 		  /// \brief Visitor class for dfs.
 		  ///
 		  /// It gives a simple interface for a functional interface for dfs
 		  /// traversal. The traversal on a linear data structure.
 		  template <typename _Digraph>
 		  struct DfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    /// \brief Called when the arc reach a node.
 		    ///
 		    /// It is called when the dfs find an arc which target is not
 		    /// reached yet.
 		    void discover(const Arc& arc) {}
 		    /// \brief Called when the node reached first time.
 		    ///
 		    /// It is Called when the node reached first time.
 		    void reach(const Node& node) {}
 		    /// \brief Called when we step back on an arc.
 		    ///
 		    /// It is called when the dfs should step back on the arc.
 		    void backtrack(const Arc& arc) {}
 		    /// \brief Called when we step back from the node.
 		    ///
 		    /// It is called when we step back from the node.
 		    void leave(const Node& node) {}
 		    /// \brief Called when the arc examined but target of the arc
 		    /// already discovered.
 		    ///
 		    /// It called when the arc examined but the target of the arc
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		    /// \brief Called for the source node of the dfs.
 		    ///
 		    /// It is called for the source node of the dfs.
 		    void start(const Node& node) {}
 		    /// \brief Called when we leave the source node of the dfs.
 		    ///
 		    /// It is called when we leave the source node of the dfs.
 		    void stop(const Node& node) {}
 		  };
 		#else
 		  template <typename _Digraph>
 		  struct DfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    void discover(const Arc&) {}
 		    void reach(const Node&) {}
 		    void backtrack(const Arc&) {}
 		    void leave(const Node&) {}
 		    void examine(const Arc&) {}
 		    void start(const Node&) {}
 		    void stop(const Node&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 			Arc arc;
 			Node node;
 			visitor.discover(arc);
 			visitor.reach(node);
 			visitor.backtrack(arc);
 			visitor.leave(node);
 			visitor.examine(arc);
 			visitor.start(node);
 			visitor.stop(arc);
+		      }
 		      _Visitor& visitor;
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of DfsVisit class.
 		  ///
 		  /// Default traits class of DfsVisit class.
-		  /// \param _Digraph Digraph type.
+		  /// \tparam _Digraph Digraph type.
 		  template<class _Digraph>
 		  struct DfsVisitDefaultTraits {
 		    /// \brief The digraph type 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::WriteMap "WriteMap" concept.
 		    /// \todo named parameter to set this type, function to read and write.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a 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);
+		    }
 		  };
 		  /// %DFS Visit algorithm class.
 		  /// \ingroup search
 		  /// 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
 		  /// on every dfs event the \c Visitor class member functions.
 		  ///
-		  /// \param _Digraph The digraph type the algorithm runs on. The default value is
+		  /// \tparam _Digraph The digraph type the algorithm runs on. The default value is
 		  /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
 		  /// is only passed to \ref DfsDefaultTraits.
-		  /// \param _Visitor The Visitor object for the algorithm. The
+		  /// \tparam _Visitor The Visitor object for the algorithm. The
 		  /// \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.
-		  /// \param _Traits Traits class to set various data types used by the
+		  /// \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.
 		  ///
 		  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
 		#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 algorithms.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw()
+		      {
 			return "lemon::DfsVisit::UninitializedParameter";
+		      }
 		    };
 		    typedef _Traits Traits;
 		    typedef typename Traits::Digraph Digraph;
 		    typedef _Visitor Visitor;
 		    ///The type of the map indicating 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 \ref _reached is locally allocated (\c true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Arc> _stack;
 		    int _stack_head;
 		    /// \brief Creates the maps if necessary.
 		    ///
 		    /// 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 DefReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 			throw UninitializedParameter();
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
 		    template <class T>
 		    struct DefReachedMap : public DfsVisit< Digraph, Visitor,
 							    DefReachedMapTraits<T> > {
 		      typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph the digraph the algorithm will run on.
 		    /// \param visitor The visitor of the algorithm.
 		    ///
 		    DfsVisit(const Digraph& digraph, Visitor& visitor)
 		      : _digraph(&digraph), _visitor(&visitor),
 			_reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ///
 		    /// Destructor.
 		    ~DfsVisit() {
 		      if(local_reached) delete _reached;
+		    }
 		    /// \brief Sets the map indicating if a node is reached.
 		    ///
 		    /// Sets the map indicating if a node is reached.
 		    /// If you don't use this function before calling \ref run(),
 		    /// it will allocate one. The destuctor 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 \c run(...).
 		    /// \n
 		    /// If you need more control on the execution,
 		    /// first you must call \ref init(), then you can adda source node
 		    /// with \ref addSource().
 		    /// Finally \ref 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);
+		      }
+		    }
 		    /// \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);
 			  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);

lemon/dijkstra.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_DIJKSTRA_H
 		#define LEMON_DIJKSTRA_H
 		///\ingroup shortest_path
 		///\file
 		///\brief Dijkstra algorithm.
 		///
 		#include <lemon/list_digraph.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/bits/invalid.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		namespace lemon {
 		  /// \brief Default OperationTraits for the Dijkstra algorithm class.
 		  ///
 		  /// It defines all computational operations and constants which are
 		  /// used in the Dijkstra algorithm.
 		  template <typename Value>
 		  struct DijkstraDefaultOperationTraits {
 		    /// \brief Gives back the zero value of the type.
 		    static Value zero() {
 		      return static_cast<Value>(0);
+		    }
 		    /// \brief Gives back the sum of the given two elements.
 		    static Value plus(const Value& left, const Value& right) {
 		      return left + right;
+		    }
 		    /// \brief Gives back true only if the first value less than the second.
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
 		  ///
 		  /// It defines all computational operations and constants which are
 		  /// used in the Dijkstra algorithm for widest path computation.
 		  template <typename Value>
 		  struct DijkstraWidestPathOperationTraits {
 		    /// \brief Gives back the maximum value of the type.
 		    static Value zero() {
 		      return std::numeric_limits<Value>::max();
+		    }
 		    /// \brief Gives back the minimum of the given two elements.
 		    static Value plus(const Value& left, const Value& right) {
 		      return std::min(left, right);
+		    }
 		    /// \brief Gives back true only if the first value less than the second.
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  ///Default traits class of Dijkstra class.
 		  ///Default traits class of Dijkstra class.
 		  ///\param GR Digraph type.
 		  ///\param LM Type of length map.
 		  ///\tparam GR Digraph type.
 		  ///\tparam LM Type of length map.
 		  template<class GR, class LM>
 		  struct DijkstraDefaultTraits
+		  {
 		    ///The digraph type the algorithm runs on.
 		    typedef GR Digraph;
 		    ///The type of the map that stores the arc lengths.
 		    ///The type of the map that stores the arc lengths.
 		    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LM LengthMap;
 		    //The type of the length of the arcs.
 		    typedef typename LM::Value Value;
 		    /// Operation traits for Dijkstra algorithm.
 		    /// It defines the used operation by the algorithm.
 		    /// \see DijkstraDefaultOperationTraits
 		    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
 		    /// The cross reference type used by heap.
 		    /// The cross reference type used by heap.
 		    /// Usually it is \c Digraph::NodeMap<int>.
 		    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		    ///Instantiates a HeapCrossRef.
 		    ///This function instantiates a \c HeapCrossRef.
 		    /// \param G is the digraph, to which we would like to define the
 		    /// HeapCrossRef.
 		    static HeapCrossRef *createHeapCrossRef(const GR &G)
+		    {
 		      return new HeapCrossRef(G);
+		    }
 		    ///The heap type used by Dijkstra algorithm.
 		    ///The heap type used by Dijkstra algorithm.
 		    ///
 		    ///\sa BinHeap
 		    ///\sa Dijkstra
 		    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
 		    static Heap *createHeap(HeapCrossRef& R)
+		    {
 		      return new Heap(R);
+		    }
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a \c PredMap.
 		    ///\param G is the digraph, to which we would like to define the PredMap.
 		    ///\todo The digraph alone may be insufficient for the initialization
 		    static PredMap *createPredMap(const GR &G)
+		    {
 		      return new PredMap(G);
+		    }
 		    ///The type of the map that stores whether a nodes is processed.
 		    ///The type of the map that stores whether a nodes is processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    ///\todo If it is set to a real map,
 		    ///Dijkstra::processed() should read this.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
 		    ///This function instantiates a \c ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \c ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const GR &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const GR &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that stores the dists of the nodes.
 		    ///The type of the map that stores the dists of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
 		    ///Instantiates a 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 GR &G)
+		    {
 		      return new DistMap(G);
+		    }
 		  };
 		  ///%Dijkstra algorithm class.
 		  /// \ingroup shortest_path
 		  ///This class provides an efficient implementation of %Dijkstra algorithm.
 		  ///The arc lengths are passed to the algorithm using a
 		  ///\ref concepts::ReadMap "ReadMap",
 		  ///so it is easy to change it to any kind of length.
 		  ///
 		  ///The type of the length is determined by the
 		  ///\ref concepts::ReadMap::Value "Value" of the length map.
 		  ///
 		  ///It is also possible to change the underlying priority heap.
 		  ///
-		  ///\param GR The digraph type the algorithm runs on. The default value
+		  ///\tparam GR The digraph type the algorithm runs on. The default value
 		  ///is \ref ListDigraph. The value of GR is not used directly by
 		  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
-		  ///\param LM This read-only ArcMap determines the lengths of the
+		  ///\tparam LM This read-only ArcMap determines the lengths of the
 		  ///arcs. It is read once for each arc, so the map may involve in
 		  ///relatively time consuming process to compute the arc length if
 		  ///it is necessary. The default map type is \ref
 		  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value
 		  ///of LM is not used directly by Dijkstra, it is only passed to \ref
-		  ///DijkstraDefaultTraits.  \param TR Traits class to set
 		  ///DijkstraDefaultTraits.
 		  ///\tparam TR Traits class to set
 		  ///various data types used by the algorithm.  The default traits
 		  ///class is \ref DijkstraDefaultTraits
 		  ///"DijkstraDefaultTraits<GR,LM>".  See \ref
 		  ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
 		  ///class.
 		  ///
 		  ///\author Jacint Szabo and Alpar Juttner
 		#ifdef DOXYGEN
 		  template <typename GR, typename LM, typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 			    typename LM=typename GR::template ArcMap<int>,
 			    typename TR=DijkstraDefaultTraits<GR,LM> >
 		#endif
 		  class Dijkstra {
 		  public:
 		    /**
 		     * \brief \ref Exception for uninitialized parameters.
+		     *
 		     * This error represents problems in the initialization
 		     * of the parameters of the algorithms.
 		     */
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 			return "lemon::Dijkstra::UninitializedParameter";
+		      }
 		    };
 		    typedef TR Traits;
 		    ///The type of the underlying digraph.
 		    typedef typename TR::Digraph Digraph;
 		    ///\e
 		    typedef typename Digraph::Node Node;
 		    ///\e
 		    typedef typename Digraph::NodeIt NodeIt;
 		    ///\e
 		    typedef typename Digraph::Arc Arc;
 		    ///\e
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///The type of the length of the arcs.
 		    typedef typename TR::LengthMap::Value Value;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map indicating if a node is processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the map that stores the dists of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The cross reference type used for the current heap.
 		    typedef typename TR::HeapCrossRef HeapCrossRef;
 		    ///The heap type used by the dijkstra algorithm.
 		    typedef typename TR::Heap Heap;
 		    ///The operation traits.
 		    typedef typename TR::OperationTraits OperationTraits;
 		  private:
 		    /// Pointer to the underlying digraph.
 		    const Digraph *G;
 		    /// Pointer to the length map
 		    const LengthMap *length;
 		    ///Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    ///Indicates if \ref _pred is locally allocated (\c true) or not.
 		    bool local_pred;
 		    ///Pointer to the map of distances.
 		    DistMap *_dist;
 		    ///Indicates if \ref _dist is locally allocated (\c true) or not.
 		    bool local_dist;
 		    ///Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    ///Indicates if \ref _processed is locally allocated (\c true) or not.
 		    bool local_processed;
 		    ///Pointer to the heap cross references.
 		    HeapCrossRef *_heap_cross_ref;
 		    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
 		    bool local_heap_cross_ref;
 		    ///Pointer to the heap.
 		    Heap *_heap;
 		    ///Indicates if \ref _heap is locally allocated (\c true) or not.
 		    bool local_heap;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    void create_maps()
+		    {
 		      if(!_pred) {
 			local_pred = true;
 			_pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 			local_dist = true;
 			_dist = Traits::createDistMap(*G);
+		      }
 		      if(!_processed) {
 			local_processed = true;
 			_processed = Traits::createProcessedMap(*G);
+		      }
 		      if (!_heap_cross_ref) {
 			local_heap_cross_ref = true;
 			_heap_cross_ref = Traits::createHeapCrossRef(*G);
+		      }
 		      if (!_heap) {
 			local_heap = true;
 			_heap = Traits::createHeap(*_heap_cross_ref);
+		      }
+		    }
 		  public :
 		    typedef Dijkstra Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct DefPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\ref named-templ-param "Named parameter" for setting PredMap type
 		    ///\ref named-templ-param "Named parameter" for setting PredMap type
 		    ///
 		    template <class T>
 		    struct DefPredMap
 		      : public Dijkstra< Digraph,	LengthMap, DefPredMapTraits<T> > {
 		      typedef Dijkstra< Digraph,	LengthMap, DefPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct DefDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\ref named-templ-param "Named parameter" for setting DistMap type
 		    ///\ref named-templ-param "Named parameter" for setting DistMap type
 		    ///
 		    template <class T>
 		    struct DefDistMap
 		      : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct DefProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &G)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
 		    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
 		    ///
 		    template <class T>
 		    struct DefProcessedMap
 		      : public Dijkstra< Digraph,	LengthMap, DefProcessedMapTraits<T> > {
 		      typedef Dijkstra< Digraph,	LengthMap, DefProcessedMapTraits<T> > Create;
 		    };
 		    struct DefDigraphProcessedMapTraits : 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 the ProcessedMap type to be Digraph::NodeMap<bool>.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
 		    ///If you don't set it explicitely, it will be automatically allocated.
 		    template <class T>
 		    struct DefProcessedMapToBeDefaultMap
 		      : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
 		      typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> Create;
 		    };
 		    template <class H, class CR>
 		    struct DefHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
 			throw UninitializedParameter();
@@ -686,386 +685,386 @@
 		    ///\pre init() must be called and at least one node should be added
 		    ///with addSource() before using this function.
 		    ///
 		    ///This method runs the %Dijkstra algorithm from the root node(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(s).
 		    ///
 		    void start()
+		    {
 		      while ( !_heap->empty() ) processNextNode();
+		    }
 		    ///Executes the algorithm until \c dest is reached.
 		    ///Executes the algorithm until \c dest is reached.
 		    ///
 		    ///\pre init() must be called and at least one node should be added
 		    ///with addSource() before using this function.
 		    ///
 		    ///This method runs the %Dijkstra algorithm from the root node(s)
 		    ///in order to
 		    ///compute the
 		    ///shortest path to \c dest. The algorithm computes
 		    ///- The shortest path to \c  dest.
 		    ///- The distance of \c dest from the root(s).
 		    ///
 		    void start(Node dest)
+		    {
 		      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
 		      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
+		    }
 		    ///Executes the algorithm until a condition is met.
 		    ///Executes the algorithm until a condition is met.
 		    ///
 		    ///\pre init() must be called and at least one node should be added
 		    ///with addSource() before using this function.
 		    ///
 		    ///\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.
 		    template<class NodeBoolMap>
 		    Node start(const NodeBoolMap &nm)
+		    {
 		      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
 		      if ( _heap->empty() ) return INVALID;
 		      finalizeNodeData(_heap->top(),_heap->prio());
 		      return _heap->top();
+		    }
 		    ///Runs %Dijkstra algorithm from node \c s.
 		    ///This method runs the %Dijkstra algorithm from a root 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 d.run(s) 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 shortest path between \c s and \c t.
 		    ///Finds the shortest path between \c s and \c t.
 		    ///
 		    ///\return The length of the shortest s---t path if there exists one,
 		    ///0 otherwise.
 		    ///\note Apart from the return value, d.run(s) is
 		    ///just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start(t);
 		    ///\endcode
 		    Value run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The result of the %Dijkstra algorithm can be obtained using these
 		    ///functions.\n
 		    ///Before the use of these functions,
 		    ///either run() or start() must be called.
 		    ///@{
 		    ///Gives back the shortest path.
 		    ///Gives back the shortest path.
 		    ///\pre The \c t should be reachable from the source.
 		    Path path(Node t)
+		    {
 		      return Path(*G, *_pred, t);
+		    }
 		    ///The distance of a node from the root.
 		    ///Returns the distance of a node from the root.
 		    ///\pre \ref run() must be called before using this function.
 		    ///\warning If node \c v in unreachable from the root the return value
 		    ///of this funcion is undefined.
 		    Value dist(Node v) const { return (*_dist)[v]; }
 		    ///The current distance of a node from the root.
 		    ///Returns the current distance of a node from the root.
 		    ///It may be decreased in the following processes.
 		    ///\pre \c node should be reached but not processed
 		    Value currentDist(Node v) const { return (*_heap)[v]; }
 		    ///Returns the 'previous arc' of the shortest path tree.
 		    ///For a node \c v it returns the 'previous arc' of the shortest path tree,
 		    ///i.e. it returns the last arc of a shortest path from the root to \c
 		    ///v. It is \ref INVALID
 		    ///if \c v is unreachable from the root or if \c v=s. The
 		    ///shortest path tree used here is equal to the shortest path tree used in
 		    ///\ref predNode().  \pre \ref run() 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 \c v it returns the 'previous node' of the shortest path tree,
 		    ///i.e. it returns the last but one node from a shortest path from the
 		    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
 		    ///\c v=s. The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predArc().  \pre \ref run() must be called before
 		    ///using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 						  G->source((*_pred)[v]); }
 		    ///Returns a reference to the NodeMap of distances.
 		    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
 		    ///be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///Returns a reference to the shortest path tree map.
 		    ///Returns a reference to the NodeMap of the arcs of the
 		    ///shortest path tree.
 		    ///\pre \ref run() must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if a node is reachable from the root.
 		    ///Returns \c true if \c v is reachable from the root.
 		    ///\warning The source nodes are inditated as unreached.
 		    ///\pre \ref run() must be called before using this function.
 		    ///
 		    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
 		    ///Checks if a node is processed.
 		    ///Returns \c true if \c v is processed, i.e. the shortest
 		    ///path to \c v has already found.
 		    ///\pre \ref run() must be called before using this function.
 		    ///
 		    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
 		    ///@}
 		  };
 		  ///Default traits class of Dijkstra function.
 		  ///Default traits class of Dijkstra function.
 		  ///\param GR Digraph type.
 		  ///\param LM Type of length map.
 		  ///\tparam GR Digraph type.
 		  ///\tparam LM Type of length map.
 		  template<class GR, class LM>
 		  struct DijkstraWizardDefaultTraits
+		  {
 		    ///The digraph type the algorithm runs on.
 		    typedef GR Digraph;
 		    ///The type of the map that stores the arc lengths.
 		    ///The type of the map that stores the arc lengths.
 		    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LM LengthMap;
 		    //The type of the length of the arcs.
 		    typedef typename LM::Value Value;
 		    /// Operation traits for Dijkstra algorithm.
 		    /// It defines the used operation by the algorithm.
 		    /// \see DijkstraDefaultOperationTraits
 		    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
 		    ///The heap type used by Dijkstra algorithm.
 		    /// The cross reference type used by heap.
 		    /// The cross reference type used by heap.
 		    /// Usually it is \c Digraph::NodeMap<int>.
 		    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		    ///Instantiates a HeapCrossRef.
 		    ///This function instantiates a \ref HeapCrossRef.
 		    /// \param G is the digraph, to which we would like to define the
 		    /// HeapCrossRef.
 		    /// \todo The digraph alone may be insufficient for the initialization
 		    static HeapCrossRef *createHeapCrossRef(const GR &G)
+		    {
 		      return new HeapCrossRef(G);
+		    }
 		    ///The heap type used by Dijkstra algorithm.
 		    ///The heap type used by Dijkstra algorithm.
 		    ///
 		    ///\sa BinHeap
 		    ///\sa Dijkstra
 		    typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
 				    std::less<Value> > Heap;
 		    static Heap *createHeap(HeapCrossRef& R)
+		    {
 		      return new Heap(R);
+		    }
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the PredMap.
 		    ///\todo The digraph alone may be insufficient for the initialization
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const GR &g)
 		#else
 		    static PredMap *createPredMap(const GR &)
 		#endif
+		    {
 		      return new PredMap();
+		    }
 		    ///The type of the map that stores whether a nodes is processed.
 		    ///The type of the map that stores whether a nodes is processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    ///\todo If it is set to a real map,
 		    ///Dijkstra::processed() should read this.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a 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 GR &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const GR &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that stores the dists of the nodes.
 		    ///The type of the map that stores the dists of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
 		    ///Instantiates a DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const GR &g)
 		#else
 		    static DistMap *createDistMap(const GR &)
 		#endif
+		    {
 		      return new DistMap();
+		    }
 		  };
 		  /// Default traits used by \ref DijkstraWizard
 		  /// To make it easier to use Dijkstra algorithm
 		  ///we have created a wizard class.
 		  /// This \ref DijkstraWizard class needs default traits,
 		  ///as well as the \ref Dijkstra class.
 		  /// The \ref DijkstraWizardBase is a class to be the default traits of the
 		  /// \ref DijkstraWizard class.
 		  /// \todo More named parameters are required...
 		  template<class GR,class LM>
 		  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
+		  {
 		    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
 		  protected:
 		    /// Type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    /// Pointer to the underlying digraph.
 		    void *_g;
 		    /// Pointer to the length map
 		    void *_length;
 		    ///Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    ///Pointer to the map of distances.
 		    void *_dist;
 		    ///Pointer to the source node.
 		    Node _source;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to default values (0, INVALID).
 		    DijkstraWizardBase() : _g(0), _length(0), _pred(0),
 					   _dist(0), _source(INVALID) {}
 		    /// Constructor.
 		    /// This constructor requires some parameters,
 		    /// listed in the parameters list.
 		    /// Others are initiated to 0.
 		    /// \param g is the initial value of  \ref _g
 		    /// \param l is the initial value of  \ref _length
 		    /// \param s is the initial value of  \ref _source
 		    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
 		      _pred(0), _dist(0), _source(s) {}
 		  };
 		  /// A class to make the usage of Dijkstra algorithm easier
 		  /// This class is created to make it easier to use Dijkstra algorithm.
 		  /// It uses the functions and features of the plain \ref Dijkstra,
 		  /// but it is much simpler to use it.
 		  ///
 		  /// Simplicity means that the way to change the types defined
 		  /// in the traits class is based on functions that returns the new class
 		  /// and not on templatable built-in classes.
 		  /// When using the plain \ref Dijkstra
 		  /// the new class with the modified type comes from
 		  /// the original class by using the ::
 		  /// operator. In the case of \ref DijkstraWizard only
 		  /// a function have to be called and it will
 		  /// return the needed class.
 		  ///
 		  /// It does not have own \ref run method. When its \ref run method is called
 		  /// it initiates a plain \ref Dijkstra class, and calls the \ref
 		  /// Dijkstra::run method of it.
 		  template<class TR>
 		  class DijkstraWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the underlying digraph.
 		    typedef typename TR::Digraph Digraph;
 		    //\e
 		    typedef typename Digraph::Node Node;

lemon/graph_to_eps.h

Show inline comments

@@ -227,433 +227,433 @@
 		  using T::DIST_BW;
 		  using T::_nodeTextColorType;
 		  using T::_nodeTextColors;
 		  using T::_autoNodeScale;
 		  using T::_autoArcWidthScale;
 		  using T::_absoluteNodeSizes;
 		  using T::_absoluteArcWidths;
 		  using T::_negY;
 		  using T::_preScale;
 		  // dradnats ++C eht yb deriuqer si ti eveileb t'naC
 		  typedef typename T::Graph Graph;
 		  typedef typename Graph::Node Node;
 		  typedef typename Graph::NodeIt NodeIt;
 		  typedef typename Graph::Arc Arc;
 		  typedef typename Graph::ArcIt ArcIt;
 		  typedef typename Graph::InArcIt InArcIt;
 		  typedef typename Graph::OutArcIt OutArcIt;
 		  static const int INTERPOL_PREC;
 		  static const double A4HEIGHT;
 		  static const double A4WIDTH;
 		  static const double A4BORDER;
 		  bool dontPrint;
 		public:
 		  ///Node shapes
 		  ///Node shapes
 		  ///
 		  enum NodeShapes {
 		    /// = 0
 		    ///\image html nodeshape_0.png
 		    ///\image latex nodeshape_0.eps "CIRCLE shape (0)" width=2cm
 		    CIRCLE=0,
 		    /// = 1
 		    ///\image html nodeshape_1.png
 		    ///\image latex nodeshape_1.eps "SQUARE shape (1)" width=2cm
 		    ///
 		    SQUARE=1,
 		    /// = 2
 		    ///\image html nodeshape_2.png
 		    ///\image latex nodeshape_2.eps "DIAMOND shape (2)" width=2cm
 		    ///
 		    DIAMOND=2,
 		    /// = 3
 		    ///\image html nodeshape_3.png
 		    ///\image latex nodeshape_2.eps "MALE shape (4)" width=2cm
 		    ///
 		    MALE=3,
 		    /// = 4
 		    ///\image html nodeshape_4.png
 		    ///\image latex nodeshape_2.eps "FEMALE shape (4)" width=2cm
 		    ///
 		    FEMALE=4
 		  };
 		private:
 		  class arcLess {
 		    const Graph &g;
 		  public:
 		    arcLess(const Graph &_g) : g(_g) {}
 		    bool operator()(Arc a,Arc b) const
+		    {
 		      Node ai=std::min(g.source(a),g.target(a));
 		      Node aa=std::max(g.source(a),g.target(a));
 		      Node bi=std::min(g.source(b),g.target(b));
 		      Node ba=std::max(g.source(b),g.target(b));
 		      return ai<bi ||
 			(ai==bi && (aa < ba ||
 				    (aa==ba && ai==g.source(a) && bi==g.target(b))));
+		    }
 		  };
 		  bool isParallel(Arc e,Arc f) const
+		  {
 		    return (g.source(e)==g.source(f)&&
 			    g.target(e)==g.target(f)) ||
 		      (g.source(e)==g.target(f)&&
 		       g.target(e)==g.source(f));
+		  }
 		  template<class TT>
 		  static std::string psOut(const dim2::Point<TT> &p)
+		    {
 		      std::ostringstream os;
 		      os << p.x << ' ' << p.y;
 		      return os.str();
+		    }
 		  static std::string psOut(const Color &c)
+		    {
 		      std::ostringstream os;
 		      os << c.red() << ' ' << c.green() << ' ' << c.blue();
 		      return os.str();
+		    }
 		public:
 		  GraphToEps(const T &t) : T(t), dontPrint(false) {};
 		  template<class X> struct CoordsTraits : public T {
 		  typedef X CoordsMapType;
 		    const X &_coords;
 		    CoordsTraits(const T &t,const X &x) : T(t), _coords(x) {}
 		  };
 		  ///Sets the map of the node coordinates
 		  ///Sets the map of the node coordinates.
 		  ///\param x must be a node map with dim2::Point<double> or
 		  ///\ref dim2::Point "dim2::Point<int>" values.
 		  template<class X> GraphToEps<CoordsTraits<X> > coords(const X &x) {
 		    dontPrint=true;
 		    return GraphToEps<CoordsTraits<X> >(CoordsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeSizesTraits : public T {
 		    const X &_nodeSizes;
 		    NodeSizesTraits(const T &t,const X &x) : T(t), _nodeSizes(x) {}
 		  };
 		  ///Sets the map of the node sizes
 		  ///Sets the map of the node sizes
 		  ///\param x must be a node map with \c double (or convertible) values.
 		  template<class X> GraphToEps<NodeSizesTraits<X> > nodeSizes(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeSizesTraits<X> >(NodeSizesTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeShapesTraits : public T {
 		    const X &_nodeShapes;
 		    NodeShapesTraits(const T &t,const X &x) : T(t), _nodeShapes(x) {}
 		  };
 		  ///Sets the map of the node shapes
 		  ///Sets the map of the node shapes.
 		  ///The available shape values
 		  ///can be found in \ref NodeShapes "enum NodeShapes".
 		  ///\param x must be a node map with \c int (or convertible) values.
 		  ///\sa NodeShapes
 		  template<class X> GraphToEps<NodeShapesTraits<X> > nodeShapes(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeShapesTraits<X> >(NodeShapesTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeTextsTraits : public T {
 		    const X &_nodeTexts;
 		    NodeTextsTraits(const T &t,const X &x) : T(t), _nodeTexts(x) {}
 		  };
 		  ///Sets the text printed on the nodes
 		  ///Sets the text printed on the nodes
 		  ///\param x must be a node map with type that can be pushed to a standard
 		  ///ostream.
 		  template<class X> GraphToEps<NodeTextsTraits<X> > nodeTexts(const X &x)
+		  {
 		    dontPrint=true;
 		    _showNodeText=true;
 		    return GraphToEps<NodeTextsTraits<X> >(NodeTextsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodePsTextsTraits : public T {
 		    const X &_nodePsTexts;
 		    NodePsTextsTraits(const T &t,const X &x) : T(t), _nodePsTexts(x) {}
 		  };
 		  ///Inserts a PostScript block to the nodes
 		  ///With this command it is possible to insert a verbatim PostScript
 		  ///block to the nodes.
 		  ///The PS current point will be moved to the centre of the node before
 		  ///the PostScript block inserted.
 		  ///
 		  ///Before and after the block a newline character is inserted so you
 		  ///don't have to bother with the separators.
 		  ///
 		  ///\param x must be a node map with type that can be pushed to a standard
 		  ///ostream.
 		  ///
 		  ///\sa nodePsTextsPreamble()
 		  template<class X> GraphToEps<NodePsTextsTraits<X> > nodePsTexts(const X &x)
+		  {
 		    dontPrint=true;
 		    _showNodePsText=true;
 		    return GraphToEps<NodePsTextsTraits<X> >(NodePsTextsTraits<X>(*this,x));
+		  }
 		  template<class X> struct ArcWidthsTraits : public T {
 		    const X &_arcWidths;
 		    ArcWidthsTraits(const T &t,const X &x) : T(t), _arcWidths(x) {}
 		  };
 		  ///Sets the map of the arc widths
 		  ///Sets the map of the arc widths
-		  ///\param x must be a arc map with \c double (or convertible) values.
+		  ///\param x must be an arc map with \c double (or convertible) values.
 		  template<class X> GraphToEps<ArcWidthsTraits<X> > arcWidths(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<ArcWidthsTraits<X> >(ArcWidthsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeColorsTraits : public T {
 		    const X &_nodeColors;
 		    NodeColorsTraits(const T &t,const X &x) : T(t), _nodeColors(x) {}
 		  };
 		  ///Sets the map of the node colors
 		  ///Sets the map of the node colors
 		  ///\param x must be a node map with \ref Color values.
 		  ///
 		  ///\sa Palette
 		  template<class X> GraphToEps<NodeColorsTraits<X> >
 		  nodeColors(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeColorsTraits<X> >(NodeColorsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeTextColorsTraits : public T {
 		    const X &_nodeTextColors;
 		    NodeTextColorsTraits(const T &t,const X &x) : T(t), _nodeTextColors(x) {}
 		  };
 		  ///Sets the map of the node text colors
 		  ///Sets the map of the node text colors
 		  ///\param x must be a node map with \ref Color values.
 		  ///
 		  ///\sa Palette
 		  template<class X> GraphToEps<NodeTextColorsTraits<X> >
 		  nodeTextColors(const X &x)
+		  {
 		    dontPrint=true;
 		    _nodeTextColorType=CUST_COL;
 		    return GraphToEps<NodeTextColorsTraits<X> >
 		      (NodeTextColorsTraits<X>(*this,x));
+		  }
 		  template<class X> struct ArcColorsTraits : public T {
 		    const X &_arcColors;
 		    ArcColorsTraits(const T &t,const X &x) : T(t), _arcColors(x) {}
 		  };
 		  ///Sets the map of the arc colors
 		  ///Sets the map of the arc colors
-		  ///\param x must be a arc map with \ref Color values.
+		  ///\param x must be an arc map with \ref Color values.
 		  ///
 		  ///\sa Palette
 		  template<class X> GraphToEps<ArcColorsTraits<X> >
 		  arcColors(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<ArcColorsTraits<X> >(ArcColorsTraits<X>(*this,x));
+		  }
 		  ///Sets a global scale factor for node sizes
 		  ///Sets a global scale factor for node sizes.
 		  ///
 		  /// If nodeSizes() is not given, this function simply sets the node
 		  /// sizes to \c d.  If nodeSizes() is given, but
 		  /// autoNodeScale() is not, then the node size given by
 		  /// nodeSizes() will be multiplied by the value \c d.
 		  /// If both nodeSizes() and autoNodeScale() are used, then the
 		  /// node sizes will be scaled in such a way that the greatest size will be
 		  /// equal to \c d.
 		  /// \sa nodeSizes()
 		  /// \sa autoNodeScale()
 		  GraphToEps<T> &nodeScale(double d=.01) {_nodeScale=d;return *this;}
 		  ///Turns on/off the automatic node width scaling.
 		  ///Turns on/off the automatic node width scaling.
 		  ///
 		  ///\sa nodeScale()
 		  ///
 		  GraphToEps<T> &autoNodeScale(bool b=true) {
 		    _autoNodeScale=b;return *this;
+		  }
 		  ///Turns on/off the absolutematic node width scaling.
 		  ///Turns on/off the absolutematic node width scaling.
 		  ///
 		  ///\sa nodeScale()
 		  ///
 		  GraphToEps<T> &absoluteNodeSizes(bool b=true) {
 		    _absoluteNodeSizes=b;return *this;
+		  }
 		  ///Negates the Y coordinates.
 		  ///Negates the Y coordinates.
 		  ///
 		  GraphToEps<T> &negateY(bool b=true) {
 		    _negY=b;return *this;
+		  }
 		  ///Turn on/off pre-scaling
 		  ///By default graphToEps() rescales the whole image in order to avoid
 		  ///very big or very small bounding boxes.
 		  ///
 		  ///This (p)rescaling can be turned off with this function.
 		  ///
 		  GraphToEps<T> &preScale(bool b=true) {
 		    _preScale=b;return *this;
+		  }
 		  ///Sets a global scale factor for arc widths
 		  /// Sets a global scale factor for arc widths.
 		  ///
 		  /// If arcWidths() is not given, this function simply sets the arc
 		  /// widths to \c d.  If arcWidths() is given, but
 		  /// autoArcWidthScale() is not, then the arc withs given by
 		  /// arcWidths() will be multiplied by the value \c d.
 		  /// If both arcWidths() and autoArcWidthScale() are used, then the
 		  /// arc withs will be scaled in such a way that the greatest width will be
 		  /// equal to \c d.
 		  GraphToEps<T> &arcWidthScale(double d=.003) {_arcWidthScale=d;return *this;}
 		  ///Turns on/off the automatic arc width scaling.
 		  ///Turns on/off the automatic arc width scaling.
 		  ///
 		  ///\sa arcWidthScale()
 		  ///
 		  GraphToEps<T> &autoArcWidthScale(bool b=true) {
 		    _autoArcWidthScale=b;return *this;
+		  }
 		  ///Turns on/off the absolutematic arc width scaling.
 		  ///Turns on/off the absolutematic arc width scaling.
 		  ///
 		  ///\sa arcWidthScale()
 		  ///
 		  GraphToEps<T> &absoluteArcWidths(bool b=true) {
 		    _absoluteArcWidths=b;return *this;
+		  }
 		  ///Sets a global scale factor for the whole picture
 		  ///Sets a global scale factor for the whole picture
 		  ///
 		  GraphToEps<T> &scale(double d) {_scale=d;return *this;}
 		  ///Sets the width of the border around the picture
 		  ///Sets the width of the border around the picture
 		  ///
 		  GraphToEps<T> &border(double b=10) {_xBorder=_yBorder=b;return *this;}
 		  ///Sets the width of the border around the picture
 		  ///Sets the width of the border around the picture
 		  ///
 		  GraphToEps<T> &border(double x, double y) {
 		    _xBorder=x;_yBorder=y;return *this;
+		  }
 		  ///Sets whether to draw arrows
 		  ///Sets whether to draw arrows
 		  ///
 		  GraphToEps<T> &drawArrows(bool b=true) {_drawArrows=b;return *this;}
 		  ///Sets the length of the arrowheads
 		  ///Sets the length of the arrowheads
 		  ///
 		  GraphToEps<T> &arrowLength(double d=1.0) {_arrowLength*=d;return *this;}
 		  ///Sets the width of the arrowheads
 		  ///Sets the width of the arrowheads
 		  ///
 		  GraphToEps<T> &arrowWidth(double d=.3) {_arrowWidth*=d;return *this;}
 		  ///Scales the drawing to fit to A4 page
 		  ///Scales the drawing to fit to A4 page
 		  ///
 		  GraphToEps<T> &scaleToA4() {_scaleToA4=true;return *this;}
 		  ///Enables parallel arcs
 		  ///Enables parallel arcs
 		  GraphToEps<T> &enableParallel(bool b=true) {_enableParallel=b;return *this;}
 		  ///Sets the distance
 		  ///Sets the distance
 		  ///
 		  GraphToEps<T> &parArcDist(double d) {_parArcDist*=d;return *this;}
 		  ///Hides the arcs
 		  ///Hides the arcs
 		  ///
 		  GraphToEps<T> &hideArcs(bool b=true) {_showArcs=!b;return *this;}
 		  ///Hides the nodes
 		  ///Hides the nodes
 		  ///
 		  GraphToEps<T> &hideNodes(bool b=true) {_showNodes=!b;return *this;}
 		  ///Sets the size of the node texts
 		  ///Sets the size of the node texts
 		  ///
 		  GraphToEps<T> &nodeTextSize(double d) {_nodeTextSize=d;return *this;}
 		  ///Sets the color of the node texts to be different from the node color
 		  ///Sets the color of the node texts to be as different from the node color
 		  ///as it is possible
 		  ///
 		  GraphToEps<T> &distantColorNodeTexts()
 		  {_nodeTextColorType=DIST_COL;return *this;}
 		  ///Sets the color of the node texts to be black or white and always visible.
 		  ///Sets the color of the node texts to be black or white according to
 		  ///which is more
 		  ///different from the node color
 		  ///
 		  GraphToEps<T> &distantBWNodeTexts()
 		  {_nodeTextColorType=DIST_BW;return *this;}
 		  ///Gives a preamble block for node Postscript block.
 		  ///Gives a preamble block for node Postscript block.
 		  ///
 		  ///\sa nodePsTexts()
 		  GraphToEps<T> & nodePsTextsPreamble(const char *str) {
 		    _nodePsTextsPreamble=str ;return *this;
+		  }
 		  ///Sets whether the the graph is undirected
 		  ///Sets whether the the graph is undirected.
 		  ///
 		  ///This setting is the default for undirected graphs.
 		  ///
 		  ///\sa directed()
 		   GraphToEps<T> &undirected(bool b=true) {_undirected=b;return *this;}

lemon/graph_utils.h

Show inline comments

@@ -165,510 +165,506 @@
 		  ///
 		  /// If the graph contains a \e nodeNum() member function and a
 		  /// \e 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 _graph_utils_bits::CountNodesSelector<Graph>::count(g);
+		  }
 		  // Arc counting:
 		  namespace _graph_utils_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).
 		  ///
 		  /// If the graph contains a \e arcNum() member function and a
 		  /// \e EdgeNumTag 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 _graph_utils_bits::CountArcsSelector<Graph>::count(g);
+		  }
 		  // Edge counting:
 		  namespace _graph_utils_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).
 		  ///
 		  /// If the graph contains a \e edgeNum() member function and a
 		  /// \e 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 _graph_utils_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.
 		  template <typename Graph>
 		  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.
 		  template <typename Graph>
 		  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.
 		  template <typename Graph>
 		  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
 		    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
+		  }
 		  namespace _graph_utils_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>
+		    {
 		      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.
 		  ///
 		  /// Finds an arc from node \c u to node \c v in graph \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)) {
 		  ///   ...
 		  /// }
 		  ///\endcode
 		  ///
 		  ///\sa ArcLookUp
 		  ///\sa AllArcLookUp
 		  ///\sa DynArcLookUp
 		  ///\sa ConArcIt
 		  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 _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
+		  }
 		  /// \brief Iterator for iterating on arcs connected the same nodes.
 		  ///
 		  /// Iterator for iterating on arcs connected the same nodes. It is
 		  /// higher level interface for the 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
 		  ///
 		  /// \author Balazs Dezso
 		  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.
 		    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.
 		    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 _graph_utils_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.source(e) == u;
 		            g.nextInc(e, b);
+		          }
 		          while (e != INVALID && (b ? g.target(e) : g.source(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.target(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.
 		  ///
 		  /// 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
 		  /// 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.
 		  ///
 		  /// Thus you can iterate through each arc from \c u to \c v as it follows.
 		  ///\code
 		  /// for(Edge e = findEdge(g,u,v); e != INVALID;
 		  ///     e = findEdge(g,u,v,e)) {
 		  ///   ...
 		  /// }
 		  ///\endcode
 		  ///
 		  ///\sa ConArcIt
 		  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 _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
+		  }
 		  /// \brief Iterator for iterating on edges connected the same nodes.
 		  ///
 		  /// Iterator for iterating on edges connected the same nodes. It is
 		  /// 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) {
 		  ///   ...
 		  /// }
 		  ///\endcode
 		  ///
 		  ///\sa findEdge()
 		  ///
 		  /// \author Balazs Dezso
 		  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.
 		    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.
 		    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.source(*this),
 						 _graph.target(*this), *this));
 		      return *this;
+		    }
 		  private:
 		    const Graph& _graph;
 		  };
 		  namespace _graph_utils_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>
 		    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
 		    public:
 		      MapCopy(ToMap& tmap, const FromMap& map)
 		        : _tmap(tmap), _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) {
 		          _tmap.set(refMap[it], _map[it]);
+		        }
+		      }
 		    private:
 		      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) {}
 		      virtual void copy(const Digraph&, const RefMap& refMap) {
 		        _it = refMap[_item];
+		      }
 		    private:
 		      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,
 		                       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,
 		                       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,
 		                       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.addArc(nodeRefMap[from.source(it)],
 						       nodeRefMap[from.target(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,
 		                       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.
 		  ///
 		  /// This class not just make a copy of a graph, 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.
 		  ///
 		  /// To make a copy from a graph, first an instance of DigraphCopy
 		  /// 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
 		  ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
 		  ///  // create a reference for the nodes
 		  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
@@ -1053,1239 +1049,1235 @@
 					  ArcRefMap, TArc>(tarc, sarc));
 		      return *this;
+		    }
 		    /// \brief Copies the edge references into the given map.
 		    ///
 		    /// Copies the edge references into the given map.
 		    template <typename EdgeRef>
 		    GraphCopy& edgeRef(EdgeRef& map) {
 		      _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
 					   EdgeRefMap, EdgeRef>(map));
 		      return *this;
+		    }
 		    /// \brief Copies the edge cross references into the given map.
 		    ///
 		    /// Copies the edge cross references (reverse
 		    /// references) into the given map.
 		    template <typename EdgeCrossRef>
 		    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
 		      _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
 					   Edge, EdgeRefMap, EdgeCrossRef>(map));
 		      return *this;
+		    }
 		    /// \brief Make copy of the given 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) {
 		      _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
 					   EdgeRefMap, ToMap, FromMap>(tmap, map));
 		      return *this;
+		    }
 		    /// \brief Make a copy of the given edge.
 		    ///
 		    /// Make a copy of the given edge.
 		    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
 		      _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
 					   EdgeRefMap, TEdge>(tedge, sedge));
 		      return *this;
+		    }
 		    /// \brief Executes the copies.
 		    ///
 		    /// Executes the copies.
 		    void run() {
 		      NodeRefMap nodeRefMap(_from);
 		      EdgeRefMap edgeRefMap(_from);
 		      ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
 		      _graph_utils_bits::GraphCopySelector<To>::
 		        copy(_to, _from, 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<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
 		    _node_maps;
 		    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
 		    _arc_maps;
 		    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
 		    _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:
 		  ///\code
 		  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(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.
 		  ///
 		  /// \see GraphCopy
 		  template <typename To, typename From>
 		  GraphCopy<To, From>
 		  copyGraph(To& to, const From& from) {
 		    return GraphCopy<To, From>(to, from);
+		  }
 		  /// @}
 		  /// \addtogroup graph_maps
 		  /// @{
 		  /// Provides an immutable and unique id for each item in the graph.
 		  /// The IdMap class provides a unique and immutable id for each item of the
 		  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
 		  /// different items (nodes) get different ids <li>\b immutable: the id of an
 		  /// item (node) does not change (even if you delete other nodes).  </ul>
 		  /// Through this map you get access (i.e. can read) the inner id values of
 		  /// the items stored in the graph. This map can be inverted with its member
 		  /// class \c InverseMap or with the \c operator() member.
 		  ///
 		  template <typename _Graph, typename _Item>
 		  class IdMap {
 		  public:
 		    typedef _Graph Graph;
 		    typedef int Value;
 		    typedef _Item Item;
 		    typedef _Item Key;
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor of the map.
 		    explicit IdMap(const Graph& graph) : _graph(&graph) {}
 		    /// \brief Gives back the \e id of the item.
 		    ///
 		    /// Gives back the immutable and unique \e id of the item.
 		    int operator[](const Item& item) const { return _graph->id(item);}
 		    /// \brief Gives back the item by its id.
 		    ///
 		    /// Gives back the item by its id.
 		    Item operator()(int id) { return _graph->fromId(id, Item()); }
 		  private:
 		    const Graph* _graph;
 		  public:
 		    /// \brief The class represents the inverse of its owner (IdMap).
 		    ///
 		    /// The class represents the inverse of its owner (IdMap).
 		    /// \see inverse()
 		    class InverseMap {
 		    public:
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor for creating an id-to-item map.
 		      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor for creating an id-to-item map.
 		      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
 		      /// \brief Gives back the given item from its id.
 		      ///
 		      /// Gives back the given item from its id.
 		      ///
 		      Item operator[](int id) const { return _graph->fromId(id, Item());}
 		    private:
 		      const Graph* _graph;
 		    };
 		    /// \brief Gives back the inverse of the map.
 		    ///
 		    /// Gives back the inverse of the IdMap.
 		    InverseMap inverse() const { return InverseMap(*_graph);}
 		  };
 		  /// \brief General invertable graph-map type.
 		  /// This type provides simple invertable graph-maps.
 		  /// The InvertableMap wraps an arbitrary ReadWriteMap
 		  /// and if a key is set to a new value then store it
 		  /// in the inverse map.
 		  ///
 		  /// The values of the map can be accessed
 		  /// with stl compatible forward iterator.
 		  ///
 		  /// \param _Graph The graph type.
 		  /// \param _Item The item type of the graph.
-		  /// \param _Value The value type of the map.
+		  /// \tparam _Graph The graph type.
 		  /// \tparam _Item The item type of the graph.
 		  /// \tparam _Value The value type of the map.
 		  ///
 		  /// \see IterableValueMap
 		  template <typename _Graph, typename _Item, typename _Value>
 		  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
 		  private:
 		    typedef DefaultMap<_Graph, _Item, _Value> Map;
 		    typedef _Graph Graph;
 		    typedef std::map<_Value, _Item> Container;
 		    Container _inv_map;
 		  public:
 		    /// The key type of InvertableMap (Node, Arc, Edge).
 		    typedef typename Map::Key Key;
 		    /// The value type of the InvertableMap.
 		    typedef typename Map::Value Value;
 		    /// \brief Constructor.
 		    ///
 		    /// Construct a new InvertableMap for the graph.
 		    ///
 		    explicit InvertableMap(const Graph& graph) : Map(graph) {}
 		    /// \brief Forward iterator for values.
 		    ///
 		    /// This iterator is an stl compatible forward
 		    /// iterator on the values of the map. The values can
 		    /// be accessed in the [beginValue, endValue) range.
 		    ///
 		    class ValueIterator
 		      : public std::iterator<std::forward_iterator_tag, Value> {
 		      friend class InvertableMap;
 		    private:
 		      ValueIterator(typename Container::const_iterator _it)
 		        : it(_it) {}
 		    public:
 		      ValueIterator() {}
 		      ValueIterator& operator++() { ++it; return *this; }
 		      ValueIterator operator++(int) {
 		        ValueIterator tmp(*this);
 		        operator++();
 		        return tmp;
+		      }
 		      const Value& operator*() const { return it->first; }
 		      const Value* operator->() const { return &(it->first); }
 		      bool operator==(ValueIterator jt) const { return it == jt.it; }
 		      bool operator!=(ValueIterator jt) const { return it != jt.it; }
 		    private:
 		      typename Container::const_iterator it;
 		    };
 		    /// \brief Returns an iterator to the first value.
 		    ///
 		    /// Returns an stl compatible iterator to the
 		    /// first value of the map. The values of the
 		    /// map can be accessed in the [beginValue, endValue)
 		    /// range.
 		    ValueIterator beginValue() const {
 		      return ValueIterator(_inv_map.begin());
+		    }
 		    /// \brief Returns an iterator after the last value.
 		    ///
 		    /// Returns an stl compatible iterator after the
 		    /// last value of the map. The values of the
 		    /// map can be accessed in the [beginValue, endValue)
 		    /// range.
 		    ValueIterator endValue() const {
 		      return ValueIterator(_inv_map.end());
+		    }
 		    /// \brief The setter function of the map.
 		    ///
 		    /// Sets the mapped value.
 		    void set(const Key& key, const Value& val) {
 		      Value oldval = Map::operator[](key);
 		      typename Container::iterator it = _inv_map.find(oldval);
 		      if (it != _inv_map.end() && it->second == key) {
 			_inv_map.erase(it);
+		      }
 		      _inv_map.insert(make_pair(val, key));
 		      Map::set(key, val);
+		    }
 		    /// \brief The getter function of the map.
 		    ///
 		    /// It gives back the value associated with the key.
 		    typename MapTraits<Map>::ConstReturnValue
 		    operator[](const Key& key) const {
 		      return Map::operator[](key);
+		    }
 		    /// \brief Gives back the item by its value.
 		    ///
 		    /// Gives back the item by its value.
 		    Key operator()(const Value& key) const {
 		      typename Container::const_iterator it = _inv_map.find(key);
 		      return it != _inv_map.end() ? it->second : INVALID;
+		    }
 		  protected:
 		    /// \brief Erase the key from the map.
 		    ///
 		    /// Erase the key to the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void erase(const Key& key) {
 		      Value val = Map::operator[](key);
 		      typename Container::iterator it = _inv_map.find(val);
 		      if (it != _inv_map.end() && it->second == key) {
 			_inv_map.erase(it);
+		      }
 		      Map::erase(key);
+		    }
 		    /// \brief Erase more keys from the map.
 		    ///
 		    /// Erase more keys from the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void erase(const std::vector<Key>& keys) {
 		      for (int i = 0; i < int(keys.size()); ++i) {
 			Value val = Map::operator[](keys[i]);
 			typename Container::iterator it = _inv_map.find(val);
 			if (it != _inv_map.end() && it->second == keys[i]) {
 			  _inv_map.erase(it);
+			}
+		      }
 		      Map::erase(keys);
+		    }
 		    /// \brief Clear the keys from the map and inverse map.
 		    ///
 		    /// Clear the keys from the map and inverse map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void clear() {
 		      _inv_map.clear();
 		      Map::clear();
+		    }
 		  public:
 		    /// \brief The inverse map type.
 		    ///
 		    /// The inverse of this map. The subscript operator of the map
 		    /// gives back always the item what was last assigned to the value.
 		    class InverseMap {
 		    public:
 		      /// \brief Constructor of the InverseMap.
 		      ///
 		      /// Constructor of the InverseMap.
 		      explicit InverseMap(const InvertableMap& inverted)
 		        : _inverted(inverted) {}
 		      /// The value type of the InverseMap.
 		      typedef typename InvertableMap::Key Value;
 		      /// The key type of the InverseMap.
 		      typedef typename InvertableMap::Value Key;
 		      /// \brief Subscript operator.
 		      ///
 		      /// Subscript operator. It gives back always the item
 		      /// what was last assigned to the value.
 		      Value operator[](const Key& key) const {
 			return _inverted(key);
+		      }
 		    private:
 		      const InvertableMap& _inverted;
 		    };
 		    /// \brief It gives back the just readable inverse map.
 		    ///
 		    /// It gives back the just readable inverse map.
 		    InverseMap inverse() const {
 		      return InverseMap(*this);
+		    }
 		  };
 		  /// \brief Provides a mutable, continuous and unique descriptor for each
 		  /// item in the graph.
 		  ///
 		  /// The DescriptorMap class provides a unique and continuous (but mutable)
 		  /// descriptor (id) for each item of the same type (e.g. node) in the
 		  /// graph. This id is <ul><li>\b unique: different items (nodes) get
 		  /// different ids <li>\b continuous: the range of the ids is the set of
 		  /// integers between 0 and \c n-1, where \c n is the number of the items of
 		  /// this type (e.g. nodes) (so the id of a node can change if you delete an
 		  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
 		  /// with its member class \c InverseMap, or with the \c operator() member.
 		  ///
 		  /// \param _Graph The graph class the \c DescriptorMap belongs to.
 		  /// \param _Item The Item is the Key of the Map. It may be Node, Arc or
 		  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
 		  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
 		  /// Edge.
 		  template <typename _Graph, typename _Item>
 		  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
 		    typedef _Item Item;
 		    typedef DefaultMap<_Graph, _Item, int> Map;
 		  public:
 		    /// The graph class of DescriptorMap.
 		    typedef _Graph Graph;
 		    /// The key type of DescriptorMap (Node, Arc, Edge).
 		    typedef typename Map::Key Key;
 		    /// The value type of DescriptorMap.
 		    typedef typename Map::Value Value;
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor for descriptor map.
 		    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
 		      Item it;
 		      const typename Map::Notifier* nf = Map::notifier();
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 			Map::set(it, _inv_map.size());
 			_inv_map.push_back(it);
+		      }
+		    }
 		  protected:
 		    /// \brief Add a new key to the map.
 		    ///
 		    /// Add a new key to the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void add(const Item& item) {
 		      Map::add(item);
 		      Map::set(item, _inv_map.size());
 		      _inv_map.push_back(item);
+		    }
 		    /// \brief Add more new keys to the map.
 		    ///
 		    /// Add more new keys to the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void add(const std::vector<Item>& items) {
 		      Map::add(items);
 		      for (int i = 0; i < int(items.size()); ++i) {
 			Map::set(items[i], _inv_map.size());
 			_inv_map.push_back(items[i]);
+		      }
+		    }
 		    /// \brief Erase the key from the map.
 		    ///
 		    /// Erase the key from the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void erase(const Item& item) {
 		      Map::set(_inv_map.back(), Map::operator[](item));
 		      _inv_map[Map::operator[](item)] = _inv_map.back();
 		      _inv_map.pop_back();
 		      Map::erase(item);
+		    }
 		    /// \brief Erase more keys from the map.
 		    ///
 		    /// Erase more keys from the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void erase(const std::vector<Item>& items) {
 		      for (int i = 0; i < int(items.size()); ++i) {
 			Map::set(_inv_map.back(), Map::operator[](items[i]));
 			_inv_map[Map::operator[](items[i])] = _inv_map.back();
 			_inv_map.pop_back();
+		      }
 		      Map::erase(items);
+		    }
 		    /// \brief Build the unique map.
 		    ///
 		    /// Build the unique map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void build() {
 		      Map::build();
 		      Item it;
 		      const typename Map::Notifier* nf = Map::notifier();
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 			Map::set(it, _inv_map.size());
 			_inv_map.push_back(it);
+		      }
+		    }
 		    /// \brief Clear the keys from the map.
 		    ///
 		    /// Clear the keys from the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void clear() {
 		      _inv_map.clear();
 		      Map::clear();
+		    }
 		  public:
 		    /// \brief Returns the maximal value plus one.
 		    ///
 		    /// Returns the maximal value plus one in the map.
 		    unsigned int size() const {
 		      return _inv_map.size();
+		    }
 		    /// \brief Swaps the position of the two items in the map.
 		    ///
 		    /// Swaps the position of the two items in the map.
 		    void swap(const Item& p, const Item& q) {
 		      int pi = Map::operator[](p);
 		      int qi = Map::operator[](q);
 		      Map::set(p, qi);
 		      _inv_map[qi] = p;
 		      Map::set(q, pi);
 		      _inv_map[pi] = q;
+		    }
 		    /// \brief Gives back the \e descriptor of the item.
 		    ///
 		    /// Gives back the mutable and unique \e descriptor of the map.
 		    int operator[](const Item& item) const {
 		      return Map::operator[](item);
+		    }
 		    /// \brief Gives back the item by its descriptor.
 		    ///
 		    /// Gives back th item by its descriptor.
 		    Item operator()(int id) const {
 		      return _inv_map[id];
+		    }
 		  private:
 		    typedef std::vector<Item> Container;
 		    Container _inv_map;
 		  public:
 		    /// \brief The inverse map type of DescriptorMap.
 		    ///
 		    /// The inverse map type of DescriptorMap.
 		    class InverseMap {
 		    public:
 		      /// \brief Constructor of the InverseMap.
 		      ///
 		      /// Constructor of the InverseMap.
 		      explicit InverseMap(const DescriptorMap& inverted)
 			: _inverted(inverted) {}
 		      /// The value type of the InverseMap.
 		      typedef typename DescriptorMap::Key Value;
 		      /// The key type of the InverseMap.
 		      typedef typename DescriptorMap::Value Key;
 		      /// \brief Subscript operator.
 		      ///
 		      /// Subscript operator. It gives back the item
 		      /// that the descriptor belongs to currently.
 		      Value operator[](const Key& key) const {
 			return _inverted(key);
+		      }
 		      /// \brief Size of the map.
 		      ///
 		      /// Returns the size of the map.
 		      unsigned int size() const {
 			return _inverted.size();
+		      }
 		    private:
 		      const DescriptorMap& _inverted;
 		    };
 		    /// \brief Gives back the inverse of the map.
 		    ///
 		    /// Gives back the inverse of the map.
 		    const InverseMap inverse() const {
 		      return InverseMap(*this);
+		    }
 		  };
 		  /// \brief Returns the source of the given arc.
 		  ///
 		  /// The SourceMap gives back the source Node of the given arc.
 		  /// \see TargetMap
 		  /// \author Balazs Dezso
 		  template <typename Digraph>
 		  class SourceMap {
 		  public:
 		    typedef typename Digraph::Node Value;
 		    typedef typename Digraph::Arc Key;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \param _digraph The digraph that the map belongs to.
 		    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
 		    /// \brief The subscript operator.
 		    ///
 		    /// The subscript operator.
 		    /// \param arc The arc
 		    /// \return The source of the arc
 		    Value operator[](const Key& arc) const {
 		      return _digraph.source(arc);
+		    }
 		  private:
 		    const Digraph& _digraph;
 		  };
 		  /// \brief Returns a \ref SourceMap class.
 		  ///
 		  /// This function just returns an \ref SourceMap class.
 		  /// \relates SourceMap
 		  template <typename Digraph>
 		  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
 		    return SourceMap<Digraph>(digraph);
+		  }
 		  /// \brief Returns the target of the given arc.
 		  ///
 		  /// The TargetMap gives back the target Node of the given arc.
 		  /// \see SourceMap
 		  /// \author Balazs Dezso
 		  template <typename Digraph>
 		  class TargetMap {
 		  public:
 		    typedef typename Digraph::Node Value;
 		    typedef typename Digraph::Arc Key;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \param _digraph The digraph that the map belongs to.
 		    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
 		    /// \brief The subscript operator.
 		    ///
 		    /// The subscript operator.
 		    /// \param e The arc
 		    /// \return The target of the arc
 		    Value operator[](const Key& e) const {
 		      return _digraph.target(e);
+		    }
 		  private:
 		    const Digraph& _digraph;
 		  };
 		  /// \brief Returns a \ref TargetMap class.
 		  ///
 		  /// This function just returns a \ref TargetMap class.
 		  /// \relates TargetMap
 		  template <typename Digraph>
 		  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
 		    return TargetMap<Digraph>(digraph);
+		  }
 		  /// \brief Returns the "forward" directed arc view of an edge.
 		  ///
 		  /// Returns the "forward" directed arc view of an edge.
 		  /// \see BackwardMap
 		  /// \author Balazs Dezso
 		  template <typename Graph>
 		  class ForwardMap {
 		  public:
 		    typedef typename Graph::Arc Value;
 		    typedef typename Graph::Edge Key;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \param _graph The graph that the map belongs to.
 		    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
 		    /// \brief The subscript operator.
 		    ///
 		    /// The subscript operator.
 		    /// \param key An edge
 		    /// \return The "forward" directed arc view of edge
 		    Value operator[](const Key& key) const {
 		      return _graph.direct(key, true);
+		    }
 		  private:
 		    const Graph& _graph;
 		  };
 		  /// \brief Returns a \ref ForwardMap class.
 		  ///
 		  /// This function just returns an \ref ForwardMap class.
 		  /// \relates ForwardMap
 		  template <typename Graph>
 		  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
 		    return ForwardMap<Graph>(graph);
+		  }
 		  /// \brief Returns the "backward" directed arc view of an edge.
 		  ///
 		  /// Returns the "backward" directed arc view of an edge.
 		  /// \see ForwardMap
 		  /// \author Balazs Dezso
 		  template <typename Graph>
 		  class BackwardMap {
 		  public:
 		    typedef typename Graph::Arc Value;
 		    typedef typename Graph::Edge Key;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \param _graph The graph that the map belongs to.
 		    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
 		    /// \brief The subscript operator.
 		    ///
 		    /// The subscript operator.
 		    /// \param key An edge
 		    /// \return The "backward" directed arc view of edge
 		    Value operator[](const Key& key) const {
 		      return _graph.direct(key, false);
+		    }
 		  private:
 		    const Graph& _graph;
 		  };
 		  /// \brief Returns a \ref BackwardMap class
 		  /// This function just returns a \ref BackwardMap class.
 		  /// \relates BackwardMap
 		  template <typename Graph>
 		  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
 		    return BackwardMap<Graph>(graph);
+		  }
 		  /// \brief Potential difference map
 		  ///
 		  /// If there is an potential map on the nodes then we
 		  /// can get an arc map as we get the substraction of the
 		  /// values of the target and source.
 		  template <typename Digraph, typename NodeMap>
 		  class PotentialDifferenceMap {
 		  public:
 		    typedef typename Digraph::Arc Key;
 		    typedef typename NodeMap::Value Value;
 		    /// \brief Constructor
 		    ///
 		    /// Contructor of the map
 		    explicit PotentialDifferenceMap(const Digraph& digraph,
 		                                    const NodeMap& potential)
 		      : _digraph(digraph), _potential(potential) {}
 		    /// \brief Const subscription operator
 		    ///
 		    /// Const subscription operator
 		    Value operator[](const Key& arc) const {
 		      return _potential[_digraph.target(arc)] -
 			_potential[_digraph.source(arc)];
+		    }
 		  private:
 		    const Digraph& _digraph;
 		    const NodeMap& _potential;
 		  };
 		  /// \brief Returns a PotentialDifferenceMap.
 		  ///
 		  /// This function just returns a PotentialDifferenceMap.
 		  /// \relates PotentialDifferenceMap
 		  template <typename Digraph, typename NodeMap>
 		  PotentialDifferenceMap<Digraph, NodeMap>
 		  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
 		    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
+		  }
 		  /// \brief Map of the node in-degrees.
 		  ///
 		  /// This map returns the in-degree of a node. Once it is constructed,
 		  /// the degrees are stored in a standard NodeMap, so each query is done
 		  /// in constant time. On the other hand, the values are updated automatically
 		  /// whenever the digraph changes.
 		  ///
 		  /// \warning Besides addNode() and addArc(), a digraph structure may provide
 		  /// alternative ways to modify the digraph. The correct behavior of InDegMap
 		  /// is not guarantied if these additional features are used. For example
 		  /// the functions \ref ListDigraph::changeSource() "changeSource()",
 		  /// \ref ListDigraph::changeTarget() "changeTarget()" and
 		  /// \ref ListDigraph::reverseArc() "reverseArc()"
 		  /// of \ref ListDigraph will \e not update the degree values correctly.
 		  ///
 		  /// \sa OutDegMap
 		  template <typename _Digraph>
 		  class InDegMap
 		    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
 		      ::ItemNotifier::ObserverBase {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef int Value;
 		    typedef typename Digraph::Node Key;
 		    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
 		    ::ItemNotifier::ObserverBase Parent;
 		  private:
 		    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
 		    public:
 		      typedef DefaultMap<Digraph, Key, int> Parent;
 		      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
 		      virtual void add(const Key& key) {
 			Parent::add(key);
 			Parent::set(key, 0);
+		      }
 		      virtual void add(const std::vector<Key>& keys) {
 			Parent::add(keys);
 			for (int i = 0; i < int(keys.size()); ++i) {
 			  Parent::set(keys[i], 0);
+			}
+		      }
 		      virtual void build() {
 			Parent::build();
 			Key it;
 			typename Parent::Notifier* nf = Parent::notifier();
 			for (nf->first(it); it != INVALID; nf->next(it)) {
 			  Parent::set(it, 0);
+			}
+		      }
 		    };
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor for creating in-degree map.
 		    explicit InDegMap(const Digraph& digraph)
 		      : _digraph(digraph), _deg(digraph) {
 		      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 			_deg[it] = countInArcs(_digraph, it);
+		      }
+		    }
 		    /// Gives back the in-degree of a Node.
 		    int operator[](const Key& key) const {
 		      return _deg[key];
+		    }
 		  protected:
 		    typedef typename Digraph::Arc Arc;
 		    virtual void add(const Arc& arc) {
 		      ++_deg[_digraph.target(arc)];
+		    }
 		    virtual void add(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        ++_deg[_digraph.target(arcs[i])];
+		      }
+		    }
 		    virtual void erase(const Arc& arc) {
 		      --_deg[_digraph.target(arc)];
+		    }
 		    virtual void erase(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        --_deg[_digraph.target(arcs[i])];
+		      }
+		    }
 		    virtual void build() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 			_deg[it] = countInArcs(_digraph, it);
+		      }
+		    }
 		    virtual void clear() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 			_deg[it] = 0;
+		      }
+		    }
 		  private:
 		    const Digraph& _digraph;
 		    AutoNodeMap _deg;
 		  };
 		  /// \brief Map of the node out-degrees.
 		  ///
 		  /// This map returns the out-degree of a node. Once it is constructed,
 		  /// the degrees are stored in a standard NodeMap, so each query is done
 		  /// in constant time. On the other hand, the values are updated automatically
 		  /// whenever the digraph changes.
 		  ///
 		  /// \warning Besides addNode() and addArc(), a digraph structure may provide
 		  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
 		  /// is not guarantied if these additional features are used. For example
 		  /// the functions \ref ListDigraph::changeSource() "changeSource()",
 		  /// \ref ListDigraph::changeTarget() "changeTarget()" and
 		  /// \ref ListDigraph::reverseArc() "reverseArc()"
 		  /// of \ref ListDigraph will \e not update the degree values correctly.
 		  ///
 		  /// \sa InDegMap
 		  template <typename _Digraph>
 		  class OutDegMap
 		    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
 		      ::ItemNotifier::ObserverBase {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef int Value;
 		    typedef typename Digraph::Node Key;
 		    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
 		    ::ItemNotifier::ObserverBase Parent;
 		  private:
 		    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
 		    public:
 		      typedef DefaultMap<Digraph, Key, int> Parent;
 		      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
 		      virtual void add(const Key& key) {
 			Parent::add(key);
 			Parent::set(key, 0);
+		      }
 		      virtual void add(const std::vector<Key>& keys) {
 			Parent::add(keys);
 			for (int i = 0; i < int(keys.size()); ++i) {
 			  Parent::set(keys[i], 0);
+			}
+		      }
 		      virtual void build() {
 			Parent::build();
 			Key it;
 			typename Parent::Notifier* nf = Parent::notifier();
 			for (nf->first(it); it != INVALID; nf->next(it)) {
 			  Parent::set(it, 0);
+			}
+		      }
 		    };
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor for creating out-degree map.
 		    explicit OutDegMap(const Digraph& digraph)
 		      : _digraph(digraph), _deg(digraph) {
 		      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 			_deg[it] = countOutArcs(_digraph, it);
+		      }
+		    }
 		    /// Gives back the out-degree of a Node.
 		    int operator[](const Key& key) const {
 		      return _deg[key];
+		    }
 		  protected:
 		    typedef typename Digraph::Arc Arc;
 		    virtual void add(const Arc& arc) {
 		      ++_deg[_digraph.source(arc)];
+		    }
 		    virtual void add(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        ++_deg[_digraph.source(arcs[i])];
+		      }
+		    }
 		    virtual void erase(const Arc& arc) {
 		      --_deg[_digraph.source(arc)];
+		    }
 		    virtual void erase(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        --_deg[_digraph.source(arcs[i])];
+		      }
+		    }
 		    virtual void build() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 			_deg[it] = countOutArcs(_digraph, it);
+		      }
+		    }
 		    virtual void clear() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 			_deg[it] = 0;
+		      }
+		    }
 		  private:
 		    const Digraph& _digraph;
 		    AutoNodeMap _deg;
 		  };
 		  ///Dynamic arc look up between given endpoints.
 		  ///\ingroup gutils
 		  ///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 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 findFirst() and \c findNext() members.
 		  ///
 		  ///See the \ref ArcLookUp and \ref AllArcLookUp classes 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
 		  ///optimal time bound in a constant factor for any distribution of
 		  ///queries.
 		  ///
-		  ///\param G The type of the underlying digraph.
+		  ///\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 DefaultMap<G, Node, Arc> {
 		    public:
 		      typedef DefaultMap<G, Node, Arc> 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);
+			    }
@@ -2348,420 +2340,420 @@
 		      _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 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.
 		    Arc operator()(Node s, Node t) const
+		    {
 		      Arc a = _head[s];
 		      while (true) {
 			if (_g.target(a) == t) {
 			  const_cast<DynArcLookUp&>(*this).splay(a);
 			  return a;
 			} else if (t < _g.target(a)) {
 			  if (_left[a] == INVALID) {
 			    const_cast<DynArcLookUp&>(*this).splay(a);
 			    return INVALID;
 			  } else {
 			    a = _left[a];
+			  }
 			} else  {
 			  if (_right[a] == INVALID) {
 			    const_cast<DynArcLookUp&>(*this).splay(a);
 			    return INVALID;
 			  } else {
 			    a = _right[a];
+			  }
+			}
+		      }
+		    }
 		    ///Find the first arc between two nodes.
 		    ///Find the first 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.
 		    Arc findFirst(Node s, Node t) const
+		    {
 		      Arc a = _head[s];
 		      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];
+			  }
+			}
+		      }
+		    }
 		    ///Find the next arc between two nodes.
 		    ///Find the next 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.
 		    ///\note If \c e is not the result of the previous \c findFirst()
 		    ///operation then the amorized time bound can not be guaranteed.
 		#ifdef DOXYGEN
 		    Arc findNext(Node s, Node t, Arc a) const
 		#else
 		    Arc findNext(Node, Node t, Arc a) const
 		#endif
+		    {
 		      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.
 		  ///\ingroup gutils
 		  ///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>,
 		  ///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).
 		  ///
-		  ///\param G The type of the underlying digraph.
+		  ///\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.
 		    ///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.
 		    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
 		    ///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
 		    ///\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.
 		    ///
 		    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.
 		  ///\ingroup gutils
 		  ///This class is the same as \ref ArcLookUp, with the addition
 		  ///that it makes it possible to find all 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).
 		  ///
-		  ///\param G The type of the underlying digraph.
+		  ///\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
 		    ///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
 		    ///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 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++;
 		    ///\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
 		    ///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.
 		    ///
 		#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
 		  };
 		  /// @}
 		} //END OF NAMESPACE LEMON
 		#endif

lemon/path.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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 paths
 		///\file
 		///\brief Classes for representing paths in digraphs.
 		///
 		#ifndef LEMON_PATH_H
 		#define LEMON_PATH_H
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/error.h>
 		#include <lemon/bits/invalid.h>
 		#include <lemon/concepts/path.h>
 		namespace lemon {
 		  /// \addtogroup paths
 		  /// @{
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
-		  /// \param Digraph The digraph type in which the path is.
+		  /// \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 of the path and the source node of
 		  /// a zero length path is undefined.
 		  ///
 		  /// This implementation is a back and front insertable and erasable
 		  /// path type. It can be indexed in O(1) time. The front and back
 		  /// insertion and erase is done in O(1) (amortized) time. The
 		  /// implementation uses two vectors for storing the front and back
 		  /// insertions.
 		  template <typename _Digraph>
 		  class Path {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    Path() {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This constuctor initializes the path from any other path type.
 		    /// It simply makes a copy of the given path.
 		    template <typename CPath>
 		    Path(const CPath& cpath) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This operator makes a copy of a path of any other type.
 		    template <typename CPath>
 		    Path& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Lemon style iterator for path arcs
 		    ///
 		    /// This class is used to iterate on the arcs of the paths.
 		    class ArcIt {
 		      friend class Path;
 		    public:
 		      /// \brief Default constructor
 		      ArcIt() {}
 		      /// \brief Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// \brief Initializate the iterator to the first arc of path
 		      ArcIt(const Path &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      ArcIt(const Path &_path, int _idx)
 		        : path(&_path), idx(_idx) {}
 		    public:
 		      /// \brief Conversion to Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// \brief Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// \brief Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// \brief Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// \brief Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const Path *path;
 		      int idx;
 		    };
 		    /// \brief Length of the path.
 		    int length() const { return head.size() + tail.size(); }
 		    /// \brief Return whether the path is empty.
 		    bool empty() const { return head.empty() && tail.empty(); }
 		    /// \brief Reset the path to an empty one.
 		    void clear() { head.clear(); tail.clear(); }
 		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return n < int(head.size()) ? *(head.rbegin() + n) :
 		        *(tail.begin() + (n - head.size()));
+		    }
 		    /// \brief Initialize arc iterator to point to the nth arc
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
 		    /// \brief The first arc of the path
 		    const Arc& front() const {
 		      return head.empty() ? tail.front() : head.back();
+		    }
 		    /// \brief Add a new arc before the current path
 		    void addFront(const Arc& arc) {
 		      head.push_back(arc);
+		    }
 		    /// \brief Erase the first arc of the path
 		    void eraseFront() {
 		      if (!head.empty()) {
 		        head.pop_back();
 		      } else {
 		        head.clear();
 		        int halfsize = tail.size() / 2;
 		        head.resize(halfsize);
 		        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
 		                  head.rbegin());
 		        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
 		        tail.resize(tail.size() - halfsize - 1);
+		      }
+		    }
 		    /// \brief The last arc of the path
 		    const Arc& back() const {
 		      return tail.empty() ? head.front() : tail.back();
+		    }
 		    /// \brief Add a new arc behind the current path
 		    void addBack(const Arc& arc) {
 		      tail.push_back(arc);
+		    }
 		    /// \brief Erase the last arc of the path
 		    void eraseBack() {
 		      if (!tail.empty()) {
 		        tail.pop_back();
 		      } else {
 		        int halfsize = head.size() / 2;
 		        tail.resize(halfsize);
 		        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
 		                  tail.rbegin());
 		        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
 		        head.resize(head.size() - halfsize - 1);
+		      }
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      int len = path.length();
 		      tail.reserve(len);
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        tail.push_back(it);
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      int len = path.length();
 		      head.reserve(len);
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        head.push_back(it);
+		      }
+		    }
 		  protected:
 		    typedef std::vector<Arc> Container;
 		    Container head, tail;
 		  };
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
-		  /// \param Digraph The digraph type in which the path is.
+		  /// \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.
 		  ///
 		  /// This implementation is a just back insertable and erasable path
 		  /// type. It can be indexed in O(1) time. The back insertion and
 		  /// erasure is amortized O(1) time. This implementation is faster
 		  /// then the \c Path type because it use just one vector for the
 		  /// arcs.
 		  template <typename _Digraph>
 		  class SimplePath {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    SimplePath() {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    SimplePath(const CPath& cpath) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    SimplePath& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Iterator class to iterate on the arcs of the paths
 		    ///
 		    /// This class is used to iterate on the arcs of the paths
 		    ///
 		    /// Of course it converts to Digraph::Arc
 		    class ArcIt {
 		      friend class SimplePath;
 		    public:
 		      /// Default constructor
 		      ArcIt() {}
 		      /// Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// \brief Initializate the constructor to the first arc of path
 		      ArcIt(const SimplePath &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      /// Constructor with starting point
 		      ArcIt(const SimplePath &_path, int _idx)
 		        : idx(_idx), path(&_path) {}
 		    public:
 		      ///Conversion to Digraph::Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const SimplePath *path;
 		      int idx;
 		    };
 		    /// \brief Length of the path.
 		    int length() const { return data.size(); }
 		    /// \brief Return true if the path is empty.
 		    bool empty() const { return data.empty(); }
 		    /// \brief Reset the path to an empty one.
 		    void clear() { data.clear(); }
 		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return data[n];
+		    }
 		    /// \brief  Initializes arc iterator to point to the nth arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
 		    /// \brief The first arc of the path.
 		    const Arc& front() const {
 		      return data.front();
+		    }
 		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return data.back();
+		    }
 		    /// \brief Add a new arc behind the current path.
 		    void addBack(const Arc& arc) {
 		      data.push_back(arc);
+		    }
 		    /// \brief Erase the last arc of the path
 		    void eraseBack() {
 		      data.pop_back();
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      int len = path.length();
 		      data.resize(len);
 		      int index = 0;
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        data[index] = it;;
 		        ++index;
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      int len = path.length();
 		      data.resize(len);
 		      int index = len;
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        --index;
 		        data[index] = it;;
+		      }
+		    }
 		  protected:
 		    typedef std::vector<Arc> Container;
 		    Container data;
 		  };
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
-		  /// \param Digraph The digraph type in which the path is.
+		  /// \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.
 		  ///
 		  /// This implementation is a back and front insertable and erasable
 		  /// path type. It can be indexed in O(k) time, where k is the rank
 		  /// of the arc in the path. The length can be computed in O(n)
 		  /// time. The front and back insertion and erasure is O(1) time
 		  /// and it can be splited and spliced in O(1) time.
 		  template <typename _Digraph>
 		  class ListPath {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		  protected:
 		    // the std::list<> is incompatible
 		    // hard to create invalid iterator
 		    struct Node {
 		      Arc arc;
 		      Node *next, *prev;
 		    };
 		    Node *first, *last;
 		    std::allocator<Node> alloc;
 		  public:
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    ListPath() : first(0), last(0) {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    ListPath(const CPath& cpath) : first(0), last(0) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Destructor of the path
 		    ///
 		    /// Destructor of the path
 		    ~ListPath() {
 		      clear();
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    ListPath& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Iterator class to iterate on the arcs of the paths
 		    ///
 		    /// This class is used to iterate on the arcs of the paths
 		    ///
 		    /// Of course it converts to Digraph::Arc
 		    class ArcIt {
 		      friend class ListPath;
 		    public:
 		      /// Default constructor
 		      ArcIt() {}
 		      /// Invalid constructor
 		      ArcIt(Invalid) : path(0), node(0) {}
 		      /// \brief Initializate the constructor to the first arc of path
 		      ArcIt(const ListPath &_path)
 		        : path(&_path), node(_path.first) {}
 		    protected:
 		      ArcIt(const ListPath &_path, Node *_node)
 		        : path(&_path), node(_node) {}
 		    public:
 		      ///Conversion to Digraph::Arc
 		      operator const Arc&() const {
 		        return node->arc;
+		      }
 		      /// Next arc
 		      ArcIt& operator++() {
 		        node = node->next;
 		        return *this;
+		      }
 		      /// Comparison operator
 		      bool operator==(const ArcIt& e) const { return node==e.node; }
 		      /// Comparison operator
 		      bool operator!=(const ArcIt& e) const { return node!=e.node; }
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return node<e.node; }
 		    private:
 		      const ListPath *path;
 		      Node *node;
 		    };
 		    /// \brief The nth arc.
 		    ///
 		    /// This function looks for the nth arc in O(n) time.
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      Node *node = first;
 		      for (int i = 0; i < n; ++i) {
 		        node = node->next;
+		      }
 		      return node->arc;
+		    }
 		    /// \brief Initializes arc iterator to point to the nth arc.
 		    ArcIt nthIt(int n) const {
 		      Node *node = first;
 		      for (int i = 0; i < n; ++i) {
 		        node = node->next;
+		      }
 		      return ArcIt(*this, node);
+		    }
 		    /// \brief Length of the path.
 		    int length() const {
 		      int len = 0;
 		      Node *node = first;
 		      while (node != 0) {
 		        node = node->next;
 		        ++len;
+		      }
 		      return len;
+		    }
 		    /// \brief Return true if the path is empty.
 		    bool empty() const { return first == 0; }
 		    /// \brief Reset the path to an empty one.
 		    void clear() {
 		      while (first != 0) {
 		        last = first->next;
 		        alloc.destroy(first);
 		        alloc.deallocate(first, 1);
 		        first = last;
+		      }
+		    }
 		    /// \brief The first arc of the path
 		    const Arc& front() const {
 		      return first->arc;
+		    }
 		    /// \brief Add a new arc before the current path
 		    void addFront(const Arc& arc) {
 		      Node *node = alloc.allocate(1);
 		      alloc.construct(node, Node());
 		      node->prev = 0;
 		      node->next = first;
 		      node->arc = arc;
 		      if (first) {
 		        first->prev = node;
 		        first = node;
 		      } else {
 		        first = last = node;
+		      }
+		    }
 		    /// \brief Erase the first arc of the path
 		    void eraseFront() {
 		      Node *node = first;
 		      first = first->next;
 		      if (first) {
 		        first->prev = 0;
 		      } else {
 		        last = 0;
+		      }
 		      alloc.destroy(node);
 		      alloc.deallocate(node, 1);
+		    }
 		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return last->arc;
+		    }
 		    /// \brief Add a new arc behind the current path.
 		    void addBack(const Arc& arc) {
 		      Node *node = alloc.allocate(1);
 		      alloc.construct(node, Node());
 		      node->next = 0;
 		      node->prev = last;
 		      node->arc = arc;
 		      if (last) {
 		        last->next = node;
 		        last = node;
 		      } else {
 		        last = first = node;
+		      }
+		    }
 		    /// \brief Erase the last arc of the path
 		    void eraseBack() {
 		      Node *node = last;
 		      last = last->prev;
 		      if (last) {
 		        last->next = 0;
 		      } else {
 		        first = 0;
+		      }
 		      alloc.destroy(node);
 		      alloc.deallocate(node, 1);
+		    }
 		    /// \brief Splice a path to the back of the current path.
 		    ///
 		    /// It splices \c tpath to the back of the current path and \c
 		    /// tpath becomes empty. The time complexity of this function is
 		    /// O(1).
 		    void spliceBack(ListPath& tpath) {
 		      if (first) {
 		        if (tpath.first) {
 		          last->next = tpath.first;
 		          tpath.first->prev = last;
 		          last = tpath.last;
+		        }
 		      } else {
 		        first = tpath.first;
 		        last = tpath.last;
+		      }
 		      tpath.first = tpath.last = 0;
+		    }
 		    /// \brief Splice a path to the front of the current path.
 		    ///
 		    /// It splices \c tpath before the current path and \c tpath
 		    /// becomes empty. The time complexity of this function
 		    /// is O(1).
 		    void spliceFront(ListPath& tpath) {
 		      if (first) {
 		        if (tpath.first) {
 		          first->prev = tpath.last;
 		          tpath.last->next = first;
 		          first = tpath.first;
+		        }
 		      } else {
 		        first = tpath.first;
 		        last = tpath.last;
+		      }
 		      tpath.first = tpath.last = 0;
+		    }
 		    /// \brief Splice a path into the current path.
 		    ///
 		    /// It splices the \c tpath into the current path before the
 		    /// position of \c it iterator and \c tpath becomes empty. The
 		    /// time complexity of this function is O(1). If the \c it is
 		    /// \c INVALID then it will splice behind the current path.
 		    void splice(ArcIt it, ListPath& tpath) {
 		      if (it.node) {
 		        if (tpath.first) {
 		          tpath.first->prev = it.node->prev;
 		          if (it.node->prev) {
 		            it.node->prev->next = tpath.first;
 		          } else {
 		            first = tpath.first;
+		          }
 		          it.node->prev = tpath.last;
 		          tpath.last->next = it.node;
+		        }
 		      } else {
 		        if (first) {
 		          if (tpath.first) {
 		            last->next = tpath.first;
 		            tpath.first->prev = last;
 		            last = tpath.last;
+		          }
 		        } else {
 		          first = tpath.first;
 		          last = tpath.last;
+		        }
+		      }
 		      tpath.first = tpath.last = 0;
+		    }
 		    /// \brief Split the current path.
 		    ///
 		    /// It splits the current path into two parts. The part before
 		    /// the iterator \c it will remain in the current path and the part
 		    /// starting with
 		    /// \c it will put into \c tpath. If \c tpath have arcs
 		    /// before the operation they are removed first.  The time
 		    /// complexity of this function is O(1) plus the the time of emtying
 		    /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
 		    void split(ArcIt it, ListPath& tpath) {
 		      tpath.clear();
 		      if (it.node) {
 		        tpath.first = it.node;
 		        tpath.last = last;
 		        if (it.node->prev) {
 		          last = it.node->prev;
 		          last->next = 0;
 		        } else {
 		          first = last = 0;
+		        }
 		        it.node->prev = 0;
+		      }
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        addBack(it);
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        addFront(it);
+		      }
+		    }
 		  };
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
-		  /// \param Digraph The digraph type in which the path is.
+		  /// \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 source node of
 		  /// a zero length path is undefined.
 		  ///
 		  /// This implementation is completly static, i.e. it can be copy constucted
 		  /// or copy assigned from another path, but otherwise it cannot be
 		  /// modified.
 		  ///
 		  /// Being the the most memory efficient path type in LEMON,
 		  /// it is intented to be
 		  /// used when you want to store a large number of paths.
 		  template <typename _Digraph>
 		  class StaticPath {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    StaticPath() : len(0), arcs(0) {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized from any other path type.
 		    template <typename CPath>
 		    StaticPath(const CPath& cpath) : arcs(0) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Destructor of the path
 		    ///
 		    /// Destructor of the path
 		    ~StaticPath() {
 		      if (arcs) delete[] arcs;
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This path can be made equal to any other path type. It simply
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    StaticPath& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Iterator class to iterate on the arcs of the paths
 		    ///
 		    /// This class is used to iterate on the arcs of the paths
 		    ///
 		    /// Of course it converts to Digraph::Arc
 		    class ArcIt {
 		      friend class StaticPath;
 		    public:
 		      /// Default constructor
 		      ArcIt() {}
 		      /// Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// Initializate the constructor to the first arc of path
 		      ArcIt(const StaticPath &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      /// Constructor with starting point
 		      ArcIt(const StaticPath &_path, int _idx)
 		        : idx(_idx), path(&_path) {}
 		    public:
 		      ///Conversion to Digraph::Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const StaticPath *path;
 		      int idx;
 		    };
 		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return arcs[n];
+		    }
 		    /// \brief The arc iterator pointing to the nth arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
 		    /// \brief The length of the path.
 		    int length() const { return len; }
 		    /// \brief Return true when the path is empty.
 		    int empty() const { return len == 0; }
 		    /// \break Erase all arcs in the digraph.
 		    void clear() {
 		      len = 0;
 		      if (arcs) delete[] arcs;
 		      arcs = 0;
+		    }
 		    /// \brief The first arc of the path.
 		    const Arc& front() const {
 		      return arcs[0];
+		    }
 		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return arcs[len - 1];
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      len = path.length();
 		      arcs = new Arc[len];
 		      int index = 0;
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        arcs[index] = it;
 		        ++index;
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      len = path.length();
 		      arcs = new Arc[len];
 		      int index = len;
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        --index;
 		        arcs[index] = it;
+		      }
+		    }
 		  private:
 		    int len;
 		    Arc* arcs;
 		  };
 		  ///////////////////////////////////////////////////////////////////////
 		  // Additional utilities
 		  ///////////////////////////////////////////////////////////////////////
 		  namespace _path_bits {
 		    template <typename Path, typename Enable = void>
 		    struct RevPathTagIndicator {
 		      static const bool value = false;
 		    };
 		    template <typename Path>
 		    struct RevPathTagIndicator<
 		      Path,
 		      typename enable_if<typename Path::RevPathTag, void>::type
 		      > {
 		      static const bool value = true;
 		    };
 		    template <typename Path, typename Enable = void>
 		    struct BuildTagIndicator {
 		      static const bool value = false;
 		    };
 		    template <typename Path>
 		    struct BuildTagIndicator<
 		      Path,
 		      typename enable_if<typename Path::BuildTag, void>::type
 		    > {

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