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

@@ -9,107 +9,105 @@
 		 * 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.
@@ -151,98 +149,97 @@
 		    ///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;
@@ -803,97 +800,96 @@
 		    ///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.
@@ -1325,98 +1321,97 @@
 		            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) {}

lemon/bits/base_extender.h

Show inline comments

@@ -60,99 +60,96 @@
      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;

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.

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;

lemon/dfs.h

Show inline comments

@@ -10,107 +10,105 @@
 		 * 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.
@@ -151,98 +149,97 @@
 		    ///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;
@@ -737,97 +734,96 @@
 		    ///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.
@@ -1272,98 +1268,97 @@
 		            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) {}

lemon/dijkstra.h

Show inline comments

@@ -99,109 +99,106 @@
 		    /// 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.
@@ -252,98 +249,97 @@
 		    ///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> > {
@@ -913,192 +909,186 @@
 		    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.

lemon/error.h

Show inline comments

@@ -57,98 +57,96 @@
 		      } 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() {

lemon/graph_to_eps.h

Show inline comments

@@ -621,148 +621,145 @@
 		  ///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.
@@ -828,130 +825,128 @@
 		       << "  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"

lemon/list_graph.h

Show inline comments

@@ -456,100 +456,98 @@
 		    /// \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:

lemon/maps.h

Show inline comments

@@ -439,154 +439,150 @@
 		  /// 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);
+		  }

lemon/random.h

Show inline comments

@@ -776,97 +776,96 @@
 		    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
 		    ///

lemon/smart_graph.h

Show inline comments

@@ -255,97 +255,96 @@
 		    /// 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.

lemon/time_measure.h

Show inline comments

@@ -247,97 +247,96 @@
+		  {
 		    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++;
@@ -442,97 +441,96 @@
+		    }
 		    ///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; }

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

0 comments (0 inline)

RhodeCode

Login to your account

...	...	@@ -60,99 +60,96 @@
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;