RhodeCode

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

/**

@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

*/

/**

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

    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 {

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

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

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

    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

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

        }

      };

    };

    /// Dereferable map concept

    /// Dereferable map concept.

    ///

    template<typename K, typename T, typename R, typename CR>

    class ReferenceMap : public ReadWriteMap<K,T>

    {

    public:

      /// Tag for reference maps.

      typedef True ReferenceMapTag;

      /// The key type of the map.

      typedef K Key;

      typedef T Value;

      /// The reference type of the map.

      typedef R Reference;

      /// The const reference type of the map.

      typedef CR ConstReference;

    public:

      /// Returns a reference to the value associated with the given key.

      Reference operator[](const Key &) {

        return *static_cast<Value *>(0);

      }

      /// Returns a const reference to the value associated with the given key.

      ConstReference operator[](const Key &) const {

        return *static_cast<Value *>(0);

      }

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

      void set(const Key &k,const Value &t) { operator[](k)=t; }

      template<typename _ReferenceMap>

      struct Constraints {

        void constraints() {

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

    }

  };

  ///%DFS algorithm class.

  ///\ingroup search

  ///This class provides an efficient implementation of the %DFS 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 Dfs, it

  ///is only passed to \ref DfsDefaultTraits.

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

  ///The default traits class is

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

  ///See \ref DfsDefaultTraits for the documentation of

  ///a Dfs traits class.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

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

  /// To make it easier to use Dfs algorithm

  ///we have created a wizard class.

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

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

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

  /// \ref DfsWizard class.

  template<class GR>

  class DfsWizardBase : public DfsWizardDefaultTraits<GR>

  {

    typedef DfsWizardDefaultTraits<GR> Base;

  protected:

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

    }

  };

  /// %DFS Visit algorithm class.

  /// \ingroup search

  /// This class provides an efficient implementation of the %DFS algorithm

  /// with visitor interface.

  ///

  /// The %DfsVisit class provides an alternative interface to the Dfs

  /// class. It works with callback mechanism, the DfsVisit object calls

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

  ///

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

  /// is only passed to \ref DfsDefaultTraits.

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

  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which

  /// does not observe the Dfs events. If you want to observe the dfs

  /// 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 DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".

  /// See \ref DfsVisitDefaultTraits for the documentation of

  /// a Dfs visit traits class.

  ///

  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

            typename _Visitor = DfsVisitor<_Digraph>,

            typename _Traits = DfsDefaultTraits<_Digraph> >

#endif

  class DfsVisit {

  public:

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

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

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

    ///we would like to define the \c 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 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<typename LM::Value> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap.

    static DistMap *createDistMap(const GR &G)

    {

      return new DistMap(G);

    }

  };

  ///%Dijkstra algorithm class.

  /// \ingroup shortest_path

  ///This class provides an efficient implementation of %Dijkstra algorithm.

  ///The arc lengths are passed to the algorithm using a

  ///\ref concepts::ReadMap "ReadMap",

  ///so it is easy to change it to any kind of length.

  ///

  ///The type of the length is determined by the

  ///\ref concepts::ReadMap::Value "Value" of the length map.

  ///

  ///It is also possible to change the underlying priority heap.

  ///

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

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

  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.

  ///\tparam LM This read-only ArcMap determines the lengths of the

  ///arcs. It is read once for each arc, so the map may involve in

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

    ///

    template <class T>

    struct DefProcessedMap

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

      typedef Dijkstra< Digraph,        LengthMap, DefProcessedMapTraits<T> > Create;

    };

    struct DefDigraphProcessedMapTraits : public Traits {

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

      static ProcessedMap *createProcessedMap(const Digraph &G)

      {

        return new ProcessedMap(G);

      }

    };

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

    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.

    ///

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

    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.

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

    template <class T>

    struct DefProcessedMapToBeDefaultMap

      : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {

    };

    template <class H, class CR>

    struct DefHeapTraits : public Traits {

      typedef CR HeapCrossRef;

      typedef H Heap;

      static HeapCrossRef *createHeapCrossRef(const Digraph &) {

        throw UninitializedParameter();

      }

      static Heap *createHeap(HeapCrossRef &)

      {

        throw UninitializedParameter();

      }

    };

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

    ///heap and cross reference type

    ///

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

    ///reference type

    ///

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

    struct DefHeap

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

      typedef Dijkstra< Digraph,        LengthMap, DefHeapTraits<H, CR> > Create;

    ///\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 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,typename LM::Value> 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 DijkstraWizard

  /// To make it easier to use Dijkstra algorithm

  ///we have created a wizard class.

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

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

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

  /// \ref DijkstraWizard class.

  /// \todo More named parameters are required...

  template<class GR,class LM>

  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>

  {

    typedef DijkstraWizardDefaultTraits<GR,LM> Base;

  bool _scaleToA4;

  std::string _title;

  std::string _copyright;

  enum NodeTextColorType

    { DIST_COL=0, DIST_BW=1, CUST_COL=2, SAME_COL=3 } _nodeTextColorType;

  ConstMap<typename Graph::Node,Color > _nodeTextColors;

  bool _autoNodeScale;

  bool _autoArcWidthScale;

  bool _absoluteNodeSizes;

  bool _absoluteArcWidths;

  bool _negY;

  bool _preScale;

  ///Constructor

  ///Constructor

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

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

  ///\param _pros If it is \c true, then the \c ostream referenced by \c _os

  ///will be explicitly deallocated by the destructor.

  DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,

                          bool _pros=false) :

    g(_g), os(_os),

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

    _nodeColors(WHITE), _arcColors(BLACK),

    _arcWidths(1.0), _arcWidthScale(0.003),

    _nodeScale(.01), _xBorder(10), _yBorder(10), _scale(1.0),

    _nodeBorderQuotient(.1),

    _drawArrows(false), _arrowLength(1), _arrowWidth(0.3),

    _showNodes(true), _showArcs(true),

    _enableParallel(false), _parArcDist(1),

    _showNodeText(false), _nodeTexts(false), _nodeTextSize(1),

    _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0),

    _undirected(lemon::UndirectedTagIndicator<G>::value),

    _pleaseRemoveOsStream(_pros), _scaleToA4(false),

    _nodeTextColorType(SAME_COL), _nodeTextColors(BLACK),

    _autoNodeScale(false),

    _autoArcWidthScale(false),

    _absoluteNodeSizes(false),

    _absoluteArcWidths(false),

    _negY(false),

    _preScale(true)

      bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));

    }

    if(_scaleToA4)

      os <<"%%BoundingBox: 0 0 596 842\n%%DocumentPaperSizes: a4\n";

    else {

      if(_preScale) {

        //Rescale so that BoundingBox won't be neither to big nor too small.

        while(bb.height()*_scale>1000||bb.width()*_scale>1000) _scale/=10;

        while(bb.height()*_scale<100||bb.width()*_scale<100) _scale*=10;

      }

      os << "%%BoundingBox: "

         << int(floor(bb.left()   * _scale - _xBorder)) << ' '

         << int(floor(bb.bottom() * _scale - _yBorder)) << ' '

         << int(ceil(bb.right()  * _scale + _xBorder)) << ' '

         << int(ceil(bb.top()    * _scale + _yBorder)) << '\n';

    }

    os << "%%EndComments\n";

    //x1 y1 x2 y2 x3 y3 cr cg cb w

    os << "/lb { setlinewidth setrgbcolor newpath moveto\n"

       << "      4 2 roll 1 index 1 index curveto stroke } bind def\n";

    //x y r

    //x y r

    os << "/sq { newpath 2 index 1 index add 2 index 2 index add moveto\n"

       << "      2 index 1 index sub 2 index 2 index add lineto\n"