LEMON/LEMON-main Changeset - r280:e7f8647ce760

Repositories » LEMON » LEMON-main

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

Changeset - r280:e7f8647ce760

« 277:7abfb5

281:e9b4fb »

r280:e7f8647ce760

Mon, 14 Jul 2008 16:23:11

[Not Reviewed]

0 comments (0 inline)

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

Remove todo-s and convert them to trac tickets

0 15 0

default

15 files changed with 7 insertions and 53 deletions:

lemon/bfs.h

lemon/bits/base_extender.h

lemon/bits/vector_map.h

lemon/concept_check.h

lemon/concepts/path.h

lemon/dfs.h

lemon/dijkstra.h

lemon/error.h

lemon/graph_to_eps.h

lemon/list_graph.h

lemon/maps.h

lemon/random.h

lemon/smart_graph.h

lemon/time_measure.h

lemon/tolerance.h

↑ Collapse diff ↑

lemon/bfs.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BFS_H
 		#define LEMON_BFS_H
 		///\ingroup search
 		///\file
 		///\brief BFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		namespace lemon {
 		  ///Default traits class of Bfs class.
 		  ///Default traits class of Bfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref DistMap.
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%BFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %BFS algorithm.
 		  ///
 		  ///There is also a \ref bfs() "function type interface" for the BFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default value is \ref ListDigraph. The value of GR is not used
 		  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
 		  ///\tparam TR Traits class to set various data types used by the algorithm.
 		  ///The default traits class is
 		  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
 		  ///See \ref BfsDefaultTraits for the documentation of
 		  ///a Bfs traits class.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=BfsDefaultTraits<GR> >
 		#endif
 		  class Bfs {
 		  public:
 		    ///\ref Exception for uninitialized parameters.
 		    ///This error represents problems in the initialization of the
 		    ///parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 		        return "lemon::Bfs::UninitializedParameter";
+		      }
 		    };
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The traits class.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::Node> _queue;
 		    int _queue_head,_queue_tail,_queue_next_dist;
 		    int _curr_dist;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Bfs() {}
 		  public:
 		    typedef Bfs Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    template <class T>
 		    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 		      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    template <class T>
 		    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    template <class T>
 		    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap :
 		      public Bfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param g The digraph the algorithm runs on.
 		    Bfs(const Digraph &g) :
 		      G(&g),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _reached(NULL), local_reached(false),
 		      _processed(NULL), local_processed(false)
 		    { }
 		    ///Destructor.
 		    ~Bfs()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_reached) delete _reached;
 		      if(local_processed) delete _processed;
+		    }
 		    ///Sets the map that stores the predecessor arcs.
 		    ///Sets the map that stores the predecessor arcs.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are reached.
 		    ///Sets the map that indicates which nodes are reached.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &reachedMap(ReachedMap &m)
+		    {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are processed.
 		    ///Sets the map that indicates which nodes are processed.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &processedMap(ProcessedMap &m)
+		    {
 		      if(local_processed) {
 		        delete _processed;
@@ -658,385 +655,384 @@
+		    {
 		      Node rnode = INVALID;
 		      while ( !emptyQueue() && rnode == INVALID ) {
 		        processNextNode(nm, rnode);
+		      }
 		      return rnode;
+		    }
 		    ///Runs the algorithm from the given node.
 		    ///This method runs the %BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree,
 		    ///- the distance of each node from the root.
 		    ///
 		    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  b.addSource(s);
 		    ///  b.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs the %BFS algorithm from node \c s
 		    ///in order to compute the shortest path to \c t.
 		    ///
 		    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
 		    ///if \c t is reachable form \c s, \c 0 otherwise.
 		    ///
 		    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
 		    ///shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  b.addSource(s);
 		    ///  b.start(t);
 		    ///\endcode
 		    int run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t) ? _curr_dist : 0;
+		    }
 		    ///Runs the algorithm to visit all nodes in the digraph.
 		    ///This method runs the %BFS algorithm in order to
 		    ///compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree (forest),
 		    ///- the distance of each node from the root(s).
 		    ///
 		    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  for (NodeIt n(gr); n != INVALID; ++n) {
 		    ///    if (!b.reached(n)) {
 		    ///      b.addSource(n);
 		    ///      b.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt n(*G); n != INVALID; ++n) {
 		        if (!reached(n)) {
 		          addSource(n);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The result of the %BFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
 		    ///"start()" must be called before using them.
 		    ///@{
 		    ///The shortest path to a node.
 		    ///Returns the shortest path to a node.
 		    ///
 		    ///\warning \c t should be reachable from the root(s).
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///The distance of a node from the root(s).
 		    ///Returns the distance of a node from the root(s).
 		    ///
 		    ///\warning If node \c v is not reachable from the root(s), then
 		    ///the return value of this function is undefined.
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the shortest path tree for a node.
 		    ///This function returns the 'previous arc' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last arc of a
 		    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
 		    ///is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predNode().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///Returns the 'previous node' of the shortest path tree for a node.
 		    ///This function returns the 'previous node' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last but one node
 		    ///from a shortest path from the root(s) to \c v. It is \c INVALID
 		    ///if \c v is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predArc().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->source((*_pred)[v]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    /// distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the distances
 		    ///of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the shortest path tree.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if a node is reachable from the root(s).
 		    ///Returns \c true if \c v is reachable from the root(s).
 		    ///\pre Either \ref run() or \ref start()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of bfs() function.
 		  ///Default traits class of bfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsWizardDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#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.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap<typename Digraph::Node,int> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const Digraph &g)
 		#else
 		    static DistMap *createDistMap(const Digraph &)
 		#endif
+		    {
 		      return new DistMap();
+		    }
 		  };
 		  /// Default traits class used by \ref BfsWizard
 		  /// To make it easier to use Bfs algorithm
 		  /// we have created a wizard class.
 		  /// This \ref BfsWizard class needs default traits,
 		  /// as well as the \ref Bfs class.
 		  /// The \ref BfsWizardBase is a class to be the default traits of the
 		  /// \ref BfsWizard class.
 		  template<class GR>
 		  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
+		  {
 		    typedef BfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the source node.
 		    Node _source;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to default values (0, INVALID).
 		    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _source(INVALID) {}
 		    /// Constructor.
 		    /// This constructor requires some parameters,
 		    /// listed in the parameters list.
 		    /// Others are initiated to 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param s The source node.
 		    BfsWizardBase(const GR &g, Node s=INVALID) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
 		  };
 		  /// Auxiliary class for the function type interface of BFS algorithm.
 		  /// This auxiliary class is created to implement the function type
 		  /// interface of \ref Bfs algorithm. It uses the functions and features
 		  /// of the plain \ref Bfs, but it is much simpler to use it.
 		  /// It should only be used through the \ref bfs() function, which makes
 		  /// it easier to use the algorithm.
 		  ///
 		  /// Simplicity means that the way to change the types defined
 		  /// in the traits class is based on functions that returns the new class
 		  /// and not on templatable built-in classes.
 		  /// When using the plain \ref Bfs
 		  /// the new class with the modified type comes from
 		  /// the original class by using the ::
 		  /// operator. In the case of \ref BfsWizard only
 		  /// a function have to be called, and it will
 		  /// return the needed class.
 		  ///
 		  /// It does not have own \ref run() method. When its \ref run() method
 		  /// is called, it initiates a plain \ref Bfs object, and calls the
 		  /// \ref Bfs::run() method of it.
 		  template<class TR>
 		  class BfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///\brief The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///\brief The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///\brief The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		  public:
 		    /// Constructor.
 		    BfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    BfsWizard(const Digraph &g, Node s=INVALID) :
 		      TR(g,s) {}
 		    ///Copy constructor
 		    BfsWizard(const TR &b) : TR(b) {}
 		    ~BfsWizard() {}
 		    ///Runs BFS algorithm from a source node.
 		    ///Runs BFS algorithm from a source node.
 		    ///The node can be given with the \ref source() function.
 		    void run()
+		    {
 		      if(Base::_source==INVALID) throw UninitializedParameter();
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if(Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if(Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if(Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if(Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
@@ -1143,386 +1139,385 @@
 		  ///Function type interface for Bfs algorithm.
 		  ///
 		  ///This function also has several
 		  ///\ref named-templ-func-param "named parameters",
 		  ///they are declared as the members of class \ref BfsWizard.
 		  ///The following
 		  ///example shows how to use these parameters.
 		  ///\code
 		  ///  bfs(g,source).predMap(preds).run();
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
 		  ///to the end of the parameter list.
 		  ///\sa BfsWizard
 		  ///\sa Bfs
 		  template<class GR>
 		  BfsWizard<BfsWizardBase<GR> >
 		  bfs(const GR &g,typename GR::Node s=INVALID)
+		  {
 		    return BfsWizard<BfsWizardBase<GR> >(g,s);
+		  }
 		#ifdef DOXYGEN
 		  /// \brief Visitor class for BFS.
 		  ///
 		  /// This class defines the interface of the BfsVisit events, and
 		  /// it could be the base of a real visitor class.
 		  template <typename _Digraph>
 		  struct BfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    /// \brief Called for the source node(s) of the BFS.
 		    ///
 		    /// This function is called for the source node(s) of the BFS.
 		    void start(const Node& node) {}
 		    /// \brief Called when a node is reached first time.
 		    ///
 		    /// This function is called when a node is reached first time.
 		    void reach(const Node& node) {}
 		    /// \brief Called when a node is processed.
 		    ///
 		    /// This function is called when a node is processed.
 		    void process(const Node& node) {}
 		    /// \brief Called when an arc reaches a new node.
 		    ///
 		    /// This function is called when the BFS finds an arc whose target node
 		    /// is not reached yet.
 		    void discover(const Arc& arc) {}
 		    /// \brief Called when an arc is examined but its target node is
 		    /// already discovered.
 		    ///
 		    /// This function is called when an arc is examined but its target node is
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		  };
 		#else
 		  template <typename _Digraph>
 		  struct BfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    void start(const Node&) {}
 		    void reach(const Node&) {}
 		    void process(const Node&) {}
 		    void discover(const Arc&) {}
 		    void examine(const Arc&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 		        Arc arc;
 		        Node node;
 		        visitor.start(node);
 		        visitor.reach(node);
 		        visitor.process(node);
 		        visitor.discover(arc);
 		        visitor.examine(arc);
+		      }
 		      _Visitor& visitor;
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of BfsVisit class.
 		  ///
 		  /// Default traits class of BfsVisit class.
 		  /// \tparam _Digraph The type of the digraph the algorithm runs on.
 		  template<class _Digraph>
 		  struct BfsVisitDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef _Digraph Digraph;
 		    /// \brief The type of the map that indicates which nodes are reached.
 		    ///
 		    /// The type of the map that indicates which nodes are reached.
 		    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a \ref ReachedMap.
 		    ///
 		    /// This function instantiates a \ref ReachedMap.
 		    /// \param digraph is the digraph, to which
 		    /// we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &digraph) {
 		      return new ReachedMap(digraph);
+		    }
 		  };
 		  /// \ingroup search
 		  ///
 		  /// \brief %BFS algorithm class with visitor interface.
 		  ///
 		  /// This class provides an efficient implementation of the %BFS algorithm
 		  /// with visitor interface.
 		  ///
 		  /// The %BfsVisit class provides an alternative interface to the Bfs
 		  /// class. It works with callback mechanism, the BfsVisit object calls
 		  /// the member functions of the \c Visitor class on every BFS event.
 		  ///
 		  /// This interface of the BFS algorithm should be used in special cases
 		  /// when extra actions have to be performed in connection with certain
 		  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
 		  /// instead.
 		  ///
 		  /// \tparam _Digraph The type of the digraph the algorithm runs on.
 		  /// The default value is
 		  /// \ref ListDigraph. The value of _Digraph is not used directly by
 		  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
 		  /// \tparam _Visitor The Visitor type that is used by the algorithm.
 		  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
 		  /// does not observe the BFS events. If you want to observe the BFS
 		  /// events, you should implement your own visitor class.
 		  /// \tparam _Traits Traits class to set various data types used by the
 		  /// algorithm. The default traits class is
 		  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
 		  /// See \ref BfsVisitDefaultTraits for the documentation of
 		  /// a BFS visit traits class.
 		#ifdef DOXYGEN
 		  template <typename _Digraph, typename _Visitor, typename _Traits>
 		#else
 		  template <typename _Digraph = ListDigraph,
 		            typename _Visitor = BfsVisitor<_Digraph>,
 		            typename _Traits = BfsDefaultTraits<_Digraph> >
 		#endif
 		  class BfsVisit {
 		  public:
 		    /// \brief \ref Exception for uninitialized parameters.
 		    ///
 		    /// This error represents problems in the initialization
 		    /// of the parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw()
+		      {
 		        return "lemon::BfsVisit::UninitializedParameter";
+		      }
 		    };
 		    ///The traits class.
 		    typedef _Traits Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The visitor type used by the algorithm.
 		    typedef _Visitor Visitor;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename Traits::ReachedMap ReachedMap;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *_digraph;
 		    //Pointer to the visitor object.
 		    Visitor *_visitor;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Node> _list;
 		    int _list_front, _list_back;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    //Creates the maps if necessary.
 		    void create_maps() {
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*_digraph);
+		      }
+		    }
 		  protected:
 		    BfsVisit() {}
 		  public:
 		    typedef BfsVisit Create;
 		    /// \name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public BfsVisit< Digraph, Visitor,
 		                                            SetReachedMapTraits<T> > {
 		      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param visitor The visitor object of the algorithm.
 		    BfsVisit(const Digraph& digraph, Visitor& visitor)
 		      : _digraph(&digraph), _visitor(&visitor),
 		        _reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ~BfsVisit() {
 		      if(local_reached) delete _reached;
+		    }
 		    /// \brief Sets the map that indicates which nodes are reached.
 		    ///
 		    /// Sets the map that indicates which nodes are reached.
 		    /// If you don't use this function before calling \ref run(),
 		    /// it will allocate one. The destructor deallocates this
 		    /// automatically allocated map, of course.
 		    /// \return <tt> (*this) </tt>
 		    BfsVisit &reachedMap(ReachedMap &m) {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached = false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  public:
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to use
 		    /// one of the member functions called \ref lemon::BfsVisit::run()
 		    /// "run()".
 		    /// \n
 		    /// If you need more control on the execution, first you must call
 		    /// \ref lemon::BfsVisit::init() "init()", then you can add several
 		    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
 		    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
 		    /// actual path computation.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    void init() {
 		      create_maps();
 		      _list.resize(countNodes(*_digraph));
 		      _list_front = _list_back = -1;
 		      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
 		        _reached->set(u, false);
+		      }
+		    }
 		    /// \brief Adds a new source node.
 		    ///
 		    /// Adds a new source node to the set of nodes to be processed.
 		    void addSource(Node s) {
 		      if(!(*_reached)[s]) {
 		          _reached->set(s,true);
 		          _visitor->start(s);
 		          _visitor->reach(s);
 		          _list[++_list_back] = s;
+		        }
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    Node processNextNode() {
 		      Node n = _list[++_list_front];
 		      _visitor->process(n);
 		      Arc e;
 		      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 		        Node m = _digraph->target(e);
 		        if (!(*_reached)[m]) {
 		          _visitor->discover(e);
 		          _visitor->reach(m);
 		          _reached->set(m, true);
 		          _list[++_list_back] = m;
 		        } else {
 		          _visitor->examine(e);
+		        }
+		      }
 		      return n;
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node and checks if the given target node
 		    /// is reached. If the target node is reachable from the processed
 		    /// node, then the \c reach parameter will be set to \c true.
 		    ///
 		    /// \param target The target node.
 		    /// \retval reach Indicates if the target node is reached.
 		    /// It should be initially \c false.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    Node processNextNode(Node target, bool& reach) {
 		      Node n = _list[++_list_front];
 		      _visitor->process(n);
 		      Arc e;
 		      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 		        Node m = _digraph->target(e);
 		        if (!(*_reached)[m]) {
 		          _visitor->discover(e);
 		          _visitor->reach(m);
 		          _reached->set(m, true);
 		          _list[++_list_back] = m;
 		          reach = reach || (target == m);
 		        } else {
 		          _visitor->examine(e);
+		        }
+		      }
 		      return n;
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node and checks if at least one of reached
 		    /// nodes has \c true value in the \c nm node map. If one node
 		    /// with \c true value is reachable from the processed node, then the
 		    /// \c rnode parameter will be set to the first of such nodes.
 		    ///
 		    /// \param nm A \c bool (or convertible) node map that indicates the
 		    /// possible targets.
 		    /// \retval rnode The reached target node.
 		    /// It should be initially \c INVALID.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    template <typename NM>
 		    Node processNextNode(const NM& nm, Node& rnode) {
 		      Node n = _list[++_list_front];
 		      _visitor->process(n);
 		      Arc e;
 		      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 		        Node m = _digraph->target(e);
 		        if (!(*_reached)[m]) {
 		          _visitor->discover(e);
 		          _visitor->reach(m);
 		          _reached->set(m, true);
 		          _list[++_list_back] = m;

lemon/bits/base_extender.h

Show inline comments

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

lemon/bits/vector_map.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_VECTOR_MAP_H
 		#define LEMON_BITS_VECTOR_MAP_H
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/core.h>
 		#include <lemon/bits/alteration_notifier.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		///\ingroup graphbits
 		///
 		///\file
 		///\brief Vector based graph maps.
 		namespace lemon {
 		  /// \ingroup graphbits
 		  ///
 		  /// \brief Graph map based on the std::vector storage.
 		  ///
 		  /// The VectorMap template class is graph map structure what
 		  /// automatically updates the map when a key is added to or erased from
 		  /// the map. This map type uses the std::vector to store the values.
 		  ///
-		  /// \tparam _Notifier The AlterationNotifier that will notify this map.
+		  /// \tparam _Graph The graph this map is attached to.
 		  /// \tparam _Item The item type of the graph items.
 		  /// \tparam _Value The value type of the map.
 		  /// \todo Fix the doc: there is _Graph parameter instead of _Notifier.
 		  template <typename _Graph, typename _Item, typename _Value>
 		  class VectorMap
 		    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
 		  private:
 		    /// The container type of the map.
 		    typedef std::vector<_Value> Container;
 		  public:
 		    /// The graph type of the map.
 		    typedef _Graph Graph;
 		    /// The item type of the map.
 		    typedef _Item Item;
 		    /// The reference map tag.
 		    typedef True ReferenceMapTag;
 		    /// The key type of the map.
 		    typedef _Item Key;
 		    /// The value type of the map.
 		    typedef _Value Value;
 		    /// The notifier type.
 		    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
 		    /// The map type.
 		    typedef VectorMap Map;
 		    /// The base class of the map.
 		    typedef typename Notifier::ObserverBase Parent;
 		    /// The reference type of the map;
 		    typedef typename Container::reference Reference;
 		    /// The const reference type of the map;
 		    typedef typename Container::const_reference ConstReference;
 		    /// \brief Constructor to attach the new map into the notifier.
 		    ///
 		    /// It constructs a map and attachs it into the notifier.
 		    /// It adds all the items of the graph to the map.
 		    VectorMap(const Graph& graph) {
 		      Parent::attach(graph.notifier(Item()));
 		      container.resize(Parent::notifier()->maxId() + 1);
+		    }
 		    /// \brief Constructor uses given value to initialize the map.
 		    ///
 		    /// It constructs a map uses a given value to initialize the map.
 		    /// It adds all the items of the graph to the map.
 		    VectorMap(const Graph& graph, const Value& value) {
 		      Parent::attach(graph.notifier(Item()));
 		      container.resize(Parent::notifier()->maxId() + 1, value);
+		    }
 		  private:
 		    /// \brief Copy constructor
 		    ///
 		    /// Copy constructor.
 		    VectorMap(const VectorMap& _copy) : Parent() {
 		      if (_copy.attached()) {
 		        Parent::attach(*_copy.notifier());
 		        container = _copy.container;
+		      }
+		    }
 		    /// \brief Assign operator.
 		    ///
 		    /// This operator assigns for each item in the map the
 		    /// value mapped to the same item in the copied map.
 		    /// The parameter map should be indiced with the same
 		    /// itemset because this assign operator does not change
 		    /// the container of the map.
 		    VectorMap& operator=(const VectorMap& cmap) {
 		      return operator=<VectorMap>(cmap);
+		    }
 		    /// \brief Template assign operator.
 		    ///
 		    /// The given parameter should be conform to the ReadMap
 		    /// concecpt and could be indiced by the current item set of
 		    /// the NodeMap. In this case the value for each item
 		    /// is assigned by the value of the given ReadMap.
 		    template <typename CMap>
 		    VectorMap& operator=(const CMap& cmap) {
 		      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
 		      const typename Parent::Notifier* nf = Parent::notifier();
 		      Item it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        set(it, cmap[it]);
+		      }
 		      return *this;
+		    }
 		  public:
 		    /// \brief The subcript operator.
 		    ///
 		    /// The subscript operator. The map can be subscripted by the
 		    /// actual items of the graph.
 		    Reference operator[](const Key& key) {
 		      return container[Parent::notifier()->id(key)];
+		    }
 		    /// \brief The const subcript operator.
 		    ///
 		    /// The const subscript operator. The map can be subscripted by the
 		    /// actual items of the graph.
 		    ConstReference operator[](const Key& key) const {
 		      return container[Parent::notifier()->id(key)];
+		    }
 		    /// \brief The setter function of the map.
 		    ///
 		    /// It the same as operator[](key) = value expression.
 		    void set(const Key& key, const Value& value) {
 		      (*this)[key] = value;
+		    }
 		  protected:
 		    /// \brief Adds a new key to the map.
 		    ///
 		    /// It adds a new key to the map. It called by the observer notifier
 		    /// and it overrides the add() member function of the observer base.
 		    virtual void add(const Key& key) {
 		      int id = Parent::notifier()->id(key);
 		      if (id >= int(container.size())) {
 		        container.resize(id + 1);
+		      }
+		    }
 		    /// \brief Adds more new keys to the map.
 		    ///
 		    /// It adds more new keys to the map. It called by the observer notifier
 		    /// and it overrides the add() member function of the observer base.
 		    virtual void add(const std::vector<Key>& keys) {
 		      int max = container.size() - 1;
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        int id = Parent::notifier()->id(keys[i]);
 		        if (id >= max) {
 		          max = id;
+		        }
+		      }
 		      container.resize(max + 1);
+		    }
 		    /// \brief Erase a key from the map.
 		    ///
 		    /// Erase a key from the map. It called by the observer notifier
 		    /// and it overrides the erase() member function of the observer base.
 		    virtual void erase(const Key& key) {
 		      container[Parent::notifier()->id(key)] = Value();
+		    }
 		    /// \brief Erase more keys from the map.
 		    ///
 		    /// Erase more keys from the map. It called by the observer notifier
 		    /// and it overrides the erase() member function of the observer base.
 		    virtual void erase(const std::vector<Key>& keys) {
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        container[Parent::notifier()->id(keys[i])] = Value();
+		      }
+		    }
 		    /// \brief Buildes the map.
 		    ///
 		    /// It buildes the map. It called by the observer notifier
 		    /// and it overrides the build() member function of the observer base.
 		    virtual void build() {
 		      int size = Parent::notifier()->maxId() + 1;
 		      container.reserve(size);
 		      container.resize(size);
+		    }
 		    /// \brief Clear the map.
 		    ///
 		    /// It erase all items from the map. It called by the observer notifier
 		    /// and it overrides the clear() member function of the observer base.
 		    virtual void clear() {
 		      container.clear();
+		    }
 		  private:
 		    Container container;
 		  };
+		}

lemon/concept_check.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		// This file contains a modified version of the concept checking
 		// utility from BOOST.
 		// See the appropriate copyright notice below.
 		// (C) Copyright Jeremy Siek 2000.
 		// Distributed under the Boost Software License, Version 1.0. (See
 		// accompanying file LICENSE_1_0.txt or copy at
 		// http://www.boost.org/LICENSE_1_0.txt)
 		//
 		// Revision History:
 		//   05 May   2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
 		//   02 April 2001: Removed limits header altogether. (Jeremy Siek)
 		//   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
 		//
 		// See http://www.boost.org/libs/concept_check for documentation.
 		///\file
 		///\brief Basic utilities for concept checking.
 		///
 		///\todo Are we still using BOOST concept checking utility?
 		///Is the BOOST copyright notice necessary?
 		#ifndef LEMON_CONCEPT_CHECK_H
 		#define LEMON_CONCEPT_CHECK_H
 		namespace lemon {
 		  /*
 		    "inline" is used for ignore_unused_variable_warning()
 		    and function_requires() to make sure there is no
 		    overtarget with g++.
 		  */
 		  template <class T> inline void ignore_unused_variable_warning(const T&) { }
 		  ///\e
 		  template <class Concept>
 		  inline void function_requires()
+		  {
 		#if !defined(NDEBUG)
 		    void (Concept::*x)() = & Concept::constraints;
 		    ignore_unused_variable_warning(x);
 		#endif
+		  }
 		  ///\e
 		  template <typename Concept, typename Type>
 		  inline void checkConcept() {
 		#if !defined(NDEBUG)
 		    typedef typename Concept::template Constraints<Type> ConceptCheck;
 		    void (ConceptCheck::*x)() = & ConceptCheck::constraints;
 		    ignore_unused_variable_warning(x);
 		#endif
+		  }
 		} // namespace lemon
 		#endif // LEMON_CONCEPT_CHECK_H

lemon/concepts/path.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup concept
 		///\file
 		///\brief Classes for representing paths in digraphs.
 		///
 		///\todo Iterators have obsolete style
 		#ifndef LEMON_CONCEPT_PATH_H
 		#define LEMON_CONCEPT_PATH_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief A skeleton structure for representing directed paths in
 		    /// a digraph.
 		    ///
 		    /// A skeleton structure for representing directed paths in a
 		    /// digraph.
 		    /// \tparam _Digraph The digraph type in which the path is.
 		    ///
 		    /// In a sense, the path can be treated as a list of arcs. The
 		    /// lemon path type stores just this list. As a consequence it
 		    /// cannot enumerate the nodes in the path and the zero length
 		    /// paths cannot store the source.
 		    ///
 		    template <typename _Digraph>
 		    class Path {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef _Digraph Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
 		      class ArcIt;
 		      /// \brief Default constructor
 		      Path() {}
 		      /// \brief Template constructor
 		      template <typename CPath>
 		      Path(const CPath& cpath) {}
 		      /// \brief Template assigment
 		      template <typename CPath>
 		      Path& operator=(const CPath& cpath) {}
 		      /// Length of the path ie. the number of arcs in the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// Resets the path to an empty path.
 		      void clear() {}
 		      /// \brief LEMON style iterator for path arcs
 		      ///
 		      /// This class is used to iterate on the arcs of the paths.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
 		        /// Constructor for first arc
 		        ArcIt(const Path &) {}
 		        /// Conversion to Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          Path<Digraph> pc;
 		          _Path p, pp(pc);
 		          int l = p.length();
 		          int e = p.empty();
 		          p.clear();
 		          p = pc;
 		          typename _Path::ArcIt id, ii(INVALID), i(p);
 		          ++i;
 		          typename Digraph::Arc ed = i;
 		          e = (i == ii);
 		          e = (i != ii);
 		          e = (i < ii);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(pp);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ii);
 		          ignore_unused_variable_warning(ed);
+		        }
 		      };
 		    };
 		    namespace _path_bits {
 		      template <typename _Digraph, typename _Path, typename RevPathTag = void>
 		      struct PathDumperConstraints {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::ArcIt id, i(p);
 		          ++i;
 		          typename _Digraph::Arc ed = i;
 		          e = (i == INVALID);
 		          e = (i != INVALID);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ed);
+		        }
 		        _Path& p;
 		      };
 		      template <typename _Digraph, typename _Path>
 		      struct PathDumperConstraints<
 		        _Digraph, _Path,
 		        typename enable_if<typename _Path::RevPathTag, void>::type
 		      > {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::RevArcIt id, i(p);
 		          ++i;
 		          typename _Digraph::Arc ed = i;
 		          e = (i == INVALID);
 		          e = (i != INVALID);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ed);
+		        }
 		        _Path& p;
 		      };
+		    }
 		    /// \brief A skeleton structure for path dumpers.
 		    ///
 		    /// A skeleton structure for path dumpers. The path dumpers are
 		    /// the generalization of the paths. The path dumpers can
 		    /// enumerate the arcs of the path wheter in forward or in
 		    /// backward order.  In most time these classes are not used
 		    /// directly rather it used to assign a dumped class to a real
 		    /// path type.
 		    ///
 		    /// The main purpose of this concept is that the shortest path
 		    /// algorithms can enumerate easily the arcs in reverse order.
 		    /// If we would like to give back a real path from these
 		    /// algorithms then we should create a temporarly path object. In
 		    /// LEMON such algorithms gives back a path dumper what can
 		    /// assigned to a real path and the dumpers can be implemented as
 		    /// an adaptor class to the predecessor map.
 		    /// \tparam _Digraph  The digraph type in which the path is.
 		    ///
 		    /// The paths can be constructed from any path type by a
 		    /// template constructor or a template assignment operator.
 		    ///
 		    template <typename _Digraph>
 		    class PathDumper {
 		    public:

lemon/dfs.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_DFS_H
 		#define LEMON_DFS_H
 		///\ingroup search
 		///\file
 		///\brief DFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/assert.h>
 		#include <lemon/maps.h>
 		namespace lemon {
 		  ///Default traits class of Dfs class.
 		  ///Default traits class of Dfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref DistMap.
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%DFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %DFS algorithm.
 		  ///
 		  ///There is also a \ref dfs() "function type interface" for the DFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default value is \ref ListDigraph. The value of GR is not used
 		  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
 		  ///\tparam TR Traits class to set various data types used by the algorithm.
 		  ///The default traits class is
 		  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
 		  ///See \ref DfsDefaultTraits for the documentation of
 		  ///a Dfs traits class.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=DfsDefaultTraits<GR> >
 		#endif
 		  class Dfs {
 		  public:
 		    ///\ref Exception for uninitialized parameters.
 		    ///This error represents problems in the initialization of the
 		    ///parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 		        return "lemon::Dfs::UninitializedParameter";
+		      }
 		    };
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The traits class.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::OutArcIt> _stack;
 		    int _stack_head;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Dfs() {}
 		  public:
 		    typedef Dfs Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    template <class T>
 		    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 		      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    template <class T>
 		    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    template <class T>
 		    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap :
 		      public Dfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param g The digraph the algorithm runs on.
 		    Dfs(const Digraph &g) :
 		      G(&g),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _reached(NULL), local_reached(false),
 		      _processed(NULL), local_processed(false)
 		    { }
 		    ///Destructor.
 		    ~Dfs()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_reached) delete _reached;
 		      if(local_processed) delete _processed;
+		    }
 		    ///Sets the map that stores the predecessor arcs.
 		    ///Sets the map that stores the predecessor arcs.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are reached.
 		    ///Sets the map that indicates which nodes are reached.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &reachedMap(ReachedMap &m)
+		    {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are processed.
 		    ///Sets the map that indicates which nodes are processed.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &processedMap(ProcessedMap &m)
+		    {
 		      if(local_processed) {
 		        delete _processed;
@@ -593,385 +590,384 @@
 		    Arc start(const ArcBoolMap &am)
+		    {
 		      while ( !emptyQueue() && !am[_stack[_stack_head]] )
 		        processNextArc();
 		      return emptyQueue() ? INVALID : _stack[_stack_head];
+		    }
 		    ///Runs the algorithm from the given node.
 		    ///This method runs the %DFS algorithm from node \c s
 		    ///in order to compute the DFS path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the %DFS tree,
 		    ///- the distance of each node from the root in the %DFS tree.
 		    ///
 		    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///Finds the %DFS path between \c s and \c t.
 		    ///This method runs the %DFS algorithm from node \c s
 		    ///in order to compute the DFS path to \c t.
 		    ///
 		    ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
 		    ///if \c t is reachable form \c s, \c 0 otherwise.
 		    ///
 		    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
 		    ///just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start(t);
 		    ///\endcode
 		    int run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t)?_stack_head+1:0;
+		    }
 		    ///Runs the algorithm to visit all nodes in the digraph.
 		    ///This method runs the %DFS algorithm in order to compute the
 		    ///%DFS path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the %DFS tree,
 		    ///- the distance of each node from the root in the %DFS tree.
 		    ///
 		    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  for (NodeIt n(digraph); n != INVALID; ++n) {
 		    ///    if (!d.reached(n)) {
 		    ///      d.addSource(n);
 		    ///      d.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt it(*G); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The result of the %DFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
 		    ///"start()" must be called before using them.
 		    ///@{
 		    ///The DFS path to a node.
 		    ///Returns the DFS path to a node.
 		    ///
 		    ///\warning \c t should be reachable from the root.
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///The distance of a node from the root.
 		    ///Returns the distance of a node from the root.
 		    ///
 		    ///\warning If node \c v is not reachable from the root, then
 		    ///the return value of this function is undefined.
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the %DFS tree for a node.
 		    ///This function returns the 'previous arc' of the %DFS tree for the
 		    ///node \c v, i.e. it returns the last arc of a %DFS path from the
 		    ///root to \c v. It is \c INVALID
 		    ///if \c v is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predNode().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before using
 		    ///this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///Returns the 'previous node' of the %DFS tree.
 		    ///This function returns the 'previous node' of the %DFS
 		    ///tree for the node \c v, i.e. it returns the last but one node
 		    ///from a %DFS path from the root to \c v. It is \c INVALID
 		    ///if \c v is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predArc().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->source((*_pred)[v]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the
 		    ///distances of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the DFS tree.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if a node is reachable from the root(s).
 		    ///Returns \c true if \c v is reachable from the root(s).
 		    ///\pre Either \ref run() or \ref start()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of dfs() function.
 		  ///Default traits class of dfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsWizardDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#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.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef NullMap<typename Digraph::Node,int> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const Digraph &g)
 		#else
 		    static DistMap *createDistMap(const Digraph &)
 		#endif
+		    {
 		      return new DistMap();
+		    }
 		  };
 		  /// Default traits class used by \ref DfsWizard
 		  /// To make it easier to use Dfs algorithm
 		  /// we have created a wizard class.
 		  /// This \ref DfsWizard class needs default traits,
 		  /// as well as the \ref Dfs class.
 		  /// The \ref DfsWizardBase is a class to be the default traits of the
 		  /// \ref DfsWizard class.
 		  template<class GR>
 		  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
+		  {
 		    typedef DfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the source node.
 		    Node _source;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to default values (0, INVALID).
 		    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _source(INVALID) {}
 		    /// Constructor.
 		    /// This constructor requires some parameters,
 		    /// listed in the parameters list.
 		    /// Others are initiated to 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param s The source node.
 		    DfsWizardBase(const GR &g, Node s=INVALID) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
 		  };
 		  /// Auxiliary class for the function type interface of DFS algorithm.
 		  /// This auxiliary class is created to implement the function type
 		  /// interface of \ref Dfs algorithm. It uses the functions and features
 		  /// of the plain \ref Dfs, but it is much simpler to use it.
 		  /// It should only be used through the \ref dfs() function, which makes
 		  /// it easier to use the algorithm.
 		  ///
 		  /// Simplicity means that the way to change the types defined
 		  /// in the traits class is based on functions that returns the new class
 		  /// and not on templatable built-in classes.
 		  /// When using the plain \ref Dfs
 		  /// the new class with the modified type comes from
 		  /// the original class by using the ::
 		  /// operator. In the case of \ref DfsWizard only
 		  /// a function have to be called, and it will
 		  /// return the needed class.
 		  ///
 		  /// It does not have own \ref run() method. When its \ref run() method
 		  /// is called, it initiates a plain \ref Dfs object, and calls the
 		  /// \ref Dfs::run() method of it.
 		  template<class TR>
 		  class DfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///\brief The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///\brief The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///\brief The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		  public:
 		    /// Constructor.
 		    DfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    DfsWizard(const Digraph &g, Node s=INVALID) :
 		      TR(g,s) {}
 		    ///Copy constructor
 		    DfsWizard(const TR &b) : TR(b) {}
 		    ~DfsWizard() {}
 		    ///Runs DFS algorithm from a source node.
 		    ///Runs DFS algorithm from a source node.
 		    ///The node can be given with the \ref source() function.
 		    void run()
+		    {
 		      if(Base::_source==INVALID) throw UninitializedParameter();
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if(Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if(Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if(Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if(Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
@@ -1090,386 +1086,385 @@
 		  ///\sa DfsWizard
 		  ///\sa Dfs
 		  template<class GR>
 		  DfsWizard<DfsWizardBase<GR> >
 		  dfs(const GR &g,typename GR::Node s=INVALID)
+		  {
 		    return DfsWizard<DfsWizardBase<GR> >(g,s);
+		  }
 		#ifdef DOXYGEN
 		  /// \brief Visitor class for DFS.
 		  ///
 		  /// This class defines the interface of the DfsVisit events, and
 		  /// it could be the base of a real visitor class.
 		  template <typename _Digraph>
 		  struct DfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    /// \brief Called for the source node of the DFS.
 		    ///
 		    /// This function is called for the source node of the DFS.
 		    void start(const Node& node) {}
 		    /// \brief Called when the source node is leaved.
 		    ///
 		    /// This function is called when the source node is leaved.
 		    void stop(const Node& node) {}
 		    /// \brief Called when a node is reached first time.
 		    ///
 		    /// This function is called when a node is reached first time.
 		    void reach(const Node& node) {}
 		    /// \brief Called when an arc reaches a new node.
 		    ///
 		    /// This function is called when the DFS finds an arc whose target node
 		    /// is not reached yet.
 		    void discover(const Arc& arc) {}
 		    /// \brief Called when an arc is examined but its target node is
 		    /// already discovered.
 		    ///
 		    /// This function is called when an arc is examined but its target node is
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		    /// \brief Called when the DFS steps back from a node.
 		    ///
 		    /// This function is called when the DFS steps back from a node.
 		    void leave(const Node& node) {}
 		    /// \brief Called when the DFS steps back on an arc.
 		    ///
 		    /// This function is called when the DFS steps back on an arc.
 		    void backtrack(const Arc& arc) {}
 		  };
 		#else
 		  template <typename _Digraph>
 		  struct DfsVisitor {
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    void start(const Node&) {}
 		    void stop(const Node&) {}
 		    void reach(const Node&) {}
 		    void discover(const Arc&) {}
 		    void examine(const Arc&) {}
 		    void leave(const Node&) {}
 		    void backtrack(const Arc&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 		        Arc arc;
 		        Node node;
 		        visitor.start(node);
 		        visitor.stop(arc);
 		        visitor.reach(node);
 		        visitor.discover(arc);
 		        visitor.examine(arc);
 		        visitor.leave(node);
 		        visitor.backtrack(arc);
+		      }
 		      _Visitor& visitor;
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of DfsVisit class.
 		  ///
 		  /// Default traits class of DfsVisit class.
 		  /// \tparam _Digraph The type of the digraph the algorithm runs on.
 		  template<class _Digraph>
 		  struct DfsVisitDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef _Digraph Digraph;
 		    /// \brief The type of the map that indicates which nodes are reached.
 		    ///
 		    /// The type of the map that indicates which nodes are reached.
 		    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a \ref ReachedMap.
 		    ///
 		    /// This function instantiates a \ref ReachedMap.
 		    /// \param digraph is the digraph, to which
 		    /// we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &digraph) {
 		      return new ReachedMap(digraph);
+		    }
 		  };
 		  /// \ingroup search
 		  ///
 		  /// \brief %DFS algorithm class with visitor interface.
 		  ///
 		  /// This class provides an efficient implementation of the %DFS algorithm
 		  /// with visitor interface.
 		  ///
 		  /// The %DfsVisit class provides an alternative interface to the Dfs
 		  /// class. It works with callback mechanism, the DfsVisit object calls
 		  /// the member functions of the \c Visitor class on every DFS event.
 		  ///
 		  /// This interface of the DFS algorithm should be used in special cases
 		  /// when extra actions have to be performed in connection with certain
 		  /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
 		  /// instead.
 		  ///
 		  /// \tparam _Digraph The type of the digraph the algorithm runs on.
 		  /// The default value is
 		  /// \ref ListDigraph. The value of _Digraph is not used directly by
 		  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
 		  /// \tparam _Visitor The Visitor type that is used by the algorithm.
 		  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
 		  /// does not observe the DFS events. If you want to observe the DFS
 		  /// events, you should implement your own visitor class.
 		  /// \tparam _Traits Traits class to set various data types used by the
 		  /// algorithm. The default traits class is
 		  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
 		  /// See \ref DfsVisitDefaultTraits for the documentation of
 		  /// a DFS visit traits class.
 		#ifdef DOXYGEN
 		  template <typename _Digraph, typename _Visitor, typename _Traits>
 		#else
 		  template <typename _Digraph = ListDigraph,
 		            typename _Visitor = DfsVisitor<_Digraph>,
 		            typename _Traits = DfsDefaultTraits<_Digraph> >
 		#endif
 		  class DfsVisit {
 		  public:
 		    /// \brief \ref Exception for uninitialized parameters.
 		    ///
 		    /// This error represents problems in the initialization
 		    /// of the parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw()
+		      {
 		        return "lemon::DfsVisit::UninitializedParameter";
+		      }
 		    };
 		    ///The traits class.
 		    typedef _Traits Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The visitor type used by the algorithm.
 		    typedef _Visitor Visitor;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename Traits::ReachedMap ReachedMap;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *_digraph;
 		    //Pointer to the visitor object.
 		    Visitor *_visitor;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Arc> _stack;
 		    int _stack_head;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    //Creates the maps if necessary.
 		    void create_maps() {
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*_digraph);
+		      }
+		    }
 		  protected:
 		    DfsVisit() {}
 		  public:
 		    typedef DfsVisit Create;
 		    /// \name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public DfsVisit< Digraph, Visitor,
 		                                            SetReachedMapTraits<T> > {
 		      typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param visitor The visitor object of the algorithm.
 		    DfsVisit(const Digraph& digraph, Visitor& visitor)
 		      : _digraph(&digraph), _visitor(&visitor),
 		        _reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ~DfsVisit() {
 		      if(local_reached) delete _reached;
+		    }
 		    /// \brief Sets the map that indicates which nodes are reached.
 		    ///
 		    /// Sets the map that indicates which nodes are reached.
 		    /// If you don't use this function before calling \ref run(),
 		    /// it will allocate one. The destructor deallocates this
 		    /// automatically allocated map, of course.
 		    /// \return <tt> (*this) </tt>
 		    DfsVisit &reachedMap(ReachedMap &m) {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  public:
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to use
 		    /// one of the member functions called \ref lemon::DfsVisit::run()
 		    /// "run()".
 		    /// \n
 		    /// If you need more control on the execution, first you must call
 		    /// \ref lemon::DfsVisit::init() "init()", then you can add several
 		    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
 		    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
 		    /// actual path computation.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    void init() {
 		      create_maps();
 		      _stack.resize(countNodes(*_digraph));
 		      _stack_head = -1;
 		      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
 		        _reached->set(u, false);
+		      }
+		    }
 		    ///Adds a new source node.
 		    ///Adds a new source node to the set of nodes to be processed.
 		    ///
 		    ///\pre The stack must be empty. (Otherwise the algorithm gives
 		    ///false results.)
 		    ///
 		    ///\warning Distances will be wrong (or at least strange) in case of
 		    ///multiple sources.
 		    void addSource(Node s)
+		    {
 		      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
 		      if(!(*_reached)[s]) {
 		          _reached->set(s,true);
 		          _visitor->start(s);
 		          _visitor->reach(s);
 		          Arc e;
 		          _digraph->firstOut(e, s);
 		          if (e != INVALID) {
 		            _stack[++_stack_head] = e;
 		          } else {
 		            _visitor->leave(s);
+		          }
+		        }
+		    }
 		    /// \brief Processes the next arc.
 		    ///
 		    /// Processes the next arc.
 		    ///
 		    /// \return The processed arc.
 		    ///
 		    /// \pre The stack must not be empty.
 		    Arc processNextArc() {
 		      Arc e = _stack[_stack_head];
 		      Node m = _digraph->target(e);
 		      if(!(*_reached)[m]) {
 		        _visitor->discover(e);
 		        _visitor->reach(m);
 		        _reached->set(m, true);
 		        _digraph->firstOut(_stack[++_stack_head], m);
 		      } else {
 		        _visitor->examine(e);
 		        m = _digraph->source(e);
 		        _digraph->nextOut(_stack[_stack_head]);
+		      }
 		      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
 		        _visitor->leave(m);
 		        --_stack_head;
 		        if (_stack_head >= 0) {
 		          _visitor->backtrack(_stack[_stack_head]);
 		          m = _digraph->source(_stack[_stack_head]);
 		          _digraph->nextOut(_stack[_stack_head]);
 		        } else {
 		          _visitor->stop(m);
+		        }
+		      }
 		      return e;
+		    }
 		    /// \brief Next arc to be processed.
 		    ///
 		    /// Next arc to be processed.
 		    ///
 		    /// \return The next arc to be processed or INVALID if the stack is
 		    /// empty.
 		    Arc nextArc() const {
 		      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
+		    }
 		    /// \brief Returns \c false if there are nodes
 		    /// to be processed.
 		    ///
 		    /// Returns \c false if there are nodes
 		    /// to be processed in the queue (stack).
 		    bool emptyQueue() const { return _stack_head < 0; }
 		    /// \brief Returns the number of the nodes to be processed.
 		    ///
 		    /// Returns the number of the nodes to be processed in the queue (stack).
 		    int queueSize() const { return _stack_head + 1; }
 		    /// \brief Executes the algorithm.
 		    ///
 		    /// Executes the algorithm.
 		    ///
 		    /// This method runs the %DFS algorithm from the root node
 		    /// in order to compute the %DFS path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the %DFS tree,
 		    /// - the distance of each node from the root in the %DFS tree.
 		    ///
 		    /// \pre init() must be called and a root node should be
 		    /// added with addSource() before using this function.
 		    ///

lemon/dijkstra.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_DIJKSTRA_H
 		#define LEMON_DIJKSTRA_H
 		///\ingroup shortest_path
 		///\file
 		///\brief Dijkstra algorithm.
 		#include <limits>
 		#include <lemon/list_graph.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		namespace lemon {
 		  /// \brief Default operation traits for the Dijkstra algorithm class.
 		  ///
 		  /// This operation traits class 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 is less than the second.
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  /// \brief Widest path operation traits for the Dijkstra algorithm class.
 		  ///
 		  /// This operation traits class defines all computational operations and
 		  /// constants which are used in the Dijkstra algorithm for widest path
 		  /// computation.
 		  ///
 		  /// \see DijkstraDefaultOperationTraits
 		  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 is 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.
 		  ///\tparam GR The type of the digraph.
 		  ///\tparam LM The type of the length map.
 		  template<class GR, class LM>
 		  struct DijkstraDefaultTraits
+		  {
 		    ///The type of the digraph 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.
 		    /// This class defines the operations that are used in the algorithm.
 		    /// \see DijkstraDefaultOperationTraits
 		    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
 		    /// The cross reference type used by the heap.
 		    /// The cross reference type used by the heap.
 		    /// Usually it is \c Digraph::NodeMap<int>.
 		    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		    ///Instantiates a \ref HeapCrossRef.
 		    ///This function instantiates a \ref HeapCrossRef.
 		    /// \param g is the digraph, to which we would like to define the
 		    /// \ref HeapCrossRef.
 		    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
+		    {
 		      return new HeapCrossRef(g);
+		    }
 		    ///The heap type used by the Dijkstra algorithm.
 		    ///The heap type used by the Dijkstra algorithm.
 		    ///
 		    ///\sa BinHeap
 		    ///\sa Dijkstra
 		    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
 		    ///Instantiates a \ref Heap.
 		    ///This function instantiates a \ref Heap.
 		    static Heap *createHeap(HeapCrossRef& r)
+		    {
 		      return new Heap(r);
+		    }
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient for the initialization
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    ///\todo If it is set to a real map,
 		    ///Dijkstra::processed() should read this.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%Dijkstra algorithm class.
 		  /// \ingroup shortest_path
 		  ///This class provides an efficient implementation of the %Dijkstra algorithm.
 		  ///
 		  ///The arc lengths are passed to the algorithm using a
 		  ///\ref concepts::ReadMap "ReadMap",
 		  ///so it is easy to change it to any kind of length.
 		  ///The type of the length is determined by the
 		  ///\ref concepts::ReadMap::Value "Value" of the length map.
 		  ///It is also possible to change the underlying priority heap.
 		  ///
 		  ///There is also a \ref dijkstra() "function type interface" for the
 		  ///%Dijkstra algorithm, which is convenient in the simplier cases and
 		  ///it can be used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default value is \ref ListDigraph.
 		  ///The value of GR is not used directly by \ref Dijkstra, it is only
 		  ///passed to \ref DijkstraDefaultTraits.
 		  ///\tparam LM A readable arc map that determines the lengths of the
 		  ///arcs. It is read once for each arc, so the map may involve in
 		  ///relatively time consuming process to compute the arc lengths if
 		  ///it is necessary. The default map type is \ref
 		  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
 		  ///The value of LM is not used directly by \ref Dijkstra, it is only
 		  ///passed to \ref DijkstraDefaultTraits.
 		  ///\tparam TR Traits class to set various data types used by the algorithm.
 		  ///The default traits class is \ref DijkstraDefaultTraits
 		  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
 		  ///for the documentation of a Dijkstra traits class.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LM, typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename LM=typename GR::template ArcMap<int>,
 		            typename TR=DijkstraDefaultTraits<GR,LM> >
 		#endif
 		  class Dijkstra {
 		  public:
 		    ///\ref Exception for uninitialized parameters.
 		    ///This error represents problems in the initialization of the
 		    ///parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 		        return "lemon::Dijkstra::UninitializedParameter";
+		      }
 		    };
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///The type of the length of the arcs.
 		    typedef typename TR::LengthMap::Value Value;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The cross reference type used for the current heap.
 		    typedef typename TR::HeapCrossRef HeapCrossRef;
 		    ///The heap type used by the algorithm.
 		    typedef typename TR::Heap Heap;
 		    ///The operation traits class.
 		    typedef typename TR::OperationTraits OperationTraits;
 		    ///The traits class.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the length map.
 		    const LengthMap *length;
 		    //Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    //Pointer to the heap cross references.
 		    HeapCrossRef *_heap_cross_ref;
 		    //Indicates if _heap_cross_ref is locally allocated (true) or not.
 		    bool local_heap_cross_ref;
 		    //Pointer to the heap.
 		    Heap *_heap;
 		    //Indicates if _heap is locally allocated (true) or not.
 		    bool local_heap;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_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 SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    template <class T>
 		    struct SetPredMap
 		      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    template <class T>
 		    struct SetDistMap
 		      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    template <class T>
 		    struct SetProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
 		      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
 		      Create;
 		    };
 		    template <class H, class CR>
 		    struct SetHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
 		        throw UninitializedParameter();
+		      }
 		      static Heap *createHeap(HeapCrossRef &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///heap and cross reference type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting heap and cross
 		    ///reference type.
 		    template <class H, class CR = typename Digraph::template NodeMap<int> >
 		    struct SetHeap
 		      : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
 		    };
 		    template <class H, class CR>
 		    struct SetStandardHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
 		        return new HeapCrossRef(G);
+		      }
 		      static Heap *createHeap(HeapCrossRef &R)
+		      {
 		        return new Heap(R);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///heap and cross reference type with automatic allocation
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting heap and cross
 		    ///reference type. It can allocate the heap and the cross reference
 		    ///object if the cross reference's constructor waits for the digraph as
 		    ///parameter and the heap's constructor waits for the cross reference.
 		    template <class H, class CR = typename Digraph::template NodeMap<int> >
 		    struct SetStandardHeap
 		      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
 		      Create;
 		    };
 		    template <class T>
 		    struct SetOperationTraitsTraits : public Traits {
 		      typedef T OperationTraits;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref OperationTraits type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref OperationTraits type.
 		    template <class T>
 		    struct SetOperationTraits
 		      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
 		      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
 		      Create;
 		    };
 		    ///@}
 		  protected:
 		    Dijkstra() {}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param _g The digraph the algorithm runs on.
 		    ///\param _length The length map used by the algorithm.
 		    Dijkstra(const Digraph& _g, const LengthMap& _length) :
 		      G(&_g), length(&_length),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _processed(NULL), local_processed(false),
@@ -768,482 +764,476 @@
 		      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
 		      if ( _heap->empty() ) return INVALID;
 		      finalizeNodeData(_heap->top(),_heap->prio());
 		      return _heap->top();
+		    }
 		    ///Runs the algorithm from the given node.
 		    ///This method runs the %Dijkstra algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree,
 		    ///- the distance of each node from the root.
 		    ///
 		    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs the %Dijkstra algorithm from node \c s
 		    ///in order to compute the shortest path to \c t.
 		    ///
 		    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
 		    ///if \c t is reachable form \c s, \c 0 otherwise.
 		    ///
 		    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
 		    ///shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start(t);
 		    ///\endcode
 		    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
 		    ///Either \ref lemon::Dijkstra::run() "run()" or
 		    ///\ref lemon::Dijkstra::start() "start()" must be called before
 		    ///using them.
 		    ///@{
 		    ///The shortest path to a node.
 		    ///Returns the shortest path to a node.
 		    ///
 		    ///\warning \c t should be reachable from the root(s).
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///The distance of a node from the root(s).
 		    ///Returns the distance of a node from the root(s).
 		    ///
 		    ///\warning If node \c v is not reachable from the root(s), then
 		    ///the return value of this function is undefined.
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Value dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the shortest path tree for a node.
 		    ///This function returns the 'previous arc' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last arc of a
 		    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
 		    ///is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predNode().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v]; }
 		    ///Returns the 'previous node' of the shortest path tree for a node.
 		    ///This function returns the 'previous node' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last but one node
 		    ///from a shortest path from the root(s) to \c v. It is \c INVALID
 		    ///if \c v is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predArc().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->source((*_pred)[v]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the distances
 		    ///of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the shortest path tree.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if a node is reachable from the root(s).
 		    ///Returns \c true if \c v is reachable from the root(s).
 		    ///\pre Either \ref run() or \ref start()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_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 Either \ref run() or \ref start()
 		    ///must be called before using this function.
 		    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
 		                                          Heap::POST_HEAP; }
 		    ///The current distance of a node from the root(s).
 		    ///Returns the current distance of a node from the root(s).
 		    ///It may be decreased in the following processes.
 		    ///\pre \c v should be reached but not processed.
 		    Value currentDist(Node v) const { return (*_heap)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of dijkstra() function.
 		  ///Default traits class of dijkstra() function.
 		  ///\tparam GR The type of the digraph.
 		  ///\tparam LM The type of the length map.
 		  template<class GR, class LM>
 		  struct DijkstraWizardDefaultTraits
+		  {
 		    ///The type of the digraph 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.
 		    /// This class defines the operations that are used in the algorithm.
 		    /// \see DijkstraDefaultOperationTraits
 		    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
 		    /// The cross reference type used by the heap.
 		    /// The cross reference type used by the heap.
 		    /// Usually it is \c Digraph::NodeMap<int>.
 		    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		    ///Instantiates a \ref 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 Digraph &g)
+		    {
 		      return new HeapCrossRef(g);
+		    }
 		    ///The heap type used by the Dijkstra algorithm.
 		    ///The heap type used by the Dijkstra algorithm.
 		    ///
 		    ///\sa BinHeap
 		    ///\sa Dijkstra
 		    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
 		                    std::less<Value> > Heap;
 		    ///Instantiates a \ref Heap.
 		    ///This function instantiates a \ref Heap.
 		    /// \param r is the HeapCrossRef which is used.
 		    static Heap *createHeap(HeapCrossRef& r)
+		    {
 		      return new Heap(r);
+		    }
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		#ifdef DOXYGEN
 		    static PredMap *createPredMap(const Digraph &g)
 		#else
 		    static PredMap *createPredMap(const Digraph &)
 		#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.
 		    ///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 \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef NullMap<typename Digraph::Node,Value> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		#ifdef DOXYGEN
 		    static DistMap *createDistMap(const Digraph &g)
 		#else
 		    static DistMap *createDistMap(const Digraph &)
 		#endif
+		    {
 		      return new DistMap();
+		    }
 		  };
 		  /// Default traits class used by \ref DijkstraWizard
 		  /// To make it easier to use Dijkstra algorithm
 		  /// we have created a wizard class.
 		  /// This \ref DijkstraWizard class needs default traits,
 		  /// as well as the \ref Dijkstra class.
 		  /// The \ref DijkstraWizardBase is a class to be the default traits of the
 		  /// \ref DijkstraWizard class.
 		  /// \todo More named parameters are required...
 		  template<class GR,class LM>
 		  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
+		  {
 		    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the length map
 		    void *_length;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the source node.
 		    Node _source;
 		  public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to default values (0, INVALID).
 		    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
 		                           _dist(0), _source(INVALID) {}
 		    /// Constructor.
 		    /// This constructor requires some parameters,
 		    /// listed in the parameters list.
 		    /// Others are initiated to 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param l The length map.
 		    /// \param s The source node.
 		    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
 		      _processed(0), _pred(0), _dist(0), _source(s) {}
 		  };
 		  /// Auxiliary class for the function type interface of Dijkstra algorithm.
 		  /// This auxiliary class is created to implement the function type
 		  /// interface of \ref Dijkstra algorithm. It uses the functions and features
 		  /// of the plain \ref Dijkstra, but it is much simpler to use it.
 		  /// It should only be used through the \ref dijkstra() function, which makes
 		  /// it easier to use the algorithm.
 		  ///
 		  /// Simplicity means that the way to change the types defined
 		  /// in the traits class is based on functions that returns the new class
 		  /// and not on templatable built-in classes.
 		  /// When using the plain \ref Dijkstra
 		  /// the new class with the modified type comes from
 		  /// the original class by using the ::
 		  /// operator. In the case of \ref DijkstraWizard only
 		  /// a function have to be called, and it will
 		  /// return the needed class.
 		  ///
 		  /// It does not have own \ref run() method. When its \ref run() method
 		  /// is called, it initiates a plain \ref Dijkstra object, and calls the
 		  /// \ref Dijkstra::run() method of it.
 		  template<class TR>
 		  class DijkstraWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    ///The type of the length of the arcs.
 		    typedef typename LengthMap::Value Value;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The heap type used by the dijkstra algorithm.
 		    typedef typename TR::Heap Heap;
 		  public:
 		    /// Constructor.
 		    DijkstraWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
 		      TR(g,l,s) {}
 		    ///Copy constructor
 		    DijkstraWizard(const TR &b) : TR(b) {}
 		    ~DijkstraWizard() {}
 		    ///Runs Dijkstra algorithm from a source node.
 		    ///Runs Dijkstra algorithm from a source node.
 		    ///The node can be given with the \ref source() function.
 		    void run()
+		    {
 		      if(Base::_source==INVALID) throw UninitializedParameter();
 		      Dijkstra<Digraph,LengthMap,TR>
 		        dij(*reinterpret_cast<const Digraph*>(Base::_g),
 		            *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if(Base::_processed)
 		        dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if(Base::_pred)
 		        dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if(Base::_dist)
 		        dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      dij.run(Base::_source);
+		    }
 		    ///Runs Dijkstra algorithm from the given node.
 		    ///Runs Dijkstra algorithm from the given node.
 		    ///\param s is the given source.
 		    void run(Node s)
+		    {
 		      Base::_source=s;
 		      run();
+		    }
 		    /// Sets the source node, from which the Dijkstra algorithm runs.
 		    /// Sets the source node, from which the Dijkstra algorithm runs.
 		    /// \param s is the source node.
 		    DijkstraWizard<TR> &source(Node s)
+		    {
 		      Base::_source=s;
 		      return *this;
+		    }
 		    template<class T>
 		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting \ref PredMap object.
 		    template<class T>
 		    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DijkstraWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    ///
 		    /// \ref named-templ-param "Named parameter"
 		    ///for setting \ref ProcessedMap object.
 		    template<class T>
 		    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DijkstraWizard<SetProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting \ref DistMap object.

lemon/error.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_ERROR_H
 		#define LEMON_ERROR_H
 		/// \ingroup exceptions
 		/// \file
 		/// \brief Basic exception classes and error handling.
 		#include <exception>
 		#include <string>
 		#include <sstream>
 		#include <iostream>
 		#include <cstdlib>
 		#include <memory>
 		namespace lemon {
 		  /// \addtogroup exceptions
 		  /// @{
 		  /// \brief Exception safe wrapper class.
 		  ///
 		  /// Exception safe wrapper class to implement the members of exceptions.
 		  template <typename _Type>
 		  class ExceptionMember {
 		  public:
 		    typedef _Type Type;
 		    ExceptionMember() throw() {
 		      try {
 		        ptr.reset(new Type());
 		      } catch (...) {}
+		    }
 		    ExceptionMember(const Type& type) throw() {
 		      try {
 		        ptr.reset(new Type());
 		        if (ptr.get() == 0) return;
 		        *ptr = type;
 		      } catch (...) {}
+		    }
 		    ExceptionMember(const ExceptionMember& copy) throw() {
 		      try {
 		        if (!copy.valid()) return;
 		        ptr.reset(new Type());
 		        if (ptr.get() == 0) return;
 		        *ptr = copy.get();
 		      } catch (...) {}
+		    }
 		    ExceptionMember& operator=(const ExceptionMember& copy) throw() {
 		      if (ptr.get() == 0) return;
 		      try {
 		        if (!copy.valid()) return;
 		        *ptr = copy.get();
 		      } catch (...) {}
+		    }
 		    void set(const Type& type) throw() {
 		      if (ptr.get() == 0) return;
 		      try {
 		        *ptr = type;
 		      } catch (...) {}
+		    }
 		    const Type& get() const {
 		      return *ptr;
+		    }
 		    bool valid() const throw() {
 		      return ptr.get() != 0;
+		    }
 		  private:
 		    std::auto_ptr<_Type> ptr;
 		  };
 		  /// Exception-safe convenient error message builder class.
 		  /// Helper class which provides a convenient ostream-like (operator <<
 		  /// based) interface to create a string message. Mostly useful in
 		  /// exception classes (therefore the name).
 		  class ErrorMessage {
 		  protected:
 		    ///\e
 		    ///\todo The good solution is boost::shared_ptr...
 		    ///
 		    mutable std::auto_ptr<std::ostringstream> buf;
 		    ///\e
 		    bool init() throw() {
 		      try {
 		        buf.reset(new std::ostringstream);
+		      }
 		      catch(...) {
 		        buf.reset();
+		      }
 		      return buf.get();
+		    }
 		  public:
 		    ///\e
 		    ErrorMessage() throw() { init(); }
 		    ErrorMessage(const ErrorMessage& em) throw() : buf(em.buf) { }
 		    ///\e
 		    ErrorMessage(const char *msg) throw() {
 		      init();
 		      *this << msg;
+		    }
 		    ///\e
 		    ErrorMessage(const std::string &msg) throw() {
 		      init();
 		      *this << msg;
+		    }
 		    ///\e
 		    template <typename T>
 		    ErrorMessage& operator<<(const T &t) throw() {
 		      if( ! buf.get() ) return *this;
 		      try {
 		        *buf << t;
+		      }
 		      catch(...) {
 		        buf.reset();
+		      }
 		      return *this;
+		    }
 		    ///\e
 		    const char* message() throw() {
 		      if( ! buf.get() ) return 0;
 		      const char* mes = 0;
 		      try {
 		        mes = buf->str().c_str();
+		      }
 		      catch(...) {}
 		      return mes;
+		    }
 		  };
 		  /// Generic exception class.
 		  /// Base class for exceptions used in LEMON.
 		  ///
 		  class Exception : public std::exception {
 		  public:
 		    ///\e
 		    Exception() {}
 		    ///\e
 		    virtual ~Exception() throw() {}
 		    ///\e
 		    virtual const char* what() const throw() {
 		      return "lemon::Exception";
+		    }
 		  };
 		  /// One of the two main subclasses of \ref Exception.
 		  /// Logic errors represent problems in the internal logic of a program;
 		  /// in theory, these are preventable, and even detectable before the
 		  /// program runs (e.g. violations of class invariants).
 		  ///
 		  /// A typical example for this is \ref UninitializedParameter.
 		  class LogicError : public Exception {
 		  public:
 		    virtual const char* what() const throw() {
 		      return "lemon::LogicError";
+		    }
 		  };
 		  /// \ref Exception for uninitialized parameters.
 		  /// This error represents problems in the initialization
 		  /// of the parameters of the algorithms.
 		  class UninitializedParameter : public LogicError {
 		  public:
 		    virtual const char* what() const throw() {
 		      return "lemon::UninitializedParameter";
+		    }
 		  };
 		  /// One of the two main subclasses of \ref Exception.
 		  /// Runtime errors represent problems outside the scope of a program;
 		  /// they cannot be easily predicted and can generally only be caught
 		  /// as the program executes.
 		  class RuntimeError : public Exception {
 		  public:
 		    virtual const char* what() const throw() {
 		      return "lemon::RuntimeError";
+		    }
 		  };
 		  ///\e
 		  class RangeError : public RuntimeError {
 		  public:
 		    virtual const char* what() const throw() {
 		      return "lemon::RangeError";
+		    }
 		  };
 		  ///\e
 		  class IoError : public RuntimeError {
 		  public:
 		    virtual const char* what() const throw() {
 		      return "lemon::IoError";
+		    }
 		  };
 		  ///\e
 		  class DataFormatError : public IoError {
 		  protected:
 		    ExceptionMember<std::string> _message;
 		    ExceptionMember<std::string> _file;
 		    int _line;
 		    mutable ExceptionMember<std::string> _message_holder;
 		  public:
 		    DataFormatError(const DataFormatError &dfe) :
 		      IoError(dfe), _message(dfe._message), _file(dfe._file),
 		      _line(dfe._line) {}
 		    ///\e
 		    explicit DataFormatError(const char *the_message)
 		      : _message(the_message), _line(0) {}
 		    ///\e
 		    DataFormatError(const std::string &file_name, int line_num,
 		                    const char *the_message)
 		      : _message(the_message), _line(line_num) { file(file_name); }
 		    ///\e
 		    void line(int ln) { _line = ln; }
 		    ///\e
 		    void message(const std::string& msg) { _message.set(msg); }
 		    ///\e
 		    void file(const std::string &fl) { _file.set(fl); }
 		    ///\e
 		    int line() const { return _line; }
 		    ///\e
 		    const char* message() const {
 		      if (_message.valid() && !_message.get().empty()) {
 		        return _message.get().c_str();
 		      } else {
 		        return 0;
+		      }
+		    }
 		    /// \brief Returns the filename.
 		    ///
 		    /// Returns \e null if the filename was not specified.
 		    const char* file() const {
 		      if (_file.valid() && !_file.get().empty()) {
 		        return _file.get().c_str();
 		      } else {
 		        return 0;
+		      }
+		    }
 		    ///\e
 		    virtual const char* what() const throw() {
 		      try {
 		        std::ostringstream ostr;
 		        ostr << "lemon:DataFormatError" << ": ";
 		        if (message()) ostr << message();
 		        if( file() || line() != 0 ) {
 		          ostr << " (";
 		          if( file() ) ostr << "in file '" << file() << "'";
 		          if( file() && line() != 0 ) ostr << " ";

lemon/graph_to_eps.h

Show inline comments

@@ -477,625 +477,620 @@
+		  }
 		  ///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 size scaling.
 		  ///Turns on/off the automatic node size scaling.
 		  ///
 		  ///\sa nodeScale()
 		  ///
 		  GraphToEps<T> &autoNodeScale(bool b=true) {
 		    _autoNodeScale=b;return *this;
+		  }
 		  ///Turns on/off the absolutematic node size scaling.
 		  ///Turns on/off the absolutematic node size scaling.
 		  ///
 		  ///\sa nodeScale()
 		  ///
 		  GraphToEps<T> &absoluteNodeSizes(bool b=true) {
 		    _absoluteNodeSizes=b;return *this;
+		  }
 		  ///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
 		  GraphToEps<T> &scale(double d) {_scale=d;return *this;}
 		  ///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
 		  GraphToEps<T> &border(double x, double y) {
 		    _xBorder=x;_yBorder=y;return *this;
+		  }
 		  ///Sets whether to draw arrows
 		  GraphToEps<T> &drawArrows(bool b=true) {_drawArrows=b;return *this;}
 		  ///Sets the length of the arrowheads
 		  GraphToEps<T> &arrowLength(double d=1.0) {_arrowLength*=d;return *this;}
 		  ///Sets the width of the arrowheads
 		  GraphToEps<T> &arrowWidth(double d=.3) {_arrowWidth*=d;return *this;}
 		  ///Scales the drawing to fit to A4 page
 		  GraphToEps<T> &scaleToA4() {_scaleToA4=true;return *this;}
 		  ///Enables parallel arcs
 		  GraphToEps<T> &enableParallel(bool b=true) {_enableParallel=b;return *this;}
 		  ///Sets the distance between parallel arcs
 		  GraphToEps<T> &parArcDist(double d) {_parArcDist*=d;return *this;}
 		  ///Hides the arcs
 		  GraphToEps<T> &hideArcs(bool b=true) {_showArcs=!b;return *this;}
 		  ///Hides the nodes
 		  GraphToEps<T> &hideNodes(bool b=true) {_showNodes=!b;return *this;}
 		  ///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 graph is undirected
 		  ///Sets whether the graph is undirected.
 		  ///
 		  ///This setting is the default for undirected graphs.
 		  ///
 		  ///\sa directed()
 		   GraphToEps<T> &undirected(bool b=true) {_undirected=b;return *this;}
 		  ///Sets whether the graph is directed
 		  ///Sets whether the graph is directed.
 		  ///Use it to show the edges as a pair of directed ones.
 		  ///
 		  ///This setting is the default for digraphs.
 		  ///
 		  ///\sa undirected()
 		  GraphToEps<T> &directed(bool b=true) {_undirected=!b;return *this;}
 		  ///Sets the title.
 		  ///Sets the title of the generated image,
 		  ///namely it inserts a <tt>%%Title:</tt> DSC field to the header of
 		  ///the EPS file.
 		  GraphToEps<T> &title(const std::string &t) {_title=t;return *this;}
 		  ///Sets the copyright statement.
 		  ///Sets the copyright statement of the generated image,
 		  ///namely it inserts a <tt>%%Copyright:</tt> DSC field to the header of
 		  ///the EPS file.
 		  GraphToEps<T> &copyright(const std::string &t) {_copyright=t;return *this;}
 		protected:
 		  bool isInsideNode(dim2::Point<double> p, double r,int t)
+		  {
 		    switch(t) {
 		    case CIRCLE:
 		    case MALE:
 		    case FEMALE:
 		      return p.normSquare()<=r*r;
 		    case SQUARE:
 		      return p.x<=r&&p.x>=-r&&p.y<=r&&p.y>=-r;
 		    case DIAMOND:
 		      return p.x+p.y<=r && p.x-p.y<=r && -p.x+p.y<=r && -p.x-p.y<=r;
+		    }
 		    return false;
+		  }
 		public:
 		  ~GraphToEps() { }
 		  ///Draws the graph.
 		  ///Like other functions using
 		  ///\ref named-templ-func-param "named template parameters",
 		  ///this function calls the algorithm itself, i.e. in this case
 		  ///it draws the graph.
 		  void run() {
 		    //\todo better 'epsilon' would be nice here.
 		    const double EPSILON=1e-9;
 		    if(dontPrint) return;
 		    _graph_to_eps_bits::_NegY<typename T::CoordsMapType>
 		      mycoords(_coords,_negY);
 		    os << "%!PS-Adobe-2.0 EPSF-2.0\n";
 		    if(_title.size()>0) os << "%%Title: " << _title << '\n';
 		     if(_copyright.size()>0) os << "%%Copyright: " << _copyright << '\n';
 		    os << "%%Creator: LEMON, graphToEps()\n";
+		    {
 		#ifndef WIN32
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      char cbuf[26];
 		      ctime_r(&tv.tv_sec,cbuf);
 		      os << "%%CreationDate: " << cbuf;
 		#else
 		      SYSTEMTIME time;
 		      char buf1[11], buf2[9], buf3[5];
 		      GetSystemTime(&time);
 		      if (GetDateFormat(LOCALE_USER_DEFAULT, 0, &time,
 		                        "ddd MMM dd", buf1, 11) &&
 		          GetTimeFormat(LOCALE_USER_DEFAULT, 0, &time,
 		                        "HH':'mm':'ss", buf2, 9) &&
 		          GetDateFormat(LOCALE_USER_DEFAULT, 0, &time,
 		                                "yyyy", buf3, 5)) {
 		        os << "%%CreationDate: " << buf1 << ' '
 		           << buf2 << ' ' << buf3 << std::endl;
+		      }
 		#endif
+		    }
 		    if (_autoArcWidthScale) {
 		      double max_w=0;
 		      for(ArcIt e(g);e!=INVALID;++e)
 		        max_w=std::max(double(_arcWidths[e]),max_w);
 		      //\todo better 'epsilon' would be nice here.
 		      if(max_w>EPSILON) {
 		        _arcWidthScale/=max_w;
+		      }
+		    }
 		    if (_autoNodeScale) {
 		      double max_s=0;
 		      for(NodeIt n(g);n!=INVALID;++n)
 		        max_s=std::max(double(_nodeSizes[n]),max_s);
 		      //\todo better 'epsilon' would be nice here.
 		      if(max_s>EPSILON) {
 		        _nodeScale/=max_s;
+		      }
+		    }
 		    double diag_len = 1;
 		    if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {
 		      dim2::Box<double> bb;
 		      for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);
 		      if (bb.empty()) {
 		        bb = dim2::Box<double>(dim2::Point<double>(0,0));
+		      }
 		      diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare());
 		      if(diag_len<EPSILON) diag_len = 1;
 		      if(!_absoluteNodeSizes) _nodeScale*=diag_len;
 		      if(!_absoluteArcWidths) _arcWidthScale*=diag_len;
+		    }
 		    dim2::Box<double> bb;
 		    for(NodeIt n(g);n!=INVALID;++n) {
 		      double ns=_nodeSizes[n]*_nodeScale;
 		      dim2::Point<double> p(ns,ns);
 		      switch(_nodeShapes[n]) {
 		      case CIRCLE:
 		      case SQUARE:
 		      case DIAMOND:
 		        bb.add(p+mycoords[n]);
 		        bb.add(-p+mycoords[n]);
 		        break;
 		      case MALE:
 		        bb.add(-p+mycoords[n]);
 		        bb.add(dim2::Point<double>(1.5*ns,1.5*std::sqrt(3.0)*ns)+mycoords[n]);
 		        break;
 		      case FEMALE:
 		        bb.add(p+mycoords[n]);
 		        bb.add(dim2::Point<double>(-ns,-3.01*ns)+mycoords[n]);
 		        break;
+		      }
+		    }
 		    if (bb.empty()) {
 		      bb = dim2::Box<double>(dim2::Point<double>(0,0));
+		    }
 		    if(_scaleToA4)
 		      os <<"%%BoundingBox: 0 0 596 842\n%%DocumentPaperSizes: a4\n";
 		    else {
 		      if(_preScale) {
 		        //Rescale so that BoundingBox won't be neither to big nor too small.
 		        while(bb.height()*_scale>1000||bb.width()*_scale>1000) _scale/=10;
 		        while(bb.height()*_scale<100||bb.width()*_scale<100) _scale*=10;
+		      }
 		      os << "%%BoundingBox: "
 		         << int(floor(bb.left()   * _scale - _xBorder)) << ' '
 		         << int(floor(bb.bottom() * _scale - _yBorder)) << ' '
 		         << int(ceil(bb.right()  * _scale + _xBorder)) << ' '
 		         << int(ceil(bb.top()    * _scale + _yBorder)) << '\n';
+		    }
 		    os << "%%EndComments\n";
 		    //x1 y1 x2 y2 x3 y3 cr cg cb w
 		    os << "/lb { setlinewidth setrgbcolor newpath moveto\n"
 		       << "      4 2 roll 1 index 1 index curveto stroke } bind def\n";
 		    os << "/l { setlinewidth setrgbcolor newpath moveto lineto stroke }"
 		       << " bind def\n";
 		    //x y r
 		    os << "/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath }"
 		       << " bind def\n";
 		    //x y r
 		    os << "/sq { newpath 2 index 1 index add 2 index 2 index add moveto\n"
 		       << "      2 index 1 index sub 2 index 2 index add lineto\n"
 		       << "      2 index 1 index sub 2 index 2 index sub lineto\n"
 		       << "      2 index 1 index add 2 index 2 index sub lineto\n"
 		       << "      closepath pop pop pop} bind def\n";
 		    //x y r
 		    os << "/di { newpath 2 index 1 index add 2 index moveto\n"
 		       << "      2 index             2 index 2 index add lineto\n"
 		       << "      2 index 1 index sub 2 index             lineto\n"
 		       << "      2 index             2 index 2 index sub lineto\n"
 		       << "      closepath pop pop pop} bind def\n";
 		    // x y r cr cg cb
 		    os << "/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill\n"
 		       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
 		       << "   } bind def\n";
 		    os << "/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill\n"
 		       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div sq fill\n"
 		       << "   } bind def\n";
 		    os << "/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill\n"
 		       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div di fill\n"
 		       << "   } bind def\n";
 		    os << "/nfemale { 0 0 0 setrgbcolor 3 index "
 		       << _nodeBorderQuotient/(1+_nodeBorderQuotient)
 		       << " 1.5 mul mul setlinewidth\n"
 		       << "  newpath 5 index 5 index moveto "
 		       << "5 index 5 index 5 index 3.01 mul sub\n"
 		       << "  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub"
 		       << " moveto\n"
 		       << "  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto "
 		       << "stroke\n"
 		       << "  5 index 5 index 5 index c fill\n"
 		       << "  setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
 		       << "  } bind def\n";
 		    os << "/nmale {\n"
 		       << "  0 0 0 setrgbcolor 3 index "
 		       << _nodeBorderQuotient/(1+_nodeBorderQuotient)
 		       <<" 1.5 mul mul setlinewidth\n"
 		       << "  newpath 5 index 5 index moveto\n"
 		       << "  5 index 4 index 1 mul 1.5 mul add\n"
 		       << "  5 index 5 index 3 sqrt 1.5 mul mul add\n"
 		       << "  1 index 1 index lineto\n"
 		       << "  1 index 1 index 7 index sub moveto\n"
 		       << "  1 index 1 index lineto\n"
 		       << "  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub"
 		       << " lineto\n"
 		       << "  stroke\n"
 		       << "  5 index 5 index 5 index c fill\n"
 		       << "  setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
 		       << "  } bind def\n";
 		    os << "/arrl " << _arrowLength << " def\n";
 		    os << "/arrw " << _arrowWidth << " def\n";
 		    // l dx_norm dy_norm
 		    os << "/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def\n";
 		    //len w dx_norm dy_norm x1 y1 cr cg cb
 		    os << "/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx "
 		       << "exch def\n"
 		       << "       /w exch def /len exch def\n"
 		      //<< "0.1 setlinewidth x1 y1 moveto dx len mul dy len mul rlineto stroke"
 		       << "       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto\n"
 		       << "       len w sub arrl sub dx dy lrl\n"
 		       << "       arrw dy dx neg lrl\n"
 		       << "       dx arrl w add mul dy w 2 div arrw add mul sub\n"
 		       << "       dy arrl w add mul dx w 2 div arrw add mul add rlineto\n"
 		       << "       dx arrl w add mul neg dy w 2 div arrw add mul sub\n"
 		       << "       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto\n"
 		       << "       arrw dy dx neg lrl\n"
 		       << "       len w sub arrl sub neg dx dy lrl\n"
 		       << "       closepath fill } bind def\n";
 		    os << "/cshow { 2 index 2 index moveto dup stringwidth pop\n"
 		       << "         neg 2 div fosi .35 mul neg rmoveto show pop pop} def\n";
 		    os << "\ngsave\n";
 		    if(_scaleToA4)
 		      if(bb.height()>bb.width()) {
 		        double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.height(),
 		                  (A4WIDTH-2*A4BORDER)/bb.width());
 		        os << ((A4WIDTH -2*A4BORDER)-sc*bb.width())/2 + A4BORDER << ' '
 		           << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER
 		           << " translate\n"
 		           << sc << " dup scale\n"
 		           << -bb.left() << ' ' << -bb.bottom() << " translate\n";
+		      }
 		      else {
 		        //\todo Verify centering
 		        double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(),
 		                  (A4WIDTH-2*A4BORDER)/bb.height());
 		        os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' '
 		           << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER
 		           << " translate\n"
 		           << sc << " dup scale\n90 rotate\n"
 		           << -bb.left() << ' ' << -bb.top() << " translate\n";
+		        }
 		    else if(_scale!=1.0) os << _scale << " dup scale\n";
 		    if(_showArcs) {
 		      os << "%Arcs:\ngsave\n";
 		      if(_enableParallel) {
 		        std::vector<Arc> el;
 		        for(ArcIt e(g);e!=INVALID;++e)
 		          if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0
 		             &&g.source(e)!=g.target(e))
 		            el.push_back(e);
 		        std::sort(el.begin(),el.end(),arcLess(g));
 		        typename std::vector<Arc>::iterator j;
 		        for(typename std::vector<Arc>::iterator i=el.begin();i!=el.end();i=j) {
 		          for(j=i+1;j!=el.end()&&isParallel(*i,*j);++j) ;
 		          double sw=0;
 		          for(typename std::vector<Arc>::iterator e=i;e!=j;++e)
 		            sw+=_arcWidths[*e]*_arcWidthScale+_parArcDist;
 		          sw-=_parArcDist;
 		          sw/=-2.0;
 		          dim2::Point<double>
 		            dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]);
 		          double l=std::sqrt(dvec.normSquare());
 		          //\todo better 'epsilon' would be nice here.
 		          dim2::Point<double> d(dvec/std::max(l,EPSILON));
 		          dim2::Point<double> m;
 		//           m=dim2::Point<double>(mycoords[g.target(*i)]+
 		//                                 mycoords[g.source(*i)])/2.0;
 		//            m=dim2::Point<double>(mycoords[g.source(*i)])+
 		//             dvec*(double(_nodeSizes[g.source(*i)])/
 		//                (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)]));
 		          m=dim2::Point<double>(mycoords[g.source(*i)])+
 		            d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0;
 		          for(typename std::vector<Arc>::iterator e=i;e!=j;++e) {
 		            sw+=_arcWidths[*e]*_arcWidthScale/2.0;
 		            dim2::Point<double> mm=m+rot90(d)*sw/.75;
 		            if(_drawArrows) {
 		              int node_shape;
 		              dim2::Point<double> s=mycoords[g.source(*e)];
 		              dim2::Point<double> t=mycoords[g.target(*e)];
 		              double rn=_nodeSizes[g.target(*e)]*_nodeScale;
 		              node_shape=_nodeShapes[g.target(*e)];
 		              dim2::Bezier3 bez(s,mm,mm,t);
 		              double t1=0,t2=1;
 		              for(int ii=0;ii<INTERPOL_PREC;++ii)
 		                if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2;
 		                else t1=(t1+t2)/2;
 		              dim2::Point<double> apoint=bez((t1+t2)/2);
 		              rn = _arrowLength+_arcWidths[*e]*_arcWidthScale;
 		              rn*=rn;
 		              t2=(t1+t2)/2;t1=0;
 		              for(int ii=0;ii<INTERPOL_PREC;++ii)
 		                if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2;
 		                else t2=(t1+t2)/2;
 		              dim2::Point<double> linend=bez((t1+t2)/2);
 		              bez=bez.before((t1+t2)/2);
 		//               rn=_nodeSizes[g.source(*e)]*_nodeScale;
 		//               node_shape=_nodeShapes[g.source(*e)];
 		//               t1=0;t2=1;
 		//               for(int i=0;i<INTERPOL_PREC;++i)
 		//                 if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape))
 		//                   t1=(t1+t2)/2;
 		//                 else t2=(t1+t2)/2;
 		//               bez=bez.after((t1+t2)/2);
 		              os << _arcWidths[*e]*_arcWidthScale << " setlinewidth "
 		                 << _arcColors[*e].red() << ' '
 		                 << _arcColors[*e].green() << ' '
 		                 << _arcColors[*e].blue() << " setrgbcolor newpath\n"
 		                 << bez.p1.x << ' ' <<  bez.p1.y << " moveto\n"
 		                 << bez.p2.x << ' ' << bez.p2.y << ' '
 		                 << bez.p3.x << ' ' << bez.p3.y << ' '
 		                 << bez.p4.x << ' ' << bez.p4.y << " curveto stroke\n";
 		              dim2::Point<double> dd(rot90(linend-apoint));
 		              dd*=(.5*_arcWidths[*e]*_arcWidthScale+_arrowWidth)/
 		                std::sqrt(dd.normSquare());
 		              os << "newpath " << psOut(apoint) << " moveto "
 		                 << psOut(linend+dd) << " lineto "
 		                 << psOut(linend-dd) << " lineto closepath fill\n";
+		            }
 		            else {
 		              os << mycoords[g.source(*e)].x << ' '
 		                 << mycoords[g.source(*e)].y << ' '
 		                 << mm.x << ' ' << mm.y << ' '
 		                 << mycoords[g.target(*e)].x << ' '
 		                 << mycoords[g.target(*e)].y << ' '
 		                 << _arcColors[*e].red() << ' '
 		                 << _arcColors[*e].green() << ' '
 		                 << _arcColors[*e].blue() << ' '
 		                 << _arcWidths[*e]*_arcWidthScale << " lb\n";
+		            }
 		            sw+=_arcWidths[*e]*_arcWidthScale/2.0+_parArcDist;
+		          }
+		        }
+		      }
 		      else for(ArcIt e(g);e!=INVALID;++e)
 		        if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0
 		           &&g.source(e)!=g.target(e)) {
 		          if(_drawArrows) {
 		            dim2::Point<double> d(mycoords[g.target(e)]-mycoords[g.source(e)]);
 		            double rn=_nodeSizes[g.target(e)]*_nodeScale;
 		            int node_shape=_nodeShapes[g.target(e)];
 		            double t1=0,t2=1;
 		            for(int i=0;i<INTERPOL_PREC;++i)
 		              if(isInsideNode((-(t1+t2)/2)*d,rn,node_shape)) t1=(t1+t2)/2;
 		              else t2=(t1+t2)/2;
 		            double l=std::sqrt(d.normSquare());
 		            d/=l;
 		            os << l*(1-(t1+t2)/2) << ' '
 		               << _arcWidths[e]*_arcWidthScale << ' '
 		               << d.x << ' ' << d.y << ' '
 		               << mycoords[g.source(e)].x << ' '
 		               << mycoords[g.source(e)].y << ' '
 		               << _arcColors[e].red() << ' '
 		               << _arcColors[e].green() << ' '
 		               << _arcColors[e].blue() << " arr\n";
+		          }
 		          else os << mycoords[g.source(e)].x << ' '
 		                  << mycoords[g.source(e)].y << ' '
 		                  << mycoords[g.target(e)].x << ' '
 		                  << mycoords[g.target(e)].y << ' '
 		                  << _arcColors[e].red() << ' '
 		                  << _arcColors[e].green() << ' '
 		                  << _arcColors[e].blue() << ' '
 		                  << _arcWidths[e]*_arcWidthScale << " l\n";
+		        }
 		      os << "grestore\n";
+		    }
 		    if(_showNodes) {
 		      os << "%Nodes:\ngsave\n";
 		      for(NodeIt n(g);n!=INVALID;++n) {
 		        os << mycoords[n].x << ' ' << mycoords[n].y << ' '
 		           << _nodeSizes[n]*_nodeScale << ' '
 		           << _nodeColors[n].red() << ' '
 		           << _nodeColors[n].green() << ' '
 		           << _nodeColors[n].blue() << ' ';
 		        switch(_nodeShapes[n]) {
 		        case CIRCLE:
 		          os<< "nc";break;
 		        case SQUARE:
 		          os<< "nsq";break;
 		        case DIAMOND:
 		          os<< "ndi";break;
 		        case MALE:
 		          os<< "nmale";break;
 		        case FEMALE:
 		          os<< "nfemale";break;
+		        }
 		        os<<'\n';
+		      }
 		      os << "grestore\n";
+		    }
 		    if(_showNodeText) {
 		      os << "%Node texts:\ngsave\n";
 		      os << "/fosi " << _nodeTextSize << " def\n";
 		      os << "(Helvetica) findfont fosi scalefont setfont\n";
 		      for(NodeIt n(g);n!=INVALID;++n) {
 		        switch(_nodeTextColorType) {
 		        case DIST_COL:
 		          os << psOut(distantColor(_nodeColors[n])) << " setrgbcolor\n";
 		          break;
 		        case DIST_BW:
 		          os << psOut(distantBW(_nodeColors[n])) << " setrgbcolor\n";
 		          break;
 		        case CUST_COL:
 		          os << psOut(distantColor(_nodeTextColors[n])) << " setrgbcolor\n";
 		          break;
 		        default:
 		          os << "0 0 0 setrgbcolor\n";
+		        }
 		        os << mycoords[n].x << ' ' << mycoords[n].y
 		           << " (" << _nodeTexts[n] << ") cshow\n";
+		      }
 		      os << "grestore\n";
+		    }
 		    if(_showNodePsText) {
 		      os << "%Node PS blocks:\ngsave\n";
 		      for(NodeIt n(g);n!=INVALID;++n)
 		        os << mycoords[n].x << ' ' << mycoords[n].y
 		           << " moveto\n" << _nodePsTexts[n] << "\n";
 		      os << "grestore\n";
+		    }
 		    os << "grestore\nshowpage\n";
 		    //CleanUp:
 		    if(_pleaseRemoveOsStream) {delete &os;}
+		  }
 		  ///\name Aliases
 		  ///These are just some aliases to other parameter setting functions.
 		  ///@{
 		  ///An alias for arcWidths()
 		  template<class X> GraphToEps<ArcWidthsTraits<X> > edgeWidths(const X &x)
+		  {
 		    return arcWidths(x);
+		  }
 		  ///An alias for arcColors()
 		  template<class X> GraphToEps<ArcColorsTraits<X> >
 		  edgeColors(const X &x)
+		  {
 		    return arcColors(x);
+		  }
 		  ///An alias for arcWidthScale()
 		  GraphToEps<T> &edgeWidthScale(double d) {return arcWidthScale(d);}
 		  ///An alias for autoArcWidthScale()
 		  GraphToEps<T> &autoEdgeWidthScale(bool b=true)
+		  {

lemon/list_graph.h

Show inline comments

@@ -312,388 +312,386 @@
 		  ///A general directed graph structure.
 		  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
 		  ///implementation based on static linked lists that are stored in
 		  ///\c std::vector structures.
 		  ///
 		  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
 		  ///also provides several useful additional functionalities.
 		  ///Most of the member functions and nested classes are documented
 		  ///only in the concept class.
 		  ///
 		  ///An important extra feature of this digraph implementation is that
 		  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
 		  ///
 		  ///\sa concepts::Digraph
 		  class ListDigraph : public ExtendedListDigraphBase {
 		  private:
 		    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 		    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 		    ///
 		    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
 		    ///\brief Assignment of ListDigraph to another one is \e not allowed.
 		    ///Use copyDigraph() instead.
 		    ///Assignment of ListDigraph to another one is \e not allowed.
 		    ///Use copyDigraph() instead.
 		    void operator=(const ListDigraph &) {}
 		  public:
 		    typedef ExtendedListDigraphBase Parent;
 		    /// Constructor
 		    /// Constructor.
 		    ///
 		    ListDigraph() {}
 		    ///Add a new node to the digraph.
 		    ///Add a new node to the digraph.
 		    ///\return the new node.
 		    Node addNode() { return Parent::addNode(); }
 		    ///Add a new arc to the digraph.
 		    ///Add a new arc to the digraph with source node \c s
 		    ///and target node \c t.
 		    ///\return the new arc.
 		    Arc addArc(const Node& s, const Node& t) {
 		      return Parent::addArc(s, t);
+		    }
 		    ///\brief Erase a node from the digraph.
 		    ///
 		    ///Erase a node from the digraph.
 		    ///
 		    void erase(const Node& n) { Parent::erase(n); }
 		    ///\brief Erase an arc from the digraph.
 		    ///
 		    ///Erase an arc from the digraph.
 		    ///
 		    void erase(const Arc& a) { Parent::erase(a); }
 		    /// Node validity check
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    ///
 		    /// \warning A Node pointing to a removed item
 		    /// could become valid again later if new nodes are
 		    /// added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// Arc validity check
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning An Arc pointing to a removed item
 		    /// could become valid again later if new nodes are
 		    /// added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    /// Change the target of \c a to \c n
 		    /// Change the target of \c a to \c n
 		    ///
 		    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
 		    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void changeTarget(Arc a, Node n) {
 		      Parent::changeTarget(a,n);
+		    }
 		    /// Change the source of \c a to \c n
 		    /// Change the source of \c a to \c n
 		    ///
 		    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
 		    ///valid. However the <tt>ArcIt<tt>s and <tt>OutArcIt</tt>s are
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void changeSource(Arc a, Node n) {
 		      Parent::changeSource(a,n);
+		    }
 		    /// Invert the direction of an arc.
 		    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
 		    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void reverseArc(Arc e) {
 		      Node t=target(e);
 		      changeTarget(e,source(e));
 		      changeSource(e,t);
+		    }
 		    /// Reserve memory for nodes.
 		    /// Using this function it is possible to avoid the superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be very large (e.g. it will contain millions of nodes and/or arcs)
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveArc
 		    void reserveNode(int n) { nodes.reserve(n); };
 		    /// Reserve memory for arcs.
 		    /// Using this function it is possible to avoid the superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be very large (e.g. it will contain millions of nodes and/or arcs)
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveNode
 		    void reserveArc(int m) { arcs.reserve(m); };
 		    ///Contract two nodes.
 		    ///This function contracts two nodes.
 		    ///Node \p b will be removed but instead of deleting
 		    ///incident arcs, they will be joined to \p a.
 		    ///The last parameter \p r controls whether to remove loops. \c true
 		    ///means that loops will be removed.
 		    ///
 		    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
 		    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
 		    ///may be invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void contract(Node a, Node b, bool r = true)
+		    {
 		      for(OutArcIt e(*this,b);e!=INVALID;) {
 		        OutArcIt f=e;
 		        ++f;
 		        if(r && target(e)==a) erase(e);
 		        else changeSource(e,a);
 		        e=f;
+		      }
 		      for(InArcIt e(*this,b);e!=INVALID;) {
 		        InArcIt f=e;
 		        ++f;
 		        if(r && source(e)==a) erase(e);
 		        else changeTarget(e,a);
 		        e=f;
+		      }
 		      erase(b);
+		    }
 		    ///Split a node.
 		    ///This function splits a node. First a new node is added to the digraph,
 		    ///then the source of each outgoing arc of \c n is moved to this new node.
 		    ///If \c connect is \c true (this is the default value), then a new arc
 		    ///from \c n to the newly created node is also added.
 		    ///\return The newly created node.
 		    ///
 		    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
 		    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
 		    ///be invalidated.
 		    ///
-		    ///\warning This functionality cannot be used together with the
+		    ///\warning This functionality cannot be used in conjunction with the
 		    ///Snapshot feature.
 		    ///
 		    ///\todo It could be implemented in a bit faster way.
 		    Node split(Node n, bool connect = true) {
 		      Node b = addNode();
 		      for(OutArcIt e(*this,n);e!=INVALID;) {
 		        OutArcIt f=e;
 		        ++f;
 		        changeSource(e,b);
 		        e=f;
+		      }
 		      if (connect) addArc(n,b);
 		      return b;
+		    }
 		    ///Split an arc.
 		    ///This function splits an arc. First a new node \c b is added to
 		    ///the digraph, then the original arc is re-targeted to \c
 		    ///b. Finally an arc from \c b to the original target is added.
 		    ///
 		    ///\return The newly created node.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    Node split(Arc e) {
 		      Node b = addNode();
 		      addArc(b,target(e));
 		      changeTarget(e,b);
 		      return b;
+		    }
 		    /// \brief Class to make a snapshot of the digraph and restore
 		    /// it later.
 		    ///
 		    /// Class to make a snapshot of the digraph and restore it later.
 		    ///
 		    /// The newly added nodes and arcs can be removed using the
 		    /// restore() function.
 		    ///
 		    /// \warning Arc and node deletions and other modifications (e.g.
 		    /// contracting, splitting, reversing arcs or nodes) cannot be
 		    /// restored. These events invalidate the snapshot.
 		    class Snapshot {
 		    protected:
 		      typedef Parent::NodeNotifier NodeNotifier;
 		      class NodeObserverProxy : public NodeNotifier::ObserverBase {
 		      public:
 		        NodeObserverProxy(Snapshot& _snapshot)
 		          : snapshot(_snapshot) {}
 		        using NodeNotifier::ObserverBase::attach;
 		        using NodeNotifier::ObserverBase::detach;
 		        using NodeNotifier::ObserverBase::attached;
 		      protected:
 		        virtual void add(const Node& node) {
 		          snapshot.addNode(node);
+		        }
 		        virtual void add(const std::vector<Node>& nodes) {
 		          for (int i = nodes.size() - 1; i >= 0; ++i) {
 		            snapshot.addNode(nodes[i]);
+		          }
+		        }
 		        virtual void erase(const Node& node) {
 		          snapshot.eraseNode(node);
+		        }
 		        virtual void erase(const std::vector<Node>& nodes) {
 		          for (int i = 0; i < int(nodes.size()); ++i) {
 		            snapshot.eraseNode(nodes[i]);
+		          }
+		        }
 		        virtual void build() {
 		          Node node;
 		          std::vector<Node> nodes;
 		          for (notifier()->first(node); node != INVALID;
 		               notifier()->next(node)) {
 		            nodes.push_back(node);
+		          }
 		          for (int i = nodes.size() - 1; i >= 0; --i) {
 		            snapshot.addNode(nodes[i]);
+		          }
+		        }
 		        virtual void clear() {
 		          Node node;
 		          for (notifier()->first(node); node != INVALID;
 		               notifier()->next(node)) {
 		            snapshot.eraseNode(node);
+		          }
+		        }
 		        Snapshot& snapshot;
 		      };
 		      class ArcObserverProxy : public ArcNotifier::ObserverBase {
 		      public:
 		        ArcObserverProxy(Snapshot& _snapshot)
 		          : snapshot(_snapshot) {}
 		        using ArcNotifier::ObserverBase::attach;
 		        using ArcNotifier::ObserverBase::detach;
 		        using ArcNotifier::ObserverBase::attached;
 		      protected:
 		        virtual void add(const Arc& arc) {
 		          snapshot.addArc(arc);
+		        }
 		        virtual void add(const std::vector<Arc>& arcs) {
 		          for (int i = arcs.size() - 1; i >= 0; ++i) {
 		            snapshot.addArc(arcs[i]);
+		          }
+		        }
 		        virtual void erase(const Arc& arc) {
 		          snapshot.eraseArc(arc);
+		        }
 		        virtual void erase(const std::vector<Arc>& arcs) {
 		          for (int i = 0; i < int(arcs.size()); ++i) {
 		            snapshot.eraseArc(arcs[i]);
+		          }
+		        }
 		        virtual void build() {
 		          Arc arc;
 		          std::vector<Arc> arcs;
 		          for (notifier()->first(arc); arc != INVALID;
 		               notifier()->next(arc)) {
 		            arcs.push_back(arc);
+		          }
 		          for (int i = arcs.size() - 1; i >= 0; --i) {
 		            snapshot.addArc(arcs[i]);
+		          }
+		        }
 		        virtual void clear() {
 		          Arc arc;
 		          for (notifier()->first(arc); arc != INVALID;
 		               notifier()->next(arc)) {
 		            snapshot.eraseArc(arc);
+		          }
+		        }
 		        Snapshot& snapshot;
 		      };
 		      ListDigraph *digraph;
 		      NodeObserverProxy node_observer_proxy;
 		      ArcObserverProxy arc_observer_proxy;
 		      std::list<Node> added_nodes;
 		      std::list<Arc> added_arcs;
 		      void addNode(const Node& node) {
 		        added_nodes.push_front(node);
+		      }
 		      void eraseNode(const Node& node) {
 		        std::list<Node>::iterator it =
 		          std::find(added_nodes.begin(), added_nodes.end(), node);
 		        if (it == added_nodes.end()) {
 		          clear();
 		          arc_observer_proxy.detach();
 		          throw NodeNotifier::ImmediateDetach();
 		        } else {
 		          added_nodes.erase(it);
+		        }
+		      }
 		      void addArc(const Arc& arc) {
 		        added_arcs.push_front(arc);
+		      }
 		      void eraseArc(const Arc& arc) {
 		        std::list<Arc>::iterator it =
 		          std::find(added_arcs.begin(), added_arcs.end(), arc);
 		        if (it == added_arcs.end()) {
 		          clear();
 		          node_observer_proxy.detach();
 		          throw ArcNotifier::ImmediateDetach();
 		        } else {
 		          added_arcs.erase(it);
+		        }
+		      }
 		      void attach(ListDigraph &_digraph) {
 		        digraph = &_digraph;
 		        node_observer_proxy.attach(digraph->notifier(Node()));
 		        arc_observer_proxy.attach(digraph->notifier(Arc()));
+		      }
 		      void detach() {
 		        node_observer_proxy.detach();

lemon/maps.h

Show inline comments

@@ -295,442 +295,438 @@
 		  public:
 		    ///\e
 		    Reference operator[](const Key &k) {
 		      return _vector[k];
+		    }
 		    ///\e
 		    ConstReference operator[](const Key &k) const {
 		      return _vector[k];
+		    }
 		    ///\e
 		    void set(const Key &k, const Value &v) {
 		      _vector[k] = v;
+		    }
 		  };
 		  /// Returns a \ref RangeMap class
 		  /// This function just returns a \ref RangeMap class.
 		  /// \relates RangeMap
 		  template<typename V>
 		  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
 		    return RangeMap<V>(size, value);
+		  }
 		  /// \brief Returns a \ref RangeMap class created from an appropriate
 		  /// \c std::vector
 		  /// This function just returns a \ref RangeMap class created from an
 		  /// appropriate \c std::vector.
 		  /// \relates RangeMap
 		  template<typename V>
 		  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
 		    return RangeMap<V>(vector);
+		  }
 		  /// Map type based on \c std::map
 		  /// This map is essentially a wrapper for \c std::map with addition
 		  /// that you can specify a default value for the keys that are not
 		  /// stored actually. This value can be different from the default
 		  /// contructed value (i.e. \c %Value()).
 		  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
 		  /// concept.
 		  ///
 		  /// This map is useful if a default value should be assigned to most of
 		  /// the keys and different values should be assigned only to a few
 		  /// keys (i.e. the map is "sparse").
 		  /// The name of this type also refers to this important usage.
 		  ///
 		  /// Apart form that this map can be used in many other cases since it
 		  /// is based on \c std::map, which is a general associative container.
 		  /// However keep in mind that it is usually not as efficient as other
 		  /// maps.
 		  ///
 		  /// The simplest way of using this map is through the sparseMap()
 		  /// function.
 		  template <typename K, typename V, typename Compare = std::less<K> >
 		  class SparseMap : public MapBase<K, V> {
 		    template <typename K1, typename V1, typename C1>
 		    friend class SparseMap;
 		  public:
 		    typedef MapBase<K, V> Parent;
 		    /// Key type
 		    typedef typename Parent::Key Key;
 		    /// Value type
 		    typedef typename Parent::Value Value;
 		    /// Reference type
 		    typedef Value& Reference;
 		    /// Const reference type
 		    typedef const Value& ConstReference;
 		    typedef True ReferenceMapTag;
 		  private:
 		    typedef std::map<K, V, Compare> Map;
 		    Map _map;
 		    Value _value;
 		  public:
 		    /// \brief Constructor with specified default value.
 		    SparseMap(const Value &value = Value()) : _value(value) {}
 		    /// \brief Constructs the map from an appropriate \c std::map, and
 		    /// explicitly specifies a default value.
 		    template <typename V1, typename Comp1>
 		    SparseMap(const std::map<Key, V1, Comp1> &map,
 		              const Value &value = Value())
 		      : _map(map.begin(), map.end()), _value(value) {}
 		    /// \brief Constructs the map from another \ref SparseMap.
 		    template<typename V1, typename Comp1>
 		    SparseMap(const SparseMap<Key, V1, Comp1> &c)
 		      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
 		  private:
 		    SparseMap& operator=(const SparseMap&);
 		  public:
 		    ///\e
 		    Reference operator[](const Key &k) {
 		      typename Map::iterator it = _map.lower_bound(k);
 		      if (it != _map.end() && !_map.key_comp()(k, it->first))
 		        return it->second;
 		      else
 		        return _map.insert(it, std::make_pair(k, _value))->second;
+		    }
 		    ///\e
 		    ConstReference operator[](const Key &k) const {
 		      typename Map::const_iterator it = _map.find(k);
 		      if (it != _map.end())
 		        return it->second;
 		      else
 		        return _value;
+		    }
 		    ///\e
 		    void set(const Key &k, const Value &v) {
 		      typename Map::iterator it = _map.lower_bound(k);
 		      if (it != _map.end() && !_map.key_comp()(k, it->first))
 		        it->second = v;
 		      else
 		        _map.insert(it, std::make_pair(k, v));
+		    }
 		    ///\e
 		    void setAll(const Value &v) {
 		      _value = v;
 		      _map.clear();
+		    }
 		  };
 		  /// Returns a \ref SparseMap class
 		  /// This function just returns a \ref SparseMap class with specified
 		  /// default value.
 		  /// \relates SparseMap
 		  template<typename K, typename V, typename Compare>
 		  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
 		    return SparseMap<K, V, Compare>(value);
+		  }
 		  template<typename K, typename V>
 		  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
 		    return SparseMap<K, V, std::less<K> >(value);
+		  }
 		  /// \brief Returns a \ref SparseMap class created from an appropriate
 		  /// \c std::map
 		  /// This function just returns a \ref SparseMap class created from an
 		  /// appropriate \c std::map.
 		  /// \relates SparseMap
 		  template<typename K, typename V, typename Compare>
 		  inline SparseMap<K, V, Compare>
 		    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
+		  {
 		    return SparseMap<K, V, Compare>(map, value);
+		  }
 		  /// @}
 		  /// \addtogroup map_adaptors
 		  /// @{
 		  /// Composition of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the
 		  /// composition of two given maps. That is to say, if \c m1 is of
 		  /// type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   ComposeMap<M1, M2> cm(m1,m2);
 		  /// \endcode
 		  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
 		  ///
 		  /// The \c Key type of the map is inherited from \c M2 and the
 		  /// \c Value type is from \c M1.
 		  /// \c M2::Value must be convertible to \c M1::Key.
 		  ///
 		  /// The simplest way of using this map is through the composeMap()
 		  /// function.
 		  ///
 		  /// \sa CombineMap
 		  ///
 		  /// \todo Check the requirements.
 		  template <typename M1, typename M2>
 		  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    typename MapTraits<M1>::ConstReturnValue
 		    operator[](const Key &k) const { return _m1[_m2[k]]; }
 		  };
 		  /// Returns a \ref ComposeMap class
 		  /// This function just returns a \ref ComposeMap class.
 		  ///
 		  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
 		  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
 		  /// will be equal to <tt>m1[m2[x]]</tt>.
 		  ///
 		  /// \relates ComposeMap
 		  template <typename M1, typename M2>
 		  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
 		    return ComposeMap<M1, M2>(m1, m2);
+		  }
 		  /// Combination of two maps using an STL (binary) functor.
 		  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
 		  /// binary functor and returns the combination of the two given maps
 		  /// using the functor.
 		  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
 		  /// and \c f is of \c F, then for
 		  /// \code
 		  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
 		  /// \endcode
 		  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
 		  ///
 		  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
 		  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
 		  /// \c M2::Value and \c M1::Value must be convertible to the
 		  /// corresponding input parameter of \c F and the return type of \c F
 		  /// must be convertible to \c V.
 		  ///
 		  /// The simplest way of using this map is through the combineMap()
 		  /// function.
 		  ///
 		  /// \sa ComposeMap
 		  ///
 		  /// \todo Check the requirements.
 		  template<typename M1, typename M2, typename F,
 		           typename V = typename F::result_type>
 		  class CombineMap : public MapBase<typename M1::Key, V> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		    F _f;
 		  public:
 		    typedef MapBase<typename M1::Key, V> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
 		      : _m1(m1), _m2(m2), _f(f) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
 		  };
 		  /// Returns a \ref CombineMap class
 		  /// This function just returns a \ref CombineMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then
 		  /// \code
 		  ///   combineMap(m1,m2,std::plus<double>())
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   addMap(m1,m2)
 		  /// \endcode
 		  ///
 		  /// This function is specialized for adaptable binary function
 		  /// classes and C++ functions.
 		  ///
 		  /// \relates CombineMap
 		  template<typename M1, typename M2, typename F, typename V>
 		  inline CombineMap<M1, M2, F, V>
 		  combineMap(const M1 &m1, const M2 &m2, const F &f) {
 		    return CombineMap<M1, M2, F, V>(m1,m2,f);
+		  }
 		  template<typename M1, typename M2, typename F>
 		  inline CombineMap<M1, M2, F, typename F::result_type>
 		  combineMap(const M1 &m1, const M2 &m2, const F &f) {
 		    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
+		  }
 		  template<typename M1, typename M2, typename K1, typename K2, typename V>
 		  inline CombineMap<M1, M2, V (*)(K1, K2), V>
 		  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
 		    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
+		  }
 		  /// Converts an STL style (unary) functor to a map
 		  /// This \ref concepts::ReadMap "read-only map" returns the value
 		  /// of a given functor. Actually, it just wraps the functor and
 		  /// provides the \c Key and \c Value typedefs.
 		  ///
 		  /// Template parameters \c K and \c V will become its \c Key and
 		  /// \c Value. In most cases they have to be given explicitly because
 		  /// a functor typically does not provide \c argument_type and
 		  /// \c result_type typedefs.
 		  /// Parameter \c F is the type of the used functor.
 		  ///
 		  /// The simplest way of using this map is through the functorToMap()
 		  /// function.
 		  ///
 		  /// \sa MapToFunctor
 		  template<typename F,
 		           typename K = typename F::argument_type,
 		           typename V = typename F::result_type>
 		  class FunctorToMap : public MapBase<K, V> {
 		    F _f;
 		  public:
 		    typedef MapBase<K, V> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    FunctorToMap(const F &f = F()) : _f(f) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _f(k); }
 		  };
 		  /// Returns a \ref FunctorToMap class
 		  /// This function just returns a \ref FunctorToMap class.
 		  ///
 		  /// This function is specialized for adaptable binary function
 		  /// classes and C++ functions.
 		  ///
 		  /// \relates FunctorToMap
 		  template<typename K, typename V, typename F>
 		  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
 		    return FunctorToMap<F, K, V>(f);
+		  }
 		  template <typename F>
 		  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
 		    functorToMap(const F &f)
+		  {
 		    return FunctorToMap<F, typename F::argument_type,
 		      typename F::result_type>(f);
+		  }
 		  template <typename K, typename V>
 		  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
 		    return FunctorToMap<V (*)(K), K, V>(f);
+		  }
 		  /// Converts a map to an STL style (unary) functor
 		  /// This class converts a map to an STL style (unary) functor.
 		  /// That is it provides an <tt>operator()</tt> to read its values.
 		  ///
 		  /// For the sake of convenience it also works as a usual
 		  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
 		  /// and the \c Key and \c Value typedefs also exist.
 		  ///
 		  /// The simplest way of using this map is through the mapToFunctor()
 		  /// function.
 		  ///
 		  ///\sa FunctorToMap
 		  template <typename M>
 		  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
 		    const M &_m;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    typedef typename Parent::Key argument_type;
 		    typedef typename Parent::Value result_type;
 		    /// Constructor
 		    MapToFunctor(const M &m) : _m(m) {}
 		    /// \e
 		    Value operator()(const Key &k) const { return _m[k]; }
 		    /// \e
 		    Value operator[](const Key &k) const { return _m[k]; }
 		  };
 		  /// Returns a \ref MapToFunctor class
 		  /// This function just returns a \ref MapToFunctor class.
 		  /// \relates MapToFunctor
 		  template<typename M>
 		  inline MapToFunctor<M> mapToFunctor(const M &m) {
 		    return MapToFunctor<M>(m);
+		  }
 		  /// \brief Map adaptor to convert the \c Value type of a map to
 		  /// another type using the default conversion.
 		  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
 		  /// "readable map" to another type using the default conversion.
 		  /// The \c Key type of it is inherited from \c M and the \c Value
 		  /// type is \c V.
 		  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
 		  ///
 		  /// The simplest way of using this map is through the convertMap()
 		  /// function.
 		  template <typename M, typename V>
 		  class ConvertMap : public MapBase<typename M::Key, V> {
 		    const M &_m;
 		  public:
 		    typedef MapBase<typename M::Key, V> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The underlying map.
 		    ConvertMap(const M &m) : _m(m) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m[k]; }
 		  };
 		  /// Returns a \ref ConvertMap class
 		  /// This function just returns a \ref ConvertMap class.
 		  /// \relates ConvertMap
 		  template<typename V, typename M>
 		  inline ConvertMap<M, V> convertMap(const M &map) {
 		    return ConvertMap<M, V>(map);

lemon/random.h

Show inline comments

@@ -632,379 +632,378 @@
 		    /// devices, <tt>/dev/random</tt> and <tt>/dev/urandom</tt> which
 		    /// could give good seed values for pseudo random generators (The
 		    /// difference between two devices is that the <tt>random</tt> may
 		    /// block the reading operation while the kernel can give good
 		    /// source of randomness, while the <tt>urandom</tt> does not
 		    /// block the input, but it could give back bytes with worse
 		    /// entropy).
 		    /// \param file The source file
 		    /// \param offset The offset, from the file read.
 		    /// \return True when the seeding successes.
 		#ifndef WIN32
 		    bool seedFromFile(const std::string& file = "/dev/urandom", int offset = 0)
 		#else
 		    bool seedFromFile(const std::string& file = "", int offset = 0)
 		#endif
+		    {
 		      std::ifstream rs(file.c_str());
 		      const int size = 4;
 		      Word buf[size];
 		      if (offset != 0 && !rs.seekg(offset)) return false;
 		      if (!rs.read(reinterpret_cast<char*>(buf), sizeof(buf))) return false;
 		      seed(buf, buf + size);
 		      return true;
+		    }
 		    /// \brief Seding from process id and time
 		    ///
 		    /// Seding from process id and time. This function uses the
 		    /// current process id and the current time for initialize the
 		    /// random sequence.
 		    /// \return Currently always true.
 		    bool seedFromTime() {
 		#ifndef WIN32
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      seed(getpid() + tv.tv_sec + tv.tv_usec);
 		#else
 		      FILETIME time;
 		      GetSystemTimeAsFileTime(&time);
 		      seed(GetCurrentProcessId() + time.dwHighDateTime + time.dwLowDateTime);
 		#endif
 		      return true;
+		    }
 		    /// @}
 		    ///\name Uniform distributions
 		    ///
 		    /// @{
 		    /// \brief Returns a random real number from the range [0, 1)
 		    ///
 		    /// It returns a random real number from the range [0, 1). The
 		    /// default Number type is \c double.
 		    template <typename Number>
 		    Number real() {
 		      return _random_bits::RealConversion<Number, Word>::convert(core);
+		    }
 		    double real() {
 		      return real<double>();
+		    }
 		    /// \brief Returns a random real number the range [0, b)
 		    ///
 		    /// It returns a random real number from the range [0, b).
 		    template <typename Number>
 		    Number real(Number b) {
 		      return real<Number>() * b;
+		    }
 		    /// \brief Returns a random real number from the range [a, b)
 		    ///
 		    /// It returns a random real number from the range [a, b).
 		    template <typename Number>
 		    Number real(Number a, Number b) {
 		      return real<Number>() * (b - a) + a;
+		    }
 		    /// @}
 		    ///\name Uniform distributions
 		    ///
 		    /// @{
 		    /// \brief Returns a random real number from the range [0, 1)
 		    ///
 		    /// It returns a random double from the range [0, 1).
 		    double operator()() {
 		      return real<double>();
+		    }
 		    /// \brief Returns a random real number from the range [0, b)
 		    ///
 		    /// It returns a random real number from the range [0, b).
 		    template <typename Number>
 		    Number operator()(Number b) {
 		      return real<Number>() * b;
+		    }
 		    /// \brief Returns a random real number from the range [a, b)
 		    ///
 		    /// It returns a random real number from the range [a, b).
 		    template <typename Number>
 		    Number operator()(Number a, Number b) {
 		      return real<Number>() * (b - a) + a;
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {0, 1, ..., b - 1}.
 		    template <typename Number>
 		    Number integer(Number b) {
 		      return _random_bits::Mapping<Number, Word>::map(core, b);
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {a, a + 1, ..., b - 1}.
 		    template <typename Number>
 		    Number integer(Number a, Number b) {
 		      return _random_bits::Mapping<Number, Word>::map(core, b - a) + a;
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {0, 1, ..., b - 1}.
 		    template <typename Number>
 		    Number operator[](Number b) {
 		      return _random_bits::Mapping<Number, Word>::map(core, b);
+		    }
 		    /// \brief Returns a random non-negative integer
 		    ///
 		    /// It returns a random non-negative integer uniformly from the
 		    /// whole range of the current \c Number type. The default result
 		    /// type of this function is <tt>unsigned int</tt>.
 		    template <typename Number>
 		    Number uinteger() {
 		      return _random_bits::IntConversion<Number, Word>::convert(core);
+		    }
 		    /// @}
 		    unsigned int uinteger() {
 		      return uinteger<unsigned int>();
+		    }
 		    /// \brief Returns a random integer
 		    ///
 		    /// It returns a random integer uniformly from the whole range of
 		    /// the current \c Number type. The default result type of this
 		    /// function is \c int.
 		    template <typename Number>
 		    Number integer() {
 		      static const int nb = std::numeric_limits<Number>::digits +
 		        (std::numeric_limits<Number>::is_signed ? 1 : 0);
 		      return _random_bits::IntConversion<Number, Word, nb>::convert(core);
+		    }
 		    int integer() {
 		      return integer<int>();
+		    }
 		    /// \brief Returns a random bool
 		    ///
 		    /// It returns a random bool. The generator holds a buffer for
 		    /// random bits. Every time when it become empty the generator makes
 		    /// a new random word and fill the buffer up.
 		    bool boolean() {
 		      return bool_producer.convert(core);
+		    }
 		    /// @}
 		    ///\name Non-uniform distributions
 		    ///
 		    ///@{
 		    /// \brief Returns a random bool
 		    ///
 		    /// It returns a random bool with given probability of true result.
 		    bool boolean(double p) {
 		      return operator()() < p;
+		    }
 		    /// Standard Gauss distribution
 		    /// Standard Gauss distribution.
 		    /// \note The Cartesian form of the Box-Muller
 		    /// transformation is used to generate a random normal distribution.
 		    /// \todo Consider using the "ziggurat" method instead.
 		    double gauss()
+		    {
 		      double V1,V2,S;
 		      do {
 		        V1=2*real<double>()-1;
 		        V2=2*real<double>()-1;
 		        S=V1*V1+V2*V2;
 		      } while(S>=1);
 		      return std::sqrt(-2*std::log(S)/S)*V1;
+		    }
 		    /// Gauss distribution with given mean and standard deviation
 		    /// Gauss distribution with given mean and standard deviation.
 		    /// \sa gauss()
 		    double gauss(double mean,double std_dev)
+		    {
 		      return gauss()*std_dev+mean;
+		    }
 		    /// Exponential distribution with given mean
 		    /// This function generates an exponential distribution random number
 		    /// with mean <tt>1/lambda</tt>.
 		    ///
 		    double exponential(double lambda=1.0)
+		    {
 		      return -std::log(1.0-real<double>())/lambda;
+		    }
 		    /// Gamma distribution with given integer shape
 		    /// This function generates a gamma distribution random number.
 		    ///
 		    ///\param k shape parameter (<tt>k>0</tt> integer)
 		    double gamma(int k)
+		    {
 		      double s = 0;
 		      for(int i=0;i<k;i++) s-=std::log(1.0-real<double>());
 		      return s;
+		    }
 		    /// Gamma distribution with given shape and scale parameter
 		    /// This function generates a gamma distribution random number.
 		    ///
 		    ///\param k shape parameter (<tt>k>0</tt>)
 		    ///\param theta scale parameter
 		    ///
 		    double gamma(double k,double theta=1.0)
+		    {
 		      double xi,nu;
 		      const double delta = k-std::floor(k);
 		      const double v0=E/(E-delta);
 		      do {
 		        double V0=1.0-real<double>();
 		        double V1=1.0-real<double>();
 		        double V2=1.0-real<double>();
 		        if(V2<=v0)
+		          {
 		            xi=std::pow(V1,1.0/delta);
 		            nu=V0*std::pow(xi,delta-1.0);
+		          }
 		        else
+		          {
 		            xi=1.0-std::log(V1);
 		            nu=V0*std::exp(-xi);
+		          }
 		      } while(nu>std::pow(xi,delta-1.0)*std::exp(-xi));
 		      return theta*(xi+gamma(int(std::floor(k))));
+		    }
 		    /// Weibull distribution
 		    /// This function generates a Weibull distribution random number.
 		    ///
 		    ///\param k shape parameter (<tt>k>0</tt>)
 		    ///\param lambda scale parameter (<tt>lambda>0</tt>)
 		    ///
 		    double weibull(double k,double lambda)
+		    {
 		      return lambda*pow(-std::log(1.0-real<double>()),1.0/k);
+		    }
 		    /// Pareto distribution
 		    /// This function generates a Pareto distribution random number.
 		    ///
 		    ///\param k shape parameter (<tt>k>0</tt>)
 		    ///\param x_min location parameter (<tt>x_min>0</tt>)
 		    ///
 		    double pareto(double k,double x_min)
+		    {
 		      return exponential(gamma(k,1.0/x_min))+x_min;
+		    }
 		    /// Poisson distribution
 		    /// This function generates a Poisson distribution random number with
 		    /// parameter \c lambda.
 		    ///
 		    /// The probability mass function of this distribusion is
 		    /// \f[ \frac{e^{-\lambda}\lambda^k}{k!} \f]
 		    /// \note The algorithm is taken from the book of Donald E. Knuth titled
 		    /// ''Seminumerical Algorithms'' (1969). Its running time is linear in the
 		    /// return value.
 		    int poisson(double lambda)
+		    {
 		      const double l = std::exp(-lambda);
 		      int k=0;
 		      double p = 1.0;
 		      do {
 		        k++;
 		        p*=real<double>();
 		      } while (p>=l);
 		      return k-1;
+		    }
 		    ///@}
 		    ///\name Two dimensional distributions
 		    ///
 		    ///@{
 		    /// Uniform distribution on the full unit circle
 		    /// Uniform distribution on the full unit circle.
 		    ///
 		    dim2::Point<double> disc()
+		    {
 		      double V1,V2;
 		      do {
 		        V1=2*real<double>()-1;
 		        V2=2*real<double>()-1;
 		      } while(V1*V1+V2*V2>=1);
 		      return dim2::Point<double>(V1,V2);
+		    }
 		    /// A kind of two dimensional Gauss distribution
 		    /// This function provides a turning symmetric two-dimensional distribution.
 		    /// Both coordinates are of standard normal distribution, but they are not
 		    /// independent.
 		    ///
 		    /// \note The coordinates are the two random variables provided by
 		    /// the Box-Muller method.
 		    dim2::Point<double> gauss2()
+		    {
 		      double V1,V2,S;
 		      do {
 		        V1=2*real<double>()-1;
 		        V2=2*real<double>()-1;
 		        S=V1*V1+V2*V2;
 		      } while(S>=1);
 		      double W=std::sqrt(-2*std::log(S)/S);
 		      return dim2::Point<double>(W*V1,W*V2);
+		    }
 		    /// A kind of two dimensional exponential distribution
 		    /// This function provides a turning symmetric two-dimensional distribution.
 		    /// The x-coordinate is of conditionally exponential distribution
 		    /// with the condition that x is positive and y=0. If x is negative and
 		    /// y=0 then, -x is of exponential distribution. The same is true for the
 		    /// y-coordinate.
 		    dim2::Point<double> exponential2()
+		    {
 		      double V1,V2,S;
 		      do {
 		        V1=2*real<double>()-1;
 		        V2=2*real<double>()-1;
 		        S=V1*V1+V2*V2;
 		      } while(S>=1);
 		      double W=-std::log(S)/S;
 		      return dim2::Point<double>(W*V1,W*V2);
+		    }
 		    ///@}
 		  };
 		  extern Random rnd;
+		}
 		#endif

lemon/smart_graph.h

Show inline comments

@@ -111,385 +111,384 @@
 		    bool valid(Node n) const {
 		      return n._id >= 0 && n._id < static_cast<int>(nodes.size());
+		    }
 		    bool valid(Arc a) const {
 		      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
+		    }
 		    class Node {
 		      friend class SmartDigraphBase;
 		      friend class SmartDigraph;
 		    protected:
 		      int _id;
 		      explicit Node(int id) : _id(id) {}
 		    public:
 		      Node() {}
 		      Node (Invalid) : _id(-1) {}
 		      bool operator==(const Node i) const {return _id == i._id;}
 		      bool operator!=(const Node i) const {return _id != i._id;}
 		      bool operator<(const Node i) const {return _id < i._id;}
 		    };
 		    class Arc {
 		      friend class SmartDigraphBase;
 		      friend class SmartDigraph;
 		    protected:
 		      int _id;
 		      explicit Arc(int id) : _id(id) {}
 		    public:
 		      Arc() { }
 		      Arc (Invalid) : _id(-1) {}
 		      bool operator==(const Arc i) const {return _id == i._id;}
 		      bool operator!=(const Arc i) const {return _id != i._id;}
 		      bool operator<(const Arc i) const {return _id < i._id;}
 		    };
 		    void first(Node& node) const {
 		      node._id = nodes.size() - 1;
+		    }
 		    static void next(Node& node) {
 		      --node._id;
+		    }
 		    void first(Arc& arc) const {
 		      arc._id = arcs.size() - 1;
+		    }
 		    static void next(Arc& arc) {
 		      --arc._id;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      arc._id = nodes[node._id].first_out;
+		    }
 		    void nextOut(Arc& arc) const {
 		      arc._id = arcs[arc._id].next_out;
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      arc._id = nodes[node._id].first_in;
+		    }
 		    void nextIn(Arc& arc) const {
 		      arc._id = arcs[arc._id].next_in;
+		    }
 		  };
 		  typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
 		  ///\ingroup graphs
 		  ///
 		  ///\brief A smart directed graph class.
 		  ///
 		  ///This is a simple and fast digraph implementation.
 		  ///It is also quite memory efficient, but at the price
 		  ///that <b> it does support only limited (only stack-like)
 		  ///node and arc deletions</b>.
 		  ///It conforms to the \ref concepts::Digraph "Digraph concept" with
 		  ///an important extra feature that its maps are real \ref
 		  ///concepts::ReferenceMap "reference map"s.
 		  ///
 		  ///\sa concepts::Digraph.
 		  class SmartDigraph : public ExtendedSmartDigraphBase {
 		  public:
 		    typedef ExtendedSmartDigraphBase Parent;
 		  private:
 		    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
 		    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
 		    ///
 		    SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
 		    ///\brief Assignment of SmartDigraph to another one is \e not allowed.
 		    ///Use DigraphCopy() instead.
 		    ///Assignment of SmartDigraph to another one is \e not allowed.
 		    ///Use DigraphCopy() instead.
 		    void operator=(const SmartDigraph &) {}
 		  public:
 		    /// Constructor
 		    /// Constructor.
 		    ///
 		    SmartDigraph() {};
 		    ///Add a new node to the digraph.
 		    /// \return the new node.
 		    ///
 		    Node addNode() { return Parent::addNode(); }
 		    ///Add a new arc to the digraph.
 		    ///Add a new arc to the digraph with source node \c s
 		    ///and target node \c t.
 		    ///\return the new arc.
 		    Arc addArc(const Node& s, const Node& t) {
 		      return Parent::addArc(s, t);
+		    }
 		    /// \brief Using this it is possible to avoid the superfluous memory
 		    /// allocation.
 		    /// Using this it is possible to avoid the superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be very large (e.g. it will contain millions of nodes and/or arcs)
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveArc
 		    void reserveNode(int n) { nodes.reserve(n); };
 		    /// \brief Using this it is possible to avoid the superfluous memory
 		    /// allocation.
 		    /// Using this it is possible to avoid the superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be very large (e.g. it will contain millions of nodes and/or arcs)
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveNode
 		    void reserveArc(int m) { arcs.reserve(m); };
 		    /// \brief Node validity check
 		    ///
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    ///
 		    /// \warning A removed node (using Snapshot) could become valid again
 		    /// when new nodes are added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// \brief Arc validity check
 		    ///
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning A removed arc (using Snapshot) could become valid again
 		    /// when new arcs are added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    ///Clear the digraph.
 		    ///Erase all the nodes and arcs from the digraph.
 		    ///
 		    void clear() {
 		      Parent::clear();
+		    }
 		    ///Split a node.
 		    ///This function splits a node. First a new node is added to the digraph,
 		    ///then the source of each outgoing arc of \c n is moved to this new node.
 		    ///If \c connect is \c true (this is the default value), then a new arc
 		    ///from \c n to the newly created node is also added.
 		    ///\return The newly created node.
 		    ///
 		    ///\note The <tt>Arc</tt>s
 		    ///referencing a moved arc remain
 		    ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
 		    ///may be invalidated.
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    ///\todo It could be implemented in a bit faster way.
 		    Node split(Node n, bool connect = true)
+		    {
 		      Node b = addNode();
 		      nodes[b._id].first_out=nodes[n._id].first_out;
 		      nodes[n._id].first_out=-1;
 		      for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
 		      if(connect) addArc(n,b);
 		      return b;
+		    }
 		  public:
 		    class Snapshot;
 		  protected:
 		    void restoreSnapshot(const Snapshot &s)
+		    {
 		      while(s.arc_num<arcs.size()) {
 		        Arc arc = arcFromId(arcs.size()-1);
 		        Parent::notifier(Arc()).erase(arc);
 		        nodes[arcs.back().source].first_out=arcs.back().next_out;
 		        nodes[arcs.back().target].first_in=arcs.back().next_in;
 		        arcs.pop_back();
+		      }
 		      while(s.node_num<nodes.size()) {
 		        Node node = nodeFromId(nodes.size()-1);
 		        Parent::notifier(Node()).erase(node);
 		        nodes.pop_back();
+		      }
+		    }
 		  public:
 		    ///Class to make a snapshot of the digraph and to restrore to it later.
 		    ///Class to make a snapshot of the digraph and to restrore to it later.
 		    ///
 		    ///The newly added nodes and arcs can be removed using the
 		    ///restore() function.
 		    ///\note After you restore a state, you cannot restore
 		    ///a later state, in other word you cannot add again the arcs deleted
 		    ///by restore() using another one Snapshot instance.
 		    ///
 		    ///\warning If you do not use correctly the snapshot that can cause
 		    ///either broken program, invalid state of the digraph, valid but
 		    ///not the restored digraph or no change. Because the runtime performance
 		    ///the validity of the snapshot is not stored.
 		    class Snapshot
+		    {
 		      SmartDigraph *_graph;
 		    protected:
 		      friend class SmartDigraph;
 		      unsigned int node_num;
 		      unsigned int arc_num;
 		    public:
 		      ///Default constructor.
 		      ///Default constructor.
 		      ///To actually make a snapshot you must call save().
 		      ///
 		      Snapshot() : _graph(0) {}
 		      ///Constructor that immediately makes a snapshot
 		      ///This constructor immediately makes a snapshot of the digraph.
 		      ///\param _g The digraph we make a snapshot of.
 		      Snapshot(SmartDigraph &graph) : _graph(&graph) {
 		        node_num=_graph->nodes.size();
 		        arc_num=_graph->arcs.size();
+		      }
 		      ///Make a snapshot.
 		      ///Make a snapshot of the digraph.
 		      ///
 		      ///This function can be called more than once. In case of a repeated
 		      ///call, the previous snapshot gets lost.
 		      ///\param _g The digraph we make the snapshot of.
 		      void save(SmartDigraph &graph)
+		      {
 		        _graph=&graph;
 		        node_num=_graph->nodes.size();
 		        arc_num=_graph->arcs.size();
+		      }
 		      ///Undo the changes until a snapshot.
 		      ///Undo the changes until a snapshot created by save().
 		      ///
 		      ///\note After you restored a state, you cannot restore
 		      ///a later state, in other word you cannot add again the arcs deleted
 		      ///by restore().
 		      void restore()
+		      {
 		        _graph->restoreSnapshot(*this);
+		      }
 		    };
 		  };
 		  class SmartGraphBase {
 		  protected:
 		    struct NodeT {
 		      int first_out;
 		    };
 		    struct ArcT {
 		      int target;
 		      int next_out;
 		    };
 		    std::vector<NodeT> nodes;
 		    std::vector<ArcT> arcs;
 		    int first_free_arc;
 		  public:
 		    typedef SmartGraphBase Digraph;
 		    class Node;
 		    class Arc;
 		    class Edge;
 		    class Node {
 		      friend class SmartGraphBase;
 		    protected:
 		      int _id;
 		      explicit Node(int id) { _id = id;}
 		    public:
 		      Node() {}
 		      Node (Invalid) { _id = -1; }
 		      bool operator==(const Node& node) const {return _id == node._id;}
 		      bool operator!=(const Node& node) const {return _id != node._id;}
 		      bool operator<(const Node& node) const {return _id < node._id;}
 		    };
 		    class Edge {
 		      friend class SmartGraphBase;
 		    protected:
 		      int _id;
 		      explicit Edge(int id) { _id = id;}
 		    public:
 		      Edge() {}
 		      Edge (Invalid) { _id = -1; }
 		      bool operator==(const Edge& arc) const {return _id == arc._id;}
 		      bool operator!=(const Edge& arc) const {return _id != arc._id;}
 		      bool operator<(const Edge& arc) const {return _id < arc._id;}
 		    };
 		    class Arc {
 		      friend class SmartGraphBase;
 		    protected:
 		      int _id;
 		      explicit Arc(int id) { _id = id;}
 		    public:
 		      operator Edge() const {
 		        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
+		      }
 		      Arc() {}
 		      Arc (Invalid) { _id = -1; }
 		      bool operator==(const Arc& arc) const {return _id == arc._id;}
 		      bool operator!=(const Arc& arc) const {return _id != arc._id;}
 		      bool operator<(const Arc& arc) const {return _id < arc._id;}
 		    };
 		    SmartGraphBase()
 		      : nodes(), arcs() {}
 		    int maxNodeId() const { return nodes.size()-1; }
 		    int maxEdgeId() const { return arcs.size() / 2 - 1; }
 		    int maxArcId() const { return arcs.size()-1; }
 		    Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
 		    Node target(Arc e) const { return Node(arcs[e._id].target); }
 		    Node u(Edge e) const { return Node(arcs[2 * e._id].target); }
 		    Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
 		    static bool direction(Arc e) {

lemon/time_measure.h

Show inline comments

@@ -103,474 +103,472 @@
 		      } else {
 		        rtime = 0;
 		        utime = 0;
 		        stime = 0;
 		        cutime = 0;
 		        cstime = 0;
+		      }
 		#endif
+		    }
 		    /// Constructor initializing with zero
 		    TimeStamp()
 		    { _reset(); }
 		    ///Constructor initializing with the current time values of the process
 		    TimeStamp(void *) { stamp();}
 		    ///Set every time value to zero
 		    TimeStamp &reset() {_reset();return *this;}
 		    ///\e
 		    TimeStamp &operator+=(const TimeStamp &b)
+		    {
 		      utime+=b.utime;
 		      stime+=b.stime;
 		      cutime+=b.cutime;
 		      cstime+=b.cstime;
 		      rtime+=b.rtime;
 		      return *this;
+		    }
 		    ///\e
 		    TimeStamp operator+(const TimeStamp &b) const
+		    {
 		      TimeStamp t(*this);
 		      return t+=b;
+		    }
 		    ///\e
 		    TimeStamp &operator-=(const TimeStamp &b)
+		    {
 		      utime-=b.utime;
 		      stime-=b.stime;
 		      cutime-=b.cutime;
 		      cstime-=b.cstime;
 		      rtime-=b.rtime;
 		      return *this;
+		    }
 		    ///\e
 		    TimeStamp operator-(const TimeStamp &b) const
+		    {
 		      TimeStamp t(*this);
 		      return t-=b;
+		    }
 		    ///\e
 		    TimeStamp &operator*=(double b)
+		    {
 		      utime*=b;
 		      stime*=b;
 		      cutime*=b;
 		      cstime*=b;
 		      rtime*=b;
 		      return *this;
+		    }
 		    ///\e
 		    TimeStamp operator*(double b) const
+		    {
 		      TimeStamp t(*this);
 		      return t*=b;
+		    }
 		    friend TimeStamp operator*(double b,const TimeStamp &t);
 		    ///\e
 		    TimeStamp &operator/=(double b)
+		    {
 		      utime/=b;
 		      stime/=b;
 		      cutime/=b;
 		      cstime/=b;
 		      rtime/=b;
 		      return *this;
+		    }
 		    ///\e
 		    TimeStamp operator/(double b) const
+		    {
 		      TimeStamp t(*this);
 		      return t/=b;
+		    }
 		    ///The time ellapsed since the last call of stamp()
 		    TimeStamp ellapsed() const
+		    {
 		      TimeStamp t(NULL);
 		      return t-*this;
+		    }
 		    friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
 		    ///Gives back the user time of the process
 		    double userTime() const
+		    {
 		      return utime;
+		    }
 		    ///Gives back the system time of the process
 		    double systemTime() const
+		    {
 		      return stime;
+		    }
 		    ///Gives back the user time of the process' children
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cUserTime() const
+		    {
 		      return cutime;
+		    }
 		    ///Gives back the user time of the process' children
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cSystemTime() const
+		    {
 		      return cstime;
+		    }
 		    ///Gives back the real time
 		    double realTime() const {return rtime;}
 		  };
 		  TimeStamp operator*(double b,const TimeStamp &t)
+		  {
 		    return t*b;
+		  }
 		  ///Prints the time counters
 		  ///Prints the time counters in the following form:
 		  ///
 		  /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
 		  ///
 		  /// where the values are the
 		  /// \li \c u: user cpu time,
 		  /// \li \c s: system cpu time,
 		  /// \li \c cu: user cpu time of children,
 		  /// \li \c cs: system cpu time of children,
 		  /// \li \c real: real time.
 		  /// \relates TimeStamp
 		  /// \note On <tt>WIN32</tt> platform the cummulative values are not
 		  /// calculated.
 		  inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
+		  {
 		    os << "u: " << t.userTime() <<
 		      "s, s: " << t.systemTime() <<
 		      "s, cu: " << t.cUserTime() <<
 		      "s, cs: " << t.cSystemTime() <<
 		      "s, real: " << t.realTime() << "s";
 		    return os;
+		  }
 		  ///Class for measuring the cpu time and real time usage of the process
 		  ///Class for measuring the cpu time and real time usage of the process.
 		  ///It is quite easy-to-use, here is a short example.
 		  ///\code
 		  /// #include<lemon/time_measure.h>
 		  /// #include<iostream>
 		  ///
 		  /// int main()
 		  /// {
 		  ///
 		  ///   ...
 		  ///
 		  ///   Timer t;
 		  ///   doSomething();
 		  ///   std::cout << t << '\n';
 		  ///   t.restart();
 		  ///   doSomethingElse();
 		  ///   std::cout << t << '\n';
 		  ///
 		  ///   ...
 		  ///
 		  /// }
 		  ///\endcode
 		  ///
 		  ///The \ref Timer can also be \ref stop() "stopped" and
 		  ///\ref start() "started" again, so it is possible to compute collected
 		  ///running times.
 		  ///
 		  ///\warning Depending on the operation system and its actual configuration
 		  ///the time counters have a certain (10ms on a typical Linux system)
 		  ///granularity.
 		  ///Therefore this tool is not appropriate to measure very short times.
 		  ///Also, if you start and stop the timer very frequently, it could lead to
 		  ///distorted results.
 		  ///
 		  ///\note If you want to measure the running time of the execution of a certain
 		  ///function, consider the usage of \ref TimeReport instead.
 		  ///
 		  ///\todo This shouldn't be Unix (Linux) specific.
 		  ///\sa TimeReport
 		  class Timer
+		  {
 		    int _running; //Timer is running iff _running>0; (_running>=0 always holds)
 		    TimeStamp start_time; //This is the relativ start-time if the timer
 		                          //is _running, the collected _running time otherwise.
 		    void _reset() {if(_running) start_time.stamp(); else start_time.reset();}
 		  public:
 		    ///Constructor.
 		    ///\param run indicates whether or not the timer starts immediately.
 		    ///
 		    Timer(bool run=true) :_running(run) {_reset();}
 		    ///\name Control the state of the timer
 		    ///Basically a Timer can be either running or stopped,
 		    ///but it provides a bit finer control on the execution.
 		    ///The \ref Timer also counts the number of \ref start()
 		    ///executions, and is stops only after the same amount (or more)
 		    ///\ref stop() "stop()"s. This can be useful e.g. to compute
 		    ///the running time
 		    ///of recursive functions.
 		    ///
 		    ///@{
 		    ///Reset and stop the time counters
 		    ///This function resets and stops the time counters
 		    ///\sa restart()
 		    void reset()
+		    {
 		      _running=0;
 		      _reset();
+		    }
 		    ///Start the time counters
 		    ///This function starts the time counters.
 		    ///
 		    ///If the timer is started more than ones, it will remain running
 		    ///until the same amount of \ref stop() is called.
 		    ///\sa stop()
 		    void start()
+		    {
 		      if(_running) _running++;
 		      else {
 		        _running=1;
 		        TimeStamp t;
 		        t.stamp();
 		        start_time=t-start_time;
+		      }
+		    }
 		    ///Stop the time counters
 		    ///This function stops the time counters. If start() was executed more than
 		    ///once, then the same number of stop() execution is necessary the really
 		    ///stop the timer.
 		    ///
 		    ///\sa halt()
 		    ///\sa start()
 		    ///\sa restart()
 		    ///\sa reset()
 		    void stop()
+		    {
 		      if(_running && !--_running) {
 		        TimeStamp t;
 		        t.stamp();
 		        start_time=t-start_time;
+		      }
+		    }
 		    ///Halt (i.e stop immediately) the time counters
 		    ///This function stops immediately the time counters, i.e. <tt>t.halt()</tt>
 		    ///is a faster
 		    ///equivalent of the following.
 		    ///\code
 		    ///  while(t.running()) t.stop()
 		    ///\endcode
 		    ///
 		    ///
 		    ///\sa stop()
 		    ///\sa restart()
 		    ///\sa reset()
 		    void halt()
+		    {
 		      if(_running) {
 		        _running=0;
 		        TimeStamp t;
 		        t.stamp();
 		        start_time=t-start_time;
+		      }
+		    }
 		    ///Returns the running state of the timer
 		    ///This function returns the number of stop() exections that is
 		    ///necessary to really stop the timer.
 		    ///For example the timer
 		    ///is running if and only if the return value is \c true
 		    ///(i.e. greater than
 		    ///zero).
 		    int running()  { return _running; }
 		    ///Restart the time counters
 		    ///This function is a shorthand for
 		    ///a reset() and a start() calls.
 		    ///
 		    void restart()
+		    {
 		      reset();
 		      start();
+		    }
 		    ///@}
 		    ///\name Query Functions for the ellapsed time
 		    ///@{
 		    ///Gives back the ellapsed user time of the process
 		    double userTime() const
+		    {
 		      return operator TimeStamp().userTime();
+		    }
 		    ///Gives back the ellapsed system time of the process
 		    double systemTime() const
+		    {
 		      return operator TimeStamp().systemTime();
+		    }
 		    ///Gives back the ellapsed user time of the process' children
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cUserTime() const
+		    {
 		      return operator TimeStamp().cUserTime();
+		    }
 		    ///Gives back the ellapsed user time of the process' children
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cSystemTime() const
+		    {
 		      return operator TimeStamp().cSystemTime();
+		    }
 		    ///Gives back the ellapsed real time
 		    double realTime() const
+		    {
 		      return operator TimeStamp().realTime();
+		    }
 		    ///Computes the ellapsed time
 		    ///This conversion computes the ellapsed time, therefore you can print
 		    ///the ellapsed time like this.
 		    ///\code
 		    ///  Timer t;
 		    ///  doSomething();
 		    ///  std::cout << t << '\n';
 		    ///\endcode
 		    operator TimeStamp () const
+		    {
 		      TimeStamp t;
 		      t.stamp();
 		      return _running?t-start_time:start_time;
+		    }
 		    ///@}
 		  };
 		  ///Same as \ref Timer but prints a report on destruction.
 		  ///Same as \ref Timer but prints a report on destruction.
 		  ///This example shows its usage.
 		  ///\code
 		  ///  void myAlg(ListGraph &g,int n)
 		  ///  {
 		  ///    TimeReport tr("Running time of myAlg: ");
 		  ///    ... //Here comes the algorithm
 		  ///  }
 		  ///\endcode
 		  ///
 		  ///\sa Timer
 		  ///\sa NoTimeReport
 		  ///\todo There is no test case for this
 		  class TimeReport : public Timer
+		  {
 		    std::string _title;
 		    std::ostream &_os;
 		  public:
 		    ///\e
 		    ///\param title This text will be printed before the ellapsed time.
 		    ///\param os The stream to print the report to.
 		    ///\param run Sets whether the timer should start immediately.
 		    TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true)
 		      : Timer(run), _title(title), _os(os){}
 		    ///\e Prints the ellapsed time on destruction.
 		    ~TimeReport()
+		    {
 		      _os << _title << *this << std::endl;
+		    }
 		  };
 		  ///'Do nothing' version of \ref TimeReport
 		  ///\sa TimeReport
 		  ///
 		  class NoTimeReport
+		  {
 		  public:
 		    ///\e
 		    NoTimeReport(std::string,std::ostream &,bool) {}
 		    ///\e
 		    NoTimeReport(std::string,std::ostream &) {}
 		    ///\e
 		    NoTimeReport(std::string) {}
 		    ///\e Do nothing.
 		    ~NoTimeReport() {}
 		    operator TimeStamp () const { return TimeStamp(); }
 		    void reset() {}
 		    void start() {}
 		    void stop() {}
 		    void halt() {}
 		    int running() { return 0; }
 		    void restart() {}
 		    double userTime() const { return 0; }
 		    double systemTime() const { return 0; }
 		    double cUserTime() const { return 0; }
 		    double cSystemTime() const { return 0; }
 		    double realTime() const { return 0; }
 		  };
 		  ///Tool to measure the running time more exactly.
 		  ///This function calls \c f several times and returns the average
 		  ///running time. The number of the executions will be choosen in such a way
 		  ///that the full real running time will be roughly between \c min_time
 		  ///and <tt>2*min_time</tt>.
 		  ///\param f the function object to be measured.
 		  ///\param min_time the minimum total running time.
 		  ///\retval num if it is not \c NULL, then the actual
 		  ///        number of execution of \c f will be written into <tt>*num</tt>.
 		  ///\retval full_time if it is not \c NULL, then the actual
 		  ///        total running time will be written into <tt>*full_time</tt>.
 		  ///\return The average running time of \c f.
 		  template<class F>
 		  TimeStamp runningTimeTest(F f,double min_time=10,unsigned int *num = NULL,
 		                            TimeStamp *full_time=NULL)
+		  {
 		    TimeStamp full;
 		    unsigned int total=0;
 		    Timer t;
 		    for(unsigned int tn=1;tn <= 1U<<31 && full.realTime()<=min_time; tn*=2) {
 		      for(;total<tn;total++) f();
 		      full=t;
+		    }
 		    if(num) *num=total;
 		    if(full_time) *full_time=full;
 		    return full/total;
+		  }
 		  /// @}
 		} //namespace lemon
 		#endif //LEMON_TIME_MEASURE_H

lemon/tolerance.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_TOLERANCE_H
 		#define LEMON_TOLERANCE_H
 		///\ingroup misc
 		///\file
 		///\brief A basic tool to handle the anomalies of calculation with
 		///floating point numbers.
 		///
 		///\todo It should be in a module like "Basic tools"
 		namespace lemon {
 		  /// \addtogroup misc
 		  /// @{
 		  ///\brief A class to provide a basic way to
 		  ///handle the comparison of numbers that are obtained
 		  ///as a result of a probably inexact computation.
 		  ///
 		  ///\ref Tolerance is a class to provide a basic way to
 		  ///handle the comparison of numbers that are obtained
 		  ///as a result of a probably inexact computation.
 		  ///
 		  ///This is an abstract class, it should be specialized for all
 		  ///numerical data types. These specialized classes like
 		  ///Tolerance<double> may offer additional tuning parameters.
 		  ///
 		  ///\sa Tolerance<float>
 		  ///\sa Tolerance<double>
 		  ///\sa Tolerance<long double>
 		  ///\sa Tolerance<int>
 		  ///\sa Tolerance<long long int>
 		  ///\sa Tolerance<unsigned int>
 		  ///\sa Tolerance<unsigned long long int>
 		  template<class T>
 		  class Tolerance
+		  {
 		  public:
 		    typedef T Value;
 		    ///\name Comparisons
 		    ///The concept is that these bool functions return \c true only if
 		    ///the related comparisons hold even if some numerical error appeared
 		    ///during the computations.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    static bool less(Value a,Value b) {return false;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    static bool different(Value a,Value b) {return false;}
 		    ///Returns \c true if \c a is \e surely positive
 		    static bool positive(Value a) {return false;}
 		    ///Returns \c true if \c a is \e surely negative
 		    static bool negative(Value a) {return false;}
 		    ///Returns \c true if \c a is \e surely non-zero
 		    static bool nonZero(Value a) {return false;}
 		    ///@}
 		    ///Returns the zero value.
 		    static Value zero() {return T();}
 		    //   static bool finite(Value a) {}
 		    //   static Value big() {}
 		    //   static Value negativeBig() {}
 		  };
 		  ///Float specialization of Tolerance.
 		  ///Float specialization of Tolerance.
 		  ///\sa Tolerance
 		  ///\relates Tolerance
 		  template<>
 		  class Tolerance<float>
+		  {
 		    static float def_epsilon;
 		    float _epsilon;
 		  public:
 		    ///\e
 		    typedef float Value;
 		    ///Constructor setting the epsilon tolerance to the default value.
 		    Tolerance() : _epsilon(def_epsilon) {}
 		    ///Constructor setting the epsilon tolerance to the given value.
 		    Tolerance(float e) : _epsilon(e) {}
 		    ///Returns the epsilon value.
 		    Value epsilon() const {return _epsilon;}
 		    ///Sets the epsilon value.
 		    void epsilon(Value e) {_epsilon=e;}
 		    ///Returns the default epsilon value.
 		    static Value defaultEpsilon() {return def_epsilon;}
 		    ///Sets the default epsilon value.
 		    static void defaultEpsilon(Value e) {def_epsilon=e;}
 		    ///\name Comparisons
 		    ///See \ref lemon::Tolerance "Tolerance" for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    bool less(Value a,Value b) const {return a+_epsilon<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
 		    ///Returns \c true if \c a is \e surely positive
 		    bool positive(Value a) const { return _epsilon<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    bool negative(Value a) const { return -_epsilon>a; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    bool nonZero(Value a) const { return positive(a)||negative(a); }
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		  ///Double specialization of Tolerance.
 		  ///Double specialization of Tolerance.
 		  ///\sa Tolerance
 		  ///\relates Tolerance
 		  template<>
 		  class Tolerance<double>
+		  {
 		    static double def_epsilon;
 		    double _epsilon;
 		  public:
 		    ///\e
 		    typedef double Value;
 		    ///Constructor setting the epsilon tolerance to the default value.
 		    Tolerance() : _epsilon(def_epsilon) {}
 		    ///Constructor setting the epsilon tolerance to the given value.
 		    Tolerance(double e) : _epsilon(e) {}
 		    ///Returns the epsilon value.
 		    Value epsilon() const {return _epsilon;}
 		    ///Sets the epsilon value.
 		    void epsilon(Value e) {_epsilon=e;}
 		    ///Returns the default epsilon value.
 		    static Value defaultEpsilon() {return def_epsilon;}
 		    ///Sets the default epsilon value.
 		    static void defaultEpsilon(Value e) {def_epsilon=e;}
 		    ///\name Comparisons
 		    ///See \ref lemon::Tolerance "Tolerance" for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    bool less(Value a,Value b) const {return a+_epsilon<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
 		    ///Returns \c true if \c a is \e surely positive
 		    bool positive(Value a) const { return _epsilon<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    bool negative(Value a) const { return -_epsilon>a; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    bool nonZero(Value a) const { return positive(a)||negative(a); }
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		  ///Long double specialization of Tolerance.
 		  ///Long double specialization of Tolerance.
 		  ///\sa Tolerance
 		  ///\relates Tolerance
 		  template<>
 		  class Tolerance<long double>
+		  {
 		    static long double def_epsilon;
 		    long double _epsilon;
 		  public:
 		    ///\e
 		    typedef long double Value;
 		    ///Constructor setting the epsilon tolerance to the default value.
 		    Tolerance() : _epsilon(def_epsilon) {}
 		    ///Constructor setting the epsilon tolerance to the given value.
 		    Tolerance(long double e) : _epsilon(e) {}
 		    ///Returns the epsilon value.
 		    Value epsilon() const {return _epsilon;}
 		    ///Sets the epsilon value.
 		    void epsilon(Value e) {_epsilon=e;}
 		    ///Returns the default epsilon value.
 		    static Value defaultEpsilon() {return def_epsilon;}
 		    ///Sets the default epsilon value.
 		    static void defaultEpsilon(Value e) {def_epsilon=e;}

0 comments (0 inline)

RhodeCode

Login to your account