LEMON/LEMON-main Changeset - r581:aa1804409f29

Repositories » LEMON » LEMON-main

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

Changeset - r581:aa1804409f29

« 580:2313ed

582:7a28e2 »

r581:aa1804409f29

Tue, 14 Apr 2009 10:35:38

[Not Reviewed]

0 comments (0 inline)

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

Exploit that the standard maps are reference maps (#190)

0 9 0

default

9 files changed:

lemon/circulation.h

lemon/core.h

lemon/elevator.h

lemon/gomory_hu.h

lemon/hao_orlin.h

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

↑ Collapse diff ↑

lemon/circulation.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-2009
 		 * 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_CIRCULATION_H
 		#define LEMON_CIRCULATION_H
 		#include <lemon/tolerance.h>
 		#include <lemon/elevator.h>
 		///\ingroup max_flow
 		///\file
 		///\brief Push-relabel algorithm for finding a feasible circulation.
 		///
 		namespace lemon {
 		  /// \brief Default traits class of Circulation class.
 		  ///
 		  /// Default traits class of Circulation class.
 		  /// \tparam GR Digraph type.
 		  /// \tparam LM Lower bound capacity map type.
 		  /// \tparam UM Upper bound capacity map type.
 		  /// \tparam DM Delta map type.
 		  template <typename GR, typename LM,
 		            typename UM, typename DM>
 		  struct CirculationDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the circulation lower
 		    /// bound.
 		    ///
 		    /// The type of the map that stores the circulation lower bound.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LM LCapMap;
 		    /// \brief The type of the map that stores the circulation upper
 		    /// bound.
 		    ///
 		    /// The type of the map that stores the circulation upper bound.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef UM UCapMap;
 		    /// \brief The type of the map that stores the lower bound for
 		    /// the supply of the nodes.
 		    ///
 		    /// The type of the map that stores the lower bound for the supply
 		    /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
 		    /// concept.
 		    typedef DM DeltaMap;
 		    /// \brief The type of the flow values.
 		    typedef typename DeltaMap::Value Value;
 		    /// \brief The type of the map that stores the flow values.
 		    ///
 		    /// The type of the map that stores the flow values.
 		    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
 		    /// \param digraph The digraph, to which we would like to define
 		    /// the flow map.
 		    static FlowMap* createFlowMap(const Digraph& digraph) {
 		      return new FlowMap(digraph);
+		    }
 		    /// \brief The elevator type used by the algorithm.
 		    ///
 		    /// The elevator type used by the algorithm.
 		    ///
 		    /// \sa Elevator
 		    /// \sa LinkedElevator
 		    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
 		    /// \brief Instantiates an Elevator.
 		    ///
 		    /// This function instantiates an \ref Elevator.
 		    /// \param digraph The digraph, to which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
 		    ///
 		    /// The tolerance used by the algorithm to handle inexact computation.
 		    typedef lemon::Tolerance<Value> Tolerance;
 		  };
 		  /**
 		     \brief Push-relabel algorithm for the network circulation problem.
 		     \ingroup max_flow
 		     This class implements a push-relabel algorithm for the network
 		     circulation problem.
 		     It is to find a feasible circulation when lower and upper bounds
 		     are given for the flow values on the arcs and lower bounds
 		     are given for the supply values of the nodes.
 		     The exact formulation of this problem is the following.
 		     Let \f$G=(V,A)\f$ be a digraph,
 		     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
 		     \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
 		     \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
 		     \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
 		     \geq delta(v) \quad \forall v\in V, \f]
 		     \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
 		     \note \f$delta(v)\f$ specifies a lower bound for the supply of node
 		     \f$v\f$. It can be either positive or negative, however note that
 		     \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
 		     have a feasible solution.
 		     \note A special case of this problem is when
 		     \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
 		     will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
 		     Thus a feasible solution for the
 		     \ref min_cost_flow "minimum cost flow" problem can be calculated
 		     in this way.
 		     \tparam GR The type of the digraph the algorithm runs on.
 		     \tparam LM The type of the lower bound capacity map. The default
 		     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		     \tparam UM The type of the upper bound capacity map. The default
 		     map type is \c LM.
 		     \tparam DM The type of the map that stores the lower bound
 		     for the supply of the nodes. The default map type is
 		     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
 		  */
 		#ifdef DOXYGEN
 		template< typename GR,
 		          typename LM,
 		          typename UM,
 		          typename DM,
 		          typename TR >
 		#else
 		template< typename GR,
 		          typename LM = typename GR::template ArcMap<int>,
 		          typename UM = LM,
 		          typename DM = typename GR::template NodeMap<typename UM::Value>,
 		          typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
 		#endif
 		  class Circulation {
 		  public:
 		    ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The type of the flow values.
 		    typedef typename Traits::Value Value;
 		    /// The type of the lower bound capacity map.
 		    typedef typename Traits::LCapMap LCapMap;
 		    /// The type of the upper bound capacity map.
 		    typedef typename Traits::UCapMap UCapMap;
 		    /// \brief The type of the map that stores the lower bound for
 		    /// the supply of the nodes.
 		    typedef typename Traits::DeltaMap DeltaMap;
 		    ///The type of the flow map.
 		    typedef typename Traits::FlowMap FlowMap;
 		    ///The type of the elevator.
 		    typedef typename Traits::Elevator Elevator;
 		    ///The type of the tolerance.
 		    typedef typename Traits::Tolerance Tolerance;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph &_g;
 		    int _node_num;
 		    const LCapMap *_lo;
 		    const UCapMap *_up;
 		    const DeltaMap *_delta;
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tol;
 		    int _el;
 		  public:
 		    typedef Circulation Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		      static FlowMap *createFlowMap(const Digraph&) {
 		        LEMON_ASSERT(false, "FlowMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// FlowMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting FlowMap
 		    /// type.
 		    template <typename T>
 		    struct SetFlowMap
 		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                           SetFlowMapTraits<T> > {
 		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                          SetFlowMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph&, int) {
 		        LEMON_ASSERT(false, "Elevator is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type. If this named parameter is used, then an external
 		    /// elevator object must be passed to the algorithm using the
 		    /// \ref elevator(Elevator&) "elevator()" function before calling
 		    /// \ref run() or \ref init().
 		    /// \sa SetStandardElevator
 		    template <typename T>
 		    struct SetElevator
 		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                           SetElevatorTraits<T> > {
 		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                          SetElevatorTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetStandardElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph& digraph, int max_level) {
 		        return new Elevator(digraph, max_level);
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type with automatic allocation
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type with automatic allocation.
 		    /// The Elevator should have standard constructor interface to be
 		    /// able to automatically created by the algorithm (i.e. the
 		    /// digraph and the maximum level should be passed to it).
 		    /// However an external elevator object could also be passed to the
 		    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
 		    /// before calling \ref run() or \ref init().
 		    /// \sa SetElevator
 		    template <typename T>
 		    struct SetStandardElevator
 		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                       SetStandardElevatorTraits<T> > {
 		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                      SetStandardElevatorTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Circulation() {}
 		  public:
 		    /// The constructor of the class.
 		    /// The constructor of the class.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param lo The lower bound capacity of the arcs.
 		    /// \param up The upper bound capacity of the arcs.
 		    /// \param delta The lower bound for the supply of the nodes.
 		    Circulation(const Digraph &g,const LCapMap &lo,
 		                const UCapMap &up,const DeltaMap &delta)
 		      : _g(g), _node_num(),
 		        _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
 		        _level(0), _local_level(false), _excess(0), _el() {}
 		    /// Destructor.
 		    ~Circulation() {
 		      destroyStructures();
+		    }
 		  private:
 		    void createStructures() {
 		      _node_num = _el = countNodes(_g);
 		      if (!_flow) {
 		        _flow = Traits::createFlowMap(_g);
 		        _local_flow = true;
+		      }
 		      if (!_level) {
 		        _level = Traits::createElevator(_g, _node_num);
 		        _local_level = true;
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_g);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_local_flow) {
 		        delete _flow;
+		      }
 		      if (_local_level) {
 		        delete _level;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
+		    }
 		  public:
 		    /// Sets the lower bound capacity map.
 		    /// Sets the lower bound capacity map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& lowerCapMap(const LCapMap& map) {
 		      _lo = &map;
 		      return *this;
+		    }
 		    /// Sets the upper bound capacity map.
 		    /// Sets the upper bound capacity map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& upperCapMap(const LCapMap& map) {
 		      _up = &map;
 		      return *this;
+		    }
 		    /// Sets the lower bound map for the supply of the nodes.
 		    /// Sets the lower bound map for the supply of the nodes.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& deltaMap(const DeltaMap& map) {
 		      _delta = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the flow map.
 		    ///
 		    /// Sets the flow map.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& flowMap(FlowMap& map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the elevator used by algorithm.
 		    ///
 		    /// Sets the elevator used by algorithm.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated elevator,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& elevator(Elevator& elevator) {
 		      if (_local_level) {
 		        delete _level;
 		        _local_level = false;
+		      }
 		      _level = &elevator;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the elevator.
 		    ///
 		    /// Returns a const reference to the elevator.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const Elevator& elevator() const {
 		      return *_level;
+		    }
 		    /// \brief Sets the tolerance used by algorithm.
 		    ///
 		    /// Sets the tolerance used by algorithm.
 		    Circulation& tolerance(const Tolerance& tolerance) const {
 		      _tol = tolerance;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the tolerance.
 		    ///
 		    /// Returns a const reference to the tolerance.
 		    const Tolerance& tolerance() const {
 		      return tolerance;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to call \ref run().\n
 		    /// If you need more control on the initial solution or the execution,
 		    /// first you have to call one of the \ref init() functions, then
 		    /// the \ref start() function.
 		    ///@{
 		    /// Initializes the internal data structures.
 		    /// Initializes the internal data structures and sets all flow values
 		    /// to the lower bound.
 		    void init()
+		    {
 		      createStructures();
 		      for(NodeIt n(_g);n!=INVALID;++n) {
-		        _excess->set(n, (*_delta)[n]);
+		        (*_excess)[n] = (*_delta)[n];
+		      }
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        _flow->set(e, (*_lo)[e]);
 		        _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);
 		        _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);
 		        (*_excess)[_g.target(e)] += (*_flow)[e];
 		        (*_excess)[_g.source(e)] -= (*_flow)[e];
+		      }
 		      // global relabeling tested, but in general case it provides
 		      // worse performance for random digraphs
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    /// Initializes the internal data structures using a greedy approach.
 		    /// Initializes the internal data structures using a greedy approach
 		    /// to construct the initial solution.
 		    void greedyInit()
+		    {
 		      createStructures();
 		      for(NodeIt n(_g);n!=INVALID;++n) {
-		        _excess->set(n, (*_delta)[n]);
+		        (*_excess)[n] = (*_delta)[n];
+		      }
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
 		          _flow->set(e, (*_up)[e]);
 		          _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);
 		          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);
 		          (*_excess)[_g.target(e)] += (*_up)[e];
 		          (*_excess)[_g.source(e)] -= (*_up)[e];
 		        } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
 		          _flow->set(e, (*_lo)[e]);
 		          _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
 		          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
 		          (*_excess)[_g.target(e)] += (*_lo)[e];
 		          (*_excess)[_g.source(e)] -= (*_lo)[e];
 		        } else {
 		          Value fc = -(*_excess)[_g.target(e)];
 		          _flow->set(e, fc);
 		          _excess->set(_g.target(e), 0);
 		          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
 		          (*_excess)[_g.target(e)] = 0;
 		          (*_excess)[_g.source(e)] -= fc;
+		        }
+		      }
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    ///Executes the algorithm
 		    ///This function executes the algorithm.
 		    ///
 		    ///\return \c true if a feasible circulation is found.
 		    ///
 		    ///\sa barrier()
 		    ///\sa barrierMap()
 		    bool start()
+		    {
 		      Node act;
 		      Node bact=INVALID;
 		      Node last_activated=INVALID;
 		      while((act=_level->highestActive())!=INVALID) {
 		        int actlevel=(*_level)[act];
 		        int mlevel=_node_num;
 		        Value exc=(*_excess)[act];
 		        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
 		          Node v = _g.target(e);
 		          Value fc=(*_up)[e]-(*_flow)[e];
 		          if(!_tol.positive(fc)) continue;
 		          if((*_level)[v]<actlevel) {
 		            if(!_tol.less(fc, exc)) {
 		              _flow->set(e, (*_flow)[e] + exc);
-		              _excess->set(v, (*_excess)[v] + exc);
+		              (*_excess)[v] += exc;
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
-		              _excess->set(act,0);
+		              (*_excess)[act] = 0;
 		              _level->deactivate(act);
 		              goto next_l;
+		            }
 		            else {
 		              _flow->set(e, (*_up)[e]);
-		              _excess->set(v, (*_excess)[v] + fc);
+		              (*_excess)[v] += fc;
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              exc-=fc;
+		            }
+		          }
 		          else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
+		        }
 		        for(InArcIt e(_g,act);e!=INVALID; ++e) {
 		          Node v = _g.source(e);
 		          Value fc=(*_flow)[e]-(*_lo)[e];
 		          if(!_tol.positive(fc)) continue;
 		          if((*_level)[v]<actlevel) {
 		            if(!_tol.less(fc, exc)) {
 		              _flow->set(e, (*_flow)[e] - exc);
-		              _excess->set(v, (*_excess)[v] + exc);
+		              (*_excess)[v] += exc;
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
-		              _excess->set(act,0);
+		              (*_excess)[act] = 0;
 		              _level->deactivate(act);
 		              goto next_l;
+		            }
 		            else {
 		              _flow->set(e, (*_lo)[e]);
-		              _excess->set(v, (*_excess)[v] + fc);
+		              (*_excess)[v] += fc;
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              exc-=fc;
+		            }
+		          }
 		          else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
+		        }
-		        _excess->set(act, exc);
+		        (*_excess)[act] = exc;
 		        if(!_tol.positive(exc)) _level->deactivate(act);
 		        else if(mlevel==_node_num) {
 		          _level->liftHighestActiveToTop();
 		          _el = _node_num;
 		          return false;
+		        }
 		        else {
 		          _level->liftHighestActive(mlevel+1);
 		          if(_level->onLevel(actlevel)==0) {
 		            _el = actlevel;
 		            return false;
+		          }
+		        }
 		      next_l:
+		        ;
+		      }
 		      return true;
+		    }
 		    /// Runs the algorithm.
 		    /// This function runs the algorithm.
 		    ///
 		    /// \return \c true if a feasible circulation is found.
 		    ///
 		    /// \note Apart from the return value, c.run() is just a shortcut of
 		    /// the following code.
 		    /// \code
 		    ///   c.greedyInit();
 		    ///   c.start();
 		    /// \endcode
 		    bool run() {
 		      greedyInit();
 		      return start();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the circulation algorithm can be obtained using
 		    /// these functions.\n
 		    /// Either \ref run() or \ref start() should be called before
 		    /// using them.
 		    ///@{
 		    /// \brief Returns the flow on the given arc.
 		    ///
 		    /// Returns the flow on the given arc.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Value flow(const Arc& arc) const {
 		      return (*_flow)[arc];
+		    }
 		    /// \brief Returns a const reference to the flow map.
 		    ///
 		    /// Returns a const reference to the arc map storing the found flow.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow;
+		    }
 		    /**
 		       \brief Returns \c true if the given node is in a barrier.
 		       Barrier is a set \e B of nodes for which
 		       \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
 		           \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
 		       holds. The existence of a set with this property prooves that a
 		       feasible circualtion cannot exist.
 		       This function returns \c true if the given node is in the found
 		       barrier. If a feasible circulation is found, the function
 		       gives back \c false for every node.
 		       \pre Either \ref run() or \ref init() must be called before
 		       using this function.
 		       \sa barrierMap()
 		       \sa checkBarrier()
 		    */
 		    bool barrier(const Node& node) const
+		    {
 		      return (*_level)[node] >= _el;
+		    }
 		    /// \brief Gives back a barrier.
 		    ///
 		    /// This function sets \c bar to the characteristic vector of the
 		    /// found barrier. \c bar should be a \ref concepts::WriteMap "writable"
 		    /// node map with \c bool (or convertible) value type.
 		    ///
 		    /// If a feasible circulation is found, the function gives back an
 		    /// empty set, so \c bar[v] will be \c false for all nodes \c v.
 		    ///
 		    /// \note This function calls \ref barrier() for each node,
 		    /// so it runs in O(n) time.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    ///
 		    /// \sa barrier()
 		    /// \sa checkBarrier()
 		    template<class BarrierMap>
 		    void barrierMap(BarrierMap &bar) const
+		    {
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        bar.set(n, (*_level)[n] >= _el);
+		    }
 		    /// @}
 		    /// \name Checker Functions
 		    /// The feasibility of the results can be checked using
 		    /// these functions.\n
 		    /// Either \ref run() or \ref start() should be called before
 		    /// using them.
 		    ///@{
 		    ///Check if the found flow is a feasible circulation
 		    ///Check if the found flow is a feasible circulation,
 		    ///
 		    bool checkFlow() const {
 		      for(ArcIt e(_g);e!=INVALID;++e)
 		        if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
 		      for(NodeIt n(_g);n!=INVALID;++n)
+		        {
 		          Value dif=-(*_delta)[n];
 		          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
 		          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
 		          if(_tol.negative(dif)) return false;
+		        }
 		      return true;
+		    }
 		    ///Check whether or not the last execution provides a barrier
 		    ///Check whether or not the last execution provides a barrier.
 		    ///\sa barrier()
 		    ///\sa barrierMap()
 		    bool checkBarrier() const
+		    {
 		      Value delta=0;
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(barrier(n))
 		          delta-=(*_delta)[n];
 		      for(ArcIt e(_g);e!=INVALID;++e)
+		        {
 		          Node s=_g.source(e);
 		          Node t=_g.target(e);
 		          if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
 		          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
+		        }
 		      return _tol.negative(delta);
+		    }
 		    /// @}
 		  };
+		}
 		#endif

lemon/core.h

Show inline comments

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

lemon/elevator.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-2009
 		 * 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_ELEVATOR_H
 		#define LEMON_ELEVATOR_H
 		///\ingroup auxdat
 		///\file
 		///\brief Elevator class
 		///
 		///Elevator class implements an efficient data structure
 		///for labeling items in push-relabel type algorithms.
 		///
 		#include <lemon/core.h>
 		#include <lemon/bits/traits.h>
 		namespace lemon {
 		  ///Class for handling "labels" in push-relabel type algorithms.
 		  ///A class for handling "labels" in push-relabel type algorithms.
 		  ///
 		  ///\ingroup auxdat
 		  ///Using this class you can assign "labels" (nonnegative integer numbers)
 		  ///to the edges or nodes of a graph, manipulate and query them through
 		  ///operations typically arising in "push-relabel" type algorithms.
 		  ///
 		  ///Each item is either \em active or not, and you can also choose a
 		  ///highest level active item.
 		  ///
 		  ///\sa LinkedElevator
 		  ///
 		  ///\param GR Type of the underlying graph.
 		  ///\param Item Type of the items the data is assigned to (\c GR::Node,
 		  ///\c GR::Arc or \c GR::Edge).
 		  template<class GR, class Item>
 		  class Elevator
+		  {
 		  public:
 		    typedef Item Key;
 		    typedef int Value;
 		  private:
 		    typedef Item *Vit;
 		    typedef typename ItemSetTraits<GR,Item>::template Map<Vit>::Type VitMap;
 		    typedef typename ItemSetTraits<GR,Item>::template Map<int>::Type IntMap;
 		    const GR &_g;
 		    int _max_level;
 		    int _item_num;
 		    VitMap _where;
 		    IntMap _level;
 		    std::vector<Item> _items;
 		    std::vector<Vit> _first;
 		    std::vector<Vit> _last_active;
 		    int _highest_active;
 		    void copy(Item i, Vit p)
+		    {
-		      _where.set(*p=i,p);
+		      _where[*p=i] = p;
+		    }
 		    void copy(Vit s, Vit p)
+		    {
 		      if(s!=p)
+		        {
 		          Item i=*s;
 		          *p=i;
-		          _where.set(i,p);
+		          _where[i] = p;
+		        }
+		    }
 		    void swap(Vit i, Vit j)
+		    {
 		      Item ti=*i;
 		      Vit ct = _where[ti];
 		      _where.set(ti,_where[*i=*j]);
 		      _where.set(*j,ct);
 		      _where[ti] = _where[*i=*j];
 		      _where[*j] = ct;
 		      *j=ti;
+		    }
 		  public:
 		    ///Constructor with given maximum level.
 		    ///Constructor with given maximum level.
 		    ///
 		    ///\param graph The underlying graph.
 		    ///\param max_level The maximum allowed level.
 		    ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
 		    Elevator(const GR &graph,int max_level) :
 		      _g(graph),
 		      _max_level(max_level),
 		      _item_num(_max_level),
 		      _where(graph),
 		      _level(graph,0),
 		      _items(_max_level),
 		      _first(_max_level+2),
 		      _last_active(_max_level+2),
 		      _highest_active(-1) {}
 		    ///Constructor.
 		    ///Constructor.
 		    ///
 		    ///\param graph The underlying graph.
 		    ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
 		    ///where \c max_level is equal to the number of labeled items in the graph.
 		    Elevator(const GR &graph) :
 		      _g(graph),
 		      _max_level(countItems<GR, Item>(graph)),
 		      _item_num(_max_level),
 		      _where(graph),
 		      _level(graph,0),
 		      _items(_max_level),
 		      _first(_max_level+2),
 		      _last_active(_max_level+2),
 		      _highest_active(-1)
+		    {
+		    }
 		    ///Activate item \c i.
 		    ///Activate item \c i.
 		    ///\pre Item \c i shouldn't be active before.
 		    void activate(Item i)
+		    {
 		      const int l=_level[i];
 		      swap(_where[i],++_last_active[l]);
 		      if(l>_highest_active) _highest_active=l;
+		    }
 		    ///Deactivate item \c i.
 		    ///Deactivate item \c i.
 		    ///\pre Item \c i must be active before.
 		    void deactivate(Item i)
+		    {
 		      swap(_where[i],_last_active[_level[i]]--);
 		      while(_highest_active>=0 &&
 		            _last_active[_highest_active]<_first[_highest_active])
 		        _highest_active--;
+		    }
 		    ///Query whether item \c i is active
 		    bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
 		    ///Return the level of item \c i.
 		    int operator[](Item i) const { return _level[i]; }
 		    ///Return the number of items on level \c l.
 		    int onLevel(int l) const
+		    {
 		      return _first[l+1]-_first[l];
+		    }
 		    ///Return true if level \c l is empty.
 		    bool emptyLevel(int l) const
+		    {
 		      return _first[l+1]-_first[l]==0;
+		    }
 		    ///Return the number of items above level \c l.
 		    int aboveLevel(int l) const
+		    {
 		      return _first[_max_level+1]-_first[l+1];
+		    }
 		    ///Return the number of active items on level \c l.
 		    int activesOnLevel(int l) const
+		    {
 		      return _last_active[l]-_first[l]+1;
+		    }
 		    ///Return true if there is no active item on level \c l.
 		    bool activeFree(int l) const
+		    {
 		      return _last_active[l]<_first[l];
+		    }
 		    ///Return the maximum allowed level.
 		    int maxLevel() const
+		    {
 		      return _max_level;
+		    }
 		    ///\name Highest Active Item
 		    ///Functions for working with the highest level
 		    ///active item.
 		    ///@{
 		    ///Return a highest level active item.
 		    ///Return a highest level active item or INVALID if there is no active
 		    ///item.
 		    Item highestActive() const
+		    {
 		      return _highest_active>=0?*_last_active[_highest_active]:INVALID;
+		    }
 		    ///Return the highest active level.
 		    ///Return the level of the highest active item or -1 if there is no active
 		    ///item.
 		    int highestActiveLevel() const
+		    {
 		      return _highest_active;
+		    }
 		    ///Lift the highest active item by one.
 		    ///Lift the item returned by highestActive() by one.
 		    ///
 		    void liftHighestActive()
+		    {
 		      Item it = *_last_active[_highest_active];
-		      _level.set(it,_level[it]+1);
+		      ++_level[it];
 		      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
 		      --_first[++_highest_active];
+		    }
 		    ///Lift the highest active item to the given level.
 		    ///Lift the item returned by highestActive() to level \c new_level.
 		    ///
 		    ///\warning \c new_level must be strictly higher
 		    ///than the current level.
 		    ///
 		    void liftHighestActive(int new_level)
+		    {
 		      const Item li = *_last_active[_highest_active];
 		      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
 		      for(int l=_highest_active+1;l<new_level;l++)
+		        {
 		          copy(--_first[l+1],_first[l]);
 		          --_last_active[l];
+		        }
 		      copy(li,_first[new_level]);
-		      _level.set(li,new_level);
+		      _level[li] = new_level;
 		      _highest_active=new_level;
+		    }
 		    ///Lift the highest active item to the top level.
 		    ///Lift the item returned by highestActive() to the top level and
 		    ///deactivate it.
 		    void liftHighestActiveToTop()
+		    {
 		      const Item li = *_last_active[_highest_active];
 		      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
 		      for(int l=_highest_active+1;l<_max_level;l++)
+		        {
 		          copy(--_first[l+1],_first[l]);
 		          --_last_active[l];
+		        }
 		      copy(li,_first[_max_level]);
 		      --_last_active[_max_level];
-		      _level.set(li,_max_level);
+		      _level[li] = _max_level;
 		      while(_highest_active>=0 &&
 		            _last_active[_highest_active]<_first[_highest_active])
 		        _highest_active--;
+		    }
 		    ///@}
 		    ///\name Active Item on Certain Level
 		    ///Functions for working with the active items.
 		    ///@{
 		    ///Return an active item on level \c l.
 		    ///Return an active item on level \c l or \ref INVALID if there is no such
 		    ///an item. (\c l must be from the range [0...\c max_level].
 		    Item activeOn(int l) const
+		    {
 		      return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
+		    }
 		    ///Lift the active item returned by \c activeOn(level) by one.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
 		    ///by one.
 		    Item liftActiveOn(int level)
+		    {
 		      Item it =*_last_active[level];
-		      _level.set(it,_level[it]+1);
+		      ++_level[it];
 		      swap(_last_active[level]--, --_first[level+1]);
 		      if (level+1>_highest_active) ++_highest_active;
+		    }
 		    ///Lift the active item returned by \c activeOn(level) to the given level.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
 		    ///to the given level.
 		    void liftActiveOn(int level, int new_level)
+		    {
 		      const Item ai = *_last_active[level];
 		      copy(--_first[level+1], _last_active[level]--);
 		      for(int l=level+1;l<new_level;l++)
+		        {
 		          copy(_last_active[l],_first[l]);
 		          copy(--_first[l+1], _last_active[l]--);
+		        }
 		      copy(ai,_first[new_level]);
-		      _level.set(ai,new_level);
+		      _level[ai] = new_level;
 		      if (new_level>_highest_active) _highest_active=new_level;
+		    }
 		    ///Lift the active item returned by \c activeOn(level) to the top level.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
 		    ///to the top level and deactivate it.
 		    void liftActiveToTop(int level)
+		    {
 		      const Item ai = *_last_active[level];
 		      copy(--_first[level+1],_last_active[level]--);
 		      for(int l=level+1;l<_max_level;l++)
+		        {
 		          copy(_last_active[l],_first[l]);
 		          copy(--_first[l+1], _last_active[l]--);
+		        }
 		      copy(ai,_first[_max_level]);
 		      --_last_active[_max_level];
-		      _level.set(ai,_max_level);
+		      _level[ai] = _max_level;
 		      if (_highest_active==level) {
 		        while(_highest_active>=0 &&
 		              _last_active[_highest_active]<_first[_highest_active])
 		          _highest_active--;
+		      }
+		    }
 		    ///@}
 		    ///Lift an active item to a higher level.
 		    ///Lift an active item to a higher level.
 		    ///\param i The item to be lifted. It must be active.
 		    ///\param new_level The new level of \c i. It must be strictly higher
 		    ///than the current level.
 		    ///
 		    void lift(Item i, int new_level)
+		    {
 		      const int lo = _level[i];
 		      const Vit w = _where[i];
 		      copy(_last_active[lo],w);
 		      copy(--_first[lo+1],_last_active[lo]--);
 		      for(int l=lo+1;l<new_level;l++)
+		        {
 		          copy(_last_active[l],_first[l]);
 		          copy(--_first[l+1],_last_active[l]--);
+		        }
 		      copy(i,_first[new_level]);
-		      _level.set(i,new_level);
+		      _level[i] = new_level;
 		      if(new_level>_highest_active) _highest_active=new_level;
+		    }
 		    ///Move an inactive item to the top but one level (in a dirty way).
 		    ///This function moves an inactive item from the top level to the top
 		    ///but one level (in a dirty way).
 		    ///\warning It makes the underlying datastructure corrupt, so use it
 		    ///only if you really know what it is for.
 		    ///\pre The item is on the top level.
 		    void dirtyTopButOne(Item i) {
-		      _level.set(i,_max_level - 1);
+		      _level[i] = _max_level - 1;
+		    }
 		    ///Lift all items on and above the given level to the top level.
 		    ///This function lifts all items on and above level \c l to the top
 		    ///level and deactivates them.
 		    void liftToTop(int l)
+		    {
 		      const Vit f=_first[l];
 		      const Vit tl=_first[_max_level];
 		      for(Vit i=f;i!=tl;++i)
-		        _level.set(*i,_max_level);
+		        _level[*i] = _max_level;
 		      for(int i=l;i<=_max_level;i++)
+		        {
 		          _first[i]=f;
 		          _last_active[i]=f-1;
+		        }
 		      for(_highest_active=l-1;
 		          _highest_active>=0 &&
 		            _last_active[_highest_active]<_first[_highest_active];
 		          _highest_active--) ;
+		    }
 		  private:
 		    int _init_lev;
 		    Vit _init_num;
 		  public:
 		    ///\name Initialization
 		    ///Using these functions you can initialize the levels of the items.
 		    ///\n
 		    ///The initialization must be started with calling \c initStart().
 		    ///Then the items should be listed level by level starting with the
 		    ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
 		    ///Finally \c initFinish() must be called.
 		    ///The items not listed are put on the highest level.
 		    ///@{
 		    ///Start the initialization process.
 		    void initStart()
+		    {
 		      _init_lev=0;
 		      _init_num=&_items[0];
 		      _first[0]=&_items[0];
 		      _last_active[0]=&_items[0]-1;
 		      Vit n=&_items[0];
 		      for(typename ItemSetTraits<GR,Item>::ItemIt i(_g);i!=INVALID;++i)
+		        {
 		          *n=i;
 		          _where.set(i,n);
 		          _level.set(i,_max_level);
 		          _where[i] = n;
 		          _level[i] = _max_level;
 		          ++n;
+		        }
+		    }
 		    ///Add an item to the current level.
 		    void initAddItem(Item i)
+		    {
 		      swap(_where[i],_init_num);
-		      _level.set(i,_init_lev);
+		      _level[i] = _init_lev;
 		      ++_init_num;
+		    }
 		    ///Start a new level.
 		    ///Start a new level.
 		    ///It shouldn't be used before the items on level 0 are listed.
 		    void initNewLevel()
+		    {
 		      _init_lev++;
 		      _first[_init_lev]=_init_num;
 		      _last_active[_init_lev]=_init_num-1;
+		    }
 		    ///Finalize the initialization process.
 		    void initFinish()
+		    {
 		      for(_init_lev++;_init_lev<=_max_level;_init_lev++)
+		        {
 		          _first[_init_lev]=_init_num;
 		          _last_active[_init_lev]=_init_num-1;
+		        }
 		      _first[_max_level+1]=&_items[0]+_item_num;
 		      _last_active[_max_level+1]=&_items[0]+_item_num-1;
 		      _highest_active = -1;
+		    }
 		    ///@}
 		  };
 		  ///Class for handling "labels" in push-relabel type algorithms.
 		  ///A class for handling "labels" in push-relabel type algorithms.
 		  ///
 		  ///\ingroup auxdat
 		  ///Using this class you can assign "labels" (nonnegative integer numbers)
 		  ///to the edges or nodes of a graph, manipulate and query them through
 		  ///operations typically arising in "push-relabel" type algorithms.
 		  ///
 		  ///Each item is either \em active or not, and you can also choose a
 		  ///highest level active item.
 		  ///
 		  ///\sa Elevator
 		  ///
 		  ///\param GR Type of the underlying graph.
 		  ///\param Item Type of the items the data is assigned to (\c GR::Node,
 		  ///\c GR::Arc or \c GR::Edge).
 		  template <class GR, class Item>
 		  class LinkedElevator {
 		  public:
 		    typedef Item Key;
 		    typedef int Value;
 		  private:
 		    typedef typename ItemSetTraits<GR,Item>::
 		    template Map<Item>::Type ItemMap;
 		    typedef typename ItemSetTraits<GR,Item>::
 		    template Map<int>::Type IntMap;
 		    typedef typename ItemSetTraits<GR,Item>::
 		    template Map<bool>::Type BoolMap;
 		    const GR &_graph;
 		    int _max_level;
 		    int _item_num;
 		    std::vector<Item> _first, _last;
 		    ItemMap _prev, _next;
 		    int _highest_active;
 		    IntMap _level;
 		    BoolMap _active;
 		  public:
 		    ///Constructor with given maximum level.
 		    ///Constructor with given maximum level.
 		    ///
 		    ///\param graph The underlying graph.
 		    ///\param max_level The maximum allowed level.
 		    ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
 		    LinkedElevator(const GR& graph, int max_level)
 		      : _graph(graph), _max_level(max_level), _item_num(_max_level),
 		        _first(_max_level + 1), _last(_max_level + 1),
 		        _prev(graph), _next(graph),
 		        _highest_active(-1), _level(graph), _active(graph) {}
 		    ///Constructor.
 		    ///Constructor.
 		    ///
 		    ///\param graph The underlying graph.
 		    ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
 		    ///where \c max_level is equal to the number of labeled items in the graph.
 		    LinkedElevator(const GR& graph)
 		      : _graph(graph), _max_level(countItems<GR, Item>(graph)),
 		        _item_num(_max_level),
 		        _first(_max_level + 1), _last(_max_level + 1),
 		        _prev(graph, INVALID), _next(graph, INVALID),
 		        _highest_active(-1), _level(graph), _active(graph) {}
 		    ///Activate item \c i.
 		    ///Activate item \c i.
 		    ///\pre Item \c i shouldn't be active before.
 		    void activate(Item i) {
-		      _active.set(i, true);
+		      _active[i] = true;
 		      int level = _level[i];
 		      if (level > _highest_active) {
 		        _highest_active = level;
+		      }
 		      if (_prev[i] == INVALID || _active[_prev[i]]) return;
 		      //unlace
-		      _next.set(_prev[i], _next[i]);
+		      _next[_prev[i]] = _next[i];
 		      if (_next[i] != INVALID) {
-		        _prev.set(_next[i], _prev[i]);
+		        _prev[_next[i]] = _prev[i];
 		      } else {
 		        _last[level] = _prev[i];
+		      }
 		      //lace
 		      _next.set(i, _first[level]);
 		      _prev.set(_first[level], i);
-		      _prev.set(i, INVALID);
+		      _next[i] = _first[level];
 		      _prev[_first[level]] = i;
 		      _prev[i] = INVALID;
 		      _first[level] = i;
+		    }
 		    ///Deactivate item \c i.
 		    ///Deactivate item \c i.
 		    ///\pre Item \c i must be active before.
 		    void deactivate(Item i) {
-		      _active.set(i, false);
+		      _active[i] = false;
 		      int level = _level[i];
 		      if (_next[i] == INVALID || !_active[_next[i]])
 		        goto find_highest_level;
 		      //unlace
-		      _prev.set(_next[i], _prev[i]);
+		      _prev[_next[i]] = _prev[i];
 		      if (_prev[i] != INVALID) {
-		        _next.set(_prev[i], _next[i]);
+		        _next[_prev[i]] = _next[i];
 		      } else {
 		        _first[_level[i]] = _next[i];
+		      }
 		      //lace
 		      _prev.set(i, _last[level]);
 		      _next.set(_last[level], i);
-		      _next.set(i, INVALID);
+		      _prev[i] = _last[level];
 		      _next[_last[level]] = i;
 		      _next[i] = INVALID;
 		      _last[level] = i;
 		    find_highest_level:
 		      if (level == _highest_active) {
 		        while (_highest_active >= 0 && activeFree(_highest_active))
 		          --_highest_active;
+		      }
+		    }
 		    ///Query whether item \c i is active
 		    bool active(Item i) const { return _active[i]; }
 		    ///Return the level of item \c i.
 		    int operator[](Item i) const { return _level[i]; }
 		    ///Return the number of items on level \c l.
 		    int onLevel(int l) const {
 		      int num = 0;
 		      Item n = _first[l];
 		      while (n != INVALID) {
 		        ++num;
 		        n = _next[n];
+		      }
 		      return num;
+		    }
 		    ///Return true if the level is empty.
 		    bool emptyLevel(int l) const {
 		      return _first[l] == INVALID;
+		    }
 		    ///Return the number of items above level \c l.
 		    int aboveLevel(int l) const {
 		      int num = 0;
 		      for (int level = l + 1; level < _max_level; ++level)
 		        num += onLevel(level);
 		      return num;
+		    }
 		    ///Return the number of active items on level \c l.
 		    int activesOnLevel(int l) const {
 		      int num = 0;
 		      Item n = _first[l];
 		      while (n != INVALID && _active[n]) {
 		        ++num;
 		        n = _next[n];
+		      }
 		      return num;
+		    }
 		    ///Return true if there is no active item on level \c l.
 		    bool activeFree(int l) const {
 		      return _first[l] == INVALID || !_active[_first[l]];
+		    }
 		    ///Return the maximum allowed level.
 		    int maxLevel() const {
 		      return _max_level;
+		    }
 		    ///\name Highest Active Item
 		    ///Functions for working with the highest level
 		    ///active item.
 		    ///@{
 		    ///Return a highest level active item.
 		    ///Return a highest level active item or INVALID if there is no active
 		    ///item.
 		    Item highestActive() const {
 		      return _highest_active >= 0 ? _first[_highest_active] : INVALID;
+		    }
 		    ///Return the highest active level.
 		    ///Return the level of the highest active item or -1 if there is no active
 		    ///item.
 		    int highestActiveLevel() const {
 		      return _highest_active;
+		    }
 		    ///Lift the highest active item by one.
 		    ///Lift the item returned by highestActive() by one.
 		    ///
 		    void liftHighestActive() {
 		      Item i = _first[_highest_active];
 		      if (_next[i] != INVALID) {
-		        _prev.set(_next[i], INVALID);
+		        _prev[_next[i]] = INVALID;
 		        _first[_highest_active] = _next[i];
 		      } else {
 		        _first[_highest_active] = INVALID;
 		        _last[_highest_active] = INVALID;
+		      }
-		      _level.set(i, ++_highest_active);
+		      _level[i] = ++_highest_active;
 		      if (_first[_highest_active] == INVALID) {
 		        _first[_highest_active] = i;
 		        _last[_highest_active] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		        _prev[i] = INVALID;
 		        _next[i] = INVALID;
 		      } else {
 		        _prev.set(_first[_highest_active], i);
 		        _next.set(i, _first[_highest_active]);
 		        _prev[_first[_highest_active]] = i;
 		        _next[i] = _first[_highest_active];
 		        _first[_highest_active] = i;
+		      }
+		    }
 		    ///Lift the highest active item to the given level.
 		    ///Lift the item returned by highestActive() to level \c new_level.
 		    ///
 		    ///\warning \c new_level must be strictly higher
 		    ///than the current level.
 		    ///
 		    void liftHighestActive(int new_level) {
 		      Item i = _first[_highest_active];
 		      if (_next[i] != INVALID) {
-		        _prev.set(_next[i], INVALID);
+		        _prev[_next[i]] = INVALID;
 		        _first[_highest_active] = _next[i];
 		      } else {
 		        _first[_highest_active] = INVALID;
 		        _last[_highest_active] = INVALID;
+		      }
-		      _level.set(i, _highest_active = new_level);
+		      _level[i] = _highest_active = new_level;
 		      if (_first[_highest_active] == INVALID) {
 		        _first[_highest_active] = _last[_highest_active] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		        _prev[i] = INVALID;
 		        _next[i] = INVALID;
 		      } else {
 		        _prev.set(_first[_highest_active], i);
 		        _next.set(i, _first[_highest_active]);
 		        _prev[_first[_highest_active]] = i;
 		        _next[i] = _first[_highest_active];
 		        _first[_highest_active] = i;
+		      }
+		    }
 		    ///Lift the highest active item to the top level.
 		    ///Lift the item returned by highestActive() to the top level and
 		    ///deactivate it.
 		    void liftHighestActiveToTop() {
 		      Item i = _first[_highest_active];
-		      _level.set(i, _max_level);
+		      _level[i] = _max_level;
 		      if (_next[i] != INVALID) {
-		        _prev.set(_next[i], INVALID);
+		        _prev[_next[i]] = INVALID;
 		        _first[_highest_active] = _next[i];
 		      } else {
 		        _first[_highest_active] = INVALID;
 		        _last[_highest_active] = INVALID;
+		      }
 		      while (_highest_active >= 0 && activeFree(_highest_active))
 		        --_highest_active;
+		    }
 		    ///@}
 		    ///\name Active Item on Certain Level
 		    ///Functions for working with the active items.
 		    ///@{
 		    ///Return an active item on level \c l.
 		    ///Return an active item on level \c l or \ref INVALID if there is no such
 		    ///an item. (\c l must be from the range [0...\c max_level].
 		    Item activeOn(int l) const
+		    {
 		      return _active[_first[l]] ? _first[l] : INVALID;
+		    }
 		    ///Lift the active item returned by \c activeOn(l) by one.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
 		    ///by one.
 		    Item liftActiveOn(int l)
+		    {
 		      Item i = _first[l];
 		      if (_next[i] != INVALID) {
-		        _prev.set(_next[i], INVALID);
+		        _prev[_next[i]] = INVALID;
 		        _first[l] = _next[i];
 		      } else {
 		        _first[l] = INVALID;
 		        _last[l] = INVALID;
+		      }
-		      _level.set(i, ++l);
+		      _level[i] = ++l;
 		      if (_first[l] == INVALID) {
 		        _first[l] = _last[l] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		        _prev[i] = INVALID;
 		        _next[i] = INVALID;
 		      } else {
 		        _prev.set(_first[l], i);
 		        _next.set(i, _first[l]);
 		        _prev[_first[l]] = i;
 		        _next[i] = _first[l];
 		        _first[l] = i;
+		      }
 		      if (_highest_active < l) {
 		        _highest_active = l;
+		      }
+		    }
 		    ///Lift the active item returned by \c activeOn(l) to the given level.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
 		    ///to the given level.
 		    void liftActiveOn(int l, int new_level)
+		    {
 		      Item i = _first[l];
 		      if (_next[i] != INVALID) {
-		        _prev.set(_next[i], INVALID);
+		        _prev[_next[i]] = INVALID;
 		        _first[l] = _next[i];
 		      } else {
 		        _first[l] = INVALID;
 		        _last[l] = INVALID;
+		      }
-		      _level.set(i, l = new_level);
+		      _level[i] = l = new_level;
 		      if (_first[l] == INVALID) {
 		        _first[l] = _last[l] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		        _prev[i] = INVALID;
 		        _next[i] = INVALID;
 		      } else {
 		        _prev.set(_first[l], i);
 		        _next.set(i, _first[l]);
 		        _prev[_first[l]] = i;
 		        _next[i] = _first[l];
 		        _first[l] = i;
+		      }
 		      if (_highest_active < l) {
 		        _highest_active = l;
+		      }
+		    }
 		    ///Lift the active item returned by \c activeOn(l) to the top level.
 		    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
 		    ///to the top level and deactivate it.
 		    void liftActiveToTop(int l)
+		    {
 		      Item i = _first[l];
 		      if (_next[i] != INVALID) {
-		        _prev.set(_next[i], INVALID);
+		        _prev[_next[i]] = INVALID;
 		        _first[l] = _next[i];
 		      } else {
 		        _first[l] = INVALID;
 		        _last[l] = INVALID;
+		      }
-		      _level.set(i, _max_level);
+		      _level[i] = _max_level;
 		      if (l == _highest_active) {
 		        while (_highest_active >= 0 && activeFree(_highest_active))
 		          --_highest_active;
+		      }
+		    }
 		    ///@}
 		    /// \brief Lift an active item to a higher level.
 		    ///
 		    /// Lift an active item to a higher level.
 		    /// \param i The item to be lifted. It must be active.
 		    /// \param new_level The new level of \c i. It must be strictly higher
 		    /// than the current level.
 		    ///
 		    void lift(Item i, int new_level) {
 		      if (_next[i] != INVALID) {
-		        _prev.set(_next[i], _prev[i]);
+		        _prev[_next[i]] = _prev[i];
 		      } else {
 		        _last[new_level] = _prev[i];
+		      }
 		      if (_prev[i] != INVALID) {
-		        _next.set(_prev[i], _next[i]);
+		        _next[_prev[i]] = _next[i];
 		      } else {
 		        _first[new_level] = _next[i];
+		      }
-		      _level.set(i, new_level);
+		      _level[i] = new_level;
 		      if (_first[new_level] == INVALID) {
 		        _first[new_level] = _last[new_level] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		        _prev[i] = INVALID;
 		        _next[i] = INVALID;
 		      } else {
 		        _prev.set(_first[new_level], i);
 		        _next.set(i, _first[new_level]);
 		        _prev[_first[new_level]] = i;
 		        _next[i] = _first[new_level];
 		        _first[new_level] = i;
+		      }
 		      if (_highest_active < new_level) {
 		        _highest_active = new_level;
+		      }
+		    }
 		    ///Move an inactive item to the top but one level (in a dirty way).
 		    ///This function moves an inactive item from the top level to the top
 		    ///but one level (in a dirty way).
 		    ///\warning It makes the underlying datastructure corrupt, so use it
 		    ///only if you really know what it is for.
 		    ///\pre The item is on the top level.
 		    void dirtyTopButOne(Item i) {
-		      _level.set(i, _max_level - 1);
+		      _level[i] = _max_level - 1;
+		    }
 		    ///Lift all items on and above the given level to the top level.
 		    ///This function lifts all items on and above level \c l to the top
 		    ///level and deactivates them.
 		    void liftToTop(int l)  {
 		      for (int i = l + 1; _first[i] != INVALID; ++i) {
 		        Item n = _first[i];
 		        while (n != INVALID) {
-		          _level.set(n, _max_level);
+		          _level[n] = _max_level;
 		          n = _next[n];
+		        }
 		        _first[i] = INVALID;
 		        _last[i] = INVALID;
+		      }
 		      if (_highest_active > l - 1) {
 		        _highest_active = l - 1;
 		        while (_highest_active >= 0 && activeFree(_highest_active))
 		          --_highest_active;
+		      }
+		    }
 		  private:
 		    int _init_level;
 		  public:
 		    ///\name Initialization
 		    ///Using these functions you can initialize the levels of the items.
 		    ///\n
 		    ///The initialization must be started with calling \c initStart().
 		    ///Then the items should be listed level by level starting with the
 		    ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
 		    ///Finally \c initFinish() must be called.
 		    ///The items not listed are put on the highest level.
 		    ///@{
 		    ///Start the initialization process.
 		    void initStart() {
 		      for (int i = 0; i <= _max_level; ++i) {
 		        _first[i] = _last[i] = INVALID;
+		      }
 		      _init_level = 0;
 		      for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph);
 		          i != INVALID; ++i) {
 		        _level.set(i, _max_level);
 		        _active.set(i, false);
 		        _level[i] = _max_level;
 		        _active[i] = false;
+		      }
+		    }
 		    ///Add an item to the current level.
 		    void initAddItem(Item i) {
-		      _level.set(i, _init_level);
+		      _level[i] = _init_level;
 		      if (_last[_init_level] == INVALID) {
 		        _first[_init_level] = i;
 		        _last[_init_level] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		        _prev[i] = INVALID;
 		        _next[i] = INVALID;
 		      } else {
 		        _prev.set(i, _last[_init_level]);
 		        _next.set(i, INVALID);
-		        _next.set(_last[_init_level], i);
+		        _prev[i] = _last[_init_level];
 		        _next[i] = INVALID;
 		        _next[_last[_init_level]] = i;
 		        _last[_init_level] = i;
+		      }
+		    }
 		    ///Start a new level.
 		    ///Start a new level.
 		    ///It shouldn't be used before the items on level 0 are listed.
 		    void initNewLevel() {
 		      ++_init_level;
+		    }
 		    ///Finalize the initialization process.
 		    void initFinish() {
 		      _highest_active = -1;
+		    }
 		    ///@}
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif

lemon/gomory_hu.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_GOMORY_HU_TREE_H
 		#define LEMON_GOMORY_HU_TREE_H
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/preflow.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		/// \ingroup min_cut
 		/// \file
 		/// \brief Gomory-Hu cut tree in graphs.
 		namespace lemon {
 		  /// \ingroup min_cut
 		  ///
 		  /// \brief Gomory-Hu cut tree algorithm
 		  ///
 		  /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
 		  /// may contain edges which are not in the original graph. It has the
 		  /// property that the minimum capacity edge of the path between two nodes
 		  /// in this tree has the same weight as the minimum cut in the graph
 		  /// between these nodes. Moreover the components obtained by removing
 		  /// this edge from the tree determine the corresponding minimum cut.
 		  ///
 		  /// Therefore once this tree is computed, the minimum cut between any pair
 		  /// of nodes can easily be obtained.
 		  ///
 		  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
 		  /// the \ref Preflow algorithm), therefore the algorithm has
 		  /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
 		  /// rooted Gomory-Hu tree, its structure and the weights can be obtained
 		  /// by \c predNode(), \c predValue() and \c rootDist().
 		  ///
 		  /// The members \c minCutMap() and \c minCutValue() calculate
 		  /// the minimum cut and the minimum cut value between any two nodes
 		  /// in the graph. You can also list (iterate on) the nodes and the
 		  /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
 		  ///
 		  /// \tparam GR The type of the undirected graph the algorithm runs on.
 		  /// \tparam CAP The type of the edge map describing the edge capacities.
 		  /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
 		#ifdef DOXYGEN
 		  template <typename GR,
 			    typename CAP>
 		#else
 		  template <typename GR,
 			    typename CAP = typename GR::template EdgeMap<int> >
 		#endif
 		  class GomoryHu {
 		  public:
 		    /// The graph type
 		    typedef GR Graph;
 		    /// The type of the edge capacity map
 		    typedef CAP Capacity;
 		    /// The value type of capacities
 		    typedef typename Capacity::Value Value;
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    const Graph& _graph;
 		    const Capacity& _capacity;
 		    Node _root;
 		    typename Graph::template NodeMap<Node>* _pred;
 		    typename Graph::template NodeMap<Value>* _weight;
 		    typename Graph::template NodeMap<int>* _order;
 		    void createStructures() {
 		      if (!_pred) {
 			_pred = new typename Graph::template NodeMap<Node>(_graph);
+		      }
 		      if (!_weight) {
 			_weight = new typename Graph::template NodeMap<Value>(_graph);
+		      }
 		      if (!_order) {
 			_order = new typename Graph::template NodeMap<int>(_graph);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_pred) {
 			delete _pred;
+		      }
 		      if (_weight) {
 			delete _weight;
+		      }
 		      if (_order) {
 			delete _order;
+		      }
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \param graph The undirected graph the algorithm runs on.
 		    /// \param capacity The edge capacity map.
 		    GomoryHu(const Graph& graph, const Capacity& capacity)
 		      : _graph(graph), _capacity(capacity),
 			_pred(0), _weight(0), _order(0)
+		    {
 		      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
+		    }
 		    /// \brief Destructor
 		    ///
 		    /// Destructor
 		    ~GomoryHu() {
 		      destroyStructures();
+		    }
 		  private:
 		    // Initialize the internal data structures
 		    void init() {
 		      createStructures();
 		      _root = NodeIt(_graph);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 			_pred->set(n, _root);
 			_order->set(n, -1);
 		        (*_pred)[n] = _root;
 		        (*_order)[n] = -1;
+		      }
 		      _pred->set(_root, INVALID);
 		      _weight->set(_root, std::numeric_limits<Value>::max());
 		      (*_pred)[_root] = INVALID;
 		      (*_weight)[_root] = std::numeric_limits<Value>::max();
+		    }
 		    // Start the algorithm
 		    void start() {
 		      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 			if (n == _root) continue;
 			Node pn = (*_pred)[n];
 			fa.source(n);
 			fa.target(pn);
 			fa.runMinCut();
-			_weight->set(n, fa.flowValue());
+			(*_weight)[n] = fa.flowValue();
 			for (NodeIt nn(_graph); nn != INVALID; ++nn) {
 			  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
-			    _pred->set(nn, n);
+			    (*_pred)[nn] = n;
+			  }
+			}
 			if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
 			  _pred->set(n, (*_pred)[pn]);
 			  _pred->set(pn, n);
 			  _weight->set(n, (*_weight)[pn]);
 			  _weight->set(pn, fa.flowValue());
 			  (*_pred)[n] = (*_pred)[pn];
 			  (*_pred)[pn] = n;
 			  (*_weight)[n] = (*_weight)[pn];
 			  (*_weight)[pn] = fa.flowValue();
+			}
+		      }
-		      _order->set(_root, 0);
+		      (*_order)[_root] = 0;
 		      int index = 1;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 			std::vector<Node> st;
 			Node nn = n;
 			while ((*_order)[nn] == -1) {
 			  st.push_back(nn);
 			  nn = (*_pred)[nn];
+			}
 			while (!st.empty()) {
-			  _order->set(st.back(), index++);
+			  (*_order)[st.back()] = index++;
 			  st.pop_back();
+			}
+		      }
+		    }
 		  public:
 		    ///\name Execution Control
 		    ///@{
 		    /// \brief Run the Gomory-Hu algorithm.
 		    ///
 		    /// This function runs the Gomory-Hu algorithm.
 		    void run() {
 		      init();
 		      start();
+		    }
 		    /// @}
 		    ///\name Query Functions
 		    ///The results of the algorithm can be obtained using these
 		    ///functions.\n
 		    ///\ref run() "run()" should be called before using them.\n
 		    ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
 		    ///@{
 		    /// \brief Return the predecessor node in the Gomory-Hu tree.
 		    ///
 		    /// This function returns the predecessor node in the Gomory-Hu tree.
 		    /// If the node is
 		    /// the root of the Gomory-Hu tree, then it returns \c INVALID.
 		    Node predNode(const Node& node) {
 		      return (*_pred)[node];
+		    }
 		    /// \brief Return the distance from the root node in the Gomory-Hu tree.
 		    ///
 		    /// This function returns the distance of \c node from the root node
 		    /// in the Gomory-Hu tree.
 		    int rootDist(const Node& node) {
 		      return (*_order)[node];
+		    }
 		    /// \brief Return the weight of the predecessor edge in the
 		    /// Gomory-Hu tree.
 		    ///
 		    /// This function returns the weight of the predecessor edge in the
 		    /// Gomory-Hu tree.  If the node is the root, the result is undefined.
 		    Value predValue(const Node& node) {
 		      return (*_weight)[node];
+		    }
 		    /// \brief Return the minimum cut value between two nodes
 		    ///
 		    /// This function returns the minimum cut value between two nodes. The
 		    /// algorithm finds the nearest common ancestor in the Gomory-Hu
 		    /// tree and calculates the minimum weight edge on the paths to
 		    /// the ancestor.
 		    Value minCutValue(const Node& s, const Node& t) const {
 		      Node sn = s, tn = t;
 		      Value value = std::numeric_limits<Value>::max();
 		      while (sn != tn) {
 			if ((*_order)[sn] < (*_order)[tn]) {
 			  if ((*_weight)[tn] <= value) value = (*_weight)[tn];
 			  tn = (*_pred)[tn];
 			} else {
 			  if ((*_weight)[sn] <= value) value = (*_weight)[sn];
 			  sn = (*_pred)[sn];
+			}
+		      }
 		      return value;
+		    }
 		    /// \brief Return the minimum cut between two nodes
 		    ///
 		    /// This function returns the minimum cut between the nodes \c s and \c t
 		    /// in the \c cutMap parameter by setting the nodes in the component of
 		    /// \c s to \c true and the other nodes to \c false.
 		    ///
 		    /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
 		    template <typename CutMap>
 		    Value minCutMap(const Node& s, ///< The base node.
 		                    const Node& t,
 		                    ///< The node you want to separate from node \c s.
 		                    CutMap& cutMap
 		                    ///< The cut will be returned in this map.
 		                    /// It must be a \c bool (or convertible)
 		                    /// \ref concepts::ReadWriteMap "ReadWriteMap"
 		                    /// on the graph nodes.
 		                    ) const {
 		      Node sn = s, tn = t;
 		      bool s_root=false;
 		      Node rn = INVALID;
 		      Value value = std::numeric_limits<Value>::max();
 		      while (sn != tn) {
 			if ((*_order)[sn] < (*_order)[tn]) {
 			  if ((*_weight)[tn] <= value) {
 			    rn = tn;
 		            s_root = false;
 			    value = (*_weight)[tn];
+			  }
 			  tn = (*_pred)[tn];
 			} else {
 			  if ((*_weight)[sn] <= value) {
 			    rn = sn;
 		            s_root = true;
 			    value = (*_weight)[sn];
+			  }
 			  sn = (*_pred)[sn];
+			}
+		      }
 		      typename Graph::template NodeMap<bool> reached(_graph, false);
-		      reached.set(_root, true);
+		      reached[_root] = true;
 		      cutMap.set(_root, !s_root);
-		      reached.set(rn, true);
+		      reached[rn] = true;
 		      cutMap.set(rn, s_root);
 		      std::vector<Node> st;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 			st.clear();
 		        Node nn = n;
 			while (!reached[nn]) {
 			  st.push_back(nn);
 			  nn = (*_pred)[nn];
+			}
 			while (!st.empty()) {
 			  cutMap.set(st.back(), cutMap[nn]);
 			  st.pop_back();
+			}
+		      }
 		      return value;
+		    }
 		    ///@}
 		    friend class MinCutNodeIt;
 		    /// Iterate on the nodes of a minimum cut
 		    /// This iterator class lists the nodes of a minimum cut found by
 		    /// GomoryHu. Before using it, you must allocate a GomoryHu class,
 		    /// and call its \ref GomoryHu::run() "run()" method.
 		    ///
 		    /// This example counts the nodes in the minimum cut separating \c s from
 		    /// \c t.
 		    /// \code
 		    /// GomoruHu<Graph> gom(g, capacities);
 		    /// gom.run();
 		    /// int cnt=0;
 		    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
 		    /// \endcode
 		    class MinCutNodeIt
+		    {
 		      bool _side;
 		      typename Graph::NodeIt _node_it;
 		      typename Graph::template NodeMap<bool> _cut;
 		    public:
 		      /// Constructor
 		      /// Constructor.
 		      ///
 		      MinCutNodeIt(GomoryHu const &gomory,
 		                   ///< The GomoryHu class. You must call its
 		                   ///  run() method
 		                   ///  before initializing this iterator.
 		                   const Node& s, ///< The base node.
 		                   const Node& t,
 		                   ///< The node you want to separate from node \c s.
 		                   bool side=true
 		                   ///< If it is \c true (default) then the iterator lists
 		                   ///  the nodes of the component containing \c s,
 		                   ///  otherwise it lists the other component.
 		                   /// \note As the minimum cut is not always unique,
 		                   /// \code
 		                   /// MinCutNodeIt(gomory, s, t, true);
 		                   /// \endcode
 		                   /// and
 		                   /// \code
 		                   /// MinCutNodeIt(gomory, t, s, false);
 		                   /// \endcode
 		                   /// does not necessarily give the same set of nodes.
 		                   /// However it is ensured that
 		                   /// \code
 		                   /// MinCutNodeIt(gomory, s, t, true);
 		                   /// \endcode
 		                   /// and
 		                   /// \code
 		                   /// MinCutNodeIt(gomory, s, t, false);
 		                   /// \endcode
 		                   /// together list each node exactly once.
+		                   )
 		        : _side(side), _cut(gomory._graph)
+		      {
 		        gomory.minCutMap(s,t,_cut);
 		        for(_node_it=typename Graph::NodeIt(gomory._graph);
 		            _node_it!=INVALID && _cut[_node_it]!=_side;
 		            ++_node_it) {}
+		      }
 		      /// Conversion to \c Node
 		      /// Conversion to \c Node.
 		      ///
 		      operator typename Graph::Node() const
+		      {
 		        return _node_it;
+		      }
 		      bool operator==(Invalid) { return _node_it==INVALID; }
 		      bool operator!=(Invalid) { return _node_it!=INVALID; }
 		      /// Next node
 		      /// Next node.
 		      ///
 		      MinCutNodeIt &operator++()
+		      {
 		        for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
 		        return *this;
+		      }
 		      /// Postfix incrementation
 		      /// Postfix incrementation.
 		      ///
 		      /// \warning This incrementation
 		      /// returns a \c Node, not a \c MinCutNodeIt, as one may
 		      /// expect.
 		      typename Graph::Node operator++(int)
+		      {
 		        typename Graph::Node n=*this;
 		        ++(*this);
 		        return n;
+		      }
 		    };
 		    friend class MinCutEdgeIt;
 		    /// Iterate on the edges of a minimum cut
 		    /// This iterator class lists the edges of a minimum cut found by
 		    /// GomoryHu. Before using it, you must allocate a GomoryHu class,
 		    /// and call its \ref GomoryHu::run() "run()" method.
 		    ///
 		    /// This example computes the value of the minimum cut separating \c s from
 		    /// \c t.
 		    /// \code
 		    /// GomoruHu<Graph> gom(g, capacities);
 		    /// gom.run();
 		    /// int value=0;
 		    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
 		    ///   value+=capacities[e];
 		    /// \endcode
 		    /// the result will be the same as it is returned by
 		    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
 		    class MinCutEdgeIt
+		    {
 		      bool _side;
 		      const Graph &_graph;
 		      typename Graph::NodeIt _node_it;
 		      typename Graph::OutArcIt _arc_it;
 		      typename Graph::template NodeMap<bool> _cut;
 		      void step()
+		      {
 		        ++_arc_it;
 		        while(_node_it!=INVALID && _arc_it==INVALID)
+		          {
 		            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
 		            if(_node_it!=INVALID)
 		              _arc_it=typename Graph::OutArcIt(_graph,_node_it);
+		          }
+		      }
 		    public:
 		      MinCutEdgeIt(GomoryHu const &gomory,
 		                   ///< The GomoryHu class. You must call its
 		                   ///  run() method
 		                   ///  before initializing this iterator.
 		                   const Node& s,  ///< The base node.
 		                   const Node& t,
 		                   ///< The node you want to separate from node \c s.
 		                   bool side=true
 		                   ///< If it is \c true (default) then the listed arcs
 		                   ///  will be oriented from the
 		                   ///  the nodes of the component containing \c s,
 		                   ///  otherwise they will be oriented in the opposite
 		                   ///  direction.
+		                   )
 		        : _graph(gomory._graph), _cut(_graph)
+		      {
 		        gomory.minCutMap(s,t,_cut);
 		        if(!side)
 		          for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
 		            _cut[n]=!_cut[n];
 		        for(_node_it=typename Graph::NodeIt(_graph);
 		            _node_it!=INVALID && !_cut[_node_it];
 		            ++_node_it) {}
 		        _arc_it = _node_it!=INVALID ?
 		          typename Graph::OutArcIt(_graph,_node_it) : INVALID;
 		        while(_node_it!=INVALID && _arc_it == INVALID)
+		          {
 		            for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
 		            if(_node_it!=INVALID)
 		              _arc_it= typename Graph::OutArcIt(_graph,_node_it);
+		          }
 		        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
+		      }
 		      /// Conversion to \c Arc
 		      /// Conversion to \c Arc.
 		      ///
 		      operator typename Graph::Arc() const
+		      {
 		        return _arc_it;
+		      }
 		      /// Conversion to \c Edge
 		      /// Conversion to \c Edge.
 		      ///
 		      operator typename Graph::Edge() const
+		      {
 		        return _arc_it;
+		      }
 		      bool operator==(Invalid) { return _node_it==INVALID; }
 		      bool operator!=(Invalid) { return _node_it!=INVALID; }
 		      /// Next edge
 		      /// Next edge.
 		      ///
 		      MinCutEdgeIt &operator++()
+		      {
 		        step();
 		        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
 		        return *this;
+		      }
 		      /// Postfix incrementation
 		      /// Postfix incrementation.
 		      ///
 		      /// \warning This incrementation
 		      /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
 		      typename Graph::Arc operator++(int)
+		      {
 		        typename Graph::Arc e=*this;
 		        ++(*this);
 		        return e;
+		      }
 		    };
 		  };
+		}
 		#endif

lemon/hao_orlin.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-2009
 		 * 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_HAO_ORLIN_H
 		#define LEMON_HAO_ORLIN_H
 		#include <vector>
 		#include <list>
 		#include <limits>
 		#include <lemon/maps.h>
 		#include <lemon/core.h>
 		#include <lemon/tolerance.h>
 		/// \file
 		/// \ingroup min_cut
 		/// \brief Implementation of the Hao-Orlin algorithm.
 		///
 		/// Implementation of the Hao-Orlin algorithm class for testing network
 		/// reliability.
 		namespace lemon {
 		  /// \ingroup min_cut
 		  ///
 		  /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs.
 		  ///
 		  /// Hao-Orlin calculates a minimum cut in a directed graph
 		  /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and
 		  /// consists of two phases: in the first phase it determines a
 		  /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
 		  /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal
 		  /// out-degree) and in the second phase it determines a minimum cut
 		  /// with \f$ source \f$ on the sink-side (i.e. a set
 		  /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal
 		  /// out-degree). Obviously, the smaller of these two cuts will be a
 		  /// minimum cut of \f$ D \f$. The algorithm is a modified
 		  /// push-relabel preflow algorithm and our implementation calculates
 		  /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
 		  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
 		  /// purpose of such algorithm is testing network reliability. For an
 		  /// undirected graph you can run just the first phase of the
 		  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki
 		  /// which solves the undirected problem in
 		  /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the
 		  /// NagamochiIbaraki algorithm class.
 		  ///
 		  /// \param GR The digraph class the algorithm runs on.
 		  /// \param CAP An arc map of capacities which can be any numreric type.
 		  /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \param TOL Tolerance class for handling inexact computations. The
 		  /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename CAP, typename TOL>
 		#else
 		  template <typename GR,
 		            typename CAP = typename GR::template ArcMap<int>,
 		            typename TOL = Tolerance<typename CAP::Value> >
 		#endif
 		  class HaoOrlin {
 		  private:
 		    typedef GR Digraph;
 		    typedef CAP CapacityMap;
 		    typedef TOL Tolerance;
 		    typedef typename CapacityMap::Value Value;
 		    TEMPLATE_GRAPH_TYPEDEFS(Digraph);
 		    const Digraph& _graph;
 		    const CapacityMap* _capacity;
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		    FlowMap* _flow;
 		    Node _source;
 		    int _node_num;
 		    // Bucketing structure
 		    std::vector<Node> _first, _last;
 		    typename Digraph::template NodeMap<Node>* _next;
 		    typename Digraph::template NodeMap<Node>* _prev;
 		    typename Digraph::template NodeMap<bool>* _active;
 		    typename Digraph::template NodeMap<int>* _bucket;
 		    std::vector<bool> _dormant;
 		    std::list<std::list<int> > _sets;
 		    std::list<int>::iterator _highest;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
 		    ExcessMap* _excess;
 		    typedef typename Digraph::template NodeMap<bool> SourceSetMap;
 		    SourceSetMap* _source_set;
 		    Value _min_cut;
 		    typedef typename Digraph::template NodeMap<bool> MinCutMap;
 		    MinCutMap* _min_cut_map;
 		    Tolerance _tolerance;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the algorithm class.
 		    HaoOrlin(const Digraph& graph, const CapacityMap& capacity,
 		             const Tolerance& tolerance = Tolerance()) :
 		      _graph(graph), _capacity(&capacity), _flow(0), _source(),
 		      _node_num(), _first(), _last(), _next(0), _prev(0),
 		      _active(0), _bucket(0), _dormant(), _sets(), _highest(),
 		      _excess(0), _source_set(0), _min_cut(), _min_cut_map(0),
 		      _tolerance(tolerance) {}
 		    ~HaoOrlin() {
 		      if (_min_cut_map) {
 		        delete _min_cut_map;
+		      }
 		      if (_source_set) {
 		        delete _source_set;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
 		      if (_next) {
 		        delete _next;
+		      }
 		      if (_prev) {
 		        delete _prev;
+		      }
 		      if (_active) {
 		        delete _active;
+		      }
 		      if (_bucket) {
 		        delete _bucket;
+		      }
 		      if (_flow) {
 		        delete _flow;
+		      }
+		    }
 		  private:
 		    void activate(const Node& i) {
-		      _active->set(i, true);
+		      (*_active)[i] = true;
 		      int bucket = (*_bucket)[i];
 		      if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return;
 		      //unlace
-		      _next->set((*_prev)[i], (*_next)[i]);
+		      (*_next)[(*_prev)[i]] = (*_next)[i];
 		      if ((*_next)[i] != INVALID) {
-		        _prev->set((*_next)[i], (*_prev)[i]);
+		        (*_prev)[(*_next)[i]] = (*_prev)[i];
 		      } else {
 		        _last[bucket] = (*_prev)[i];
+		      }
 		      //lace
 		      _next->set(i, _first[bucket]);
 		      _prev->set(_first[bucket], i);
-		      _prev->set(i, INVALID);
+		      (*_next)[i] = _first[bucket];
 		      (*_prev)[_first[bucket]] = i;
 		      (*_prev)[i] = INVALID;
 		      _first[bucket] = i;
+		    }
 		    void deactivate(const Node& i) {
-		      _active->set(i, false);
+		      (*_active)[i] = false;
 		      int bucket = (*_bucket)[i];
 		      if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return;
 		      //unlace
-		      _prev->set((*_next)[i], (*_prev)[i]);
+		      (*_prev)[(*_next)[i]] = (*_prev)[i];
 		      if ((*_prev)[i] != INVALID) {
-		        _next->set((*_prev)[i], (*_next)[i]);
+		        (*_next)[(*_prev)[i]] = (*_next)[i];
 		      } else {
 		        _first[bucket] = (*_next)[i];
+		      }
 		      //lace
 		      _prev->set(i, _last[bucket]);
 		      _next->set(_last[bucket], i);
-		      _next->set(i, INVALID);
+		      (*_prev)[i] = _last[bucket];
 		      (*_next)[_last[bucket]] = i;
 		      (*_next)[i] = INVALID;
 		      _last[bucket] = i;
+		    }
 		    void addItem(const Node& i, int bucket) {
 		      (*_bucket)[i] = bucket;
 		      if (_last[bucket] != INVALID) {
 		        _prev->set(i, _last[bucket]);
 		        _next->set(_last[bucket], i);
-		        _next->set(i, INVALID);
+		        (*_prev)[i] = _last[bucket];
 		        (*_next)[_last[bucket]] = i;
 		        (*_next)[i] = INVALID;
 		        _last[bucket] = i;
 		      } else {
-		        _prev->set(i, INVALID);
+		        (*_prev)[i] = INVALID;
 		        _first[bucket] = i;
-		        _next->set(i, INVALID);
+		        (*_next)[i] = INVALID;
 		        _last[bucket] = i;
+		      }
+		    }
 		    void findMinCutOut() {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
-		        _excess->set(n, 0);
+		        (*_excess)[n] = 0;
+		      }
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
-		        _flow->set(a, 0);
+		        (*_flow)[a] = 0;
+		      }
 		      int bucket_num = 0;
 		      std::vector<Node> queue(_node_num);
 		      int qfirst = 0, qlast = 0, qsep = 0;
+		      {
 		        typename Digraph::template NodeMap<bool> reached(_graph, false);
-		        reached.set(_source, true);
+		        reached[_source] = true;
 		        bool first_set = true;
 		        for (NodeIt t(_graph); t != INVALID; ++t) {
 		          if (reached[t]) continue;
 		          _sets.push_front(std::list<int>());
 		          queue[qlast++] = t;
-		          reached.set(t, true);
+		          reached[t] = true;
 		          while (qfirst != qlast) {
 		            if (qsep == qfirst) {
 		              ++bucket_num;
 		              _sets.front().push_front(bucket_num);
 		              _dormant[bucket_num] = !first_set;
 		              _first[bucket_num] = _last[bucket_num] = INVALID;
 		              qsep = qlast;
+		            }
 		            Node n = queue[qfirst++];
 		            addItem(n, bucket_num);
 		            for (InArcIt a(_graph, n); a != INVALID; ++a) {
 		              Node u = _graph.source(a);
 		              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
-		                reached.set(u, true);
+		                reached[u] = true;
 		                queue[qlast++] = u;
+		              }
+		            }
+		          }
 		          first_set = false;
+		        }
 		        ++bucket_num;
-		        _bucket->set(_source, 0);
+		        (*_bucket)[_source] = 0;
 		        _dormant[0] = true;
+		      }
-		      _source_set->set(_source, true);
+		      (*_source_set)[_source] = true;
 		      Node target = _last[_sets.back().back()];
+		      {
 		        for (OutArcIt a(_graph, _source); a != INVALID; ++a) {
 		          if (_tolerance.positive((*_capacity)[a])) {
 		            Node u = _graph.target(a);
 		            _flow->set(a, (*_capacity)[a]);
 		            _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
 		            (*_flow)[a] = (*_capacity)[a];
 		            (*_excess)[u] += (*_capacity)[a];
 		            if (!(*_active)[u] && u != _source) {
 		              activate(u);
+		            }
+		          }
+		        }
 		        if ((*_active)[target]) {
 		          deactivate(target);
+		        }
 		        _highest = _sets.back().begin();
 		        while (_highest != _sets.back().end() &&
 		               !(*_active)[_first[*_highest]]) {
 		          ++_highest;
+		        }
+		      }
 		      while (true) {
 		        while (_highest != _sets.back().end()) {
 		          Node n = _first[*_highest];
 		          Value excess = (*_excess)[n];
 		          int next_bucket = _node_num;
 		          int under_bucket;
 		          if (++std::list<int>::iterator(_highest) == _sets.back().end()) {
 		            under_bucket = -1;
 		          } else {
 		            under_bucket = *(++std::list<int>::iterator(_highest));
+		          }
 		          for (OutArcIt a(_graph, n); a != INVALID; ++a) {
 		            Node v = _graph.target(a);
 		            if (_dormant[(*_bucket)[v]]) continue;
 		            Value rem = (*_capacity)[a] - (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            if ((*_bucket)[v] == under_bucket) {
 		              if (!(*_active)[v] && v != target) {
 		                activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(a, (*_flow)[a] + excess);
 		                _excess->set(v, (*_excess)[v] + excess);
 		                (*_flow)[a] += excess;
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push;
 		              } else {
 		                excess -= rem;
 		                _excess->set(v, (*_excess)[v] + rem);
 		                _flow->set(a, (*_capacity)[a]);
 		                (*_excess)[v] += rem;
 		                (*_flow)[a] = (*_capacity)[a];
+		              }
 		            } else if (next_bucket > (*_bucket)[v]) {
 		              next_bucket = (*_bucket)[v];
+		            }
+		          }
 		          for (InArcIt a(_graph, n); a != INVALID; ++a) {
 		            Node v = _graph.source(a);
 		            if (_dormant[(*_bucket)[v]]) continue;
 		            Value rem = (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            if ((*_bucket)[v] == under_bucket) {
 		              if (!(*_active)[v] && v != target) {
 		                activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(a, (*_flow)[a] - excess);
 		                _excess->set(v, (*_excess)[v] + excess);
 		                (*_flow)[a] -= excess;
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push;
 		              } else {
 		                excess -= rem;
 		                _excess->set(v, (*_excess)[v] + rem);
 		                _flow->set(a, 0);
 		                (*_excess)[v] += rem;
 		                (*_flow)[a] = 0;
+		              }
 		            } else if (next_bucket > (*_bucket)[v]) {
 		              next_bucket = (*_bucket)[v];
+		            }
+		          }
 		        no_more_push:
-		          _excess->set(n, excess);
+		          (*_excess)[n] = excess;
 		          if (excess != 0) {
 		            if ((*_next)[n] == INVALID) {
 		              typename std::list<std::list<int> >::iterator new_set =
 		                _sets.insert(--_sets.end(), std::list<int>());
 		              new_set->splice(new_set->end(), _sets.back(),
 		                              _sets.back().begin(), ++_highest);
 		              for (std::list<int>::iterator it = new_set->begin();
 		                   it != new_set->end(); ++it) {
 		                _dormant[*it] = true;
+		              }
 		              while (_highest != _sets.back().end() &&
 		                     !(*_active)[_first[*_highest]]) {
 		                ++_highest;
+		              }
 		            } else if (next_bucket == _node_num) {
 		              _first[(*_bucket)[n]] = (*_next)[n];
-		              _prev->set((*_next)[n], INVALID);
+		              (*_prev)[(*_next)[n]] = INVALID;
 		              std::list<std::list<int> >::iterator new_set =
 		                _sets.insert(--_sets.end(), std::list<int>());
 		              new_set->push_front(bucket_num);
-		              _bucket->set(n, bucket_num);
+		              (*_bucket)[n] = bucket_num;
 		              _first[bucket_num] = _last[bucket_num] = n;
 		              _next->set(n, INVALID);
 		              _prev->set(n, INVALID);
 		              (*_next)[n] = INVALID;
 		              (*_prev)[n] = INVALID;
 		              _dormant[bucket_num] = true;
 		              ++bucket_num;
 		              while (_highest != _sets.back().end() &&
 		                     !(*_active)[_first[*_highest]]) {
 		                ++_highest;
+		              }
 		            } else {
 		              _first[*_highest] = (*_next)[n];
-		              _prev->set((*_next)[n], INVALID);
+		              (*_prev)[(*_next)[n]] = INVALID;
 		              while (next_bucket != *_highest) {
 		                --_highest;
+		              }
 		              if (_highest == _sets.back().begin()) {
 		                _sets.back().push_front(bucket_num);
 		                _dormant[bucket_num] = false;
 		                _first[bucket_num] = _last[bucket_num] = INVALID;
 		                ++bucket_num;
+		              }
 		              --_highest;
 		              _bucket->set(n, *_highest);
 		              _next->set(n, _first[*_highest]);
 		              (*_bucket)[n] = *_highest;
 		              (*_next)[n] = _first[*_highest];
 		              if (_first[*_highest] != INVALID) {
-		                _prev->set(_first[*_highest], n);
+		                (*_prev)[_first[*_highest]] = n;
 		              } else {
 		                _last[*_highest] = n;
+		              }
 		              _first[*_highest] = n;
+		            }
 		          } else {
 		            deactivate(n);
 		            if (!(*_active)[_first[*_highest]]) {
 		              ++_highest;
 		              if (_highest != _sets.back().end() &&
 		                  !(*_active)[_first[*_highest]]) {
 		                _highest = _sets.back().end();
+		              }
+		            }
+		          }
+		        }
 		        if ((*_excess)[target] < _min_cut) {
 		          _min_cut = (*_excess)[target];
 		          for (NodeIt i(_graph); i != INVALID; ++i) {
-		            _min_cut_map->set(i, true);
+		            (*_min_cut_map)[i] = true;
+		          }
 		          for (std::list<int>::iterator it = _sets.back().begin();
 		               it != _sets.back().end(); ++it) {
 		            Node n = _first[*it];
 		            while (n != INVALID) {
-		              _min_cut_map->set(n, false);
+		              (*_min_cut_map)[n] = false;
 		              n = (*_next)[n];
+		            }
+		          }
+		        }
+		        {
 		          Node new_target;
 		          if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
 		            if ((*_next)[target] == INVALID) {
 		              _last[(*_bucket)[target]] = (*_prev)[target];
 		              new_target = (*_prev)[target];
 		            } else {
-		              _prev->set((*_next)[target], (*_prev)[target]);
+		              (*_prev)[(*_next)[target]] = (*_prev)[target];
 		              new_target = (*_next)[target];
+		            }
 		            if ((*_prev)[target] == INVALID) {
 		              _first[(*_bucket)[target]] = (*_next)[target];
 		            } else {
-		              _next->set((*_prev)[target], (*_next)[target]);
+		              (*_next)[(*_prev)[target]] = (*_next)[target];
+		            }
 		          } else {
 		            _sets.back().pop_back();
 		            if (_sets.back().empty()) {
 		              _sets.pop_back();
 		              if (_sets.empty())
 		                break;
 		              for (std::list<int>::iterator it = _sets.back().begin();
 		                   it != _sets.back().end(); ++it) {
 		                _dormant[*it] = false;
+		              }
+		            }
 		            new_target = _last[_sets.back().back()];
+		          }
-		          _bucket->set(target, 0);
+		          (*_bucket)[target] = 0;
-		          _source_set->set(target, true);
+		          (*_source_set)[target] = true;
 		          for (OutArcIt a(_graph, target); a != INVALID; ++a) {
 		            Value rem = (*_capacity)[a] - (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.target(a);
 		            if (!(*_active)[v] && !(*_source_set)[v]) {
 		              activate(v);
+		            }
 		            _excess->set(v, (*_excess)[v] + rem);
 		            _flow->set(a, (*_capacity)[a]);
 		            (*_excess)[v] += rem;
 		            (*_flow)[a] = (*_capacity)[a];
+		          }
 		          for (InArcIt a(_graph, target); a != INVALID; ++a) {
 		            Value rem = (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.source(a);
 		            if (!(*_active)[v] && !(*_source_set)[v]) {
 		              activate(v);
+		            }
 		            _excess->set(v, (*_excess)[v] + rem);
 		            _flow->set(a, 0);
 		            (*_excess)[v] += rem;
 		            (*_flow)[a] = 0;
+		          }
 		          target = new_target;
 		          if ((*_active)[target]) {
 		            deactivate(target);
+		          }
 		          _highest = _sets.back().begin();
 		          while (_highest != _sets.back().end() &&
 		                 !(*_active)[_first[*_highest]]) {
 		            ++_highest;
+		          }
+		        }
+		      }
+		    }
 		    void findMinCutIn() {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
-		        _excess->set(n, 0);
+		        (*_excess)[n] = 0;
+		      }
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
-		        _flow->set(a, 0);
+		        (*_flow)[a] = 0;
+		      }
 		      int bucket_num = 0;
 		      std::vector<Node> queue(_node_num);
 		      int qfirst = 0, qlast = 0, qsep = 0;
+		      {
 		        typename Digraph::template NodeMap<bool> reached(_graph, false);
-		        reached.set(_source, true);
+		        reached[_source] = true;
 		        bool first_set = true;
 		        for (NodeIt t(_graph); t != INVALID; ++t) {
 		          if (reached[t]) continue;
 		          _sets.push_front(std::list<int>());
 		          queue[qlast++] = t;
-		          reached.set(t, true);
+		          reached[t] = true;
 		          while (qfirst != qlast) {
 		            if (qsep == qfirst) {
 		              ++bucket_num;
 		              _sets.front().push_front(bucket_num);
 		              _dormant[bucket_num] = !first_set;
 		              _first[bucket_num] = _last[bucket_num] = INVALID;
 		              qsep = qlast;
+		            }
 		            Node n = queue[qfirst++];
 		            addItem(n, bucket_num);
 		            for (OutArcIt a(_graph, n); a != INVALID; ++a) {
 		              Node u = _graph.target(a);
 		              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
-		                reached.set(u, true);
+		                reached[u] = true;
 		                queue[qlast++] = u;
+		              }
+		            }
+		          }
 		          first_set = false;
+		        }
 		        ++bucket_num;
-		        _bucket->set(_source, 0);
+		        (*_bucket)[_source] = 0;
 		        _dormant[0] = true;
+		      }
-		      _source_set->set(_source, true);
+		      (*_source_set)[_source] = true;
 		      Node target = _last[_sets.back().back()];
+		      {
 		        for (InArcIt a(_graph, _source); a != INVALID; ++a) {
 		          if (_tolerance.positive((*_capacity)[a])) {
 		            Node u = _graph.source(a);
 		            _flow->set(a, (*_capacity)[a]);
 		            _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
 		            (*_flow)[a] = (*_capacity)[a];
 		            (*_excess)[u] += (*_capacity)[a];
 		            if (!(*_active)[u] && u != _source) {
 		              activate(u);
+		            }
+		          }
+		        }
 		        if ((*_active)[target]) {
 		          deactivate(target);
+		        }
 		        _highest = _sets.back().begin();
 		        while (_highest != _sets.back().end() &&
 		               !(*_active)[_first[*_highest]]) {
 		          ++_highest;
+		        }
+		      }
 		      while (true) {
 		        while (_highest != _sets.back().end()) {
 		          Node n = _first[*_highest];
 		          Value excess = (*_excess)[n];
 		          int next_bucket = _node_num;
 		          int under_bucket;
 		          if (++std::list<int>::iterator(_highest) == _sets.back().end()) {
 		            under_bucket = -1;
 		          } else {
 		            under_bucket = *(++std::list<int>::iterator(_highest));
+		          }
 		          for (InArcIt a(_graph, n); a != INVALID; ++a) {
 		            Node v = _graph.source(a);
 		            if (_dormant[(*_bucket)[v]]) continue;
 		            Value rem = (*_capacity)[a] - (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            if ((*_bucket)[v] == under_bucket) {
 		              if (!(*_active)[v] && v != target) {
 		                activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(a, (*_flow)[a] + excess);
 		                _excess->set(v, (*_excess)[v] + excess);
 		                (*_flow)[a] += excess;
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push;
 		              } else {
 		                excess -= rem;
 		                _excess->set(v, (*_excess)[v] + rem);
 		                _flow->set(a, (*_capacity)[a]);
 		                (*_excess)[v] += rem;
 		                (*_flow)[a] = (*_capacity)[a];
+		              }
 		            } else if (next_bucket > (*_bucket)[v]) {
 		              next_bucket = (*_bucket)[v];
+		            }
+		          }
 		          for (OutArcIt a(_graph, n); a != INVALID; ++a) {
 		            Node v = _graph.target(a);
 		            if (_dormant[(*_bucket)[v]]) continue;
 		            Value rem = (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            if ((*_bucket)[v] == under_bucket) {
 		              if (!(*_active)[v] && v != target) {
 		                activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(a, (*_flow)[a] - excess);
 		                _excess->set(v, (*_excess)[v] + excess);
 		                (*_flow)[a] -= excess;
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push;
 		              } else {
 		                excess -= rem;
 		                _excess->set(v, (*_excess)[v] + rem);
 		                _flow->set(a, 0);
 		                (*_excess)[v] += rem;
 		                (*_flow)[a] = 0;
+		              }
 		            } else if (next_bucket > (*_bucket)[v]) {
 		              next_bucket = (*_bucket)[v];
+		            }
+		          }
 		        no_more_push:
-		          _excess->set(n, excess);
+		          (*_excess)[n] = excess;
 		          if (excess != 0) {
 		            if ((*_next)[n] == INVALID) {
 		              typename std::list<std::list<int> >::iterator new_set =
 		                _sets.insert(--_sets.end(), std::list<int>());
 		              new_set->splice(new_set->end(), _sets.back(),
 		                              _sets.back().begin(), ++_highest);
 		              for (std::list<int>::iterator it = new_set->begin();
 		                   it != new_set->end(); ++it) {
 		                _dormant[*it] = true;
+		              }
 		              while (_highest != _sets.back().end() &&
 		                     !(*_active)[_first[*_highest]]) {
 		                ++_highest;
+		              }
 		            } else if (next_bucket == _node_num) {
 		              _first[(*_bucket)[n]] = (*_next)[n];
-		              _prev->set((*_next)[n], INVALID);
+		              (*_prev)[(*_next)[n]] = INVALID;
 		              std::list<std::list<int> >::iterator new_set =
 		                _sets.insert(--_sets.end(), std::list<int>());
 		              new_set->push_front(bucket_num);
-		              _bucket->set(n, bucket_num);
+		              (*_bucket)[n] = bucket_num;
 		              _first[bucket_num] = _last[bucket_num] = n;
 		              _next->set(n, INVALID);
 		              _prev->set(n, INVALID);
 		              (*_next)[n] = INVALID;
 		              (*_prev)[n] = INVALID;
 		              _dormant[bucket_num] = true;
 		              ++bucket_num;
 		              while (_highest != _sets.back().end() &&
 		                     !(*_active)[_first[*_highest]]) {
 		                ++_highest;
+		              }
 		            } else {
 		              _first[*_highest] = (*_next)[n];
-		              _prev->set((*_next)[n], INVALID);
+		              (*_prev)[(*_next)[n]] = INVALID;
 		              while (next_bucket != *_highest) {
 		                --_highest;
+		              }
 		              if (_highest == _sets.back().begin()) {
 		                _sets.back().push_front(bucket_num);
 		                _dormant[bucket_num] = false;
 		                _first[bucket_num] = _last[bucket_num] = INVALID;
 		                ++bucket_num;
+		              }
 		              --_highest;
 		              _bucket->set(n, *_highest);
 		              _next->set(n, _first[*_highest]);
 		              (*_bucket)[n] = *_highest;
 		              (*_next)[n] = _first[*_highest];
 		              if (_first[*_highest] != INVALID) {
-		                _prev->set(_first[*_highest], n);
+		                (*_prev)[_first[*_highest]] = n;
 		              } else {
 		                _last[*_highest] = n;
+		              }
 		              _first[*_highest] = n;
+		            }
 		          } else {
 		            deactivate(n);
 		            if (!(*_active)[_first[*_highest]]) {
 		              ++_highest;
 		              if (_highest != _sets.back().end() &&
 		                  !(*_active)[_first[*_highest]]) {
 		                _highest = _sets.back().end();
+		              }
+		            }
+		          }
+		        }
 		        if ((*_excess)[target] < _min_cut) {
 		          _min_cut = (*_excess)[target];
 		          for (NodeIt i(_graph); i != INVALID; ++i) {
-		            _min_cut_map->set(i, false);
+		            (*_min_cut_map)[i] = false;
+		          }
 		          for (std::list<int>::iterator it = _sets.back().begin();
 		               it != _sets.back().end(); ++it) {
 		            Node n = _first[*it];
 		            while (n != INVALID) {
-		              _min_cut_map->set(n, true);
+		              (*_min_cut_map)[n] = true;
 		              n = (*_next)[n];
+		            }
+		          }
+		        }
+		        {
 		          Node new_target;
 		          if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) {
 		            if ((*_next)[target] == INVALID) {
 		              _last[(*_bucket)[target]] = (*_prev)[target];
 		              new_target = (*_prev)[target];
 		            } else {
-		              _prev->set((*_next)[target], (*_prev)[target]);
+		              (*_prev)[(*_next)[target]] = (*_prev)[target];
 		              new_target = (*_next)[target];
+		            }
 		            if ((*_prev)[target] == INVALID) {
 		              _first[(*_bucket)[target]] = (*_next)[target];
 		            } else {
-		              _next->set((*_prev)[target], (*_next)[target]);
+		              (*_next)[(*_prev)[target]] = (*_next)[target];
+		            }
 		          } else {
 		            _sets.back().pop_back();
 		            if (_sets.back().empty()) {
 		              _sets.pop_back();
 		              if (_sets.empty())
 		                break;
 		              for (std::list<int>::iterator it = _sets.back().begin();
 		                   it != _sets.back().end(); ++it) {
 		                _dormant[*it] = false;
+		              }
+		            }
 		            new_target = _last[_sets.back().back()];
+		          }
-		          _bucket->set(target, 0);
+		          (*_bucket)[target] = 0;
-		          _source_set->set(target, true);
+		          (*_source_set)[target] = true;
 		          for (InArcIt a(_graph, target); a != INVALID; ++a) {
 		            Value rem = (*_capacity)[a] - (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.source(a);
 		            if (!(*_active)[v] && !(*_source_set)[v]) {
 		              activate(v);
+		            }
 		            _excess->set(v, (*_excess)[v] + rem);
 		            _flow->set(a, (*_capacity)[a]);
 		            (*_excess)[v] += rem;
 		            (*_flow)[a] = (*_capacity)[a];
+		          }
 		          for (OutArcIt a(_graph, target); a != INVALID; ++a) {
 		            Value rem = (*_flow)[a];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.target(a);
 		            if (!(*_active)[v] && !(*_source_set)[v]) {
 		              activate(v);
+		            }
 		            _excess->set(v, (*_excess)[v] + rem);
 		            _flow->set(a, 0);
 		            (*_excess)[v] += rem;
 		            (*_flow)[a] = 0;
+		          }
 		          target = new_target;
 		          if ((*_active)[target]) {
 		            deactivate(target);
+		          }
 		          _highest = _sets.back().begin();
 		          while (_highest != _sets.back().end() &&
 		                 !(*_active)[_first[*_highest]]) {
 		            ++_highest;
+		          }
+		        }
+		      }
+		    }
 		  public:
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to use
 		    /// one of the member functions called \ref run().
 		    /// \n
 		    /// If you need more control on the execution,
 		    /// first you must call \ref init(), then the \ref calculateIn() or
 		    /// \ref calculateOut() functions.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures. It creates
 		    /// the maps, residual graph adaptors and some bucket structures
 		    /// for the algorithm.
 		    void init() {
 		      init(NodeIt(_graph));
+		    }
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures. It creates
 		    /// the maps, residual graph adaptor and some bucket structures
 		    /// for the algorithm. Node \c source  is used as the push-relabel
 		    /// algorithm's source.
 		    void init(const Node& source) {
 		      _source = source;
 		      _node_num = countNodes(_graph);
 		      _first.resize(_node_num);
 		      _last.resize(_node_num);
 		      _dormant.resize(_node_num);
 		      if (!_flow) {
 		        _flow = new FlowMap(_graph);
+		      }
 		      if (!_next) {
 		        _next = new typename Digraph::template NodeMap<Node>(_graph);
+		      }
 		      if (!_prev) {
 		        _prev = new typename Digraph::template NodeMap<Node>(_graph);
+		      }
 		      if (!_active) {
 		        _active = new typename Digraph::template NodeMap<bool>(_graph);
+		      }
 		      if (!_bucket) {
 		        _bucket = new typename Digraph::template NodeMap<int>(_graph);
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_graph);
+		      }
 		      if (!_source_set) {
 		        _source_set = new SourceSetMap(_graph);
+		      }
 		      if (!_min_cut_map) {
 		        _min_cut_map = new MinCutMap(_graph);
+		      }
 		      _min_cut = std::numeric_limits<Value>::max();
+		    }
 		    /// \brief Calculates a minimum cut with \f$ source \f$ on the
 		    /// source-side.
 		    ///
 		    /// Calculates a minimum cut with \f$ source \f$ on the
 		    /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
 		    /// \f$ source \in X \f$ and minimal out-degree).
 		    void calculateOut() {
 		      findMinCutOut();
+		    }
 		    /// \brief Calculates a minimum cut with \f$ source \f$ on the
 		    /// target-side.
 		    ///
 		    /// Calculates a minimum cut with \f$ source \f$ on the
 		    /// target-side (i.e. a set \f$ X\subsetneq V \f$ with
 		    /// \f$ source \in X \f$ and minimal out-degree).
 		    void calculateIn() {
 		      findMinCutIn();
+		    }
 		    /// \brief Runs the algorithm.
 		    ///
 		    /// Runs the algorithm. It finds nodes \c source and \c target
 		    /// arbitrarily and then calls \ref init(), \ref calculateOut()
 		    /// and \ref calculateIn().
 		    void run() {
 		      init();
 		      calculateOut();
 		      calculateIn();
+		    }
 		    /// \brief Runs the algorithm.
 		    ///
 		    /// Runs the algorithm. It uses the given \c source node, finds a
 		    /// proper \c target and then calls the \ref init(), \ref
 		    /// calculateOut() and \ref calculateIn().
 		    void run(const Node& s) {
 		      init(s);
 		      calculateOut();
 		      calculateIn();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The result of the %HaoOrlin algorithm
 		    /// can be obtained using these functions.
 		    /// \n
 		    /// Before using these functions, either \ref run(), \ref
 		    /// calculateOut() or \ref calculateIn() must be called.
 		    /// @{
 		    /// \brief Returns the value of the minimum value cut.
 		    ///
 		    /// Returns the value of the minimum value cut.
 		    Value minCutValue() const {
 		      return _min_cut;
+		    }
 		    /// \brief Returns a minimum cut.
 		    ///
 		    /// Sets \c nodeMap to the characteristic vector of a minimum
 		    /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$
 		    /// with minimal out-degree (i.e. \c nodeMap will be true exactly
 		    /// for the nodes of \f$ X \f$).  \pre nodeMap should be a
 		    /// bool-valued node-map.
 		    template <typename NodeMap>
 		    Value minCutMap(NodeMap& nodeMap) const {
 		      for (NodeIt it(_graph); it != INVALID; ++it) {
 		        nodeMap.set(it, (*_min_cut_map)[it]);
+		      }
 		      return _min_cut;
+		    }
 		    /// @}
 		  }; //class HaoOrlin
 		} //namespace lemon
 		#endif //LEMON_HAO_ORLIN_H

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

0 comments (0 inline)

RhodeCode

Login to your account

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

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