LEMON/LEMON-official Changeset - r283:66bb22401834

Repositories » LEMON » LEMON-official

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

Changeset - r283:66bb22401834

« 281:e9b4fb
« 282:dc9e8d

284:a16cc7 »

r283:66bb22401834

Sat, 27 Sep 2008 13:45:50

[Not Reviewed]

0 comments (0 inline)

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

Merge

0 15 0

merge default

0 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>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///Default traits class of Bfs class.
 		  ///Default traits class of Bfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref DistMap.
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%BFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %BFS algorithm.
 		  ///
 		  ///There is also a \ref bfs() "function-type interface" for the BFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default value is \ref ListDigraph. The value of GR is not used
 		  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
 		  ///\tparam TR Traits class to set various data types used by the algorithm.
 		  ///The default traits class is
 		  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
 		  ///See \ref BfsDefaultTraits for the documentation of
 		  ///a Bfs traits class.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=BfsDefaultTraits<GR> >
 		#endif
 		  class Bfs {
 		  public:
 		    ///\ref Exception for uninitialized parameters.
 		    ///This error represents problems in the initialization of the
 		    ///parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 		        return "lemon::Bfs::UninitializedParameter";
+		      }
 		    };
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The traits class.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::Node> _queue;
 		    int _queue_head,_queue_tail,_queue_next_dist;
 		    int _curr_dist;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Bfs() {}
 		  public:
 		    typedef Bfs Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    template <class T>
 		    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 		      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    template <class T>
 		    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    template <class T>
 		    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap :
 		      public Bfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
@@ -723,257 +720,256 @@
 		    ///    if (!b.reached(n)) {
 		    ///      b.addSource(n);
 		    ///      b.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt n(*G); n != INVALID; ++n) {
 		        if (!reached(n)) {
 		          addSource(n);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The result of the %BFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
 		    ///"start()" must be called before using them.
 		    ///@{
 		    ///The shortest path to a node.
 		    ///Returns the shortest path to a node.
 		    ///
 		    ///\warning \c t should be reachable from the root(s).
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///The distance of a node from the root(s).
 		    ///Returns the distance of a node from the root(s).
 		    ///
 		    ///\warning If node \c v is not reachable from the root(s), then
 		    ///the return value of this function is undefined.
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the shortest path tree for a node.
 		    ///This function returns the 'previous arc' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last arc of a
 		    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
 		    ///is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predNode().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///Returns the 'previous node' of the shortest path tree for a node.
 		    ///This function returns the 'previous node' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last but one node
 		    ///from a shortest path from the root(s) to \c v. It is \c INVALID
 		    ///if \c v is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predArc().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->source((*_pred)[v]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    /// distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the distances
 		    ///of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the shortest path tree.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if a node is reachable from the root(s).
 		    ///Returns \c true if \c v is reachable from the root(s).
 		    ///\pre Either \ref run() or \ref start()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of bfs() function.
 		  ///Default traits class of bfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsWizardDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
 		    ///It must meet the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by \ref BfsWizard
 		  /// To make it easier to use Bfs algorithm
 		  /// we have created a wizard class.
 		  /// This \ref BfsWizard class needs default traits,
 		  /// as well as the \ref Bfs class.
 		  /// The \ref BfsWizardBase is a class to be the default traits of the
 		  /// \ref BfsWizard class.
 		  template<class GR>
 		  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
+		  {
 		    typedef BfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the shortest path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    int *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to \c 0.
 		    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires one parameter,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    BfsWizardBase(const GR &g) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of BFS algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
 		  /// It does not have own \ref run() method, it uses the functions
 		  /// and features of the plain \ref Bfs.
 		  ///
 		  /// This class should only be used through the \ref bfs() function,
 		  /// which makes it easier to use the algorithm.
 		  template<class TR>
 		  class BfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
@@ -1245,258 +1241,257 @@
 		    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);

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


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

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) {
 		        ignore_unused_variable_warning(cpath);
 		        return *this;
+		      }
 		      /// Length of the path ie. the number of arcs in the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// Resets the path to an empty path.
 		      void clear() {}
 		      /// \brief LEMON style iterator for path arcs
 		      ///
 		      /// This class is used to iterate on the arcs of the paths.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
 		        /// Constructor for first arc
 		        ArcIt(const Path &) {}
 		        /// Conversion to Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          Path<Digraph> pc;
 		          _Path p, pp(pc);
 		          int l = p.length();
 		          int e = p.empty();
 		          p.clear();
 		          p = pc;
 		          typename _Path::ArcIt id, ii(INVALID), i(p);
 		          ++i;
 		          typename Digraph::Arc ed = i;
 		          e = (i == ii);
 		          e = (i != ii);
 		          e = (i < ii);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(pp);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ii);
 		          ignore_unused_variable_warning(ed);
+		        }
 		      };
 		    };
 		    namespace _path_bits {
 		      template <typename _Digraph, typename _Path, typename RevPathTag = void>
 		      struct PathDumperConstraints {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::ArcIt id, i(p);
 		          ++i;

lemon/dfs.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_DFS_H
 		#define LEMON_DFS_H
 		///\ingroup search
 		///\file
 		///\brief DFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/assert.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///Default traits class of Dfs class.
 		  ///Default traits class of Dfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref DistMap.
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%DFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %DFS algorithm.
 		  ///
 		  ///There is also a \ref dfs() "function-type interface" for the DFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default value is \ref ListDigraph. The value of GR is not used
 		  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
 		  ///\tparam TR Traits class to set various data types used by the algorithm.
 		  ///The default traits class is
 		  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
 		  ///See \ref DfsDefaultTraits for the documentation of
 		  ///a Dfs traits class.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=DfsDefaultTraits<GR> >
 		#endif
 		  class Dfs {
 		  public:
 		    ///\ref Exception for uninitialized parameters.
 		    ///This error represents problems in the initialization of the
 		    ///parameters of the algorithm.
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 		        return "lemon::Dfs::UninitializedParameter";
+		      }
 		    };
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The traits class.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::OutArcIt> _stack;
 		    int _stack_head;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Dfs() {}
 		  public:
 		    typedef Dfs Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref PredMap type.
 		    template <class T>
 		    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 		      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref DistMap type.
 		    template <class T>
 		    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type.
 		    template <class T>
 		    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap :
 		      public Dfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
@@ -657,257 +654,256 @@
 		    ///    if (!d.reached(n)) {
 		    ///      d.addSource(n);
 		    ///      d.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt it(*G); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The result of the %DFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
 		    ///"start()" must be called before using them.
 		    ///@{
 		    ///The DFS path to a node.
 		    ///Returns the DFS path to a node.
 		    ///
 		    ///\warning \c t should be reachable from the root.
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///The distance of a node from the root.
 		    ///Returns the distance of a node from the root.
 		    ///
 		    ///\warning If node \c v is not reachable from the root, then
 		    ///the return value of this function is undefined.
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the %DFS tree for a node.
 		    ///This function returns the 'previous arc' of the %DFS tree for the
 		    ///node \c v, i.e. it returns the last arc of a %DFS path from the
 		    ///root to \c v. It is \c INVALID
 		    ///if \c v is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predNode().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before using
 		    ///this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///Returns the 'previous node' of the %DFS tree.
 		    ///This function returns the 'previous node' of the %DFS
 		    ///tree for the node \c v, i.e. it returns the last but one node
 		    ///from a %DFS path from the root to \c v. It is \c INVALID
 		    ///if \c v is not reachable from the root(s) or if \c v is a root.
 		    ///
 		    ///The %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predArc().
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->source((*_pred)[v]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the
 		    ///distances of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the DFS tree.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if a node is reachable from the root(s).
 		    ///Returns \c true if \c v is reachable from the root(s).
 		    ///\pre Either \ref run() or \ref start()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of dfs() function.
 		  ///Default traits class of dfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsWizardDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \ref PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    ///\todo The digraph alone may be insufficient to initialize
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \ref ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \ref ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \ref DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		    ///The type of the DFS paths.
 		    ///The type of the DFS paths.
 		    ///It must meet the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by \ref DfsWizard
 		  /// To make it easier to use Dfs algorithm
 		  /// we have created a wizard class.
 		  /// This \ref DfsWizard class needs default traits,
 		  /// as well as the \ref Dfs class.
 		  /// The \ref DfsWizardBase is a class to be the default traits of the
 		  /// \ref DfsWizard class.
 		  template<class GR>
 		  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
+		  {
 		    typedef DfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the DFS path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    int *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to \c 0.
 		    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires one parameter,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    DfsWizardBase(const GR &g) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of DFS algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
 		  /// It does not have own \ref run() method, it uses the functions
 		  /// and features of the plain \ref Dfs.
 		  ///
 		  /// This class should only be used through the \ref dfs() function,
 		  /// which makes it easier to use the algorithm.
 		  template<class TR>
 		  class DfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
@@ -1192,258 +1188,257 @@
 		    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.
 		    ///

lemon/dijkstra.h

Show inline comments

@@ -19,411 +19,407 @@
 		#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>
 		#include <lemon/path.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> > {
@@ -833,352 +829,346 @@
 		    ///\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 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.
 		    ///\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 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);
+		    }
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
 		    ///It must meet the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by \ref 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 shortest path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    void *_di;
 		  public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to \c 0.
 		    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
 		                           _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires two parameters,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param l The length map.
 		    DijkstraWizardBase(const GR &g,const LM &l) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
 		      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
 		  /// It does not have own \ref run() method, it uses the functions
 		  /// and features of the plain \ref Dijkstra.
 		  ///
 		  /// This class should only be used through the \ref dijkstra() function,
 		  /// which makes it easier to use the algorithm.
 		  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 type of the shortest paths
 		    typedef typename TR::Path Path;
 		    ///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.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param l The length map.
 		    DijkstraWizard(const Digraph &g, const LengthMap &l) :
 		      TR(g,l) {}
 		    ///Copy constructor
 		    DijkstraWizard(const TR &b) : TR(b) {}
 		    ~DijkstraWizard() {}
 		    ///Runs Dijkstra algorithm from the given source node.
 		    ///This method runs %Dijkstra algorithm from the given source node
 		    ///in order to compute the shortest path to each node.
 		    void run(Node s)
+		    {
 		      if (s==INVALID) throw UninitializedParameter();
 		      Dijkstra<Digraph,LengthMap,TR>
 		        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
 		             *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if (Base::_pred)
 		        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_processed)
 		        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      dijk.run(s);
+		    }
 		    ///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 node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)

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";
+		    }

lemon/graph_to_eps.h

Show inline comments

@@ -541,497 +541,492 @@
 		  ///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';

lemon/list_graph.h

Show inline comments

@@ -376,260 +376,258 @@
 		    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)) {

lemon/maps.h

Show inline comments

@@ -359,314 +359,310 @@
 		    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>

lemon/random.h

Show inline comments

@@ -696,257 +696,256 @@
 		    ///
 		    /// 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.

lemon/smart_graph.h

Show inline comments

@@ -175,257 +175,256 @@
 		      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;

lemon/time_measure.h

Show inline comments

@@ -167,410 +167,408 @@
 		      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) {}

0 comments (0 inline)

RhodeCode

Login to your account

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#ifndef LEMON_BITS_BASE_EXTENDER_H
20	20	#define LEMON_BITS_BASE_EXTENDER_H
21	21
22	22	#include <lemon/core.h>
23	23	#include <lemon/error.h>
24	24
25	25	#include <lemon/bits/map_extender.h>
26	26	#include <lemon/bits/default_map.h>
27	27
28	28	#include <lemon/concept_check.h>
29	29	#include <lemon/concepts/maps.h>
30	30
31	31	///\ingroup digraphbits
32	32	///\file
33	33	///\brief Extenders for the digraph types
34	34	namespace lemon {
35	35
36	36	/// \ingroup digraphbits
37	37	///
38	38	/// \brief BaseDigraph to BaseGraph extender
39	39	template <typename Base>
40	40	class UndirDigraphExtender : public Base {
41	41
42	42	public:
43	43
44	44	typedef Base Parent;
45	45	typedef typename Parent::Arc Edge;
46	46	typedef typename Parent::Node Node;
47	47
48	48	typedef True UndirectedTag;
49	49
50	50	class Arc : public Edge {
51	51	friend class UndirDigraphExtender;
52	52
53	53	protected:
54	54	bool forward;
55	55
56	56	Arc(const Edge &ue, bool _forward) :
57	57	Edge(ue), forward(_forward) {}
58	58
59	59	public:
60	60	Arc() {}
61	61
62	62	// Invalid arc constructor
63	63	Arc(Invalid i) : Edge(i), forward(true) {}
64	64
65	65	bool operator==(const Arc &that) const {
66	66	return forward==that.forward && Edge(*this)==Edge(that);
67	67	}
68	68	bool operator!=(const Arc &that) const {
69	69	return forward!=that.forward \|\| Edge(*this)!=Edge(that);
70	70	}
71	71	bool operator<(const Arc &that) const {
72	72	return forward<that.forward \|\|
73	73	(!(that.forward<forward) && Edge(*this)<Edge(that));
74	74	}
75	75	};
76	76
77	77	/// First node of the edge
78	78	Node u(const Edge &e) const {
79	79	return Parent::source(e);
80	80	}
81	81
82	82	/// Source of the given arc
83	83	Node source(const Arc &e) const {
84	84	return e.forward ? Parent::source(e) : Parent::target(e);
85	85	}
86	86
87	87	/// Second node of the edge
88	88	Node v(const Edge &e) const {
89	89	return Parent::target(e);
90	90	}
91	91
92	92	/// Target of the given arc
93	93	Node target(const Arc &e) const {
94	94	return e.forward ? Parent::target(e) : Parent::source(e);
95	95	}
96	96
97	97	/// \brief Directed arc from an edge.
98	98	///
99	99	/// Returns a directed arc corresponding to the specified edge.
100	100	/// If the given bool is true, the first node of the given edge and
101	101	/// the source node of the returned arc are the same.
102	102	static Arc direct(const Edge &e, bool d) {
103	103	return Arc(e, d);
104	104	}
105	105
106	106	/// Returns whether the given directed arc has the same orientation
107	107	/// as the corresponding edge.
108		///
109		/// \todo reference to the corresponding point of the undirected digraph
110		/// concept. "What does the direction of an edge mean?"
111	108	static bool direction(const Arc &a) { return a.forward; }
112	109
113	110	using Parent::first;
114	111	using Parent::next;
115	112
116	113	void first(Arc &e) const {
117	114	Parent::first(e);
118	115	e.forward=true;
119	116	}
120	117
121	118	void next(Arc &e) const {
122	119	if( e.forward ) {
123	120	e.forward = false;
124	121	}
125	122	else {
126	123	Parent::next(e);
127	124	e.forward = true;
128	125	}
129	126	}
130	127
131	128	void firstOut(Arc &e, const Node &n) const {
132	129	Parent::firstIn(e,n);
133	130	if( Edge(e) != INVALID ) {
134	131	e.forward = false;
135	132	}
136	133	else {
137	134	Parent::firstOut(e,n);
138	135	e.forward = true;
139	136	}
140	137	}
141	138	void nextOut(Arc &e) const {
142	139	if( ! e.forward ) {
143	140	Node n = Parent::target(e);
144	141	Parent::nextIn(e);
145	142	if( Edge(e) == INVALID ) {
146	143	Parent::firstOut(e, n);
147	144	e.forward = true;
148	145	}
149	146	}
150	147	else {
151	148	Parent::nextOut(e);
152	149	}
153	150	}
154	151
155	152	void firstIn(Arc &e, const Node &n) const {
156	153	Parent::firstOut(e,n);
157	154	if( Edge(e) != INVALID ) {
158	155	e.forward = false;
159	156	}
160	157	else {
161	158	Parent::firstIn(e,n);
162	159	e.forward = true;
163	160	}
164	161	}
165	162	void nextIn(Arc &e) const {
166	163	if( ! e.forward ) {
167	164	Node n = Parent::source(e);
168	165	Parent::nextOut(e);
169	166	if( Edge(e) == INVALID ) {
170	167	Parent::firstIn(e, n);
171	168	e.forward = true;
172	169	}
173	170	}
174	171	else {
175	172	Parent::nextIn(e);
176	173	}
177	174	}
178	175
179	176	void firstInc(Edge &e, bool &d, const Node &n) const {
180	177	d = true;
181	178	Parent::firstOut(e, n);
182	179	if (e != INVALID) return;
183	180	d = false;
184	181	Parent::firstIn(e, n);
185	182	}
186	183
187	184	void nextInc(Edge &e, bool &d) const {
188	185	if (d) {
189	186	Node s = Parent::source(e);
190	187	Parent::nextOut(e);
191	188	if (e != INVALID) return;
192	189	d = false;
193	190	Parent::firstIn(e, s);
194	191	} else {
195	192	Parent::nextIn(e);
196	193	}
197	194	}
198	195
199	196	Node nodeFromId(int ix) const {
200	197	return Parent::nodeFromId(ix);
201	198	}
202	199
203	200	Arc arcFromId(int ix) const {
204	201	return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
205	202	}
206	203
207	204	Edge edgeFromId(int ix) const {
208	205	return Parent::arcFromId(ix);
209	206	}
210	207
211	208	int id(const Node &n) const {
212	209	return Parent::id(n);
213	210	}
214	211
215	212	int id(const Edge &e) const {
216	213	return Parent::id(e);
217	214	}
218	215
219	216	int id(const Arc &e) const {
220	217	return 2 * Parent::id(e) + int(e.forward);
221	218	}
222	219
223	220	int maxNodeId() const {
224	221	return Parent::maxNodeId();
225	222	}
226	223
227	224	int maxArcId() const {
228	225	return 2 * Parent::maxArcId() + 1;
229	226	}
230	227
231	228	int maxEdgeId() const {
232	229	return Parent::maxArcId();
233	230	}
234	231
235	232	int arcNum() const {
236	233	return 2 * Parent::arcNum();
237	234	}
238	235