RhodeCode

/* -*- 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_BFS_H

#define LEMON_BFS_H

///\ingroup search

///\file

///\brief BFS algorithm.

#include <lemon/list_graph.h>

#include <lemon/bits/path_dump.h>

#include <lemon/core.h>

#include <lemon/error.h>

#include <lemon/maps.h>

#include <lemon/path.h>

namespace lemon {

  ///Default traits class of Bfs class.

  ///Default traits class of Bfs class.

  ///\tparam GR Digraph type.

  template<class GR>

  struct BfsDefaultTraits

  {

    ///The type of the digraph the algorithm runs on.

    typedef GR Digraph;

    ///\brief The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///\param g is the digraph, to which we would like to define the

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

    ///The type of the map that indicates which nodes are processed.

    ///The type of the map that indicates which nodes are processed.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///\param g is the digraph, to which

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

      return new ProcessedMap();

    }

    ///The type of the map that indicates which nodes are reached.

    ///The type of the map that indicates which nodes are reached.

    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    ///\param g is the digraph, to which

    static ReachedMap *createReachedMap(const Digraph &g)

    {

      return new ReachedMap(g);

    }

    ///The type of the map that stores the distances of the nodes.

    ///The type of the map that stores the distances of the nodes.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///\param g is the digraph, to which we would like to define the

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

  };

  ///%BFS algorithm class.

  ///\ingroup search

  ///This class provides an efficient implementation of the %BFS algorithm.

  ///

  ///There is also a \ref bfs() "function-type interface" for the BFS

  ///algorithm, which is convenient in the simplier cases and it can be

  ///used easier.

  ///

  ///\tparam GR The type of the digraph the algorithm runs on.

  ///The default type is \ref ListDigraph.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

            typename TR=BfsDefaultTraits<GR> >

#endif

  class Bfs {

  public:

    ///The type of the digraph the algorithm runs on.

    typedef typename TR::Digraph Digraph;

    ///\brief The type of the map that stores the predecessor arcs of the

    ///shortest paths.

    typedef typename TR::PredMap PredMap;

    ///The type of the map that stores the distances of the nodes.

    typedef typename TR::DistMap DistMap;

    ///The type of the map that indicates which nodes are reached.

    typedef typename TR::ReachedMap ReachedMap;

    ///The type of the map that indicates which nodes are processed.

    typedef typename TR::ProcessedMap ProcessedMap;

    ///The type of the paths.

    typedef PredMapPath<Digraph, PredMap> Path;

    ///The \ref BfsDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *G;

    //Pointer to the map of predecessor arcs.

    PredMap *_pred;

    //Indicates if _pred is locally allocated (true) or not.

    bool local_pred;

    //Pointer to the map of distances.

    DistMap *_dist;

    //Indicates if _dist is locally allocated (true) or not.

    bool local_dist;

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    //Indicates if _reached is locally allocated (true) or not.

    bool local_reached;

    //Pointer to the map of processed status of the nodes.

    ProcessedMap *_processed;

    //Indicates if _processed is locally allocated (true) or not.

    bool local_processed;

    std::vector<typename Digraph::Node> _queue;

    int _queue_head,_queue_tail,_queue_next_dist;

    int _curr_dist;

    //Creates the maps if necessary.

    void create_maps()

    {

      if(!_pred) {

        local_pred = true;

        _pred = Traits::createPredMap(*G);

      }

      if(!_dist) {

        local_dist = true;

        _dist = Traits::createDistMap(*G);

      }

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*G);

      }

      if(!_processed) {

        local_processed = true;

        _processed = Traits::createProcessedMap(*G);

      }

    }

  protected:

    Bfs() {}

  public:

    typedef Bfs Create;

    ///\name Named Template Parameters

    ///@{

    template <class T>

    struct SetPredMapTraits : public Traits {

      typedef T PredMap;

      static PredMap *createPredMap(const Digraph &)

      {

        LEMON_ASSERT(false, "PredMap is not initialized");

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {

      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;

    };

    template <class T>

    struct SetDistMapTraits : public Traits {

      typedef T DistMap;

      static DistMap *createDistMap(const Digraph &)

      {

        LEMON_ASSERT(false, "DistMap is not initialized");

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {

      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;

    };

    template <class T>

    struct SetReachedMapTraits : public Traits {

      typedef T ReachedMap;

      static ReachedMap *createReachedMap(const Digraph &)

      {

        LEMON_ASSERT(false, "ReachedMap is not initialized");

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    template <class T>

    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {

      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;

    };

    template <class T>

    struct SetProcessedMapTraits : public Traits {

      typedef T ProcessedMap;

      static ProcessedMap *createProcessedMap(const Digraph &)

      {

        LEMON_ASSERT(false, "ProcessedMap is not initialized");

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {

      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;

    };

    struct SetStandardProcessedMapTraits : public Traits {

      typedef typename Digraph::template NodeMap<bool> ProcessedMap;

      static ProcessedMap *createProcessedMap(const Digraph &g)

      {

        return new ProcessedMap(g);

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///If you don't set it explicitly, it will be automatically allocated.

    struct SetStandardProcessedMap :

      public Bfs< Digraph, SetStandardProcessedMapTraits > {

      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;

    };

    ///@}

  public:

    ///Constructor.

    ///Constructor.

    ///\param g The digraph the algorithm runs on.

    Bfs(const Digraph &g) :

      G(&g),

      _pred(NULL), local_pred(false),

      _dist(NULL), local_dist(false),

      _reached(NULL), local_reached(false),

      _processed(NULL), local_processed(false)

    { }

    ///Destructor.

    ~Bfs()

    {

      if(local_pred) delete _pred;

      if(local_dist) delete _dist;

      if(local_reached) delete _reached;

      if(local_processed) delete _processed;

    }

    ///Sets the map that stores the predecessor arcs.

    ///Sets the map that stores the predecessor arcs.

    ///If you don't use this function before calling \ref run(Node) "run()"

    ///or \ref init(), an instance will be allocated automatically.

    ///The destructor deallocates this automatically allocated map,

    ///of course.

    ///\return <tt> (*this) </tt>

    Bfs &predMap(PredMap &m)

    {

      if(local_pred) {

        delete _pred;

        local_pred=false;

      }

      _pred = &m;

      return *this;

    }

    ///Sets the map that indicates which nodes are reached.

    ///Sets the map that indicates which nodes are reached.

    ///If you don't use this function before calling \ref run(Node) "run()"

    ///or \ref init(), an instance will be allocated automatically.

    ///The destructor deallocates this automatically allocated map,

    ///of course.

    ///\return <tt> (*this) </tt>

    Bfs &reachedMap(ReachedMap &m)

    {

      if(local_reached) {

        delete _reached;

        local_reached=false;

      }

      _reached = &m;

      return BfsWizard<SetProcessedMapBase<T> >(*this);

    }

    template<class T>

    struct SetPathBase : public Base {

      typedef T Path;

      SetPathBase(const TR &b) : TR(b) {}

    };

    ///\brief \ref named-func-param "Named parameter"

    ///for getting the shortest path to the target node.

    ///

    ///\ref named-func-param "Named parameter"

    ///for getting the shortest path to the target node.

    template<class T>

    BfsWizard<SetPathBase<T> > path(const T &t)

    {

      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));

      return BfsWizard<SetPathBase<T> >(*this);

    }

    ///\brief \ref named-func-param "Named parameter"

    ///for getting the distance of the target node.

    ///

    ///\ref named-func-param "Named parameter"

    ///for getting the distance of the target node.

    BfsWizard dist(const int &d)

    {

      Base::_di=const_cast<int*>(&d);

      return *this;

    }

  };

  ///Function-type interface for BFS algorithm.

  /// \ingroup search

  ///Function-type interface for BFS algorithm.

  ///

  ///This function also has several \ref named-func-param "named parameters",

  ///they are declared as the members of class \ref BfsWizard.

  ///The following examples show how to use these parameters.

  ///\code

  ///  // Compute shortest path from node s to each node

  ///  bfs(g).predMap(preds).distMap(dists).run(s);

  ///

  ///  // Compute shortest path from s to t

  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);

  ///\endcode

  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"

  ///to the end of the parameter list.

  ///\sa BfsWizard

  ///\sa Bfs

  template<class GR>

  BfsWizard<BfsWizardBase<GR> >

  bfs(const GR &digraph)

  {

    return BfsWizard<BfsWizardBase<GR> >(digraph);

  }

#ifdef DOXYGEN

  /// \brief Visitor class for BFS.

  ///

  /// This class defines the interface of the BfsVisit events, and

  /// it could be the base of a real visitor class.

  struct BfsVisitor {

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Node Node;

    /// \brief Called for the source node(s) of the BFS.

    ///

    /// This function is called for the source node(s) of the BFS.

    void start(const Node& node) {}

    /// \brief Called when a node is reached first time.

    ///

    /// This function is called when a node is reached first time.

    void reach(const Node& node) {}

    /// \brief Called when a node is processed.

    ///

    /// This function is called when a node is processed.

    void process(const Node& node) {}

    /// \brief Called when an arc reaches a new node.

    ///

    /// This function is called when the BFS finds an arc whose target node

    /// is not reached yet.

    void discover(const Arc& arc) {}

    /// \brief Called when an arc is examined but its target node is

    /// already discovered.

    ///

    /// This function is called when an arc is examined but its target node is

    /// already discovered.

    void examine(const Arc& arc) {}

  };

#else

  struct BfsVisitor {

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Node Node;

    void start(const Node&) {}

    void reach(const Node&) {}

    void process(const Node&) {}

    void discover(const Arc&) {}

    void examine(const Arc&) {}

    template <typename _Visitor>

    struct Constraints {

      void constraints() {

        Arc arc;

        Node node;

        visitor.start(node);

        visitor.reach(node);

        visitor.process(node);

        visitor.discover(arc);

        visitor.examine(arc);

      }

      _Visitor& visitor;

    };

  };

#endif

  /// \brief Default traits class of BfsVisit class.

  ///

  /// Default traits class of BfsVisit class.

  struct BfsVisitDefaultTraits {

    /// \brief The type of the digraph the algorithm runs on.

    /// \brief The type of the map that indicates which nodes are reached.

    ///

    /// The type of the map that indicates which nodes are reached.

    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a ReachedMap.

    ///

    /// This function instantiates a ReachedMap.

    /// \param digraph is the digraph, to which

    /// we would like to define the ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  ///

  /// with visitor interface.

  ///

  /// class. It works with callback mechanism, the BfsVisit object calls

  /// the member functions of the \c Visitor class on every BFS event.

  ///

  /// This interface of the BFS algorithm should be used in special cases

  /// when extra actions have to be performed in connection with certain

  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()

  /// instead.

  ///

  /// does not observe the BFS events. If you want to observe the BFS

  /// events, you should implement your own visitor class.

  /// algorithm. The default traits class is

  /// See \ref BfsVisitDefaultTraits for the documentation of

  /// a BFS visit traits class.

#ifdef DOXYGEN

#else

#endif

  class BfsVisit {

  public:

    ///The traits class.

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;

    ///The visitor type used by the algorithm.

    ///The type of the map that indicates which nodes are reached.

    typedef typename Traits::ReachedMap ReachedMap;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *_digraph;

    //Pointer to the visitor object.

    Visitor *_visitor;

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    //Indicates if _reached is locally allocated (true) or not.

    bool local_reached;

    std::vector<typename Digraph::Node> _list;

    int _list_front, _list_back;

    //Creates the maps if necessary.

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

      }

    }

  protected:

    BfsVisit() {}

  public:

    typedef BfsVisit Create;

    /// \name Named Template Parameters

    ///@{

    template <class T>

    struct SetReachedMapTraits : public Traits {

      typedef T ReachedMap;

      static ReachedMap *createReachedMap(const Digraph &digraph) {

        LEMON_ASSERT(false, "ReachedMap is not initialized");

        return 0; // ignore warnings

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// ReachedMap type.

    ///

    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.

    template <class T>

    struct SetReachedMap : public BfsVisit< Digraph, Visitor,

                                            SetReachedMapTraits<T> > {

      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;

    };

    ///@}

  public:

    /// \brief Constructor.

  public:

    // \brief Graph initialized map constructor.

    //

    // Graph initialized map constructor.

    explicit ArrayMap(const Graph& graph) {

      Parent::attach(graph.notifier(Item()));

      allocate_memory();

      Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

        int id = nf->id(it);;

        allocator.construct(&(values[id]), Value());

      }

    }

    // \brief Constructor to use default value to initialize the map.

    //

    // It constructs a map and initialize all of the the map.

    ArrayMap(const Graph& graph, const Value& value) {

      Parent::attach(graph.notifier(Item()));

      allocate_memory();

      Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

        int id = nf->id(it);;

        allocator.construct(&(values[id]), value);

      }

    }

  private:

    // \brief Constructor to copy a map of the same map type.

    //

    // Constructor to copy a map of the same map type.

    ArrayMap(const ArrayMap& copy) : Parent() {

      if (copy.attached()) {

        attach(*copy.notifier());

      }

      capacity = copy.capacity;

      if (capacity == 0) return;

      values = allocator.allocate(capacity);

      Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

        int id = nf->id(it);;

        allocator.construct(&(values[id]), copy.values[id]);

      }

    }

    // \brief Assign operator.

    //

    // This operator assigns for each item in the map the

    // value mapped to the same item in the copied map.

    // The parameter map should be indiced with the same

    // itemset because this assign operator does not change

    // the container of the map.

    ArrayMap& operator=(const ArrayMap& cmap) {

      return operator=<ArrayMap>(cmap);

    }

    // \brief Template assign operator.

    //

    // concecpt and could be indiced by the current item set of

    // the NodeMap. In this case the value for each item

    // is assigned by the value of the given ReadMap.

    template <typename CMap>

    ArrayMap& operator=(const CMap& cmap) {

      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();

      const typename Parent::Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

        set(it, cmap[it]);

      }

      return *this;

    }

  public:

    // \brief The destructor of the map.

    //

    // The destructor of the map.

    virtual ~ArrayMap() {

      if (attached()) {

        clear();

        detach();

      }

    }

  protected:

    using Parent::attach;

    using Parent::detach;

    using Parent::attached;

  public:

    // \brief The subscript operator.

    //

    // The subscript operator. The map can be subscripted by the

    // actual keys of the graph.

    Value& operator[](const Key& key) {

      int id = Parent::notifier()->id(key);

      return values[id];

    }

    // \brief The const subscript operator.

    //

    // The const subscript operator. The map can be subscripted by the

    // actual keys of the graph.

    const Value& operator[](const Key& key) const {

      int id = Parent::notifier()->id(key);

      return values[id];

    }

    // \brief Setter function of the map.

    //

    // Setter function of the map. Equivalent with map[key] = val.

    // This is a compatibility feature with the not dereferable maps.

    void set(const Key& key, const Value& val) {

      (*this)[key] = val;

    }

  protected:

    // \brief Adds a new key to the map.

    //

    // It adds a new key to the map. It is called by the observer notifier

    typedef True ReferenceMapTag;

    // The key type of the map.

    typedef _Item Key;

    // The value type of the map.

    typedef _Value Value;

    // The notifier type.

    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;

    // The map type.

    typedef VectorMap Map;

    // The base class of the map.

    typedef typename Notifier::ObserverBase Parent;

    // The reference type of the map;

    typedef typename Container::reference Reference;

    // The const reference type of the map;

    typedef typename Container::const_reference ConstReference;

    // \brief Constructor to attach the new map into the notifier.

    //

    // It constructs a map and attachs it into the notifier.

    // It adds all the items of the graph to the map.

    VectorMap(const Graph& graph) {

      Parent::attach(graph.notifier(Item()));

      container.resize(Parent::notifier()->maxId() + 1);

    }

    // \brief Constructor uses given value to initialize the map.

    //

    // It constructs a map uses a given value to initialize the map.

    // It adds all the items of the graph to the map.

    VectorMap(const Graph& graph, const Value& value) {

      Parent::attach(graph.notifier(Item()));

      container.resize(Parent::notifier()->maxId() + 1, value);

    }

  private:

    // \brief Copy constructor

    //

    // Copy constructor.

    VectorMap(const VectorMap& _copy) : Parent() {

      if (_copy.attached()) {

        Parent::attach(*_copy.notifier());

        container = _copy.container;

      }

    }

    // \brief Assign operator.

    //

    // This operator assigns for each item in the map the

    // value mapped to the same item in the copied map.

    // The parameter map should be indiced with the same

    // itemset because this assign operator does not change

    // the container of the map.

    VectorMap& operator=(const VectorMap& cmap) {

      return operator=<VectorMap>(cmap);

    }

    // \brief Template assign operator.

    //

    // concecpt and could be indiced by the current item set of

    // the NodeMap. In this case the value for each item

    // is assigned by the value of the given ReadMap.

    template <typename CMap>

    VectorMap& operator=(const CMap& cmap) {

      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();

      const typename Parent::Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

        set(it, cmap[it]);

      }

      return *this;

    }

  public:

    // \brief The subcript operator.

    //

    // The subscript operator. The map can be subscripted by the

    // actual items of the graph.

    Reference operator[](const Key& key) {

      return container[Parent::notifier()->id(key)];

    }

    // \brief The const subcript operator.

    //

    // The const subscript operator. The map can be subscripted by the

    // actual items of the graph.

    ConstReference operator[](const Key& key) const {

      return container[Parent::notifier()->id(key)];

    }

    // \brief The setter function of the map.

    //

    // It the same as operator[](key) = value expression.

    void set(const Key& key, const Value& value) {

      (*this)[key] = value;

    }

  protected:

    // \brief Adds a new key to the map.

    //

    // It adds a new key to the map. It is called by the observer notifier

    // and it overrides the add() member function of the observer base.

    virtual void add(const Key& key) {

      int id = Parent::notifier()->id(key);

      if (id >= int(container.size())) {

        container.resize(id + 1);

      }

    }

    // \brief Adds more new keys to the map.

    //

    // It adds more new keys to the map. It is called by the observer notifier

    // and it overrides the add() member function of the observer base.

    virtual void add(const std::vector<Key>& keys) {

      int max = container.size() - 1;

      for (int i = 0; i < int(keys.size()); ++i) {

        int id = Parent::notifier()->id(keys[i]);

        if (id >= max) {

          max = id;

        }

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

  struct CirculationDefaultTraits {

    /// \brief The type of the digraph the algorithm runs on.

    /// \brief The type of the map that stores the circulation lower

    /// bound.

    ///

    /// The type of the map that stores the circulation lower bound.

    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.

    /// \brief The type of the map that stores the circulation upper

    /// bound.

    ///

    /// The type of the map that stores the circulation upper bound.

    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.

    /// \brief The type of the map that stores the lower bound for

    /// the supply of the nodes.

    ///

    /// The type of the map that stores the lower bound for the supply

    /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"

    /// concept.

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

    typedef typename DeltaMap::Value Value;

    /// \brief The type of the map that stores the flow values.

    ///

    /// The type of the map that stores the flow values.

    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

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

    /// \brief Instantiates a FlowMap.

    ///

    /// This function instantiates a \ref FlowMap.

    /// \param digraph The digraph, to which we would like to define

    /// the flow map.

    static FlowMap* createFlowMap(const Digraph& digraph) {

      return new FlowMap(digraph);

    }

    /// \brief The elevator type used by the algorithm.

    ///

    /// The elevator type used by the algorithm.

    ///

    /// \sa Elevator

    /// \sa LinkedElevator

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

    /// \brief Instantiates an Elevator.

    ///

    /// This function instantiates an \ref Elevator.

    /// \param digraph The digraph, to which we would like to define

    /// the elevator.

    /// \param max_level The maximum level of the elevator.

    static Elevator* createElevator(const Digraph& digraph, int max_level) {

      return new Elevator(digraph, max_level);

    }

    /// \brief The tolerance used by the algorithm

    ///

    /// The tolerance used by the algorithm to handle inexact computation.

    typedef lemon::Tolerance<Value> Tolerance;

  };

  /**

     \brief Push-relabel algorithm for the network circulation problem.

     \ingroup max_flow

     This class implements a push-relabel algorithm for the network

     circulation problem.

     It is to find a feasible circulation when lower and upper bounds

     are given for the flow values on the arcs and lower bounds

     are given for the supply values of the nodes.

     The exact formulation of this problem is the following.

     Let \f$G=(V,A)\f$ be a digraph,

     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,

     \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation

     \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that

     \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)

     \geq delta(v) \quad \forall v\in V, \f]

     \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]

     \note \f$delta(v)\f$ specifies a lower bound for the supply of node

     \f$v\f$. It can be either positive or negative, however note that

     \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to

     have a feasible solution.

     \note A special case of this problem is when

     \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$

     will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.

     Thus a feasible solution for the

     \ref min_cost_flow "minimum cost flow" problem can be calculated

     in this way.