LEMON/LEMON-main Changeset - r610:dacc2cee2b4c

Repositories » LEMON » LEMON-main

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

Changeset - r610:dacc2cee2b4c

« 609:e6927f

611:85cb3a »

r610:dacc2cee2b4c

Fri, 17 Apr 2009 18:14:35

[Not Reviewed]

0 comments (0 inline)

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

Slightly modify the interface of Circulation and Preflow (#266) in order to synchronize them to the interface of NetworkSimplex. Circulation: - The "delta" notation is replaced by "supply". - lowerCapMap(), upperCapMap() are renamed to lowerMap() and upperMap(). - Value is renamed to Flow. Preflow: - Value is renamed to Flow.

0 3 0

default

3 files changed with 150 insertions and 133 deletions:

lemon/circulation.h

122

105

lemon/preflow.h

test/circulation_test.cc

↑ 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.
 		  ///
 		  /// \tparam GR Type of the digraph the algorithm runs on.
 		  /// \tparam LM The type of the lower bound map.
 		  /// \tparam UM The type of the upper bound (capacity) map.
 		  /// \tparam SM The type of the supply map.
 		  template <typename GR, typename LM,
-		            typename UM, typename DM>
+		            typename UM, typename SM>
 		  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.
 		    /// \brief The type of the lower bound map.
 		    ///
 		    /// The type of the map that stores the circulation lower bound.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-		    typedef LM LCapMap;
+		    /// The type of the map that stores the lower bounds on the arcs.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LM LowerMap;
 		    /// \brief The type of the map that stores the circulation upper
 		    /// bound.
 		    /// \brief The type of the upper bound (capacity) map.
 		    ///
 		    /// The type of the map that stores the circulation upper bound.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-		    typedef UM UCapMap;
+		    /// The type of the map that stores the upper bounds (capacities)
 		    /// on the arcs.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef UM UpperMap;
 		    /// \brief The type of the map that stores the lower bound for
 		    /// the supply of the nodes.
 		    /// \brief The type of supply map.
 		    ///
 		    /// 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;
 		    /// The type of the map that stores the signed supply values of the
 		    /// nodes.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef SM SupplyMap;
 		    /// \brief The type of the flow values.
-		    typedef typename DeltaMap::Value Value;
+		    typedef typename SupplyMap::Value Flow;
 		    /// \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;
 		    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
 		    /// concept.
 		    typedef typename Digraph::template ArcMap<Flow> FlowMap;
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
-		    /// \param digraph The digraph, to which we would like to define
+		    /// \param digraph The digraph for 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
+		    /// \param digraph The digraph for 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;
+		    typedef lemon::Tolerance<Flow> 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.
 		     This class implements a push-relabel algorithm for the \e network
 		     \e 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.
 		     are given for the flow values on the arcs and lower bounds are
 		     given for the difference between the outgoing and incoming flow
 		     at 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.
 		     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
 		     upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
 		     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
 		     denotes the signed supply values of the nodes.
 		     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		     \f$-sup(u)\f$ demand.
 		     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
 		     solution of the following problem.
 		     \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.
 		     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
 		     \geq sup(u) \quad \forall u\in V, \f]
 		     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
 		     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		     zero or negative in order to have a feasible solution (since the sum
 		     of the expressions on the left-hand side of the inequalities is zero).
 		     It means that the total demand must be greater or equal to the total
 		     supply and all the supplies have to be carried out from the supply nodes,
 		     but there could be demands that are not satisfied.
 		     If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		     constraints have to be satisfied with equality, i.e. all demands
 		     have to be satisfied and all supplies have to be used.
 		     If you need the opposite inequalities in the supply/demand constraints
 		     (i.e. the total demand is less than the total supply and all the demands
 		     have to be satisfied while there could be supplies that are not used),
 		     then you could easily transform the problem to the above form by reversing
 		     the direction of the arcs and taking the negative of the supply values
 		     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
 		     Note that this algorithm also provides a feasible solution for the
 		     \ref min_cost_flow "minimum cost flow problem".
 		     \tparam GR The type of the digraph the algorithm runs on.
-		     \tparam LM The type of the lower bound capacity map. The default
 		     \tparam LM The type of the lower bound 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
 		     \tparam UM The type of the upper bound (capacity) map.
 		     The default map type is \c LM.
 		     \tparam SM The type of the supply map. 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 SM,
 		          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> >
 		          typename SM = typename GR::template NodeMap<typename UM::Value>,
 		          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
 		#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;
+		    typedef typename Traits::Flow Flow;
 		    /// 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 lower bound map.
 		    typedef typename Traits::LowerMap LowerMap;
 		    ///The type of the upper bound (capacity) map.
 		    typedef typename Traits::UpperMap UpperMap;
 		    ///The type of the supply map.
 		    typedef typename Traits::SupplyMap SupplyMap;
 		    ///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;
+		    const LowerMap *_lo;
 		    const UpperMap *_up;
 		    const SupplyMap *_supply;
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
-		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
+		    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tol;
 		    int _el;
 		  public:
 		    typedef Circulation Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename _FlowMap>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef _FlowMap 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 _FlowMap>
 		    struct SetFlowMap
-		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                           SetFlowMapTraits<_FlowMap> > {
-		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                          SetFlowMapTraits<_FlowMap> > Create;
 		    };
 		    template <typename _Elevator>
 		    struct SetElevatorTraits : public Traits {
 		      typedef _Elevator 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 _Elevator>
 		    struct SetElevator
-		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                           SetElevatorTraits<_Elevator> > {
-		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                          SetElevatorTraits<_Elevator> > Create;
 		    };
 		    template <typename _Elevator>
 		    struct SetStandardElevatorTraits : public Traits {
 		      typedef _Elevator 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 _Elevator>
 		    struct SetStandardElevator
-		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                       SetStandardElevatorTraits<_Elevator> > {
-		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
+		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                      SetStandardElevatorTraits<_Elevator> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Circulation() {}
 		  public:
-		    /// The constructor of the class.
+		    /// Constructor.
 		    /// 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() {}
+		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    /// \param lower The lower bounds for the flow values on the arcs.
 		    /// \param upper The upper bounds (capacities) for the flow values
 		    /// on the arcs.
 		    /// \param supply The signed supply values of the nodes.
 		    Circulation(const Digraph &graph, const LowerMap &lower,
 		                const UpperMap &upper, const SupplyMap &supply)
 		      : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
 		        _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
 		        _excess(NULL) {}
 		    /// 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 map.
-		    /// Sets the lower bound capacity map.
 		    /// Sets the lower bound map.
 		    /// \return <tt>(*this)</tt>
-		    Circulation& lowerCapMap(const LCapMap& map) {
+		    Circulation& lowerMap(const LowerMap& map) {
 		      _lo = &map;
 		      return *this;
+		    }
 		    /// Sets the upper bound capacity map.
+		    /// Sets the upper bound (capacity) map.
 		    /// Sets the upper bound capacity map.
+		    /// Sets the upper bound (capacity) map.
 		    /// \return <tt>(*this)</tt>
-		    Circulation& upperCapMap(const LCapMap& map) {
+		    Circulation& upperMap(const LowerMap& map) {
 		      _up = &map;
 		      return *this;
+		    }
-		    /// Sets the lower bound map for the supply of the nodes.
+		    /// Sets the supply map.
-		    /// Sets the lower bound map for the supply of the nodes.
+		    /// Sets the supply map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& deltaMap(const DeltaMap& map) {
 		      _delta = &map;
 		    Circulation& supplyMap(const SupplyMap& map) {
 		      _supply = &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->set(n, (*_supply)[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]);
+		      }
 		      // 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->set(n, (*_supply)[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]);
 		        } 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]);
 		        } else {
-		          Value fc = -(*_excess)[_g.target(e)];
+		          Flow 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);
+		        }
+		      }
 		      _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];
+		        Flow exc=(*_excess)[act];
 		        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
 		          Node v = _g.target(e);
-		          Value fc=(*_up)[e]-(*_flow)[e];
+		          Flow 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);
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              _excess->set(act,0);
 		              _level->deactivate(act);
 		              goto next_l;
+		            }
 		            else {
 		              _flow->set(e, (*_up)[e]);
 		              _excess->set(v, (*_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];
+		          Flow 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);
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              _excess->set(act,0);
 		              _level->deactivate(act);
 		              goto next_l;
+		            }
 		            else {
 		              _flow->set(e, (*_lo)[e]);
 		              _excess->set(v, (*_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);
 		        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 {
+		    Flow 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]
 		       \f[ \sum_{uv\in A: u\in B} upper(uv) -
 		           \sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(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 \f$O(n)\f$ 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];
+		          Flow dif=-(*_supply)[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;
+		      Flow delta=0;
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(barrier(n))
-		          delta-=(*_delta)[n];
+		          delta-=(*_supply)[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/preflow.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_PREFLOW_H
 		#define LEMON_PREFLOW_H
 		#include <lemon/tolerance.h>
 		#include <lemon/elevator.h>
 		/// \file
 		/// \ingroup max_flow
 		/// \brief Implementation of the preflow algorithm.
 		namespace lemon {
 		  /// \brief Default traits class of Preflow class.
 		  ///
 		  /// Default traits class of Preflow class.
 		  /// \tparam GR Digraph type.
 		  /// \tparam CM Capacity map type.
 		  template <typename GR, typename CM>
 		  struct PreflowDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc capacities.
 		    ///
 		    /// The type of the map that stores the arc capacities.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef CM CapacityMap;
 		    /// \brief The type of the flow values.
-		    typedef typename CapacityMap::Value Value;
+		    typedef typename CapacityMap::Value Flow;
 		    /// \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;
+		    typedef typename Digraph::template ArcMap<Flow> FlowMap;
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
-		    /// \param digraph The digraph, to which we would like to define
+		    /// \param digraph The digraph for 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 Preflow algorithm.
 		    ///
 		    /// The elevator type used by Preflow algorithm.
 		    ///
 		    /// \sa Elevator
 		    /// \sa LinkedElevator
 		    typedef LinkedElevator<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
+		    /// \param digraph The digraph for 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;
+		    typedef lemon::Tolerance<Flow> Tolerance;
 		  };
 		  /// \ingroup max_flow
 		  ///
 		  /// \brief %Preflow algorithm class.
 		  ///
 		  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
 		  /// \e push-relabel algorithm producing a flow of maximum value in a
 		  /// digraph. The preflow algorithms are the fastest known maximum
 		  /// flow algorithms. The current implementation use a mixture of the
 		  /// \e "highest label" and the \e "bound decrease" heuristics.
 		  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
 		  ///
 		  /// The algorithm consists of two phases. After the first phase
 		  /// the maximum flow value and the minimum cut is obtained. The
 		  /// second phase constructs a feasible maximum flow on each arc.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam CM The type of the capacity map. The default map
 		  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename CM, typename TR>
 		#else
 		  template <typename GR,
 		            typename CM = typename GR::template ArcMap<int>,
 		            typename TR = PreflowDefaultTraits<GR, CM> >
 		#endif
 		  class Preflow {
 		  public:
 		    ///The \ref PreflowDefaultTraits "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 capacity map.
 		    typedef typename Traits::CapacityMap CapacityMap;
 		    ///The type of the flow values.
-		    typedef typename Traits::Value Value;
+		    typedef typename Traits::Flow Flow;
 		    ///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& _graph;
 		    const CapacityMap* _capacity;
 		    int _node_num;
 		    Node _source, _target;
 		    FlowMap* _flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
-		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
+		    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tolerance;
 		    bool _phase;
 		    void createStructures() {
 		      _node_num = countNodes(_graph);
 		      if (!_flow) {
 		        _flow = Traits::createFlowMap(_graph);
 		        _local_flow = true;
+		      }
 		      if (!_level) {
 		        _level = Traits::createElevator(_graph, _node_num);
 		        _local_level = true;
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_graph);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_local_flow) {
 		        delete _flow;
+		      }
 		      if (_local_level) {
 		        delete _level;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
+		    }
 		  public:
 		    typedef Preflow Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename _FlowMap>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef _FlowMap 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 _FlowMap>
 		    struct SetFlowMap
 		      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
 		      typedef Preflow<Digraph, CapacityMap,
 		                      SetFlowMapTraits<_FlowMap> > Create;
 		    };
 		    template <typename _Elevator>
 		    struct SetElevatorTraits : public Traits {
 		      typedef _Elevator 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 _Elevator>
 		    struct SetElevator
 		      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
 		      typedef Preflow<Digraph, CapacityMap,
 		                      SetElevatorTraits<_Elevator> > Create;
 		    };
 		    template <typename _Elevator>
 		    struct SetStandardElevatorTraits : public Traits {
 		      typedef _Elevator Elevator;
 		      static Elevator *createElevator(const Digraph& digraph, int max_level) {
 		        return new Elevator(digraph, max_level);
+		      }
 		    };
@@ -376,589 +376,589 @@
 		    Preflow& tolerance(const Tolerance& tolerance) const {
 		      _tolerance = 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 preflow algorithm is to use
 		    /// \ref run() or \ref runMinCut().\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
 		    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures and sets the initial
 		    /// flow to zero on each arc.
 		    void init() {
 		      createStructures();
 		      _phase = true;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _excess->set(n, 0);
+		      }
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        _flow->set(e, 0);
+		      }
 		      typename Digraph::template NodeMap<bool> reached(_graph, false);
 		      _level->initStart();
 		      _level->initAddItem(_target);
 		      std::vector<Node> queue;
 		      reached.set(_source, true);
 		      queue.push_back(_target);
 		      reached.set(_target, true);
 		      while (!queue.empty()) {
 		        _level->initNewLevel();
 		        std::vector<Node> nqueue;
 		        for (int i = 0; i < int(queue.size()); ++i) {
 		          Node n = queue[i];
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node u = _graph.source(e);
 		            if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
 		              reached.set(u, true);
 		              _level->initAddItem(u);
 		              nqueue.push_back(u);
+		            }
+		          }
+		        }
 		        queue.swap(nqueue);
+		      }
 		      _level->initFinish();
 		      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
 		        if (_tolerance.positive((*_capacity)[e])) {
 		          Node u = _graph.target(e);
 		          if ((*_level)[u] == _level->maxLevel()) continue;
 		          _flow->set(e, (*_capacity)[e]);
 		          _excess->set(u, (*_excess)[u] + (*_capacity)[e]);
 		          if (u != _target && !_level->active(u)) {
 		            _level->activate(u);
+		          }
+		        }
+		      }
+		    }
 		    /// \brief Initializes the internal data structures using the
 		    /// given flow map.
 		    ///
 		    /// Initializes the internal data structures and sets the initial
 		    /// flow to the given \c flowMap. The \c flowMap should contain a
 		    /// flow or at least a preflow, i.e. at each node excluding the
 		    /// source node the incoming flow should greater or equal to the
 		    /// outgoing flow.
 		    /// \return \c false if the given \c flowMap is not a preflow.
 		    template <typename FlowMap>
 		    bool init(const FlowMap& flowMap) {
 		      createStructures();
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        _flow->set(e, flowMap[e]);
+		      }
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
-		        Value excess = 0;
+		        Flow excess = 0;
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		          excess += (*_flow)[e];
+		        }
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          excess -= (*_flow)[e];
+		        }
 		        if (excess < 0 && n != _source) return false;
 		        _excess->set(n, excess);
+		      }
 		      typename Digraph::template NodeMap<bool> reached(_graph, false);
 		      _level->initStart();
 		      _level->initAddItem(_target);
 		      std::vector<Node> queue;
 		      reached.set(_source, true);
 		      queue.push_back(_target);
 		      reached.set(_target, true);
 		      while (!queue.empty()) {
 		        _level->initNewLevel();
 		        std::vector<Node> nqueue;
 		        for (int i = 0; i < int(queue.size()); ++i) {
 		          Node n = queue[i];
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node u = _graph.source(e);
 		            if (!reached[u] &&
 		                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
 		              reached.set(u, true);
 		              _level->initAddItem(u);
 		              nqueue.push_back(u);
+		            }
+		          }
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node v = _graph.target(e);
 		            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
 		              reached.set(v, true);
 		              _level->initAddItem(v);
 		              nqueue.push_back(v);
+		            }
+		          }
+		        }
 		        queue.swap(nqueue);
+		      }
 		      _level->initFinish();
 		      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
-		        Value rem = (*_capacity)[e] - (*_flow)[e];
+		        Flow rem = (*_capacity)[e] - (*_flow)[e];
 		        if (_tolerance.positive(rem)) {
 		          Node u = _graph.target(e);
 		          if ((*_level)[u] == _level->maxLevel()) continue;
 		          _flow->set(e, (*_capacity)[e]);
 		          _excess->set(u, (*_excess)[u] + rem);
 		          if (u != _target && !_level->active(u)) {
 		            _level->activate(u);
+		          }
+		        }
+		      }
 		      for (InArcIt e(_graph, _source); e != INVALID; ++e) {
-		        Value rem = (*_flow)[e];
+		        Flow rem = (*_flow)[e];
 		        if (_tolerance.positive(rem)) {
 		          Node v = _graph.source(e);
 		          if ((*_level)[v] == _level->maxLevel()) continue;
 		          _flow->set(e, 0);
 		          _excess->set(v, (*_excess)[v] + rem);
 		          if (v != _target && !_level->active(v)) {
 		            _level->activate(v);
+		          }
+		        }
+		      }
 		      return true;
+		    }
 		    /// \brief Starts the first phase of the preflow algorithm.
 		    ///
 		    /// The preflow algorithm consists of two phases, this method runs
 		    /// the first phase. After the first phase the maximum flow value
 		    /// and a minimum value cut can already be computed, although a
 		    /// maximum flow is not yet obtained. So after calling this method
 		    /// \ref flowValue() returns the value of a maximum flow and \ref
 		    /// minCut() returns a minimum cut.
 		    /// \pre One of the \ref init() functions must be called before
 		    /// using this function.
 		    void startFirstPhase() {
 		      _phase = true;
 		      Node n = _level->highestActive();
 		      int level = _level->highestActiveLevel();
 		      while (n != INVALID) {
 		        int num = _node_num;
 		        while (num > 0 && n != INVALID) {
-		          Value excess = (*_excess)[n];
+		          Flow excess = (*_excess)[n];
 		          int new_level = _level->maxLevel();
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-		            Value rem = (*_capacity)[e] - (*_flow)[e];
+		            Flow rem = (*_capacity)[e] - (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.target(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] + excess);
 		                _excess->set(v, (*_excess)[v] + excess);
 		                excess = 0;
 		                goto no_more_push_1;
 		              } else {
 		                excess -= rem;
 		                _excess->set(v, (*_excess)[v] + rem);
 		                _flow->set(e, (*_capacity)[e]);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
-		            Value rem = (*_flow)[e];
+		            Flow rem = (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.source(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] - excess);
 		                _excess->set(v, (*_excess)[v] + excess);
 		                excess = 0;
 		                goto no_more_push_1;
 		              } else {
 		                excess -= rem;
 		                _excess->set(v, (*_excess)[v] + rem);
 		                _flow->set(e, 0);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		        no_more_push_1:
 		          _excess->set(n, excess);
 		          if (excess != 0) {
 		            if (new_level + 1 < _level->maxLevel()) {
 		              _level->liftHighestActive(new_level + 1);
 		            } else {
 		              _level->liftHighestActiveToTop();
+		            }
 		            if (_level->emptyLevel(level)) {
 		              _level->liftToTop(level);
+		            }
 		          } else {
 		            _level->deactivate(n);
+		          }
 		          n = _level->highestActive();
 		          level = _level->highestActiveLevel();
 		          --num;
+		        }
 		        num = _node_num * 20;
 		        while (num > 0 && n != INVALID) {
-		          Value excess = (*_excess)[n];
+		          Flow excess = (*_excess)[n];
 		          int new_level = _level->maxLevel();
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-		            Value rem = (*_capacity)[e] - (*_flow)[e];
+		            Flow rem = (*_capacity)[e] - (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.target(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] + excess);
 		                _excess->set(v, (*_excess)[v] + excess);
 		                excess = 0;
 		                goto no_more_push_2;
 		              } else {
 		                excess -= rem;
 		                _excess->set(v, (*_excess)[v] + rem);
 		                _flow->set(e, (*_capacity)[e]);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
-		            Value rem = (*_flow)[e];
+		            Flow rem = (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.source(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] - excess);
 		                _excess->set(v, (*_excess)[v] + excess);
 		                excess = 0;
 		                goto no_more_push_2;
 		              } else {
 		                excess -= rem;
 		                _excess->set(v, (*_excess)[v] + rem);
 		                _flow->set(e, 0);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		        no_more_push_2:
 		          _excess->set(n, excess);
 		          if (excess != 0) {
 		            if (new_level + 1 < _level->maxLevel()) {
 		              _level->liftActiveOn(level, new_level + 1);
 		            } else {
 		              _level->liftActiveToTop(level);
+		            }
 		            if (_level->emptyLevel(level)) {
 		              _level->liftToTop(level);
+		            }
 		          } else {
 		            _level->deactivate(n);
+		          }
 		          while (level >= 0 && _level->activeFree(level)) {
 		            --level;
+		          }
 		          if (level == -1) {
 		            n = _level->highestActive();
 		            level = _level->highestActiveLevel();
 		          } else {
 		            n = _level->activeOn(level);
+		          }
 		          --num;
+		        }
+		      }
+		    }
 		    /// \brief Starts the second phase of the preflow algorithm.
 		    ///
 		    /// The preflow algorithm consists of two phases, this method runs
 		    /// the second phase. After calling one of the \ref init() functions
 		    /// and \ref startFirstPhase() and then \ref startSecondPhase(),
 		    /// \ref flowMap() returns a maximum flow, \ref flowValue() returns the
 		    /// value of a maximum flow, \ref minCut() returns a minimum cut
 		    /// \pre One of the \ref init() functions and \ref startFirstPhase()
 		    /// must be called before using this function.
 		    void startSecondPhase() {
 		      _phase = false;
 		      typename Digraph::template NodeMap<bool> reached(_graph);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        reached.set(n, (*_level)[n] < _level->maxLevel());
+		      }
 		      _level->initStart();
 		      _level->initAddItem(_source);
 		      std::vector<Node> queue;
 		      queue.push_back(_source);
 		      reached.set(_source, true);
 		      while (!queue.empty()) {
 		        _level->initNewLevel();
 		        std::vector<Node> nqueue;
 		        for (int i = 0; i < int(queue.size()); ++i) {
 		          Node n = queue[i];
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node v = _graph.target(e);
 		            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
 		              reached.set(v, true);
 		              _level->initAddItem(v);
 		              nqueue.push_back(v);
+		            }
+		          }
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node u = _graph.source(e);
 		            if (!reached[u] &&
 		                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
 		              reached.set(u, true);
 		              _level->initAddItem(u);
 		              nqueue.push_back(u);
+		            }
+		          }
+		        }
 		        queue.swap(nqueue);
+		      }
 		      _level->initFinish();
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if (!reached[n]) {
 		          _level->dirtyTopButOne(n);
 		        } else if ((*_excess)[n] > 0 && _target != n) {
 		          _level->activate(n);
+		        }
+		      }
 		      Node n;
 		      while ((n = _level->highestActive()) != INVALID) {
-		        Value excess = (*_excess)[n];
+		        Flow excess = (*_excess)[n];
 		        int level = _level->highestActiveLevel();
 		        int new_level = _level->maxLevel();
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-		          Value rem = (*_capacity)[e] - (*_flow)[e];
+		          Flow rem = (*_capacity)[e] - (*_flow)[e];
 		          if (!_tolerance.positive(rem)) continue;
 		          Node v = _graph.target(e);
 		          if ((*_level)[v] < level) {
 		            if (!_level->active(v) && v != _source) {
 		              _level->activate(v);
+		            }
 		            if (!_tolerance.less(rem, excess)) {
 		              _flow->set(e, (*_flow)[e] + excess);
 		              _excess->set(v, (*_excess)[v] + excess);
 		              excess = 0;
 		              goto no_more_push;
 		            } else {
 		              excess -= rem;
 		              _excess->set(v, (*_excess)[v] + rem);
 		              _flow->set(e, (*_capacity)[e]);
+		            }
 		          } else if (new_level > (*_level)[v]) {
 		            new_level = (*_level)[v];
+		          }
+		        }
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
-		          Value rem = (*_flow)[e];
+		          Flow rem = (*_flow)[e];
 		          if (!_tolerance.positive(rem)) continue;
 		          Node v = _graph.source(e);
 		          if ((*_level)[v] < level) {
 		            if (!_level->active(v) && v != _source) {
 		              _level->activate(v);
+		            }
 		            if (!_tolerance.less(rem, excess)) {
 		              _flow->set(e, (*_flow)[e] - excess);
 		              _excess->set(v, (*_excess)[v] + excess);
 		              excess = 0;
 		              goto no_more_push;
 		            } else {
 		              excess -= rem;
 		              _excess->set(v, (*_excess)[v] + rem);
 		              _flow->set(e, 0);
+		            }
 		          } else if (new_level > (*_level)[v]) {
 		            new_level = (*_level)[v];
+		          }
+		        }
 		      no_more_push:
 		        _excess->set(n, excess);
 		        if (excess != 0) {
 		          if (new_level + 1 < _level->maxLevel()) {
 		            _level->liftHighestActive(new_level + 1);
 		          } else {
 		            // Calculation error
 		            _level->liftHighestActiveToTop();
+		          }
 		          if (_level->emptyLevel(level)) {
 		            // Calculation error
 		            _level->liftToTop(level);
+		          }
 		        } else {
 		          _level->deactivate(n);
+		        }
+		      }
+		    }
 		    /// \brief Runs the preflow algorithm.
 		    ///
 		    /// Runs the preflow algorithm.
 		    /// \note pf.run() is just a shortcut of the following code.
 		    /// \code
 		    ///   pf.init();
 		    ///   pf.startFirstPhase();
 		    ///   pf.startSecondPhase();
 		    /// \endcode
 		    void run() {
 		      init();
 		      startFirstPhase();
 		      startSecondPhase();
+		    }
 		    /// \brief Runs the preflow algorithm to compute the minimum cut.
 		    ///
 		    /// Runs the preflow algorithm to compute the minimum cut.
 		    /// \note pf.runMinCut() is just a shortcut of the following code.
 		    /// \code
 		    ///   pf.init();
 		    ///   pf.startFirstPhase();
 		    /// \endcode
 		    void runMinCut() {
 		      init();
 		      startFirstPhase();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the preflow algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either one of the \ref run() "run*()" functions or one of the
 		    /// \ref startFirstPhase() "start*()" functions should be called
 		    /// before using them.
 		    ///@{
 		    /// \brief Returns the value of the maximum flow.
 		    ///
 		    /// Returns the value of the maximum flow by returning the excess
 		    /// of the target node. This value equals to the value of
 		    /// the maximum flow already after the first phase of the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
-		    Value flowValue() const {
+		    Flow flowValue() const {
 		      return (*_excess)[_target];
+		    }
 		    /// \brief Returns the flow on the given arc.
 		    ///
 		    /// Returns the flow on the given arc. This method can
 		    /// be called after the second phase of the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
-		    Value flow(const Arc& arc) const {
+		    Flow 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.
 		    /// This method can be called after the second phase of the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow;
+		    }
 		    /// \brief Returns \c true when the node is on the source side of the
 		    /// minimum cut.
 		    ///
 		    /// Returns true when the node is on the source side of the found
 		    /// minimum cut. This method can be called both after running \ref
 		    /// startFirstPhase() and \ref startSecondPhase().
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    bool minCut(const Node& node) const {
 		      return ((*_level)[node] == _level->maxLevel()) == _phase;
+		    }
 		    /// \brief Gives back a minimum value cut.
 		    ///
 		    /// Sets \c cutMap to the characteristic vector of a minimum value
 		    /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
 		    /// node map with \c bool (or convertible) value type.
 		    ///
 		    /// This method can be called both after running \ref startFirstPhase()
 		    /// and \ref startSecondPhase(). The result after the second phase
 		    /// could be slightly different if inexact computation is used.
 		    ///
 		    /// \note This function calls \ref minCut() for each node, so it runs in
 		    /// \f$O(n)\f$ time.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    template <typename CutMap>
 		    void minCutMap(CutMap& cutMap) const {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        cutMap.set(n, minCut(n));
+		      }
+		    }
 		    /// @}
 		  };
+		}
 		#endif

test/circulation_test.cc

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.
+		 *
 		 */
 		#include <iostream>
 		#include "test_tools.h"
 		#include <lemon/list_graph.h>
 		#include <lemon/circulation.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/maps.h>
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "@arcs\n"
 		  "     lcap  ucap\n"
 		  "0 1  2  10\n"
 		  "0 2  2  6\n"
 		  "1 3  4  7\n"
 		  "1 4  0  5\n"
 		  "2 4  1  3\n"
 		  "3 5  3  8\n"
 		  "4 5  3  7\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "sink   5\n";
 		void checkCirculationCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::Arc Arc;
 		  typedef concepts::ReadMap<Arc,VType> CapMap;
-		  typedef concepts::ReadMap<Node,VType> DeltaMap;
+		  typedef concepts::ReadMap<Node,VType> SupplyMap;
 		  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
 		  typedef concepts::WriteMap<Node,bool> BarrierMap;
 		  typedef Elevator<Digraph, Digraph::Node> Elev;
 		  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
 		  Digraph g;
 		  Node n;
 		  Arc a;
 		  CapMap lcap, ucap;
-		  DeltaMap delta;
+		  SupplyMap supply;
 		  FlowMap flow;
 		  BarrierMap bar;
-		  Circulation<Digraph, CapMap, CapMap, DeltaMap>
+		  Circulation<Digraph, CapMap, CapMap, SupplyMap>
 		    ::SetFlowMap<FlowMap>
 		    ::SetElevator<Elev>
 		    ::SetStandardElevator<LinkedElev>
-		    ::Create circ_test(g,lcap,ucap,delta);
+		    ::Create circ_test(g,lcap,ucap,supply);
 		  circ_test.lowerCapMap(lcap);
 		  circ_test.upperCapMap(ucap);
-		  circ_test.deltaMap(delta);
+		  circ_test.lowerMap(lcap);
 		  circ_test.upperMap(ucap);
 		  circ_test.supplyMap(supply);
 		  flow = circ_test.flowMap();
 		  circ_test.flowMap(flow);
 		  circ_test.init();
 		  circ_test.greedyInit();
 		  circ_test.start();
 		  circ_test.run();
 		  circ_test.barrier(n);
 		  circ_test.barrierMap(bar);
 		  circ_test.flow(a);
+		}
 		template <class G, class LM, class UM, class DM>
 		void checkCirculation(const G& g, const LM& lm, const UM& um,
 		                      const DM& dm, bool find)
+		{
 		  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
 		  bool ret = circ.run();
 		  if (find) {
 		    check(ret, "A feasible solution should have been found.");
 		    check(circ.checkFlow(), "The found flow is corrupt.");
 		    check(!circ.checkBarrier(), "A barrier should not have been found.");
 		  } else {
 		    check(!ret, "A feasible solution should not have been found.");
 		    check(circ.checkBarrier(), "The found barrier is corrupt.");
+		  }
+		}
 		int main (int, char*[])
+		{
 		  typedef ListDigraph Digraph;
 		  DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph g;
 		  IntArcMap lo(g), up(g);
 		  IntNodeMap delta(g, 0);
 		  Node s, t;
 		  std::istringstream input(test_lgf);
 		  DigraphReader<Digraph>(g,input).
 		    arcMap("lcap", lo).
 		    arcMap("ucap", up).
 		    node("source",s).
 		    node("sink",t).
 		    run();
 		  delta[s] = 7; delta[t] = -7;
 		  checkCirculation(g, lo, up, delta, true);
 		  delta[s] = 13; delta[t] = -13;
 		  checkCirculation(g, lo, up, delta, true);
 		  delta[s] = 6; delta[t] = -6;
 		  checkCirculation(g, lo, up, delta, false);
 		  delta[s] = 14; delta[t] = -14;
 		  checkCirculation(g, lo, up, delta, false);
 		  delta[s] = 7; delta[t] = -13;
 		  checkCirculation(g, lo, up, delta, true);
 		  delta[s] = 5; delta[t] = -15;
 		  checkCirculation(g, lo, up, delta, true);
 		  delta[s] = 10; delta[t] = -11;
 		  checkCirculation(g, lo, up, delta, true);
 		  delta[s] = 11; delta[t] = -10;
 		  checkCirculation(g, lo, up, delta, false);
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account