RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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.

 *

 */

namespace lemon {

/*!

\page lgf-format LEMON Graph Format (LGF)

The \e LGF is a <em>column oriented</em>

file format for storing graphs and associated data like

node and edge maps.

Each line with \c '#' first non-whitespace

character is considered as a comment line.

Otherwise the file consists of sections starting with

a header line. The header lines starts with an \c '@' character followed by the

type of section. The standard section types are \c \@nodes, \c

\@arcs and \c \@edges

and \@attributes. Each header line may also have an optional

\e name, which can be use to distinguish the sections of the same

type.

The standard sections are column oriented, each line consists of

<em>token</em>s separated by whitespaces. A token can be \e plain or

\e quoted. A plain token is just a sequence of non-whitespace characters,

while a quoted token is a

character sequence surrounded by double quotes, and it can also

contain whitespaces and escape sequences.

The \c \@nodes section describes a set of nodes and associated

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

The following

non-empty lines until the next section describes nodes of the

graph. Each line contains the values of the node maps

associated to the current node.

\code

 @nodes

 label  coordinates  size    title

 1      (10,20)      10      "First node"

 2      (80,80)      8       "Second node"

 3      (40,10)      10      "Third node"

\endcode

The \c \@arcs section is very similar to the \c \@nodes section, it

again starts with a header line describing the names of the maps, but

the \c "label" map is not obligatory here. The following lines

describe the arcs. The first two tokens of each line are the source

and the target node of the arc, respectively, then come the map

values. The source and target tokens must be node labels.

\code

 @arcs

         capacity

 1   2   16

 1   3   12

 2   3   18

\endcode

If there is no map in the \c \@arcs section at all, then it must be

indicated by a sole '-' sign in the first line.

\code

 @arcs

         -

 1   2

 1   3

 2   3

\endcode

The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can

also store the edge set of an undirected graph. In such case there is

a conventional method for store arc maps in the file, if two columns

have the same caption with \c '+' and \c '-' prefix, then these columns

can be regarded as the values of an arc map.

The \c \@attributes section contains key-value pairs, each line

consists of two tokens, an attribute name, and then an attribute

value. The value of the attribute could be also a label value of a

node or an edge, or even an edge label prefixed with \c '+' or \c '-',

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H

#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H

#include <lemon/core.h>

#include <lemon/error.h>

namespace lemon {

  template <typename _Digraph>

  class DigraphAdaptorExtender : public _Digraph {

    typedef _Digraph Parent;

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorExtender Adaptor;

    // Base extensions

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    int maxId(Node) const {

      return Parent::maxNodeId();

    }

    int maxId(Arc) const {

      return Parent::maxArcId();

    }

    Node fromId(int id, Node) const {

      return Parent::nodeFromId(id);

    }

    Arc fromId(int id, Arc) const {

      return Parent::arcFromId(id);

    }

    Node oppositeNode(const Node &n, const Arc &e) const {

      if (n == Parent::source(e))

        return Parent::target(e);

      else if(n==Parent::target(e))

        return Parent::source(e);

      else

        return INVALID;

    }

    class NodeIt : public Node {

      const Adaptor* _adaptor;

    public:

      NodeIt() {}

      NodeIt(Invalid i) : Node(i) { }

      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {

        _adaptor->first(static_cast<Node&>(*this));

      }

      NodeIt(const Adaptor& adaptor, const Node& node)

        : Node(node), _adaptor(&adaptor) {}

      NodeIt& operator++() {

        _adaptor->next(*this);

        return *this;

      }

    };

    class ArcIt : public Arc {

      const Adaptor* _adaptor;

    public:

      ArcIt() { }

      ArcIt(Invalid i) : Arc(i) { }

      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {

        _adaptor->first(static_cast<Arc&>(*this));

      }

      ArcIt(const Adaptor& adaptor, const Arc& e) :

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_PATH_DUMP_H

#define LEMON_BITS_PATH_DUMP_H

#include <lemon/core.h>

#include <lemon/concept_check.h>

namespace lemon {

  template <typename _Digraph, typename _PredMap>

  class PredMapPath {

  public:

    typedef True RevPathTag;

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef _PredMap PredMap;

    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,

                typename Digraph::Node _target)

      : digraph(_digraph), predMap(_predMap), target(_target) {}

    int length() const {

      int len = 0;

      typename Digraph::Node node = target;

      typename Digraph::Arc arc;

      while ((arc = predMap[node]) != INVALID) {

        node = digraph.source(arc);

        ++len;

      }

      return len;

    }

    bool empty() const {

      return predMap[target] == INVALID;

    }

    class RevArcIt {

    public:

      RevArcIt() {}

      RevArcIt(Invalid) : path(0), current(INVALID) {}

      RevArcIt(const PredMapPath& _path)

        : path(&_path), current(_path.target) {

        if (path->predMap[current] == INVALID) current = INVALID;

      }

      operator const typename Digraph::Arc() const {

        return path->predMap[current];

      }

      RevArcIt& operator++() {

        current = path->digraph.source(path->predMap[current]);

        if (path->predMap[current] == INVALID) current = INVALID;

        return *this;

      }

      bool operator==(const RevArcIt& e) const {

        return current == e.current;

      }

      bool operator!=(const RevArcIt& e) const {

        return current != e.current;

      }

      bool operator<(const RevArcIt& e) const {

        return current < e.current;

      }

    private:

      const PredMapPath* path;

      typename Digraph::Node current;

    };

  private:

    const Digraph& digraph;

    const PredMap& predMap;

    typename Digraph::Node target;

  };

  template <typename _Digraph, typename _PredMatrixMap>

  class PredMatrixMapPath {

  public:

    typedef True RevPathTag;

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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.

 *

 */

///\file

///\brief Some basic non-inline functions and static global data.

#include<lemon/bits/windows.h>

#ifdef WIN32

#ifndef WIN32_LEAN_AND_MEAN

#define WIN32_LEAN_AND_MEAN

#endif

#ifndef NOMINMAX

#define NOMINMAX

#endif

#ifdef UNICODE

#undef UNICODE

#endif

#include <windows.h>

#ifdef LOCALE_INVARIANT

#define MY_LOCALE LOCALE_INVARIANT

#else

#define MY_LOCALE LOCALE_NEUTRAL

#endif

#else

#include <unistd.h>

#include <ctime>

#ifndef WIN32

#include <sys/times.h>

#endif

#include <sys/time.h>

#endif

#include <cmath>

#include <sstream>

namespace lemon {

  namespace bits {

    void getWinProcTimes(double &rtime,

                         double &utime, double &stime,

                         double &cutime, double &cstime)

    {

#ifdef WIN32

      static const double ch = 4294967296.0e-7;

      static const double cl = 1.0e-7;

      FILETIME system;

      GetSystemTimeAsFileTime(&system);

      rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime;

      FILETIME create, exit, kernel, user;

      if (GetProcessTimes(GetCurrentProcess(),&create, &exit, &kernel, &user)) {

        utime = ch * user.dwHighDateTime + cl * user.dwLowDateTime;

        stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime;

        cutime = 0;

        cstime = 0;

      } else {

        rtime = 0;

        utime = 0;

        stime = 0;

        cutime = 0;

        cstime = 0;

      }

#else

      timeval tv;

      gettimeofday(&tv, 0);

      rtime=tv.tv_sec+double(tv.tv_usec)/1e6;

      tms ts;

      double tck=sysconf(_SC_CLK_TCK);

      times(&ts);

      utime=ts.tms_utime/tck;

      stime=ts.tms_stime/tck;

      cutime=ts.tms_cutime/tck;

      cstime=ts.tms_cstime/tck;

#endif

    }

    std::string getWinFormattedDate()

    {

      std::ostringstream os;

#ifdef WIN32

      SYSTEMTIME time;

      GetSystemTime(&time);

      char buf1[11], buf2[9], buf3[5];

          if (GetDateFormat(MY_LOCALE, 0, &time,

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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_COST_SCALING_H

#define LEMON_COST_SCALING_H

/// \ingroup min_cost_flow_algs

/// \file

/// \brief Cost scaling algorithm for finding a minimum cost flow.

#include <vector>

#include <deque>

#include <limits>

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/math.h>

#include <lemon/static_graph.h>

#include <lemon/circulation.h>

#include <lemon/bellman_ford.h>

namespace lemon {

  /// \brief Default traits class of CostScaling algorithm.

  ///

  /// Default traits class of CostScaling algorithm.

  /// \tparam GR Digraph type.

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// and supply values. By default it is \c int.

  /// \tparam C The number type used for costs and potentials.

  /// By default it is the same as \c V.

#ifdef DOXYGEN

  template <typename GR, typename V = int, typename C = V>

#else

  template < typename GR, typename V = int, typename C = V,

             bool integer = std::numeric_limits<C>::is_integer >

#endif

  struct CostScalingDefaultTraits

  {

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef V Value;

    /// The type of the arc costs

    typedef C Cost;

    /// \brief The large cost type used for internal computations

    ///

    /// The large cost type used for internal computations.

    /// It is \c long \c long if the \c Cost type is integer,

    /// otherwise it is \c double.

    /// \c Cost must be convertible to \c LargeCost.

    typedef double LargeCost;

  };

  // Default traits class for integer cost types

  template <typename GR, typename V, typename C>

  struct CostScalingDefaultTraits<GR, V, C, true>

  {

    typedef GR Digraph;

    typedef V Value;

    typedef C Cost;

#ifdef LEMON_HAVE_LONG_LONG

    typedef long long LargeCost;

#else

    typedef long LargeCost;

#endif

  };

  /// \addtogroup min_cost_flow_algs

  /// @{

  /// \brief Implementation of the Cost Scaling algorithm for

  /// finding a \ref min_cost_flow "minimum cost flow".

  ///

  /// \ref CostScaling implements a cost scaling algorithm that performs

  /// push/augment and relabel operations for finding a \ref min_cost_flow

  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,

  /// \ref goldberg97efficient, \ref bunnagel98efficient.

  /// It is a highly efficient primal-dual solution method, which

  /// can be viewed as the generalization of the \ref Preflow

  /// "preflow push-relabel" algorithm for the maximum flow problem.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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_MAPS_H

#define LEMON_MAPS_H

#include <iterator>

#include <functional>

#include <vector>

#include <map>

#include <lemon/core.h>

///\file

///\ingroup maps

///\brief Miscellaneous property maps

namespace lemon {

  /// \addtogroup maps

  /// @{

  /// Base class of maps.

  /// Base class of maps. It provides the necessary type definitions

  /// required by the map %concepts.

  template<typename K, typename V>

  class MapBase {

  public:

    /// \brief The key type of the map.

    typedef K Key;

    /// \brief The value type of the map.

    /// (The type of objects associated with the keys).

    typedef V Value;

  };

  /// Null map. (a.k.a. DoNothingMap)

  /// This map can be used if you have to provide a map only for

  /// its type definitions, or if you have to provide a writable map,

  /// but data written to it is not required (i.e. it will be sent to

  /// <tt>/dev/null</tt>).

  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

  ///

  /// \sa ConstMap

  template<typename K, typename V>

  class NullMap : public MapBase<K, V> {

  public:

    ///\e

    typedef K Key;

    ///\e

    typedef V Value;

    /// Gives back a default constructed element.

    Value operator[](const Key&) const { return Value(); }

    /// Absorbs the value.

    void set(const Key&, const Value&) {}

  };

  /// Returns a \c NullMap class

  /// This function just returns a \c NullMap class.

  /// \relates NullMap

  template <typename K, typename V>

  NullMap<K, V> nullMap() {

    return NullMap<K, V>();

  }

  /// Constant map.

  /// This \ref concepts::ReadMap "readable map" assigns a specified

  /// value to each key.

  ///

  /// In other aspects it is equivalent to \c NullMap.

  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"

  /// concept, but it absorbs the data written to it.

  ///

  /// The simplest way of using this map is through the constMap()

  /// function.

  ///

  /// \sa NullMap

  /// \sa IdentityMap

  template<typename K, typename V>

  class ConstMap : public MapBase<K, V> {

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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 CAP Capacity map type.

  template <typename GR, typename CAP>

  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 CAP CapacityMap;

    /// \brief The type of the flow values.

    typedef typename CapacityMap::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.

#ifdef DOXYGEN

    typedef GR::ArcMap<Value> FlowMap;

#else

    typedef typename Digraph::template ArcMap<Value> FlowMap;

#endif

    /// \brief Instantiates a FlowMap.

    ///

    /// This function instantiates a \ref FlowMap.

    /// \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, LinkedElevator

#ifdef DOXYGEN

    typedef lemon::Elevator<GR, GR::Node> Elevator;

#else

    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;

#endif

    /// \brief Instantiates an Elevator.

    ///

    /// This function instantiates an \ref Elevator.

    /// \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;

  };

  /// \ingroup max_flow

  ///

  /// \brief %Preflow algorithm class.

        if (_tolerance.positive((*_capacity)[e])) {

          Node u = _graph.target(e);

          if ((*_level)[u] == _level->maxLevel()) continue;

          _flow->set(e, (*_capacity)[e]);

          (*_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;

        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)[n] = excess;

      }

      typename Digraph::template NodeMap<bool> reached(_graph, false);

      _level->initStart();

      _level->initAddItem(_target);

      std::vector<Node> queue;

      reached[_source] = true;

      queue.push_back(_target);

      reached[_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[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[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];

        if (_tolerance.positive(rem)) {

          Node u = _graph.target(e);

          if ((*_level)[u] == _level->maxLevel()) continue;

          _flow->set(e, (*_capacity)[e]);

          (*_excess)[u] += rem;

        }

      }

      for (InArcIt e(_graph, _source); e != INVALID; ++e) {

        Value rem = (*_flow)[e];

        if (_tolerance.positive(rem)) {

          Node v = _graph.source(e);

          if ((*_level)[v] == _level->maxLevel()) continue;

          _flow->set(e, 0);

          (*_excess)[v] += rem;

        }

      }

        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))

          _level->activate(n);

      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;

      while (true) {

        int num = _node_num;

        Node n = INVALID;

        int level = -1;

        while (num > 0) {

          n = _level->highestActive();

          if (n == INVALID) goto first_phase_done;

          level = _level->highestActiveLevel();

          --num;

          Value excess = (*_excess)[n];

          int new_level = _level->maxLevel();

          for (OutArcIt e(_graph, n); e != INVALID; ++e) {

            Value 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)[v] += excess;

                excess = 0;

                goto no_more_push_1;

              } else {

                excess -= rem;

                (*_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];

            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)[v] += excess;

                excess = 0;

                goto no_more_push_1;

              } else {

                excess -= rem;

                (*_excess)[v] += rem;

                _flow->set(e, 0);

              }

            } else if (new_level > (*_level)[v]) {

              new_level = (*_level)[v];

            }

          }

        no_more_push_1:

          (*_excess)[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);

          }

        }

        num = _node_num * 20;

        while (num > 0) {

          while (level >= 0 && _level->activeFree(level)) {

            --level;

          }

          if (level == -1) {

            n = _level->highestActive();

            level = _level->highestActiveLevel();

            if (n == INVALID) goto first_phase_done;

          } else {

            n = _level->activeOn(level);

          }

          --num;

          Value excess = (*_excess)[n];

          int new_level = _level->maxLevel();

          for (OutArcIt e(_graph, n); e != INVALID; ++e) {

            Value 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)[v] += excess;

                excess = 0;

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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 <lemon/concepts/digraph.h>

#include <lemon/smart_graph.h>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/dfs.h>

#include <lemon/path.h>

#include "graph_test.h"

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "6\n"

  "@arcs\n"

  "     label\n"

  "0 1  0\n"

  "1 2  1\n"

  "2 3  2\n"

  "1 4  3\n"

  "4 2  4\n"

  "4 5  5\n"

  "5 0  6\n"

  "6 3  7\n"

  "@attributes\n"

  "source 0\n"

  "target 5\n"

  "source1 6\n"

  "target1 3\n";

void checkDfsCompile()

{

  typedef concepts::Digraph Digraph;

  typedef Dfs<Digraph> DType;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  Digraph G;

  Node s, t;

  Arc e;

  int l, i;

  bool b;

  DType::DistMap d(G);

  DType::PredMap p(G);

  Path<Digraph> pp;

  concepts::ReadMap<Arc,bool> am;

  {

    DType dfs_test(G);

    const DType& const_dfs_test = dfs_test;

    dfs_test.run(s);

    dfs_test.run(s,t);

    dfs_test.run();

    dfs_test.init();

    dfs_test.addSource(s);

    e = dfs_test.processNextArc();

    e = const_dfs_test.nextArc();

    b = const_dfs_test.emptyQueue();

    i = const_dfs_test.queueSize();

    dfs_test.start();

    dfs_test.start(t);

    dfs_test.start(am);

    l  = const_dfs_test.dist(t);

    e  = const_dfs_test.predArc(t);

    s  = const_dfs_test.predNode(t);

    b  = const_dfs_test.reached(t);

    d  = const_dfs_test.distMap();

    p  = const_dfs_test.predMap();

    pp = const_dfs_test.path(t);

  }

    dfs_test.addSource(s);

    e = dfs_test.processNextArc();

    e = dfs_test.nextArc();

    b = dfs_test.emptyQueue();

    i = dfs_test.queueSize();

    dfs_test.start();

    dfs_test.start(t);

    dfs_test.start(am);

    l  = dfs_test.dist(t);

    e  = dfs_test.predArc(t);

    s  = dfs_test.predNode(t);

    b  = dfs_test.reached(t);

    pp = dfs_test.path(t);

  }

}

void checkDfsFunctionCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Arc Arc;

  typedef Digraph::Node Node;

  Digraph g;

  bool b;

  dfs(g).run(Node());

  b=dfs(g).run(Node(),Node());

  dfs(g).run();

  dfs(g)

    .predMap(concepts::ReadWriteMap<Node,Arc>())

    .distMap(concepts::ReadWriteMap<Node,VType>())

    .reachedMap(concepts::ReadWriteMap<Node,bool>())