RhodeCode

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

 *

 */

/*!

\page coding_style LEMON Coding Style

\section naming_conv Naming Conventions

In order to make development easier we have made some conventions

according to coding style. These include names of types, classes,

functions, variables, constants and exceptions. If these conventions

are met in one's code then it is easier to read and maintain

it. Please comply with these conventions if you want to contribute

developing LEMON library.

\note When the coding style requires the capitalization of an abbreviation,

only the first letter should be upper case.

\code

XmlReader

\endcode

\warning In some cases we diverge from these rules.

This is primary done because STL uses different naming convention and

in certain cases

it is beneficial to provide STL compatible interface.

\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

*/

\code

  Digraph graph;

  typedef Digraph::ArcMap<double> DoubleArcMap;

  DoubleArcMap length(graph);

  DoubleArcMap speed(graph);

  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;

  TimeMap time(length, speed);

  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);

  dijkstra.run(source, target);

\endcode

We have a length map and a maximum speed map on the arcs of a digraph.

The minimum time to pass the arc can be calculated as the division of

the two maps which can be done implicitly with the \c DivMap template

class. We use the implicit minimum time map as the length map of the

\c Dijkstra algorithm.

*/

/**

@defgroup matrices Matrices

@ingroup datas

\brief Two dimensional data storages implemented in LEMON.

This group describes two dimensional data storages implemented in LEMON.

*/

/**

@defgroup paths Path Structures

@ingroup datas

\brief Path structures implemented in LEMON.

This group describes the path structures implemented in LEMON.

LEMON provides flexible data structures to work with paths.

All of them have similar interfaces and they can be copied easily with

assignment operators and copy constructors. This makes it easy and

efficient to have e.g. the Dijkstra algorithm to store its result in

any kind of path structure.

\sa lemon::concepts::Path

*/

/**

@defgroup auxdat Auxiliary Data Structures

@ingroup datas

\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 spantree Minimum Spanning Tree algorithms

@ingroup algs

\brief Algorithms for finding a minimum cost spanning tree in a graph.

This group describes the algorithms for finding a minimum cost spanning

tree in a graph

*/

/**

@defgroup auxalg Auxiliary algorithms

@ingroup algs

\brief Auxiliary algorithms implemented in LEMON.

This group describes some algorithms implemented in LEMON

in order to make it easier to implement complex algorithms.

*/

/**

@defgroup approx Approximation algorithms

\brief Approximation algorithms.

This group describes the approximation and heuristic algorithms

implemented in LEMON.

*/

/**

@defgroup gen_opt_group General Optimization Tools

\brief This group describes some general optimization frameworks

implemented in LEMON.

This group describes some general optimization frameworks

implemented in LEMON.

*/

/**

@defgroup lp_group Lp and Mip solvers

@ingroup gen_opt_group

\brief Lp and Mip solver interfaces for LEMON.

This group describes Lp and Mip solver interfaces for LEMON. The

various LP solvers could be used in the same manner with this

interface.

*/

/**

@defgroup lp_utils Tools for Lp and Mip solvers

@ingroup lp_group

\brief Helper tools to the Lp and Mip solvers.

This group adds some helper tools to general optimization framework

implemented in LEMON.

*/

/**

@defgroup metah Metaheuristics

@ingroup gen_opt_group

\brief Metaheuristics for LEMON library.

This group describes some metaheuristic optimization tools.

*/

/**

@defgroup utils Tools and Utilities

\brief Tools and utilities for programming in LEMON

Tools and utilities for programming in LEMON.

*/

/**

@defgroup gutils Basic Graph Utilities

@ingroup utils

\brief Simple basic graph utilities.

This group describes some simple basic graph utilities.

*/

/**

@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

This group describes the skeletons and concept checking classes of LEMON's

graph structures and helper classes used to implement these.

*/

/* --- Unused group

@defgroup experimental Experimental Structures and Algorithms

This group describes some Experimental structures and algorithms.

The stuff here is subject to change.

*/

/**

\anchor demoprograms

@defgroup demos Demo programs

Some demo programs are listed here. Their full source codes can be found in

the \c demo subdirectory of the source tree.

It order to compile them, use <tt>--enable-demo</tt> configure option when

build the library.

*/

/**

@defgroup tools Standalone utility applications

Some utility applications are listed here.

The standard compilation procedure (<tt>./configure;make</tt>) will compile

them, as well.

*/

        std::cerr << std::endl << indent;

        pos=indent.size();

      }

      std::cerr << cstr.str();

      pos+=cstr.str().size();

    }

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

      if(!i->second.ingroup&&!i->second.syn) {

        std::ostringstream cstr;

        cstr << ' ';

        if(!i->second.mandatory) cstr << '[';

        show(cstr,i);

        if(!i->second.mandatory) cstr << ']';

        if(pos+cstr.str().size()>LINE_LEN) {

          std::cerr << std::endl << indent;

          pos=indent.size();

        }

        std::cerr << cstr.str();

        pos+=cstr.str().size();

      }

    for(std::vector<OtherArg>::iterator i=_others_help.begin();

        i!=_others_help.end();++i)

      {

        std::ostringstream cstr;

        cstr << ' ' << i->name;

        if(pos+cstr.str().size()>LINE_LEN) {

          std::cerr << std::endl << indent;

          pos=indent.size();

        }

        std::cerr << cstr.str();

        pos+=cstr.str().size();

      }

    std::cerr << std::endl;

  }

  void ArgParser::showHelp()

  {

    shortHelp();

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

    for(std::vector<OtherArg>::iterator i=_others_help.begin();

        i!=_others_help.end();++i) showHelp(i);

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

    exit(1);

  }

  void ArgParser::unknownOpt(std::string arg)

  {

    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);

          }

          p.set = true;

        }

      }

    }

    checkMandatories();

    return *this;

  }

}

      return str;

    }

  }

}

#endif // LEMON_ASSERT_H

#undef LEMON_ASSERT

#undef LEMON_FIXME

#undef LEMON_DEBUG

#if (defined(LEMON_ASSERT_LOG) ? 1 : 0) +                \

  (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +                \

  (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1

#error "LEMON assertion system is not set properly"

#endif

#if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) +                \

     (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +                \

     (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 ||        \

     defined(LEMON_ENABLE_ASSERTS)) &&                        \

  (defined(LEMON_DISABLE_ASSERTS) ||                        \

   defined(NDEBUG))

#error "LEMON assertion system is not set properly"

#endif

#if defined LEMON_ASSERT_LOG

#  undef LEMON_ASSERT_HANDLER

#  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_log

#elif defined LEMON_ASSERT_ABORT

#  undef LEMON_ASSERT_HANDLER

#  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort

#elif defined LEMON_ASSERT_CUSTOM

#  undef LEMON_ASSERT_HANDLER

#  ifndef LEMON_CUSTOM_ASSERT_HANDLER

#    error "LEMON_CUSTOM_ASSERT_HANDLER is not set"

#  endif

#  define LEMON_ASSERT_HANDLER LEMON_CUSTOM_ASSERT_HANDLER

#elif defined LEMON_DISABLE_ASSERTS

#  undef LEMON_ASSERT_HANDLER

#elif defined NDEBUG

#  undef LEMON_ASSERT_HANDLER

#else

#  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort

#endif

#ifndef LEMON_FUNCTION_NAME

#  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

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

#include <lemon/bits/path_dump.h>

#include <lemon/bits/invalid.h>

#include <lemon/error.h>

#include <lemon/maps.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 digraph type the algorithm runs on.

    typedef GR Digraph;

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

    ///arcs of the shortest paths.

    ///

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

    ///arcs of the shortest paths.

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

    ///

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

    ///Instantiates a PredMap.

    ///This function instantiates a \ref PredMap.

    ///\param G is the digraph, to which we would like to define the PredMap.

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

    typedef typename TR::PredMap PredMap;