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

*/

'not' etc.) or e.g. convert a map to another one of different Value type.

The typical usage of this classes is passing implicit maps to

algorithms.  If a function type algorithm is called then the function

type map adaptors can be used comfortable. For example let's see the

usage of map adaptors with the \c digraphToEps() function.

\code

  Color nodeColor(int deg) {

    if (deg >= 2) {

      return Color(0.5, 0.0, 0.5);

    } else if (deg == 1) {

      return Color(1.0, 0.5, 1.0);

    } else {

      return Color(0.0, 0.0, 0.0);

    }

  }

  Digraph::NodeMap<int> degree_map(graph);

  digraphToEps(graph, "graph.eps")

    .coords(coords).scaleToA4().undirected()

    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))

    .run();

\endcode

The \c functorToMap() function makes an \c int to \c Color map from the

\e nodeColor() function. The \c composeMap() compose the \e degree_map

and the previously created map. The composed map is a proper function to

get the color of each node.

The usage with class type algorithms is little bit harder. In this

case the function type map adaptors can not be used, because the

function map adaptors give back temporary objects.

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

*/

      if(o!=i->second.opts.end()) os<<'|';

    }

  }

  void ArgParser::showHelp(Opts::iterator i)

  {

    if(i->second.help.size()==0||i->second.syn) return;

    std::cerr << "  ";

    show(std::cerr,i);

    std::cerr << std::endl;

    std::cerr << "     " << i->second.help << std::endl;

  }

  void ArgParser::showHelp(std::vector<ArgParser::OtherArg>::iterator i)

  {

    if(i->help.size()==0) return;

    std::cerr << "  " << i->name << std::endl

              << "     " << i->help << std::endl;

  }

  void ArgParser::shortHelp()

  {

    const unsigned int LINE_LEN=77;

    const std::string indent("    ");

    std::cerr << "Usage:\n  " << _command_name;

    int pos=_command_name.size()+2;

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

      std::ostringstream cstr;

      cstr << ' ';

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

      show(cstr,g);

      if(!g->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(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;

  }

}

#include <lemon/error.h>

namespace lemon {

  inline void assert_fail_log(const char *file, int line, const char *function,

                              const char *message, const char *assertion)

  {

    std::cerr << file << ":" << line << ": ";

    if (function)

      std::cerr << function << ": ";

    std::cerr << message;

    if (assertion)

      std::cerr << " (assertion '" << assertion << "' failed)";

    std::cerr << std::endl;

  }

  inline void assert_fail_abort(const char *file, int line,

                                const char *function, const char* message,

                                const char *assertion)

  {

    assert_fail_log(file, line, function, message, assertion);

    std::abort();

  }

  namespace _assert_bits {

    inline const char* cstringify(const std::string& str) {

      return str.c_str();

    }

    inline const char* cstringify(const char* str) {

      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

/* -*- 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_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;