RhodeCode

if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials

the following \e complementary \e slackness optimality conditions hold.

 - For all \f$uv\in A\f$ arcs:

   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;

   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;

   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.

 - For all \f$u\in V\f$ nodes:

   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

     then \f$\pi(u)=0\f$.

Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc

\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.

\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]

All algorithms provide dual solution (node potentials), as well,

is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$

node potentials the following conditions hold.

 - For all \f$uv\in A\f$ arcs:

   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;

   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;

   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.

 - For all \f$u\in V\f$ nodes:

   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

     then \f$\pi(u)=0\f$.

*/

}

      typedef T OperationTraits;

    };

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

    /// \c OperationTraits type.

    ///

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

    /// \c OperationTraits type.

    template <class T>

    struct SetOperationTraits

      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {

      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >

      Create;

    };

    ///@}

    /// the given node.

    ///

    /// This function returns the 'previous arc' of the shortest path

    /// tree for node \c v, i.e. it returns the last arc of a

    /// shortest path from a root to \c v. It is \c INVALID if \c v

    /// is not reached from the root(s) or if \c v is a root.

    ///

    /// The shortest path tree used here is equal to the shortest path

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    Arc predArc(Node v) const { return (*_pred)[v]; }

    /// \brief Returns the 'previous node' of the shortest path tree for

    /// the given node.

    ///

    /// This function returns the 'previous node' of the shortest path

    /// tree for node \c v, i.e. it returns the last but one node of

    /// a shortest path from a root to \c v. It is \c INVALID if \c v

    /// is not reached from the root(s) or if \c v is a root.

    ///

    /// The shortest path tree used here is equal to the shortest path

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    Node predNode(Node v) const { 

      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 

    }

    /// \brief Returns a const reference to the node map that stores the

    {

      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 conform to the \ref concepts::WriteMap "WriteMap" concept.

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

    ///Instantiates a \c ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

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

    ///we would like to define the \ref ProcessedMap

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(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 conform to the \ref concepts::WriteMap "WriteMap" concept.

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

    ///Instantiates a ProcessedMap.

    ///This function instantiates a ProcessedMap.

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

    ///we would like to define the ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

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

    /// Elevator type with automatic allocation

    ///

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

    /// type with automatic allocation.

    /// The Elevator should have standard constructor interface to be

    /// able to automatically created by the algorithm (i.e. the

    /// digraph and the maximum level should be passed to it).

    /// algorithm with the \ref elevator(Elevator&) "elevator()" function

    /// before calling \ref run() or \ref init().

    /// \sa SetElevator

    template <typename T>

    struct SetStandardElevator

      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,

                       SetStandardElevatorTraits<T> > {

      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,

        /// the nodes; this order has nothing to do with the iteration

        /// ordering of the nodes.

        bool operator<(Node) const { return false; }

      };

      /// Iterator class for the nodes.

      /// This iterator goes through each node of the digraph.

      /// of nodes in a digraph \c g of type \c %Digraph like this:

      ///\code

      /// int count=0;

      /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;

      ///\endcode

      class NodeIt : public Node {

      public:

        /// Default constructor

        /// ordering of the arcs.

        bool operator<(Arc) const { return false; }

      };

      /// Iterator class for the outgoing arcs of a node.

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

      /// of a digraph.

      /// of outgoing arcs of a node \c n

      /// in a digraph \c g of type \c %Digraph as follows.

      ///\code

      /// int count=0;

      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;

      ///\endcode

      class OutArcIt : public Arc {

      public:

        /// outgoing arc of the corresponding node.

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

      };

      /// Iterator class for the incoming arcs of a node.

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

      /// of a digraph.

      /// of incoming arcs of a node \c n

      /// in a digraph \c g of type \c %Digraph as follows.

      ///\code

      /// int count=0;

      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;

      ///\endcode

      class InArcIt : public Arc {

      public:

        /// Assign the iterator to the next

        /// incoming arc of the corresponding node.

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

      };

      /// Iterator class for the arcs.

      /// This iterator goes through each arc of the digraph.

      /// of arcs in a digraph \c g of type \c %Digraph as follows:

      ///\code

      /// int count=0;

      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;

      ///\endcode

      class ArcIt : public Arc {

      public:

        /// Default constructor

        /// ordering of the items.

        bool operator<(Node) const { return false; }

      };

      /// Iterator class for the nodes.

      /// This iterator goes through each node of the graph.

      /// of nodes in a graph \c g of type \c %Graph like this:

      ///\code

      /// int count=0;

      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;

      ///\endcode

      class NodeIt : public Node {

      public:

        /// Default constructor

        /// the edges; this order has nothing to do with the iteration

        /// ordering of the edges.

        bool operator<(Edge) const { return false; }

      };

      /// Iterator class for the edges.

      /// This iterator goes through each edge of the graph.

      /// of edges in a graph \c g of type \c %Graph as follows:

      ///\code

      /// int count=0;

      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;

      ///\endcode

      class EdgeIt : public Edge {

      public:

        /// Default constructor

        ///

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

      };

      /// Iterator class for the incident edges of a node.

      /// This iterator goes trough the incident undirected edges

      /// of a certain node of a graph.

      /// degree (i.e. the number of incident edges) of a node \c n

      /// in a graph \c g of type \c %Graph as follows.

      ///

      ///\code

      /// int count=0;

      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;

      ///\endcode

      ///

        /// Converison to \c Edge.

        ///

        operator Edge() const { return Edge(); }

      };

      /// Iterator class for the arcs.

      /// This iterator goes through each directed arc of the graph.

      /// of arcs in a graph \c g of type \c %Graph as follows:

      ///\code

      /// int count=0;

      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;

      ///\endcode

      class ArcIt : public Arc {

      public:

        /// Default constructor

        ///

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

      };

      /// Iterator class for the outgoing arcs of a node.

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

      /// certain node of a graph.

      /// of outgoing arcs of a node \c n

      /// in a graph \c g of type \c %Graph as follows.

      ///\code

      /// int count=0;

      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;

      ///\endcode

      class OutArcIt : public Arc {

      public:

        /// outgoing arc of the corresponding node.

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

      };

      /// Iterator class for the incoming arcs of a node.

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

      /// certain node of a graph.

      /// of incoming arcs of a node \c n

      /// in a graph \c g of type \c %Graph as follows.

      ///\code

      /// int count=0;

      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;

      ///\endcode

      class InArcIt : public Arc {

      public:

          return *this;

        }

      };

      /// \brief The first node of the edge.

      ///

      /// Returns the first node of the given edge.

      ///

      /// u() and v() are used to query the two end-nodes of an edge.

      /// The orientation of an edge that arises this way is called

      /// the inherent direction, it is used to define the default

      /// direction for the corresponding arcs.

      /// \sa v()

      /// \sa direction()

      Node u(Edge) const { return INVALID; }

      /// \brief The second node of the edge.

      ///

      /// Returns the second node of the given edge.

      ///

      /// u() and v() are used to query the two end-nodes of an edge.

      /// The orientation of an edge that arises this way is called

      /// the inherent direction, it is used to define the default

      /// direction for the corresponding arcs.

      /// \sa u()

      /// \sa direction()

      Node v(Edge) const { return INVALID; }

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

///\file

#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H

#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H

#include <lemon/core.h>

#include <lemon/concepts/maps.h>

#include <lemon/bits/alteration_notifier.h>

    /// "NoSubCounter"s along with the main counter.

    void reset(int c=0) {count=c;}

    /// Returns the value of the counter.

    operator int() {return count;}

  };

  /// 'Do nothing' version of Counter.

  /// does not count at all and does not print report on destruction.

  ///

  /// Replacing a \ref Counter with a \ref NoCounter makes it possible

  /// to turn off all counting and reporting (SubCounters should also

  /// be replaced with NoSubCounters), so it does not affect the

  /// efficiency of the program at all.

  ///

  /// \sa Counter

    {

      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 conform to the \ref concepts::WriteMap "WriteMap" concept.

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

    ///Instantiates a \c ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

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

    ///we would like to define the \ref ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(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 conform to the \ref concepts::WriteMap "WriteMap" concept.

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

    ///Instantiates a ProcessedMap.

    ///This function instantiates a ProcessedMap.

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

    ///we would like to define the ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(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 conform to the \ref concepts::WriteMap "WriteMap" concept.

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

    ///Instantiates a \c ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

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

    ///we would like to define the \ref ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

    ///heap and cross reference types with automatic allocation

    ///

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

    ///reference types with automatic allocation.

    ///They should have standard constructor interfaces to be able to

    ///automatically created by the algorithm (i.e. the digraph should be

    ///passed to the constructor of the cross reference and the cross

    ///reference should be passed to the constructor of the heap).

    ///passed to the algorithm using the \ref heap() function before

    ///calling \ref run(Node) "run()" or \ref init().

    ///\sa SetHeap

    template <class H, class CR = typename Digraph::template NodeMap<int> >

    struct SetStandardHeap

      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {

      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >

      Create;

      typedef T OperationTraits;

    };

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

    ///\c OperationTraits type

    ///

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

    ///\c OperationTraits type.

    template <class T>

    struct SetOperationTraits

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

      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >

      Create;

    };

    ///@}

    {

      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 conform to the \ref concepts::WriteMap "WriteMap" concept.

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

    ///Instantiates a ProcessedMap.

    ///This function instantiates a ProcessedMap.

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

    ///we would like to define the ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

    /// \param cutMap The cut will be returned in this map.

    /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap

    /// "ReadWriteMap" on the graph nodes.

    ///

    /// \return The value of the minimum cut between \c s and \c t.

    ///

    /// \pre \ref run() must be called before using this function.

    template <typename CutMap>

                    const Node& t,

                    CutMap& cutMap

                    ) const {

      Node sn = s, tn = t;

      bool s_root=false;

      Node rn = INVALID;

      Value value = std::numeric_limits<Value>::max();

      while (sn != tn) {

	if ((*_order)[sn] < (*_order)[tn]) {

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, true);

                   /// \endcode

                   /// and

                   /// \code

                   /// MinCutNodeIt(gomory, t, s, false);

                   /// \endcode

                   /// does not necessarily give the same set of nodes.

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, true);

                   /// \endcode

                   /// and

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, false);

                   /// \endcode

                   /// together list each node exactly once.

  bool _negY;

  bool _preScale;

  ///Constructor

  ///Constructor

  ///\param gr  Reference to the graph to be printed.

  ///\param ost Reference to the output stream.

  ///\param pros If it is \c true, then the \c ostream referenced by \c os

  ///will be explicitly deallocated by the destructor.

  DefaultGraphToEpsTraits(const GR &gr, std::ostream& ost = std::cout,

                          bool pros = false) :

    g(gr), os(ost),

    _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0),

    _nodeColors(WHITE), _arcColors(BLACK),

    _arcWidths(1.0), _arcWidthScale(0.003),

  ///Negates the Y coordinates.

  GraphToEps<T> &negateY(bool b=true) {

    _negY=b;return *this;

  }

  ///Turn on/off pre-scaling

  ///very big or very small bounding boxes.

  ///

  ///This (p)rescaling can be turned off with this function.

  ///

  GraphToEps<T> &preScale(bool b=true) {

    _preScale=b;return *this;

  }

///Generates an EPS file from a graph

///\ingroup eps_io

///Generates an EPS file from a graph.

///\param g Reference to the graph to be printed.

///\param os Reference to the output stream.

///

///This function also has a lot of

///\ref named-templ-func-param "named parameters",

///they are declared as the members of class \ref GraphToEps. The following

///example shows how to use these parameters.

///\code

/// graphToEps(g,os).scale(10).coords(coords)

///              .nodeScale(2).nodeSizes(sizes)

///              .arcWidthScale(.4).run();

///\endcode

///

///

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

///to the end of the parameter list.

///\sa GraphToEps

///\sa graphToEps(GR &g, const char *file_name)

template<class GR>

GraphToEps<DefaultGraphToEpsTraits<GR> >

graphToEps(GR &g, std::ostream& os=std::cout)

  ///

  /// \brief Hypercube graph class

  ///

  /// HypercubeGraph implements a special graph type. The nodes of the

  /// graph are indexed with integers having at most \c dim binary digits.

  /// Two nodes are connected in the graph if and only if their indices

  /// differ only on one position in the binary form.

  /// This class is completely static and it needs constant memory space.

  /// the structure can be resized using resize().

  ///

  /// This type fully conforms to the \ref concepts::Graph "Graph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  ///

  /// \note The type of the indices is chosen to \c int for efficiency

  /// reasons. Thus the maximum dimension of this implementation is 26

  ///   nodeMap("coordinates", coord_map).

  ///   arcMap("capacity", cap_map).

  ///   node("source", src).

  ///   node("target", trg).

  ///   attribute("caption", caption).

  ///   run();

  ///\endcode

  ///

  /// proper type. If a section has an optional name, then it can be

  /// selected for reading by giving an optional name parameter to the

  /// \c nodes(), \c arcs() or \c attributes() functions.

  ///

  /// The \c useNodes() and \c useArcs() functions are used to tell the reader

  /// that the nodes or arcs should not be constructed (added to the

  /// graph) during the reading, but instead the label map of the items

  /// are given as a parameter of these functions. An

    ///

    /// The first parameter is the type descriptor of the section, the

    /// second is a functor, which takes just one \c std::string

    /// parameter. At the reading process, each line of the section

    /// will be given to the functor object. However, the empty lines

    /// and the comment lines are filtered out, and the leading

    /// whitespaces are trimmed from each processed string.

    ///

    /// integers, which should be inserted into a vector.

    ///\code

    ///  @numbers

    ///  12 45 23

    ///  4

    ///  23 6

    ///\endcode

    ///

    /// added to the digraph.

    bool valid(Arc a) const { return Parent::valid(a); }

    /// Change the target node of an arc

    /// This function changes the target node of the given arc \c a to \c n.

    ///

    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    void changeTarget(Arc a, Node n) {

      Parent::changeTarget(a,n);

    }

    /// Change the source node of an arc

    /// This function changes the source node of the given arc \c a to \c n.

    ///

    ///\note \c InArcIt iterators referencing the changed arc remain

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    void changeSource(Arc a, Node n) {

      Parent::changeSource(a,n);

    }

    /// Reverse the direction of an arc.

    ///

    /// \note After a state is restored, you cannot restore a later state, 

    /// i.e. you cannot add the removed nodes and arcs again using

    /// another Snapshot instance.

    ///

    /// \warning Node and arc deletions and other modifications (e.g.

    /// reversing, contracting, splitting arcs or nodes) cannot be

    /// restored. These events invalidate the snapshot.

    /// making the current snapshot can be removed without invalidating it.

    class Snapshot {

    protected:

      typedef Parent::NodeNotifier NodeNotifier;

      class NodeObserverProxy : public NodeNotifier::ObserverBase {

      public:

    void changeU(Edge e, Node n) {

      Parent::changeU(e,n);

    }

    /// \brief Change the second node of an edge.

    ///

    /// This function changes the second node of the given edge \c e to \c n.

    ///

    ///\note \c EdgeIt iterators referencing the changed edge remain

    ///all other iterators whose base node is the changed node are also

    ///invalidated.

    ///

    ///\warning This functionality cannot be used together with the

    ///Snapshot feature.

    void changeV(Edge e, Node n) {

      Parent::changeV(e,n);

    }

    ///

    /// \note After a state is restored, you cannot restore a later state, 

    /// i.e. you cannot add the removed nodes and edges again using

    /// another Snapshot instance.

    ///

    /// \warning Node and edge deletions and other modifications

    /// (e.g. changing the end-nodes of edges or contracting nodes)

    /// cannot be restored. These events invalidate the snapshot.

    /// making the current snapshot can be removed without invalidating it.

    class Snapshot {

    protected:

      typedef Parent::NodeNotifier NodeNotifier;

      class NodeObserverProxy : public NodeNotifier::ObserverBase {

      public:

      /// \note This operator only have to define some strict ordering of

      /// the items; this order has nothing to do with the iteration

      /// ordering of the items.

      bool operator<(Col c) const  {return _id < c._id;}

    };

    ///Iterator for iterate over the columns of an LP problem

    /// of columns in an LP \c lp:

    ///\code

    /// int count=0;

    /// for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count;

    ///\endcode

    class ColIt : public Col {

      const LpBase *_solver;

    public:

      /// \note This operator only have to define some strict ordering of

      /// the items; this order has nothing to do with the iteration

      /// ordering of the items.

      bool operator<(Row r) const  {return _id < r._id;}

    };

    ///Iterator for iterate over the rows of an LP problem

    /// of rows in an LP \c lp:

    ///\code

    /// int count=0;

    /// for (LpBase::RowIt c(lp); c!=INVALID; ++c) ++count;

    ///\endcode

    class RowIt : public Row {

      const LpBase *_solver;

    public:

  }

  /// \brief Map for storing values for integer keys from the range

  /// <tt>[0..size-1]</tt>.

  ///

  /// This map is essentially a wrapper for \c std::vector. It assigns

  /// values to integer keys from the range <tt>[0..size-1]</tt>.

  /// integers. This map conforms to the \ref concepts::ReferenceMap

  ///

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

  /// function.

  template <typename V>

  class RangeMap : public MapBase<int, V> {

    template <typename V1>

    friend class RangeMap;

  private:

  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"

  /// concept.

  ///

  /// This map is useful if a default value should be assigned to most of

  /// the keys and different values should be assigned only to a few

  /// keys (i.e. the map is "sparse").

  /// The name of this type also refers to this important usage.

  ///

  /// is based on \c std::map, which is a general associative container.

  /// maps.

  ///

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

  /// function.

  template <typename K, typename V, typename Comp = std::less<K> >

  class SparseMap : public MapBase<K, V> {

    template <typename K1, typename V1, typename C1>

    friend class SparseMap;

  };

  /// Returns a \c LoggerBoolMap class

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

  ///

  /// The most important usage of it is storing certain nodes or arcs

  /// that were marked \c true by an algorithm.

  /// order of Dfs algorithm, as the following examples show.

  /// \code

  ///   std::vector<Node> v;

  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);

  /// \endcode

  /// \code

  ///   std::vector<Node> v(countNodes(g));

  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);

  /// \endcode

  ///

  /// \note The container of the iterator must contain enough space

  /// for the elements or the iterator should be an inserter iterator.

  ///

  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so

  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.

  ///

  /// \relates LoggerBoolMap

  template<typename Iterator>

  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {

    return LoggerBoolMap<Iterator>(it);

  }

  /// \c InverseMap or \c operator()(), and the values of the map can be

  /// accessed with an STL compatible forward iterator (\c ValueIt).

  /// 

  /// This map is intended to be used when all associated values are

  /// different (the map is actually invertable) or there are only a few

  /// items with the same value.

  /// Otherwise consider to use \c IterableValueMap, which is more 

  /// suitable and more efficient for such cases. It provides iterators

  /// it does not have \c InverseMap.

  ///

  /// This type is not reference map, so it cannot be modified with

  /// the subscript operator.

  ///

  /// \tparam GR The graph type.

  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or

  /// \c GR::Edge).

  /// This map returns the in-degree of a node. Once it is constructed,

  /// the degrees are stored in a standard \c NodeMap, so each query is done

  /// in constant time. On the other hand, the values are updated automatically

  /// whenever the digraph changes.

  ///

  /// \warning Besides \c addNode() and \c addArc(), a digraph structure

  /// may provide alternative ways to modify the digraph.

  /// The correct behavior of InDegMap is not guarantied if these additional

  /// \ref ListDigraph::changeSource() "changeSource()",

  /// \ref ListDigraph::changeTarget() "changeTarget()" and

  /// \ref ListDigraph::reverseArc() "reverseArc()"

  /// of \ref ListDigraph will \e not update the degree values correctly.

  ///

  /// \sa OutDegMap

  template <typename GR>

  class InDegMap

  /// This map returns the out-degree of a node. Once it is constructed,

  /// the degrees are stored in a standard \c NodeMap, so each query is done

  /// in constant time. On the other hand, the values are updated automatically

  /// whenever the digraph changes.

  ///

  /// \warning Besides \c addNode() and \c addArc(), a digraph structure

  /// may provide alternative ways to modify the digraph.

  /// The correct behavior of OutDegMap is not guarantied if these additional

  /// \ref ListDigraph::changeSource() "changeSource()",

  /// \ref ListDigraph::changeTarget() "changeTarget()" and

  /// \ref ListDigraph::reverseArc() "reverseArc()"

  /// of \ref ListDigraph will \e not update the degree values correctly.

  ///

  /// \sa InDegMap

  template <typename GR>

  class OutDegMap

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

  /// This algorithm is a specialized version of the linear programming

  /// simplex method directly for the minimum cost flow problem.

  /// It is one of the most efficient solution methods.

  ///

  /// In general this class is the fastest implementation available

  /// in LEMON for the minimum cost flow problem.

  /// Moreover it supports both directions of the supply/demand inequality

  ///

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

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

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

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

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

  /// \tparam C The value type used for costs and potentials in the

  ///

  /// \warning Both value types must be signed and all input data must

  /// be integer.

  ///

  /// \note %NetworkSimplex provides five different pivot rule

  /// implementations, from which the most efficient one is used

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

  class NetworkSimplex

  {

  public:

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

    typedef V Value;

    /// The type of the arc costs

    /// \brief Constants for selecting the pivot rule.

    ///

    /// Enum type containing constants for selecting the pivot rule for

    /// the \ref run() function.

    ///

    /// \ref NetworkSimplex provides five different pivot rule

    /// implementations that significantly affect the running time

    /// of the algorithm.

    /// proved to be the most efficient and the most robust on various

    /// test inputs according to our benchmark tests.

    /// function with the proper parameter.

    enum PivotRule {

      /// The next eligible arc is selected in a wraparound fashion

      /// in every iteration.

      FIRST_ELIGIBLE,

      /// The best eligible arc is selected in every iteration.

      BEST_ELIGIBLE,

      /// A specified number of arcs are examined in every iteration

      /// in a wraparound fashion and the best eligible arc is selected

      /// from this block.

      BLOCK_SEARCH,