RhodeCode

SORT_MEMBER_DOCS       = NO

SORT_BRIEF_DOCS        = NO

SORT_GROUP_NAMES       = NO

SORT_BY_SCOPE_NAME     = NO

GENERATE_TODOLIST      = YES

GENERATE_TESTLIST      = YES

GENERATE_BUGLIST       = YES

GENERATE_DEPRECATEDLIST= YES

ENABLED_SECTIONS       = 

MAX_INITIALIZER_LINES  = 5

SHOW_USED_FILES        = YES

SHOW_DIRECTORIES       = YES

FILE_VERSION_FILTER    = 

#---------------------------------------------------------------------------

# configuration options related to warning and progress messages

#---------------------------------------------------------------------------

QUIET                  = NO

WARNINGS               = YES

WARN_IF_UNDOCUMENTED   = YES

WARN_IF_DOC_ERROR      = YES

WARN_NO_PARAMDOC       = NO

WARN_FORMAT            = "$file:$line: $text  "

WARN_LOGFILE           = doxygen.log

#---------------------------------------------------------------------------

# configuration options related to the input files

#---------------------------------------------------------------------------

INPUT                  = @abs_top_srcdir@/doc \

                         @abs_top_srcdir@/lemon \

                         @abs_top_srcdir@/lemon/bits \

                         @abs_top_srcdir@/lemon/concepts \

                         @abs_top_srcdir@/demo \

                         @abs_top_srcdir@/tools \

                         @abs_top_srcdir@/test/test_tools.h

INPUT_ENCODING         = UTF-8

FILE_PATTERNS          = *.h \

                         *.cc \

                         *.dox

RECURSIVE              = NO

EXCLUDE                = 

EXCLUDE_SYMLINKS       = NO

EXCLUDE_PATTERNS       = 

EXCLUDE_SYMBOLS        = 

EXAMPLE_PATH           = @abs_top_srcdir@/demo \

                         @abs_top_srcdir@/LICENSE \

                         @abs_top_srcdir@/doc

EXAMPLE_PATTERNS       = 

EXAMPLE_RECURSIVE      = NO

IMAGE_PATH             = @abs_top_srcdir@/doc/images \

INPUT_FILTER           = 

FILTER_PATTERNS        = 

FILTER_SOURCE_FILES    = NO

#---------------------------------------------------------------------------

# configuration options related to source browsing

#---------------------------------------------------------------------------

SOURCE_BROWSER         = NO

INLINE_SOURCES         = NO

STRIP_CODE_COMMENTS    = YES

REFERENCED_BY_RELATION = NO

REFERENCES_RELATION    = NO

REFERENCES_LINK_SOURCE = YES

USE_HTAGS              = NO

VERBATIM_HEADERS       = NO

#---------------------------------------------------------------------------

# configuration options related to the alphabetical class index

#---------------------------------------------------------------------------

ALPHABETICAL_INDEX     = YES

COLS_IN_ALPHA_INDEX    = 2

IGNORE_PREFIX          = 

#---------------------------------------------------------------------------

# configuration options related to the HTML output

#---------------------------------------------------------------------------

GENERATE_HTML          = YES

HTML_OUTPUT            = html

HTML_FILE_EXTENSION    = .html

HTML_HEADER            = 

HTML_FOOTER            = 

HTML_STYLESHEET        = 

HTML_ALIGN_MEMBERS     = YES

GENERATE_HTMLHELP      = NO

GENERATE_DOCSET        = NO

DOCSET_FEEDNAME        = "Doxygen generated docs"

DOCSET_BUNDLE_ID       = org.doxygen.Project

HTML_DYNAMIC_SECTIONS  = NO

CHM_FILE               = 

HHC_LOCATION           = 

GENERATE_CHI           = NO

BINARY_TOC             = NO

TOC_EXPAND             = NO

DISABLE_INDEX          = NO

ENUM_VALUES_PER_LINE   = 4

GENERATE_TREEVIEW      = YES

TREEVIEW_WIDTH         = 250

#---------------------------------------------------------------------------

# configuration options related to the LaTeX output

#---------------------------------------------------------------------------

GENERATE_LATEX         = NO

 *

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

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

 * purpose.

 *

 */

namespace lemon {

/*!

\page lgf-format Lemon Graph Format (LGF)

The \e LGF is a <em>column oriented</em>

file format for storing graphs and associated data like

node and edge maps.

Each line with \c '#' first non-whitespace

character is considered as a comment line.

Otherwise the file consists of sections starting with

a header line. The header lines starts with an \c '@' character followed by the

type of section. The standard section types are \c \@nodes, \c

\@arcs and \c \@edges

and \@attributes. Each header line may also have an optional

\e name, which can be use to distinguish the sections of the same

type.

The standard sections are column oriented, each line consists of

<em>token</em>s separated by whitespaces. A token can be \e plain or

\e quoted. A plain token is just a sequence of non-whitespace characters,

while a quoted token is a

character sequence surrounded by double quotes, and it can also

contain whitespaces and escape sequences.

The \c \@nodes section describes a set of nodes and associated

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

The following

non-empty lines until the next section describes nodes of the

graph. Each line contains the values of the node maps

associated to the current node.

\code

 @nodes

\endcode

The \c \@arcs section is very similar to the \c \@nodes section,

it again starts with a header line describing the names of the maps,

but the \c "label" map is not obligatory here. The following lines

describe the arcs. The first two tokens of each line are

the source and the target node of the arc, respectively, then come the map

values. The source and target tokens must be node labels.

\code

 @arcs

 1   2   16

 1   3   12

 2   3   18

\endcode

The \c \@edges is just a synonym of \c \@arcs. The @arcs section can

also store the edge set of an undirected graph. In such case there is

a conventional method for store arc maps in the file, if two columns

has the same caption with \c '+' and \c '-' prefix, then these columns

can be regarded as the values of an arc map.

The \c \@attributes section contains key-value pairs, each line

consists of two tokens, an attribute name, and then an attribute

value. The value of the attribute could be also a label value of a

node or an edge, or even an edge label prefixed with \c '+' or \c '-',

which regards to the forward or backward directed arc of the

corresponding edge.

\code

 @attributes

 source 1

 target 3

 caption "LEMON test digraph"

\endcode

The \e LGF can contain extra sections, but there is no restriction on

the format of such sections.

*/

}

//  LocalWords:  whitespace whitespaces

/// \ingroup exceptions

/// \file

/// \brief Extended assertion handling

#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

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

#error "LEMON assertion system is not set properly"

#endif

   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

///     void custom_assert_handler(const char* file, int line,

///                                const char* function, const char* message,

///                                const char* assertion);

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

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

  (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

    LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                            \

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

        LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                        \

                             #exp), 0)))

                             static_cast<const char*>(0)))

#    if LEMON_ENABLE_DEBUG

#      define LEMON_DEBUG(exp, msg)

                                #exp), 0)))

#    else

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

#    endif

#  endif

#endif

      typedef _Digraph Digraph;

      /// Arc type of the underlying digraph.

      typedef typename Digraph::Arc Arc;

      class ArcIt;

      /// \brief Default constructor

      Path() {}

      /// \brief Template constructor

      template <typename CPath>

      Path(const CPath& cpath) {}

      /// \brief Template assigment

      template <typename CPath>

      Path& operator=(const CPath& cpath) {}

      /// Length of the path ie. the number of arcs in the path.

      int length() const { return 0;}

      /// Returns whether the path is empty.

      bool empty() const { return true;}

      /// Resets the path to an empty path.

      void clear() {}

      /// \brief Lemon style iterator for path arcs

      ///

      /// This class is used to iterate on the arcs of the paths.

      class ArcIt {

      public:

        /// Default constructor

        ArcIt() {}

        /// Invalid constructor

        ArcIt(Invalid) {}

        /// Constructor for first arc

        ArcIt(const Path &) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

        ArcIt& operator++() {return *this;}

        /// Comparison operator

        bool operator==(const ArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const ArcIt&) const {return true;}

      };

      template <typename _Path>

      struct Constraints {

        void constraints() {

          Path<Digraph> pc;

          _Path p, pp(pc);

          int l = p.length();

          int e = p.empty();

          p.clear();

          p = pc;

          typename _Path::ArcIt id, ii(INVALID), i(p);

          ++i;

          typename Digraph::Arc ed = i;

          e = (i == ii);

          e = (i != ii);

          e = (i < ii);

          ignore_unused_variable_warning(l);

          ignore_unused_variable_warning(pp);

          ignore_unused_variable_warning(e);

          ignore_unused_variable_warning(id);

          ignore_unused_variable_warning(ii);

          ignore_unused_variable_warning(ed);

        }

      };

    };

    namespace _path_bits {

      template <typename _Digraph, typename _Path, typename RevPathTag = void>

      struct PathDumperConstraints {

        void constraints() {

          int l = p.length();

          int e = p.empty();

          typename _Path::ArcIt id, i(p);

          ++i;

          typename _Digraph::Arc ed = i;

          e = (i == INVALID);

    /// The paths can be constructed from any path type by a

    /// template constructor or a template assignment operator.

    ///

    template <typename _Digraph>

    class PathDumper {

    public:

      /// Type of the underlying digraph.

      typedef _Digraph Digraph;

      /// Arc type of the underlying digraph.

      typedef typename Digraph::Arc Arc;

      /// Length of the path ie. the number of arcs in the path.

      int length() const { return 0;}

      /// Returns whether the path is empty.

      bool empty() const { return true;}

      /// \brief Forward or reverse dumping

      ///

      /// If the RevPathTag is defined and true then reverse dumping

      /// is provided in the path dumper. In this case instead of the

      /// ArcIt the RevArcIt iterator should be implemented in the

      /// dumper.

      typedef False RevPathTag;

      /// \brief Lemon style iterator for path arcs

      ///

      /// This class is used to iterate on the arcs of the paths.

      class ArcIt {

      public:

        /// Default constructor

        ArcIt() {}

        /// Invalid constructor

        ArcIt(Invalid) {}

        /// Constructor for first arc

        ArcIt(const PathDumper&) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

        ArcIt& operator++() {return *this;}

        /// Comparison operator

        bool operator==(const ArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const ArcIt&) const {return true;}

      };

      /// \brief Lemon style iterator for path arcs

      ///

      /// This class is used to iterate on the arcs of the paths in

      /// reverse direction.

      class RevArcIt {

      public:

        /// Default constructor

        RevArcIt() {}

        /// Invalid constructor

        RevArcIt(Invalid) {}

        /// Constructor for first arc

        RevArcIt(const PathDumper &) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

        RevArcIt& operator++() {return *this;}

        /// Comparison operator

        bool operator==(const RevArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const RevArcIt&) const {return true;}

      };

      template <typename _Path>

      struct Constraints {

        void constraints() {

          function_requires<_path_bits::

            PathDumperConstraints<Digraph, _Path> >();

        }

      };

    };

    ///@}

  }

} // namespace lemon

#endif // LEMON_CONCEPT_PATH_H

#include <exception>

#include <string>

#include <sstream>

#include <iostream>

#include <cstdlib>

#include <memory>

namespace lemon {

  /// \addtogroup exceptions

  /// @{

  /// \brief Exception safe wrapper class.

  ///

  /// Exception safe wrapper class to implement the members of exceptions.

  template <typename _Type>

  class ExceptionMember {

  public:

    typedef _Type Type;

    ExceptionMember() throw() {

      try {

        ptr.reset(new Type());

      } catch (...) {}

    }

    ExceptionMember(const Type& type) throw() {

      try {

        ptr.reset(new Type());

        if (ptr.get() == 0) return;

        *ptr = type;

      } catch (...) {}

    }

    ExceptionMember(const ExceptionMember& copy) throw() {

      try {

        if (!copy.valid()) return;

        ptr.reset(new Type());

        if (ptr.get() == 0) return;

        *ptr = copy.get();

      } catch (...) {}

    }

    ExceptionMember& operator=(const ExceptionMember& copy) throw() {

      if (ptr.get() == 0) return;

      try {

        if (!copy.valid()) return;

      } catch (...) {}

    }

    void set(const Type& type) throw() {

      if (ptr.get() == 0) return;

      try {

        *ptr = type;

      } catch (...) {}

    }

    const Type& get() const {

      return *ptr;

    }

    bool valid() const throw() {

      return ptr.get() != 0;

    }

  private:

    std::auto_ptr<_Type> ptr;

  };

  /// Exception-safe convenient error message builder class.

  /// Helper class which provides a convenient ostream-like (operator <<

  /// based) interface to create a string message. Mostly useful in

  /// exception classes (therefore the name).

  class ErrorMessage {

  protected:

    ///\e

    ///\todo The good solution is boost::shared_ptr...

    ///

    mutable std::auto_ptr<std::ostringstream> buf;

    ///\e

    bool init() throw() {

      try {

        buf.reset(new std::ostringstream);

      }

      catch(...) {

        buf.reset();

      }

      return buf.get();

    }

  public:

    os << "\ngsave\n";

    if(_scaleToA4)

      if(bb.height()>bb.width()) {

        double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.height(),

                  (A4WIDTH-2*A4BORDER)/bb.width());

        os << ((A4WIDTH -2*A4BORDER)-sc*bb.width())/2 + A4BORDER << ' '

           << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER

           << " translate\n"

           << sc << " dup scale\n"

           << -bb.left() << ' ' << -bb.bottom() << " translate\n";

      }

      else {

        //\todo Verify centering

        double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(),

                  (A4WIDTH-2*A4BORDER)/bb.height());

        os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' '

           << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER

           << " translate\n"

           << sc << " dup scale\n90 rotate\n"

           << -bb.left() << ' ' << -bb.top() << " translate\n";

        }

    else if(_scale!=1.0) os << _scale << " dup scale\n";

    if(_showArcs) {

      os << "%Arcs:\ngsave\n";

      if(_enableParallel) {

        std::vector<Arc> el;

        for(ArcIt e(g);e!=INVALID;++e)

          if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0

             &&g.source(e)!=g.target(e))

            el.push_back(e);

        std::sort(el.begin(),el.end(),arcLess(g));

        typename std::vector<Arc>::iterator j;

        for(typename std::vector<Arc>::iterator i=el.begin();i!=el.end();i=j) {

          for(j=i+1;j!=el.end()&&isParallel(*i,*j);++j) ;

          double sw=0;

          for(typename std::vector<Arc>::iterator e=i;e!=j;++e)

            sw+=_arcWidths[*e]*_arcWidthScale+_parArcDist;

          sw-=_parArcDist;

          sw/=-2.0;

          dim2::Point<double>

            dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]);

          double l=std::sqrt(dvec.normSquare());

          //\todo better 'epsilon' would be nice here.

          dim2::Point<double> d(dvec/std::max(l,EPSILON));

//           m=dim2::Point<double>(mycoords[g.target(*i)]+

//                                 mycoords[g.source(*i)])/2.0;

//            m=dim2::Point<double>(mycoords[g.source(*i)])+

//             dvec*(double(_nodeSizes[g.source(*i)])/

//                (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)]));

            d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0;

          for(typename std::vector<Arc>::iterator e=i;e!=j;++e) {

            sw+=_arcWidths[*e]*_arcWidthScale/2.0;

            dim2::Point<double> mm=m+rot90(d)*sw/.75;

            if(_drawArrows) {

              int node_shape;

              dim2::Point<double> s=mycoords[g.source(*e)];

              dim2::Point<double> t=mycoords[g.target(*e)];

              double rn=_nodeSizes[g.target(*e)]*_nodeScale;

              node_shape=_nodeShapes[g.target(*e)];

              dim2::Bezier3 bez(s,mm,mm,t);

              double t1=0,t2=1;

              for(int ii=0;ii<INTERPOL_PREC;++ii)

                if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2;

                else t1=(t1+t2)/2;

              dim2::Point<double> apoint=bez((t1+t2)/2);

              rn = _arrowLength+_arcWidths[*e]*_arcWidthScale;

              rn*=rn;

              t2=(t1+t2)/2;t1=0;

              for(int ii=0;ii<INTERPOL_PREC;++ii)

                if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2;

                else t2=(t1+t2)/2;

              dim2::Point<double> linend=bez((t1+t2)/2);

              bez=bez.before((t1+t2)/2);

//               rn=_nodeSizes[g.source(*e)]*_nodeScale;

//               node_shape=_nodeShapes[g.source(*e)];

//               t1=0;t2=1;

//               for(int i=0;i<INTERPOL_PREC;++i)

//                 if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape))

//                   t1=(t1+t2)/2;

//                 else t2=(t1+t2)/2;

//               bez=bez.after((t1+t2)/2);

              os << _arcWidths[*e]*_arcWidthScale << " setlinewidth "

                 << _arcColors[*e].red() << ' '

                 << _arcColors[*e].green() << ' '

                 << _arcColors[*e].blue() << " setrgbcolor newpath\n"

                 << bez.p1.x << ' ' <<  bez.p1.y << " moveto\n"

                 << bez.p2.x << ' ' << bez.p2.y << ' '

                 << bez.p3.x << ' ' << bez.p3.y << ' '

                 << bez.p4.x << ' ' << bez.p4.y << " curveto stroke\n";

              dim2::Point<double> dd(rot90(linend-apoint));

              dd*=(.5*_arcWidths[*e]*_arcWidthScale+_arrowWidth)/

                std::sqrt(dd.normSquare());

              os << "newpath " << psOut(apoint) << " moveto "

                 << psOut(linend+dd) << " lineto "

                 << psOut(linend-dd) << " lineto closepath fill\n";

            }

 * (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_GRAPH_UTILS_H

#define LEMON_GRAPH_UTILS_H

#include <iterator>

#include <vector>

#include <map>

#include <cmath>

#include <algorithm>

#include <lemon/bits/invalid.h>

#include <lemon/bits/utility.h>

#include <lemon/maps.h>

#include <lemon/bits/traits.h>

#include <lemon/bits/alteration_notifier.h>

#include <lemon/bits/default_map.h>

///\ingroup gutils

///\file

///\brief Graph utilities.

namespace lemon {

  /// \addtogroup gutils

  /// @{

  ///Creates convenience typedefs for the digraph types and iterators

  ///This \c \#define creates convenience typedefs for the following types

  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,

  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,

  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.

  ///

  ///\note If the graph type is a dependent type, ie. the graph type depend

  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()

  ///macro.

  typedef Digraph::ArcMap<double> DoubleArcMap

  ///Creates convenience typedefs for the digraph types and iterators

  ///\see DIGRAPH_TYPEDEFS

  ///

  ///\note Use this macro, if the graph type is a dependent type,

  ///ie. the graph type depend on a template parameter.

  typedef typename Digraph::ArcIt ArcIt;                                \

  typedef typename Digraph::template ArcMap<double> DoubleArcMap

  ///Creates convenience typedefs for the graph types and iterators

  ///This \c \#define creates the same convenience typedefs as defined

  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates

  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,

  ///\c DoubleEdgeMap.

  ///

  ///\note If the graph type is a dependent type, ie. the graph type depend

  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()

  ///macro.

  typedef Graph::EdgeMap<double> DoubleEdgeMap

  ///Creates convenience typedefs for the graph types and iterators

  ///\see GRAPH_TYPEDEFS

  ///

  ///\note Use this macro, if the graph type is a dependent type,

  ///ie. the graph type depend on a template parameter.

  typedef typename Graph::EdgeIt EdgeIt;                                \

  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap

  /// \brief Function to count the items in the graph.

  ///

  /// This function counts the items (nodes, arcs etc) in the graph.

  /// The complexity of the function is O(n) because

  /// it iterates on all of the items.

  template <typename Graph, typename Item>

  inline int countItems(const Graph& g) {

    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;

    int num = 0;

    for (ItemIt it(g); it != INVALID; ++it) {

      ++num;

    }

    return num;

  }

  // Node counting:

  namespace _graph_utils_bits {

    template <typename Graph, typename Enable = void>

    struct CountNodesSelector {

      static int count(const Graph &g) {

        return countItems<Graph, typename Graph::Node>(g);

      }

    };

    template <typename Graph>

    struct CountNodesSelector<

      Graph, typename

      enable_if<typename Graph::NodeNumTag, void>::type>

    {

      static int count(const Graph &g) {

        return g.nodeNum();

      }

    };

  }

  /// \brief Function to count the nodes in the graph.

  ///

  /// This function counts the nodes in the graph.

  /// The complexity of the function is O(n) but for some

  /// graph structures it is specialized to run in O(1).

  ///

  /// If the graph contains a \e nodeNum() member function and a

  /// \e NodeNumTag tag then this function calls directly the member

  /// function to query the cardinality of the node set.