RhodeCode

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

///\ingroup demos

///\file

///\brief Argument parser demo

///

/// This example shows how the argument parser can be used.

///

/// \include arg_parser_demo.cc

#include <lemon/arg_parser.h>

using namespace lemon;

int main(int argc, char **argv)

{

  // Initialize the argument parser

  ArgParser ap(argc, argv);

  int i;

  std::string s;

  double d = 1.0;

  bool b, nh;

  bool g1, g2, g3;

  // Add a mandatory integer option with storage reference

  ap.refOption("n", "An integer input.", i, true);

  // Add a double option with storage reference (the default value is 1.0)

  ap.refOption("val", "A double input.", d);

  // Add a double option without storage reference (the default value is 3.14)

  ap.doubleOption("val2", "A double input.", 3.14);

  // Set synonym for -val option

  ap.synonym("vals", "val");

  // Add a string option

  ap.refOption("name", "A string input.", s);

  // Add bool options

  ap.refOption("f", "A switch.", b)

    .refOption("nohelp", "", nh)

    .refOption("gra", "Choice A", g1)

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

namespace lemon {

/**

@defgroup datas Data Structures

This group contains the several data structures implemented in LEMON.

*/

/**

@defgroup graphs Graph Structures

@ingroup datas

\brief Graph structures implemented in LEMON.

The implementation of combinatorial algorithms heavily relies on

efficient graph implementations. LEMON offers data structures which are

planned to be easily used in an experimental phase of implementation studies,

and thereafter the program code can be made efficient by small modifications.

The most efficient implementation of diverse applications require the

usage of different physical graph implementations. These differences

appear in the size of graph we require to handle, memory or time usage

limitations or in the set of operations through which the graph can be

accessed.  LEMON provides several physical graph structures to meet

the diverging requirements of the possible users.  In order to save on

running time or on memory usage, some structures may fail to provide

some graph features like arc/edge or node deletion.

Alteration of standard containers need a very limited number of

operations, these together satisfy the everyday requirements.

In the case of graph structures, different operations are needed which do

not alter the physical graph, but gives another view. If some nodes or

arcs have to be hidden or the reverse oriented graph have to be used, then

this is the case. It also may happen that in a flow implementation

the residual graph can be accessed by another algorithm, or a node-set

is to be shrunk for another algorithm.

LEMON also provides a variety of graphs for these requirements called

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

/**

\mainpage LEMON Documentation

\section intro Introduction

<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling

and <b>O</b>ptimization in <b>N</b>etworks</i>.

It is a C++ template library providing efficient implementations of common

data structures and algorithms with focus on combinatorial optimization

tasks connected mainly with graphs and networks. 

<b>

LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>

project.

You are free to use it in your commercial or

non-commercial applications under very permissive

\ref license "license terms".

</b>

The project is maintained by the 

<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on

Combinatorial Optimization</a> \ref egres

at the Operations Research Department of the

<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,

Budapest, Hungary.

LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>

initiative \ref coinor.

\section howtoread How to Read the Documentation

If you would like to get to know the library, see

<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.

If you are interested in starting to use the library, see the <a class="el"

href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

namespace lemon {

/**

\page min_cost_flow Minimum Cost Flow Problem

\section mcf_def Definition (GEQ form)

The \e minimum \e cost \e flow \e problem is to find a feasible flow of

minimum total cost from a set of supply nodes to a set of demand nodes

in a network with capacity constraints (lower and upper bounds)

and arc costs \ref amo93networkflows.

Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,

\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and

upper bounds for the flow values on the arcs, for which

\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,

\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow

on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the

signed supply values of the nodes.

If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$

supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with

\f$-sup(u)\f$ demand.

A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution

of the following optimization problem.

\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]

\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq

    sup(u) \quad \forall u\in V \f]

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

The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be

zero or negative in order to have a feasible solution (since the sum

of the expressions on the left-hand side of the inequalities is zero).

It means that the total demand must be greater or equal to the total

supply and all the supplies have to be carried out from the supply nodes,

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

#ifndef LEMON_ADAPTORS_H

#define LEMON_ADAPTORS_H

/// \ingroup graph_adaptors

/// \file

/// \brief Adaptor classes for digraphs and graphs

///

/// This file contains several useful adaptors for digraphs and graphs.

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/bits/variant.h>

#include <lemon/bits/graph_adaptor_extender.h>

#include <lemon/bits/map_extender.h>

#include <lemon/tolerance.h>

#include <algorithm>

namespace lemon {

#ifdef _MSC_VER

#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED

#else

#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED

#endif

  template<typename DGR>

  class DigraphAdaptorBase {

  public:

    typedef DGR Digraph;

    typedef DigraphAdaptorBase Adaptor;

  protected:

    DGR* _digraph;

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

#include <lemon/arg_parser.h>

namespace lemon {

  void ArgParser::_terminate(ArgParserException::Reason reason) const

  {

    if(_exit_on_problems)

      exit(1);

    else throw(ArgParserException(reason));

  }

  void ArgParser::_showHelp(void *p)

  {

    (static_cast<ArgParser*>(p))->showHelp();

    (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);

  }

  ArgParser::ArgParser(int argc, const char * const *argv)

    :_argc(argc), _argv(argv), _command_name(argv[0]),

    _exit_on_problems(true) {

    funcOption("-help","Print a short help message",_showHelp,this);

    synonym("help","-help");

    synonym("h","-help");

  }

  ArgParser::~ArgParser()

  {

    for(Opts::iterator i=_opts.begin();i!=_opts.end();++i)

      if(i->second.self_delete)

        switch(i->second.type) {

        case BOOL:

          delete i->second.bool_p;

          break;

        case STRING:

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

#ifndef LEMON_ARG_PARSER_H

#define LEMON_ARG_PARSER_H

#include <vector>

#include <map>

#include <list>

#include <string>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <lemon/assert.h>

///\ingroup misc

///\file

///\brief A tool to parse command line arguments.

namespace lemon {

  ///Exception used by ArgParser

  class ArgParserException : public Exception {

  public:

    enum Reason {

      HELP,         /// <tt>--help</tt> option was given

      UNKNOWN_OPT,  /// Unknown option was given

      INVALID_OPT   /// Invalid combination of options

    };

  private:

    Reason _reason;

  public:

    ///Constructor

    ArgParserException(Reason r) throw() : _reason(r) {}

    ///Virtual destructor

    virtual ~ArgParserException() throw() {}

 *

 *

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

#define LEMON_BELLMAN_FORD_H

/// \ingroup shortest_path

/// \file

/// \brief Bellman-Ford 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/tolerance.h>

#include <lemon/path.h>

#include <limits>

namespace lemon {

  /// \brief Default operation traits for the BellmanFord algorithm class.

  ///  

  /// This operation traits class defines all computational operations

  /// and constants that are used in the Bellman-Ford algorithm.

  /// The default implementation is based on the \c numeric_limits class.

  /// If the numeric type does not have infinity value, then the maximum

  /// value is used as extremal infinity value.

  ///

  /// \see BellmanFordToleranceOperationTraits

  template <

    typename V, 

    bool has_inf = std::numeric_limits<V>::has_infinity>

  struct BellmanFordDefaultOperationTraits {

    /// \brief Value type for the algorithm.

    typedef V Value;

    /// \brief Gives back the zero value of the type.

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

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

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

    ///Instantiates a \c PredMap.

    ///This function instantiates a \ref PredMap.

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

    ///\ref PredMap.

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

    ///By default, it is a NullMap.

    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)

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

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

    ///Instantiates a \c ReachedMap.

    ///This function instantiates a \ref ReachedMap.

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

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

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

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

    ///Instantiates a \c DistMap.

    ///This function instantiates a \ref DistMap.

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

    ///\ref DistMap.

    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.

  ///\tparam TR The traits class that defines various types used by the

  ///algorithm. By default, it is \ref BfsDefaultTraits

  ///"BfsDefaultTraits<GR>".

  ///In most cases, this parameter should not be set directly,

  ///consider to use the named template parameters instead.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

        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 conform to 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

    ///\c DistMap type.

    ///

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

    ///\c DistMap type.

    ///It must conform to 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

    ///\c ReachedMap type.

    ///

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

    ///\c ReachedMap type.

    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

    ///\c ProcessedMap type.

    ///

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

    ///\c ProcessedMap type.

    ///It must conform to 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

    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.

    ///

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

    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.

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

    struct SetStandardProcessedMap :

      public Bfs< Digraph, SetStandardProcessedMapTraits > {

      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;

    };

    ///@}

  public:

  ///Default traits class of bfs() function.

  ///\tparam GR Digraph type.

  template<class GR>

  struct BfsWizardDefaultTraits

  {

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

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

    ///Instantiates a PredMap.

    ///This function instantiates a PredMap.

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

    ///PredMap.

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

    ///By default, it is a NullMap.

    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)

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

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

    ///Instantiates a ReachedMap.

    ///This function instantiates a ReachedMap.

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

    ///we would like to define the ReachedMap.

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

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

    ///Instantiates a DistMap.

    ///This function instantiates a DistMap.

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

    ///the DistMap

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

    ///The type of the shortest paths.

    ///The type of the shortest paths.

    ///It must conform to the \ref concepts::Path "Path" concept.

    typedef lemon::Path<Digraph> Path;

  };

  /// Default traits class used by BfsWizard

  /// Default traits class used by BfsWizard.

  /// \tparam GR The type of the digraph.

  template<class GR>

  class BfsWizardBase : public BfsWizardDefaultTraits<GR>

  {

    typedef BfsWizardDefaultTraits<GR> Base;

  protected:

    //The type of the nodes in the digraph.

    typedef typename Base::Digraph::Node Node;

    //Pointer to the digraph the algorithm runs on.

    void *_g;

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

  template <typename GR>

  struct BfsVisitor {

    typedef GR Digraph;

    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.

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

  template<class GR>

  struct BfsVisitDefaultTraits {

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

    typedef GR Digraph;

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

    ///

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

    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

  ///

  /// \brief BFS algorithm class with visitor interface.

  ///

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

  /// with visitor interface.

  ///

  /// The BfsVisit class provides an alternative interface to the Bfs

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

  ///

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

  /// The default type is \ref ListDigraph.

  /// The value of GR is not used directly by \ref BfsVisit,

  /// it is only passed to \ref BfsVisitDefaultTraits.

  /// \tparam VS The Visitor type that is used by the algorithm.

  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which

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

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

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref BfsVisitDefaultTraits

  /// "BfsVisitDefaultTraits<GR>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

#ifdef DOXYGEN

  template <typename GR, typename VS, typename TR>

#else

  template <typename GR = ListDigraph,

            typename VS = BfsVisitor<GR>,

            typename TR = BfsVisitDefaultTraits<GR> >

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

#ifndef LEMON_BINOMIAL_HEAP_H

#define LEMON_BINOMIAL_HEAP_H

///\file

///\ingroup heaps

///\brief Binomial Heap implementation.

#include <vector>

#include <utility>

#include <functional>

#include <lemon/math.h>

#include <lemon/counter.h>

namespace lemon {

  /// \ingroup heaps

  ///

  ///\brief Binomial heap data structure.

  ///

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

  /// It fully conforms to the \ref concepts::Heap "heap concept".

  ///

  /// The methods \ref increase() and \ref erase() are not efficient

  /// in a binomial heap. In case of many calls of these operations,

  /// it is better to use other heap structure, e.g. \ref BinHeap

  /// "binary heap".

  ///

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

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

  /// internally to handle the cross references.

  /// \tparam CMP A functor class for comparing the priorities.

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

#ifdef DOXYGEN

  template <typename PR, typename IM, typename CMP>

#else

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

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

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

 * purpose.

 *

 */

#ifndef LEMON_BITS_ARRAY_MAP_H

#define LEMON_BITS_ARRAY_MAP_H

#include <memory>

#include <lemon/bits/traits.h>

#include <lemon/bits/alteration_notifier.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

// \ingroup graphbits

// \file

// \brief Graph map based on the array storage.

namespace lemon {

  // \ingroup graphbits

  //

  // \brief Graph map based on the array storage.

  //

  // The ArrayMap template class is graph map structure that automatically

  // updates the map when a key is added to or erased from the graph.

  // This map uses the allocators to implement the container functionality.

  //

  // The template parameters are the Graph, the current Item type and

  // the Value type of the map.

  template <typename _Graph, typename _Item, typename _Value>

  class ArrayMap

    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {

  public:

    // The graph type.

    typedef _Graph GraphType;

    // The item type.

    typedef _Item Item;

    // The reference map tag.

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

 *

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

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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