RhodeCode

\subsection cs-files File Names

The header file names should look like the following.

\code

header_file.h

\endcode

Note that all standard LEMON headers are located in the \c lemon subdirectory,

so you should include them from C++ source like this:

\code

#include <lemon/header_file.h>

\endcode

The source code files use the same style and they have '.cc' extension.

\code

source_code.cc

\endcode

\subsection cs-class Classes and other types

The name of a class or any type should look like the following.

\code

AllWordsCapitalizedWithoutUnderscores

\endcode

\subsection cs-func Methods and other functions

The name of a function should look like the following.

\code

firstWordLowerCaseRestCapitalizedWithoutUnderscores

\endcode

\subsection cs-funcs Constants, Macros

The names of constants and macros should look like the following.

\code

ALL_UPPER_CASE_WITH_UNDERSCORES

\endcode

\subsection cs-loc-var Class and instance member variables, auto variables

\code

all_lower_case_with_underscores

\endcode

\subsection pri-loc-var Private member variables

Private member variables should start with underscore

\code

_start_with_underscores

\endcode

\subsection cs-excep Exceptions

When writing exceptions please comply the following naming conventions.

\code

ClassNameEndsWithException

\endcode

or

\code

ClassNameEndsWithError

\endcode

\section header-template Template Header File

Each LEMON header file should look like this:

\include template.h

*/

\brief Auxiliary data structures implemented in LEMON.

This group describes some data structures implemented in LEMON in

order to make it easier to implement combinatorial algorithms.

*/

/**

@defgroup algs Algorithms

\brief This group describes the several algorithms

implemented in LEMON.

This group describes the several algorithms

implemented in LEMON.

*/

/**

@defgroup search Graph Search

@ingroup algs

\brief Common graph search algorithms.

This group describes the common graph search algorithms like

Breadth-first search (Bfs) and Depth-first search (Dfs).

*/

/**

@defgroup shortest_path Shortest Path algorithms

@ingroup algs

\brief Algorithms for finding shortest paths.

This group describes the algorithms for finding shortest paths in graphs.

*/

/**

@defgroup max_flow Maximum Flow algorithms

@ingroup algs

\brief Algorithms for finding maximum flows.

This group describes the algorithms for finding maximum flows and

feasible circulations.

The maximum flow problem is to find a flow between a single source and

a single target that is maximum. Formally, there is a \f$G=(V,A)\f$

directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity

function and given \f$s, t \in V\f$ source and target node. The

maximum flow is the \f$f_a\f$ solution of the next optimization problem:

\f[ 0 \le f_a \le c_a \f]

\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]

LEMON contains several algorithms for solving maximum flow problems:

- \ref lemon::EdmondsKarp "Edmonds-Karp"

- \ref lemon::Preflow "Goldberg's Preflow algorithm"

- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"

- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"

In most cases the \ref lemon::Preflow "Preflow" algorithm provides the

fastest method to compute the maximum flow. All impelementations

provides functions to query the minimum cut, which is the dual linear

programming problem of the maximum flow.

*/

/**

@defgroup min_cost_flow Minimum Cost Flow algorithms

@ingroup algs

\brief Algorithms for finding minimum cost flows and circulations.

This group describes the algorithms for finding minimum cost flows and

circulations.

*/

/**

@defgroup min_cut Minimum Cut algorithms

@ingroup algs

\brief Algorithms for finding minimum cut in graphs.

This group describes the algorithms for finding minimum cut in graphs.

The minimum cut problem is to find a non-empty and non-complete

\f$X\f$ subset of the vertices with minimum overall capacity on

outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an

\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum

cut is the \f$X\f$ solution of the next optimization problem:

LEMON contains several algorithms related to minimum cut problems:

- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut

  in directed graphs

- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to

  calculate minimum cut in undirected graphs

- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all

  pairs minimum cut in undirected graphs

If you want to find minimum cut just between two distinict nodes,

please see the \ref max_flow "Maximum Flow page".

*/

/**

@defgroup graph_prop Connectivity and other graph properties

@ingroup algs

\brief Algorithms for discovering the graph properties

This group describes the algorithms for discovering the graph properties

like connectivity, bipartiteness, euler property, simplicity etc.

\image html edge_biconnected_components.png

\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth

*/

/**

@defgroup planar Planarity embedding and drawing

@ingroup algs

\brief Algorithms for planarity checking, embedding and drawing

\image html planar.png

\image latex planar.eps "Plane graph" width=\textwidth

*/

/**

@defgroup matching Matching algorithms

@ingroup algs

\brief Algorithms for finding matchings in graphs and bipartite graphs.

This group contains algorithm objects and functions to calculate

matchings in graphs and bipartite graphs. The general matching problem is

finding a subset of the arcs which does not shares common endpoints.

There are several different algorithms for calculate matchings in

graphs.  The matching problems in bipartite graphs are generally

easier than in general graphs. The goal of the matching optimization

can be the finding maximum cardinality, maximum weight or minimum cost

matching. The search can be constrained to find perfect or

maximum cardinality matching.

Lemon contains the next algorithms:

- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp

  augmenting path algorithm for calculate maximum cardinality matching in

  bipartite graphs

- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel

  algorithm for calculate maximum cardinality matching in bipartite graphs

- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"

  Successive shortest path algorithm for calculate maximum weighted matching

  and maximum weighted bipartite matching in bipartite graph

- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"

  Successive shortest path algorithm for calculate minimum cost maximum

  matching in bipartite graph

- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm

  for calculate maximum cardinality matching in general graph

- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom

  shrinking algorithm for calculate maximum weighted matching in general

  graph

- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"

  Edmond's blossom shrinking algorithm for calculate maximum weighted

  perfect matching in general graph

\image html bipartite_matching.png

\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth

*/

/**

@defgroup misc Miscellaneous Tools

@ingroup utils

\brief Tools for development, debugging and testing.

This group describes several useful tools for development,

debugging and testing.

*/

/**

@defgroup timecount Time measuring and Counting

@ingroup misc

\brief Simple tools for measuring the performance of algorithms.

This group describes simple tools for measuring the performance

of algorithms.

*/

/**

@defgroup graphbits Tools for Graph Implementation

@ingroup utils

\brief Tools to make it easier to create graphs.

This group describes the tools that makes it easier to create graphs and

the maps that dynamically update with the graph changes.

*/

/**

@defgroup exceptions Exceptions

@ingroup utils

\brief Exceptions defined in LEMON.

This group describes the exceptions defined in LEMON.

*/

/**

@defgroup io_group Input-Output

\brief Graph Input-Output methods

This group describes the tools for importing and exporting graphs

and graph related data. Now it supports the LEMON format, the

\c DIMACS format and the encapsulated postscript (EPS) format.

*/

/**

@defgroup lemon_io Lemon Input-Output

@ingroup io_group

\brief Reading and writing \ref lgf-format "Lemon Graph Format".

*/

/**

@defgroup eps_io Postscript exporting

@ingroup io_group

\brief General \c EPS drawer and graph exporter

This group describes general \c EPS drawing methods and special

graph exporting tools.

*/

/**

@defgroup concept Concepts

\brief Skeleton classes and concept checking classes

This group describes the data/algorithm skeletons and concept checking

classes implemented in LEMON.

The purpose of the classes in this group is fourfold.

- These classes contain the documentations of the concepts. In order

  to avoid document multiplications, an implementation of a concept

  simply refers to the corresponding concept class.

- These classes declare every functions, <tt>typedef</tt>s etc. an

  implementation of the concepts should provide, however completely

  without implementations and real data structures behind the

  interface. On the other hand they should provide nothing else. All

  the algorithms working on a data structure meeting a certain concept

  should compile with these classes. (Though it will not run properly,

  of course.) In this way it is easily to check if an algorithm

  doesn't use any extra feature of a certain implementation.

- The concept descriptor classes also provide a <em>checker class</em>

  that makes it possible to check whether a certain implementation of a

  concept indeed provides all the required features.

- Finally, They can serve as a skeleton of a new implementation of a concept.

*/

/**

@defgroup graph_concepts Graph Structure Concepts

@ingroup concept

\brief Skeleton and concept checking classes for graph structures

  {

    std::cerr << "\nUnknown option: " << arg << "\n";

    std::cerr << "\nType '" << _command_name <<

      " --help' to obtain a short summary on the usage.\n\n";

    exit(1);

  }

  void ArgParser::requiresValue(std::string arg, OptType t)

  {

    std::cerr << "Argument '" << arg << "' requires a";

    switch(t) {

    case STRING:

      std::cerr << " string";

      break;

    case INTEGER:

      std::cerr << "n integer";

      break;

    case DOUBLE:

      std::cerr << " floating point";

      break;

    default:

      break;

    }

    std::cerr << " value\n\n";

    showHelp();

  }

  void ArgParser::checkMandatories()

  {

    bool ok=true;

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

      if(i->second.mandatory&&!i->second.set)

        {

          if(ok)

            std::cerr << _command_name

                      << ": The following mandatory arguments are missing.\n";

          ok=false;

          showHelp(i);

        }

    for(Groups::iterator i=_groups.begin();i!=_groups.end();++i)

      if(i->second.mandatory||i->second.only_one)

        {

          int set=0;

          for(GroupData::Opts::iterator o=i->second.opts.begin();

              o!=i->second.opts.end();++o)

            if(_opts.find(*o)->second.set) ++set;

          if(i->second.mandatory&&!set) {

            ok=false;

            for(GroupData::Opts::iterator o=i->second.opts.begin();

                o!=i->second.opts.end();++o)

              showHelp(_opts.find(*o));

          }

          if(i->second.only_one&&set>1) {

            ok=false;

            for(GroupData::Opts::iterator o=i->second.opts.begin();

                o!=i->second.opts.end();++o)

              showHelp(_opts.find(*o));

          }

        }

    if(!ok) {

      std::cerr << "\nType '" << _command_name <<

        " --help' to obtain a short summary on the usage.\n\n";

      exit(1);

    }

  }

  ArgParser &ArgParser::parse()

  {

    for(int ar=1; ar<_argc; ++ar) {

      std::string arg(_argv[ar]);

      if (arg[0] != '-' || arg.size() == 1) {

        _file_args.push_back(arg);

      }

      else {

        Opts::iterator i = _opts.find(arg.substr(1));

        if(i==_opts.end()) unknownOpt(arg);

        else {

          if(i->second.syn) i=_opts.find(i->second.help);

          ParData &p(i->second);

          if (p.type==BOOL) *p.bool_p=true;

          else if (p.type==FUNC) p.func_p.p(p.func_p.data);

          else if(++ar==_argc) requiresValue(arg, p.type);

          else {

            std::string val(_argv[ar]);

            std::istringstream vals(val);

            switch(p.type) {

            case STRING:

              *p.string_p=val;

              break;

            case INTEGER:

              vals >> *p.int_p;

              break;

            case DOUBLE:

              vals >> *p.double_p;

              break;

            default:

              break;

            }

            if(p.type!=STRING&&(!vals||!vals.eof()))

              requiresValue(arg, p.type);

          }

#  if defined __GNUC__

#    define LEMON_FUNCTION_NAME (__PRETTY_FUNCTION__)

#  elif defined _MSC_VER

#    define LEMON_FUNCTION_NAME (__FUNCSIG__)

#  else

#    define LEMON_FUNCTION_NAME (__func__)

#  endif

#endif

#ifdef DOXYGEN

/// \ingroup exceptions

///

/// \brief Macro for assertion with customizable message

///

/// Macro for assertion with customizable message.  \param exp An

/// expression that must be convertible to \c bool.  If it is \c

/// false, then an assertion is raised. The concrete behaviour depends

/// on the settings of the assertion system.  \param msg A <tt>const

/// char*</tt> parameter, which can be used to provide information

/// about the circumstances of the failed assertion.

///

/// The assertions are enabled in the default behaviour.

/// You can disable them with the following code:

/// \code

/// #define LEMON_DISABLE_ASSERTS

/// \endcode

/// or with compilation parameters:

/// \code

/// g++ -DLEMON_DISABLE_ASSERTS

/// make CXXFLAGS='-DLEMON_DISABLE_ASSERTS'

/// \endcode

/// The checking is also disabled when the standard macro \c NDEBUG is defined.

///

/// The LEMON assertion system has a wide range of customization

/// properties. As a default behaviour the failed assertion prints a

/// short log message to the standard error and aborts the execution.

///

/// The following modes can be used in the assertion system:

///

/// - \c LEMON_ASSERT_LOG The failed assertion prints a short log

///   message to the standard error and continues the execution.

/// - \c LEMON_ASSERT_ABORT This mode is similar to the \c

///   LEMON_ASSERT_LOG, but it aborts the program. It is the default

///   behaviour.

/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler

///   function.

///   \code

///   \endcode

///   The name of the function should be defined as the \c

///   LEMON_CUSTOM_ASSERT_HANDLER macro name.

///   \code

///     #define LEMON_CUSTOM_ASSERT_HANDLER custom_assert_handler

///   \endcode

///   Whenever an assertion is occured, the custom assertion

///   handler is called with appropiate parameters.

///

/// The assertion mode can also be changed within one compilation unit.

/// If the macros are redefined with other settings and the

/// \ref lemon/assert.h "assert.h" file is reincluded, then the

/// behaviour is changed appropiately to the new settings.

#  define LEMON_ASSERT(exp, msg)                                        \

  (static_cast<void> (!!(exp) ? 0 : (                                        \

    LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                                \

                         LEMON_FUNCTION_NAME,                                \

                         ::lemon::_assert_bits::cstringify(msg), #exp), 0)))

/// \ingroup exceptions

///

/// \brief Macro for mark not yet implemented features.

///

/// Macro for mark not yet implemented features and outstanding bugs.

/// It is close to be the shortcut of the following code:

/// \code

///   LEMON_ASSERT(false, msg);

/// \endcode

///

/// \see LEMON_ASSERT

#  define LEMON_FIXME(msg)                                                \

  (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,        \

                        static_cast<const char*>(0)))

/// \ingroup exceptions

///

/// \brief Macro for internal assertions

///

/// Macro for internal assertions, it is used in the library to check

/// the consistency of results of algorithms, several pre- and

/// postconditions and invariants. The checking is disabled by

/// default, but it can be turned on with the macro \c

/// LEMON_ENABLE_DEBUG.

/// \code

/// #define LEMON_ENABLE_DEBUG

/// \endcode

/// or with compilation parameters:

/// \code

/// g++ -DLEMON_ENABLE_DEBUG

/// make CXXFLAGS='-DLEMON_ENABLE_DEBUG'

/// \endcode

///

/// This macro works like the \c LEMON_ASSERT macro, therefore the

/// current behaviour depends on the settings of \c LEMON_ASSERT

/// macro.

///

/// \see LEMON_ASSERT

#  define LEMON_DEBUG(exp, msg)                                                \

  (static_cast<void> (!!(exp) ? 0 : (                                        \

    LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                            \

                         LEMON_FUNCTION_NAME,                                \

                         ::lemon::_assert_bits::cstringify(msg), #exp), 0)))

#else

#  ifndef LEMON_ASSERT_HANDLER

#    define LEMON_ASSERT(exp, msg)  (static_cast<void>(0))

#    define LEMON_FIXME(msg) (static_cast<void>(0))

#    define LEMON_DEBUG(exp, msg) (static_cast<void>(0))

#  else

#    define LEMON_ASSERT(exp, msg)                                        \

       (static_cast<void> (!!(exp) ? 0 : (                                \

        LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                        \

                             LEMON_FUNCTION_NAME,                        \

                             ::lemon::_assert_bits::cstringify(msg),        \

                             #exp), 0)))

#    define LEMON_FIXME(msg)                                                \

       (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,        \

                             ::lemon::_assert_bits::cstringify(msg),        \

                             static_cast<const char*>(0)))

#    if LEMON_ENABLE_DEBUG

#      define LEMON_DEBUG(exp, msg)

         (static_cast<void> (!!(exp) ? 0 : (         \

           LEMON_ASSERT_HANDLER(__FILE__, __LINE__,  \

                                LEMON_FUNCTION_NAME, \

                                #exp), 0)))

#    else

#      define LEMON_DEBUG(exp, msg) (static_cast<void>(0))

#    endif

#  endif

#endif

#ifdef DOXYGEN

#else

#endif

    ///\todo The digraph alone may be insufficient to initialize

    static PredMap *createPredMap(const GR &G)

    {

      return new PredMap(G);

    }

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

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

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

    ///\todo named parameter to set this type, function to read and write.

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

    ///Instantiates a 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 GR &g)

#else

    static ProcessedMap *createProcessedMap(const GR &)

#endif

    {

      return new ProcessedMap();

    }

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

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

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

    ///\todo named parameter to set this type, function to read and write.

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

    ///Instantiates a 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 GR &G)

    {

      return new ReachedMap(G);

    }

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

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

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

    ///

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

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap.

    static DistMap *createDistMap(const GR &G)

    {

      return new DistMap(G);

    }

  };

  ///%BFS algorithm class.

  ///\ingroup search

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

  ///

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

  ///\ref ListDigraph. The value of GR is not used directly by Bfs, it

  ///is only passed to \ref BfsDefaultTraits.

  ///\tparam TR Traits class to set various data types used by the algorithm.

  ///The default traits class is

  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".

  ///See \ref BfsDefaultTraits for the documentation of

  ///a Bfs traits class.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

            typename TR=BfsDefaultTraits<GR> >

#endif

  class Bfs {

  public:

    /**

     * \brief \ref Exception for uninitialized parameters.

     *

     * This error represents problems in the initialization

     * of the parameters of the algorithms.

     */

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw() {

        return "lemon::Bfs::UninitializedParameter";

      }

    };

    typedef TR Traits;

    ///The type of the underlying digraph.

    typedef typename TR::Digraph Digraph;

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

    ///arcs of the shortest paths.

#endif

    {

      return new PredMap();

    }

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

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

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

    ///\todo named parameter to set this type, function to read and write.

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

    ///Instantiates a 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 GR &g)

#else

    static ProcessedMap *createProcessedMap(const GR &)

#endif

    {

      return new ProcessedMap();

    }

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

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

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

    ///\todo named parameter to set this type, function to read and write.

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

    ///Instantiates a 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 GR &G)

    {

      return new ReachedMap(G);

    }

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

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

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

    ///

    typedef NullMap<typename Digraph::Node,int> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap.

#ifdef DOXYGEN

    static DistMap *createDistMap(const GR &g)

#else

    static DistMap *createDistMap(const GR &)

#endif

    {

      return new DistMap();

    }

  };

  /// Default traits used by \ref BfsWizard

  /// To make it easier to use Bfs algorithm

  ///we have created a wizard class.

  /// This \ref BfsWizard class needs default traits,

  ///as well as the \ref Bfs class.

  /// The \ref BfsWizardBase is a class to be the default traits of the

  /// \ref BfsWizard class.

  template<class GR>

  class BfsWizardBase : public BfsWizardDefaultTraits<GR>

  {

    typedef BfsWizardDefaultTraits<GR> Base;

  protected:

    /// Type of the nodes in the digraph.

    typedef typename Base::Digraph::Node Node;

    /// Pointer to the underlying digraph.

    void *_g;

    ///Pointer to the map of reached nodes.

    void *_reached;

    ///Pointer to the map of processed nodes.

    void *_processed;

    ///Pointer to the map of predecessors arcs.

    void *_pred;

    ///Pointer to the map of distances.

    void *_dist;

    ///Pointer to the source node.

    Node _source;

    public:

    /// Constructor.

    /// This constructor does not require parameters, therefore it initiates

    /// all of the attributes to default values (0, INVALID).

    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),

                           _dist(0), _source(INVALID) {}

        visitor.examine(arc);

        visitor.start(node);

        visitor.process(node);

      }

      _Visitor& visitor;

    };

  };

#endif

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

  ///

  /// Default traits class of BfsVisit class.

  /// \tparam _Digraph Digraph type.

  template<class _Digraph>

  struct BfsVisitDefaultTraits {

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

    typedef _Digraph Digraph;

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

    ///

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

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

    /// \todo named parameter to set this type, function to read and write.

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

    /// \brief Instantiates a ReachedMap.

    ///

    /// This function instantiates a \ref ReachedMap.

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

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

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  /// \brief %BFS Visit algorithm class.

  ///

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

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

  ///

  /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it

  /// is only passed to \ref BfsDefaultTraits.

  /// \tparam _Visitor The Visitor object for the algorithm. The

  /// \ref BfsVisitor "BfsVisitor<_Digraph>" 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 _Traits Traits class to set various data types used by the

  /// algorithm. The default traits class is

  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".

  /// See \ref BfsVisitDefaultTraits for the documentation of

  /// a Bfs visit traits class.

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

            typename _Visitor = BfsVisitor<_Digraph>,

            typename _Traits = BfsDefaultTraits<_Digraph> >

#endif

  class BfsVisit {

  public:

    /// \brief \ref Exception for uninitialized parameters.

    ///

    /// This error represents problems in the initialization

    /// of the parameters of the algorithms.

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw()

      {

        return "lemon::BfsVisit::UninitializedParameter";

      }

    };

    typedef _Traits Traits;

    typedef typename Traits::Digraph Digraph;

    typedef _Visitor Visitor;

    ///The type of the map indicating which nodes are reached.

    typedef typename Traits::ReachedMap ReachedMap;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

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

 *

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

 *

 * Copyright (C) 2003-2008

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

#define LEMON_CONCEPT_MAPS_H

#include <lemon/bits/utility.h>

#include <lemon/concept_check.h>

///\ingroup concept

///\file

///\brief The concept of maps.

namespace lemon {

  namespace concepts {

    /// \addtogroup concept

    /// @{

    /// Readable map concept

    /// Readable map concept.

    ///

    template<typename K, typename T>

    class ReadMap

    {

    public:

      /// The key type of the map.

      typedef K Key;

      typedef T Value;

      /// Returns the value associated with the given key.

      Value operator[](const Key &) const {

        return *static_cast<Value *>(0);

      }

      template<typename _ReadMap>

      struct Constraints {

        void constraints() {

          Value val = m[key];

          val = m[key];

          typename _ReadMap::Value own_val = m[own_key];

          own_val = m[own_key];

          ignore_unused_variable_warning(key);

          ignore_unused_variable_warning(val);

          ignore_unused_variable_warning(own_key);

          ignore_unused_variable_warning(own_val);

        }

        const Key& key;

        const typename _ReadMap::Key& own_key;

        const _ReadMap& m;

      };

    };

    /// Writable map concept

    /// Writable map concept.

    ///

    template<typename K, typename T>

    class WriteMap

    {

    public:

      /// The key type of the map.

      typedef K Key;

      typedef T Value;

      /// Sets the value associated with the given key.

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

      /// Default constructor.

      WriteMap() {}

      template <typename _WriteMap>

      struct Constraints {

        void constraints() {

          m.set(key, val);

          m.set(own_key, own_val);

          ignore_unused_variable_warning(key);

          ignore_unused_variable_warning(val);

          ignore_unused_variable_warning(own_key);

          ignore_unused_variable_warning(own_val);

        }

        const Key& key;

        const Value& val;

        const typename _WriteMap::Key& own_key;

        const typename _WriteMap::Value& own_val;

        _WriteMap& m;

      };

    };

    /// Read/writable map concept

    /// Read/writable map concept.

    ///

    template<typename K, typename T>

    class ReadWriteMap : public ReadMap<K,T>,

                         public WriteMap<K,T>

    {

    public:

      /// The key type of the map.

      typedef K Key;

      typedef T Value;

      /// Returns the value associated with the given key.

      Value operator[](const Key &) const {

        return *static_cast<Value *>(0);

      }

      /// Sets the value associated with the given key.

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

      template<typename _ReadWriteMap>

      struct Constraints {

        void constraints() {

          checkConcept<ReadMap<K, T>, _ReadWriteMap >();

          checkConcept<WriteMap<K, T>, _ReadWriteMap >();

        }

      };

    };