RhodeCode

 *

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

#define LEMON_BIN_HEAP_H

///\ingroup auxdat

///\file

///\brief Binary Heap implementation.

#include <vector>

#include <utility>

#include <functional>

namespace lemon {

  ///\ingroup auxdat

  ///

  ///\brief A Binary Heap implementation.

  ///

  ///This class implements the \e binary \e heap data structure. 

  /// 

  ///A \e heap is a data structure for storing items with specified values

  ///called \e priorities in such a way that finding the item with minimum

  ///priority is efficient. \c Comp specifies the ordering of the priorities.

  ///In a heap one can change the priority of an item, add or erase an

  ///item, etc.

  ///

  ///\tparam PR Type of the priority of the items.

  ///\tparam IM A read and writable item map with int values, used internally

  ///to handle the cross references.

  ///\tparam Comp A functor class for the ordering of the priorities.

  ///The default is \c std::less<PR>.

  ///

  ///\sa FibHeap

  ///\sa Dijkstra

  template <typename PR, typename IM, typename Comp = std::less<PR> >

  class BinHeap {

  public:

    ///\e

    typedef IM ItemIntMap;

    ///\e

    typedef PR Prio;

    ///\e

    typedef typename ItemIntMap::Key Item;

    ///\e

    typedef std::pair<Item,Prio> Pair;

    ///\e

    typedef Comp Compare;

    /// \brief Type to represent the items states.

    ///

    /// Each Item element have a state associated to it. It may be "in heap",

    /// "pre heap" or "post heap". The latter two are indifferent from the

    /// heap's point of view, but may be useful to the user.

    ///

    /// The item-int map must be initialized in such way that it assigns

    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.

    enum State {

    };

  private:

    std::vector<Pair> _data;

    Compare _comp;

    ItemIntMap &_iim;

  public:

    /// \brief The constructor.

    ///

    /// The constructor.

    /// \param map should be given to the constructor, since it is used

    /// internally to handle the cross references. The value of the map

    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.

    explicit BinHeap(ItemIntMap &map) : _iim(map) {}

    /// \brief The constructor.

    ///

    /// The constructor.

    /// \param map should be given to the constructor, since it is used

    /// internally to handle the cross references. The value of the map

    /// should be PRE_HEAP (-1) for each element.

    ///

    /// \param comp The comparator function object.

    BinHeap(ItemIntMap &map, const Compare &comp)

      : _iim(map), _comp(comp) {}

    /// The number of items stored in the heap.

    ///

    /// \brief Returns the number of items stored in the heap.

    int size() const { return _data.size(); }

    /// \brief Checks if the heap stores no items.

    ///

    /// Returns \c true if and only if the heap stores no items.

    bool empty() const { return _data.empty(); }

    /// \brief Make empty this heap.

    ///

    /// Make empty this heap. It does not change the cross reference map.

    /// If you want to reuse what is not surely empty you should first clear

    /// the heap and after that you should set the cross reference map for

    /// each item to \c PRE_HEAP.

    void clear() {

      _data.clear();

    }

  private:

    static int parent(int i) { return (i-1)/2; }

    static int second_child(int i) { return 2*i+2; }

    bool less(const Pair &p1, const Pair &p2) const {

      return _comp(p1.second, p2.second);

    }

    int bubble_up(int hole, Pair p) {

      int par = parent(hole);

      while( hole>0 && less(p,_data[par]) ) {

        move(_data[par],hole);

        hole = par;

        par = parent(hole);

      }

      move(p, hole);

      GraphIncIt(Invalid) {}

      /// \brief Assignment operator.

      ///

      /// Assignment operator for the iterator.

      GraphIncIt& operator=(const GraphIncIt&) { return *this; }

      /// \brief Increment the iterator.

      ///

      /// This operator increments the iterator, i.e. assigns it to the

      /// next arc incoming to or outgoing from the given node.

      GraphIncIt& operator++() { return *this; }

      /// \brief Equality operator

      ///

      /// Equality operator.

      /// Two iterators are equal if and only if they point to the

      /// same object or both are invalid.

      bool operator==(const GraphIncIt&) const { return true;}

      /// \brief Inequality operator

      ///

      /// Inequality operator.

      /// Two iterators are equal if and only if they point to the

      /// same object or both are invalid.

      bool operator!=(const GraphIncIt&) const { return true;}

      template <typename _GraphIncIt>

      struct Constraints {

        void constraints() {

          checkConcept<GraphItem<sel>, _GraphIncIt>();

          _GraphIncIt it1(graph, node);

          _GraphIncIt it2;

          _GraphIncIt it3 = it1;

          _GraphIncIt it4 = INVALID;

          it2 = ++it1;

          ++it2 = it1;

          ++(++it1);

          Item e = it1;

          e = it2;

        }

        const Base& node;

        const GR& graph;

      };

    };

    /// \brief Skeleton class for iterable directed graphs.

    ///

    /// This class describes the interface of iterable directed

    /// graphs. It extends \ref BaseDigraphComponent with the core

    /// iterable interface.

    /// This concept is part of the Digraph concept.

    template <typename BAS = BaseDigraphComponent>

    class IterableDigraphComponent : public BAS {

    public:

      typedef BAS Base;

      typedef typename Base::Node Node;

      typedef typename Base::Arc Arc;

      typedef IterableDigraphComponent Digraph;

      ///

      /// This interface provides functions for iteration on digraph items.

      ///

      /// @{

      /// \brief Return the first node.

      ///

      /// This function gives back the first node in the iteration order.

      void first(Node&) const {}

      /// \brief Return the next node.

      ///

      /// This function gives back the next node in the iteration order.

      void next(Node&) const {}

      /// \brief Return the first arc.

      ///

      /// This function gives back the first arc in the iteration order.

      void first(Arc&) const {}

      /// \brief Return the next arc.

      ///

      /// This function gives back the next arc in the iteration order.

      void next(Arc&) const {}

      /// \brief Return the first arc incomming to the given node.

      ///

      /// This function gives back the first arc incomming to the

      /// given node.

      void firstIn(Arc&, const Node&) const {}

      /// \brief Return the next arc incomming to the given node.

      ///

      /// This function gives back the next arc incomming to the

      /// given node.

      void nextIn(Arc&) const {}

      /// \brief Return the first arc outgoing form the given node.

      ///

      /// This function gives back the first arc outgoing form the

      /// given node.

      void firstOut(Arc&, const Node&) const {}

      /// \brief Return the next arc outgoing form the given node.

      ///

      /// This function gives back the next arc outgoing form the

      /// given node.

      void nextOut(Arc&) const {}

      /// @}

      ///

      /// This interface provides iterator classes for digraph items.

      ///

      /// @{

      /// \brief This iterator goes through each node.

      ///

      /// This iterator goes through each node.

      ///

      typedef GraphItemIt<Digraph, Node> NodeIt;

      /// \brief This iterator goes through each arc.

      ///

      /// This iterator goes through each arc.

      ///

      typedef GraphItemIt<Digraph, Arc> ArcIt;

      /// \brief This iterator goes trough the incoming arcs of a node.

      ///

      /// This iterator goes trough the \e incoming arcs of a certain node

      /// of a digraph.

      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;

      /// \brief This iterator goes trough the outgoing arcs of a node.

      ///

      /// This iterator goes trough the \e outgoing arcs of a certain node

      /// of a digraph.

      typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;

      /// \brief The base node of the iterator.

      ///

      /// This function gives back the base node of the iterator.

      /// It is always the target node of the pointed arc.

      Node baseNode(const InArcIt&) const { return INVALID; }

      /// \brief The running node of the iterator.

      ///

      /// This function gives back the running node of the iterator.

      /// It is always the source node of the pointed arc.

      Node runningNode(const InArcIt&) const { return INVALID; }

      /// \brief The base node of the iterator.

      ///

      /// This function gives back the base node of the iterator.

      /// It is always the source node of the pointed arc.

      Node baseNode(const OutArcIt&) const { return INVALID; }

      /// \brief The running node of the iterator.

      ///

      /// This function gives back the running node of the iterator.

      /// It is always the target node of the pointed arc.

      Node runningNode(const OutArcIt&) const { return INVALID; }

      /// @}

      template <typename _Digraph>

      struct Constraints {

        void constraints() {

          checkConcept<Base, _Digraph>();

          {

            typename _Digraph::Node node(INVALID);

            typename _Digraph::Arc arc(INVALID);

            {

              digraph.first(node);

              digraph.next(node);

            }

            {

              digraph.first(arc);

              digraph.next(arc);

            }

            {

              digraph.firstIn(arc, node);

              digraph.nextIn(arc);

            }

            {

              digraph.firstOut(arc, node);

              digraph.nextOut(arc);

            }

          }

          {

            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,

              typename _Digraph::ArcIt >();

            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,

              typename _Digraph::NodeIt >();

            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,

              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();

            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,

              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();

            typename _Digraph::Node n;

            const typename _Digraph::InArcIt iait(INVALID);

            const typename _Digraph::OutArcIt oait(INVALID);

            n = digraph.baseNode(iait);

            n = digraph.runningNode(iait);

            n = digraph.baseNode(oait);

            n = digraph.runningNode(oait);

            ignore_unused_variable_warning(n);

          }

        }

        const _Digraph& digraph;

      };

    };

    /// \brief Skeleton class for iterable undirected graphs.

    ///

    /// This class describes the interface of iterable undirected

    /// graphs. It extends \ref IterableDigraphComponent with the core

    /// iterable interface of undirected graphs.

    /// This concept is part of the Graph concept.

    template <typename BAS = BaseGraphComponent>

    class IterableGraphComponent : public IterableDigraphComponent<BAS> {

    public:

      typedef BAS Base;

      typedef typename Base::Node Node;

      typedef typename Base::Arc Arc;

      typedef typename Base::Edge Edge;

      typedef IterableGraphComponent Graph;

      ///

      /// This interface provides functions for iteration on edges.

      ///

      /// @{

      using IterableDigraphComponent<Base>::first;

      using IterableDigraphComponent<Base>::next;

      /// \brief Return the first edge.

      ///

      /// This function gives back the first edge in the iteration order.

      void first(Edge&) const {}

      /// \brief Return the next edge.

      ///

      /// This function gives back the next edge in the iteration order.

      void next(Edge&) const {}

      /// \brief Return the first edge incident to the given node.

      ///

      /// This function gives back the first edge incident to the given 

      /// node. The bool parameter gives back the direction for which the

      /// source node of the directed arc representing the edge is the 

      /// given node.

      void firstInc(Edge&, bool&, const Node&) const {}

      /// \brief Gives back the next of the edges from the

      /// given node.

      ///

      /// This function gives back the next edge incident to the given 

      /// node. The bool parameter should be used as \c firstInc() use it.

      void nextInc(Edge&, bool&) const {}

      using IterableDigraphComponent<Base>::baseNode;

      using IterableDigraphComponent<Base>::runningNode;

      /// @}

      ///

      /// This interface provides iterator classes for edges.

      ///

      /// @{

      /// \brief This iterator goes through each edge.

      ///

      /// This iterator goes through each edge.

      typedef GraphItemIt<Graph, Edge> EdgeIt;

      /// \brief This iterator goes trough the incident edges of a

      /// node.

      ///

      /// This iterator goes trough the incident edges of a certain

      /// node of a graph.

      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;

      /// \brief The base node of the iterator.

      ///

      /// This function gives back the base node of the iterator.

      Node baseNode(const IncEdgeIt&) const { return INVALID; }

      /// \brief The running node of the iterator.

      ///

      /// This function gives back the running node of the iterator.

      Node runningNode(const IncEdgeIt&) const { return INVALID; }

      /// @}

      template <typename _Graph>

      struct Constraints {

        void constraints() {

          checkConcept<IterableDigraphComponent<Base>, _Graph>();

          {

            typename _Graph::Node node(INVALID);

            typename _Graph::Edge edge(INVALID);

            bool dir;

            {

              graph.first(edge);

              graph.next(edge);

            }

            {

              graph.firstInc(edge, dir, node);

              graph.nextInc(edge, dir);

            }

          }

          {

            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,

              typename _Graph::EdgeIt >();

            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,

              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();

            typename _Graph::Node n;

            const typename _Graph::IncEdgeIt ieit(INVALID);

            n = graph.baseNode(ieit);

            n = graph.runningNode(ieit);

          }

        }

        const _Graph& graph;

      };

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

///\ingroup concept

///\file

///\brief The concept of heaps.

#ifndef LEMON_CONCEPTS_HEAP_H

#define LEMON_CONCEPTS_HEAP_H

#include <lemon/core.h>

#include <lemon/concept_check.h>

namespace lemon {

  namespace concepts {

    /// \addtogroup concept

    /// @{

    /// \brief The heap concept.

    ///

    /// Concept class describing the main interface of heaps. A \e heap

    /// is a data structure for storing items with specified values called

    /// \e priorities in such a way that finding the item with minimum

    /// priority is efficient. In a heap one can change the priority of an

    /// item, add or erase an item, etc.

    ///

    /// \tparam PR Type of the priority of the items.

    /// \tparam IM A read and writable item map with int values, used

    /// internally to handle the cross references.

    /// \tparam Comp A functor class for the ordering of the priorities.

    /// The default is \c std::less<PR>.

#ifdef DOXYGEN

    template <typename PR, typename IM, typename Comp = std::less<PR> >

#else

    template <typename PR, typename IM>

#endif

    class Heap {

    public:

      /// Type of the item-int map.

      typedef IM ItemIntMap;

      /// Type of the priorities.

      typedef PR Prio;

      /// Type of the items stored in the heap.

      typedef typename ItemIntMap::Key Item;

      /// \brief Type to represent the states of the items.

      ///

      /// Each item has a state associated to it. It can be "in heap",

      /// "pre heap" or "post heap". The later two are indifferent

      /// from the point of view of the heap, but may be useful for

      /// the user.

      ///

      /// The item-int map must be initialized in such way that it assigns

      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.

      enum State {

      };

      /// \brief The constructor.

      ///

      /// The constructor.

      /// \param map A map that assigns \c int values to keys of type

      /// \c Item. It is used internally by the heap implementations to

      /// handle the cross references. The assigned value must be

      /// \c PRE_HEAP (<tt>-1</tt>) for every item.

      explicit Heap(ItemIntMap &map) {}

      /// \brief The number of items stored in the heap.

      ///

      /// Returns the number of items stored in the heap.

      int size() const { return 0; }

      /// \brief Checks if the heap is empty.

      ///

      /// Returns \c true if the heap is empty.

      bool empty() const { return false; }

      /// \brief Makes the heap empty.

      ///

      /// Makes the heap empty.

      void clear();

      /// \brief Inserts an item into the heap with the given priority.

      ///

      /// Inserts the given item into the heap with the given priority.

      /// \param i The item to insert.

      /// \param p The priority of the item.

      void push(const Item &i, const Prio &p) {}

      /// \brief Returns the item having minimum priority.

      ///

      /// Returns the item having minimum priority.

      /// \pre The heap must be non-empty.

      Item top() const {}

      /// \brief The minimum priority.

      ///

      /// Returns the minimum priority.

      /// \pre The heap must be non-empty.

      Prio prio() const {}

      /// \brief Removes the item having minimum priority.

      ///

      /// Removes the item having minimum priority.

      /// \pre The heap must be non-empty.

      void pop() {}

      /// \brief Removes an item from the heap.

      ///

      /// Removes the given item from the heap if it is already stored.

      /// \param i The item to delete.

      void erase(const Item &i) {}

      /// \brief The priority of an item.

      ///

      /// Returns the priority of the given item.

      /// \param i The item.

      /// \pre \c i must be in the heap.

      Prio operator[](const Item &i) const {}

    ///The type of the paths.

    typedef PredMapPath<Digraph, PredMap> Path;

    ///The \ref DfsDefaultTraits "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::OutArcIt> _stack;

    int _stack_head;

    //Creates the maps if necessary.

    void create_maps()

    {

      if(!_pred) {

        local_pred = true;

        _pred = Traits::createPredMap(*G);

      }

      if(!_dist) {

        local_dist = true;

        _dist = Traits::createDistMap(*G);

      }

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*G);

      }

      if(!_processed) {

        local_processed = true;

        _processed = Traits::createProcessedMap(*G);

      }

    }

  protected:

    Dfs() {}

  public:

    typedef Dfs Create;

    ///@{

    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

    ///\c PredMap type.

    ///

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

    ///\c PredMap type.

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

    template <class T>

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

      typedef Dfs<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

    ///\c DistMap type.

    ///

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

    ///\c DistMap type.

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

    template <class T>

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

      typedef Dfs<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

    ///\c ReachedMap type.

    ///

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

    ///\c ReachedMap type.

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

    template <class T>

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

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

    };

    template <class T>

    ///The \ref DijkstraDefaultTraits "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 length map.

    const LengthMap *_length;

    //Pointer to the map of predecessors arcs.

    PredMap *_pred;

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

    bool local_pred;

    //Pointer to the map of distances.

    DistMap *_dist;

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

    bool local_dist;

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

    ProcessedMap *_processed;

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

    bool local_processed;

    //Pointer to the heap cross references.

    HeapCrossRef *_heap_cross_ref;

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

    bool local_heap_cross_ref;

    //Pointer to the heap.

    Heap *_heap;

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

    bool local_heap;

    //Creates the maps if necessary.

    void create_maps()

    {

      if(!_pred) {

        local_pred = true;

        _pred = Traits::createPredMap(*G);

      }

      if(!_dist) {

        local_dist = true;

        _dist = Traits::createDistMap(*G);

      }

      if(!_processed) {

        local_processed = true;

        _processed = Traits::createProcessedMap(*G);

      }

      if (!_heap_cross_ref) {

        local_heap_cross_ref = true;

        _heap_cross_ref = Traits::createHeapCrossRef(*G);

      }

      if (!_heap) {

        local_heap = true;

        _heap = Traits::createHeap(*_heap_cross_ref);

      }

    }

  public:

    typedef Dijkstra Create;

    ///@{

    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

    ///\c PredMap type.

    ///

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

    ///\c PredMap type.

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

    template <class T>

    struct SetPredMap

      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {

      typedef Dijkstra< Digraph, LengthMap, 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

    ///\c DistMap type.

    ///

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

    ///\c DistMap type.

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

    template <class T>

    struct SetDistMap

      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {

      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<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

    ///\c ProcessedMap type.

    ///

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

    ///\c ProcessedMap type.

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

    template <class T>

    struct SetProcessedMap

      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {

      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;

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

#define LEMON_DIMACS_H

#include <iostream>

#include <string>

#include <vector>

#include <limits>

#include <lemon/maps.h>

#include <lemon/error.h>

/// \ingroup dimacs_group

/// \file

/// \brief DIMACS file format reader.

namespace lemon {

  /// \addtogroup dimacs_group

  /// @{

  /// DIMACS file type descriptor.

  struct DimacsDescriptor

  {

      };

    ///The file type

    Type type;

    ///The number of nodes in the graph

    int nodeNum;

    ///The number of edges in the graph

    int edgeNum;

    int lineShift;

    DimacsDescriptor() : type(NONE) {}

  };

  ///Discover the type of a DIMACS file

  DimacsDescriptor dimacsType(std::istream& is)

  {

    DimacsDescriptor r;

    std::string problem,str;

    char c;

    r.lineShift=0;

    while (is >> c)

      switch(c)

        {

        case 'p':

          if(is >> problem >> r.nodeNum >> r.edgeNum)

            {

              getline(is, str);

              r.lineShift++;

              if(problem=="min") r.type=DimacsDescriptor::MIN;

              else if(problem=="max") r.type=DimacsDescriptor::MAX;

              else if(problem=="sp") r.type=DimacsDescriptor::SP;

              else if(problem=="mat") r.type=DimacsDescriptor::MAT;

              else throw FormatError("Unknown problem type");

              return r;

            }

          else

            {

              throw FormatError("Missing or wrong problem type declaration.");

            }

          break;

        case 'c':

          getline(is, str);

          r.lineShift++;

          break;

        default:

          throw FormatError("Unknown DIMACS declaration.");

        }

    throw FormatError("Missing problem type declaration.");

  }

  ///

  /// This function reads a minimum cost flow instance from DIMACS format,

  /// i.e. from a DIMACS file having a line starting with

  /// \code

  ///   p min

  /// \endcode

  /// At the beginning, \c g is cleared by \c g.clear(). The supply

  /// amount of the nodes are written to the \c supply node map

  /// (they are signed values). The lower bounds, capacities and costs

  /// of the arcs are written to the \c lower, \c capacity and \c cost

  /// arc maps.

  ///

  /// If the capacity of an arc is less than the lower bound, it will

  /// be set to "infinite" instead. The actual value of "infinite" is

  /// contolled by the \c infty parameter. If it is 0 (the default value),

  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,

  /// \c std::numeric_limits<Capacity>::max() otherwise. If \c infty is set to

  /// a non-zero value, that value will be used as "infinite".

  ///

  /// If the file type was previously evaluated by dimacsType(), then

  /// the descriptor struct should be given by the \c dest parameter.

  template <typename Digraph, typename LowerMap,

            typename CapacityMap, typename CostMap,

            typename SupplyMap>

  void readDimacsMin(std::istream& is,

                     Digraph &g,

                     LowerMap& lower,

                     CapacityMap& capacity,

                     CostMap& cost,

                     SupplyMap& supply,

                     typename CapacityMap::Value infty = 0,

                     DimacsDescriptor desc=DimacsDescriptor())

  {

    g.clear();

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

    typename Digraph::Arc e;

    std::string problem, str;

    char c;

    int i, j;

    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);

    if(desc.type!=DimacsDescriptor::MIN)

      throw FormatError("Problem type mismatch");

    nodes.resize(desc.nodeNum + 1);

    for (int k = 1; k <= desc.nodeNum; ++k) {

      nodes[k] = g.addNode();

      supply.set(nodes[k], 0);

    }

    typename SupplyMap::Value sup;

    typename CapacityMap::Value low;

    typename CapacityMap::Value cap;

    typename CostMap::Value co;

    typedef typename CapacityMap::Value Capacity;

    if(infty==0)

      infty = std::numeric_limits<Capacity>::has_infinity ?

        std::numeric_limits<Capacity>::infinity() :

        std::numeric_limits<Capacity>::max();

    while (is >> c) {

      switch (c) {

      case 'c': // comment line

        getline(is, str);

        break;

                   DimacsDescriptor desc=DimacsDescriptor()) {

    g.clear();

    s=t=INVALID;

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

    typename Digraph::Arc e;

    char c, d;

    int i, j;

    typename CapacityMap::Value _cap;

    std::string str;

    nodes.resize(desc.nodeNum + 1);

    for (int k = 1; k <= desc.nodeNum; ++k) {

      nodes[k] = g.addNode();

    }

    typedef typename CapacityMap::Value Capacity;

    if(infty==0)