LEMON/LEMON-main Changeset - r145:95d905b6e33d

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r145:95d905b6e33d

« 144:4e626d
« 140:356930

146:4b42aa »

r145:95d905b6e33d

Tue, 22 Apr 2008 18:52:01

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

6 6 4

merge default

6 files changed with 86 insertions and 31 deletions:

CMakeLists.txt

demo/CMakeLists.txt

lemon/CMakeLists.txt

test/CMakeLists.txt

.hgignore

demo/lgf_demo.cc

lemon/assert.h

lemon/graph_to_eps.h

lemon/path.h

lemon/time_measure.h

benchmark/Makefile

demo/Makefile

doc/Makefile

lemon/Makefile

test/Makefile

tools/Makefile

↑ Collapse diff ↑

CMakeLists.txt

Show inline comments

 		project (LEMON)
 		enable_testing ()
 		add_subdirectory (lemon)
 		add_subdirectory (demo)
 		add_subdirectory (test)

demo/CMakeLists.txt

Show inline comments

 		include_directories (${LEMON_SOURCE_DIR})
 		link_directories (${LEMON_BINARY_DIR}/lemon)
 		set (DEMOS
 		  arg_parser_demo
 		  graph_to_eps_demo
 		  lgf_demo)
 		foreach (DEMO_NAME ${DEMOS})
 		  add_executable (${DEMO_NAME} ${DEMO_NAME}.cc)
 		  target_link_libraries (${DEMO_NAME} lemon)
 		  endforeach (DEMO_NAME)

lemon/CMakeLists.txt

Show inline comments

	1	include_directories (${LEMON_SOURCE_DIR})
	2	add_library (lemon arg_parser.cc base.cc color.cc random.cc)

test/CMakeLists.txt

Show inline comments

 		include_directories (${LEMON_SOURCE_DIR})
 		link_directories (${LEMON_BINARY_DIR}/lemon)
 		set (TESTS
 		  bfs_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dim_test
 		  error_test
 		  graph_test
 		  kruskal_test
 		  maps_test
 		  random_test
 		  path_test
 		  time_measure_test
 		  unionfind_test)
 		foreach (TEST_NAME ${TESTS})
 		  add_executable (${TEST_NAME} ${TEST_NAME}.cc)
 		  target_link_libraries (${TEST_NAME} lemon)
 		  add_test(${TEST_NAME} ${TEST_NAME})
 		endforeach (TEST_NAME)

.hgignore

Show inline comments

 		syntax: glob
 		*.obj
 		*.orig
 		*.rej
 		*~
 		*.o
 		*.log
 		*.lo
 		*.tar.*
 		Makefile.in
 		aclocal.m4
 		config.h.in
 		configure
 		Makefile
 		config.h
 		config.log
 		config.status
 		libtool
 		stamp-h1
 		lemon/lemon.pc
 		lemon/libemon.la
 		lemon/stamp-h2
 		doc/Doxyfile
 		.dirstamp
 		.libs/*
 		.deps/*
 		demo/*.eps
 		syntax: regexp
 		(.*/)?\#[^/]*\#$
 		^doc/html/.*
 		^autom4te.cache/.*
 		^build-aux/.*
 		^objs.*/.*
 		^test/[a-z_]*$
 		^demo/.*_demo$
 		^build/.*
 		CMakeFiles
 		DartTestfile.txt
 		cmake_install.cmake
 		CMakeCache.txt

demo/lgf_demo.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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.
+		 *
 		 */
 		///\ingroup demos
 		///\file
 		///\brief Demonstrating graph input and output
 		///
 		/// This simple demo program gives an example of how to read and write
 		/// a graph and additional maps (on the nodes or the edges) from/to a
 		/// stream.
 		///
 		/// \include reader_writer_demo.cc
 		#include <iostream>
 		#include <lemon/smart_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/lgf_writer.h>
 		#include <lemon/random.h>
 		using namespace lemon;
 		int main(int argc, const char *argv[]) {
 		  const int n = argc > 1 ? std::atoi(argv[1]) : 20;
 		  const int e = argc > 2 ? std::atoi(argv[2]) : static_cast<int>(n * log(n));
+		  const int e = argc > 2 ? std::atoi(argv[2]) : static_cast<int>(n * std::log(double(n)));
 		  const int m = argc > 3 ? std::atoi(argv[3]) : 100;
 		  SmartDigraph digraph;
 		  std::stringstream ss;
 		  try {
 		    typedef SmartDigraph Digraph;
 		    typedef Digraph::Node Node;
 		    typedef Digraph::Arc Arc;
 		    typedef Digraph::ArcIt ArcIt;
 		    typedef Digraph::NodeMap<int> PotentialMap;
 		    typedef Digraph::ArcMap<int> CapacityMap;
 		    typedef Digraph::ArcMap<std::string> NameMap;
 		    Digraph digraph;
 		    PotentialMap potential(digraph);
 		    CapacityMap capacity(digraph);
 		    NameMap name(digraph);
 		    std::vector<Node> nodes;
 		    for (int i = 0; i < n; ++i) {
 		      Node node = digraph.addNode();
 		      potential[node] = rnd[m];
 		      nodes.push_back(node);
+		    }
 		    std::vector<Arc> arcs;
 		    for (int i = 0; i < e; ++i) {
 		      int s = rnd[n];
 		      int t = rnd[n];
 		      int c = rnd[m];
 		      Arc arc = digraph.addArc(nodes[s], nodes[t]);
 		      capacity[arc] = c;
 		      std::ostringstream os;
 		      os << "arc \t" << i << std::endl;
 		      name[arc] = os.str();
 		      arcs.push_back(arc);
+		    }
 		    DigraphWriter<Digraph>(ss, digraph).
 		      nodeMap("potential", potential).
 		      arcMap("capacity", capacity).
 		      arcMap("name", name).
 		      node("source", nodes[0]).
 		      node("target", nodes[1]).
 		      arc("bottleneck", arcs[e / 2]).
 		      attribute("creator", "lemon library").
 		      run();
 		  } catch (DataFormatError& error) {
 		    std::cerr << error.what() << std::endl;
+		  }
 		  try {
 		    typedef SmartDigraph Digraph;
 		    typedef Digraph::Node Node;
 		    typedef Digraph::Arc Arc;
 		    typedef Digraph::ArcIt ArcIt;
 		    typedef Digraph::NodeMap<int> LabelMap;
 		    typedef Digraph::NodeMap<int> PotentialMap;
 		    typedef Digraph::ArcMap<int> CapacityMap;
 		    typedef Digraph::ArcMap<std::string> NameMap;
 		    Digraph digraph;
 		    LabelMap label(digraph);
 		    PotentialMap potential(digraph);
 		    CapacityMap capacity(digraph);
 		    NameMap name(digraph);
 		    Node s, t;
 		    Arc a;
 		    std::string creator;
 		    for (int i = 0; i < n; ++i) {
 		      Node node = digraph.addNode();
 		      label[node] = i;
+		    }
 		    DigraphReader<Digraph>(ss, digraph).
 		      useNodes(label).
 		      nodeMap("potential", potential).
 		      arcMap("capacity", capacity).
 		      arcMap("name", name).
 		      node("source", s).
 		      node("target", t).
 		      arc("bottleneck", a).
 		      attribute("creator", creator).
 		      run();
 		    DigraphWriter<Digraph>(std::cout, digraph).
 		      nodeMap("potential", potential).
 		      arcMap("capacity", capacity).
 		      arcMap("name", name).
 		      node("source", s).
 		      node("target", t).
 		      arc("bottleneck", a).
 		      attribute("creator", creator).
 		      run();
 		  } catch (DataFormatError& error) {
 		    std::cerr << error.what() << std::endl;
+		  }
 		  return 0;
+		}

lemon/assert.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_ASSERT_H
 		#define LEMON_ASSERT_H
 		/// \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
 		#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
 		///     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)					\
 		  (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,	\
 					::lemon::_assert_bits::cstringify(msg),		\
 					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, \
 						::lemon::_assert_bits::cstringify(msg),	\
 						#exp), 0)))
 		#    else
 		#      define LEMON_DEBUG(exp, msg) (static_cast<void>(0))
 		#    endif
 		#  endif
 		#endif
 		#ifdef DOXYGEN
 		#else
 		#endif

lemon/graph_to_eps.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_GRAPH_TO_EPS_H
 		#define LEMON_GRAPH_TO_EPS_H
 		#include<iostream>
 		#include<fstream>
 		#include<sstream>
 		#include<algorithm>
 		#include<vector>
 		#ifndef WIN32
 		#include<sys/time.h>
 		#include<ctime>
 		#else
 		#define WIN32_LEAN_AND_MEAN
 		#define NOMINMAX
 		#include<windows.h>
 		#endif
 		#include<lemon/math.h>
 		#include<lemon/bits/invalid.h>
 		#include<lemon/dim2.h>
 		#include<lemon/maps.h>
 		#include<lemon/color.h>
 		#include<lemon/bits/bezier.h>
 		///\ingroup eps_io
 		///\file
 		///\brief A well configurable tool for visualizing graphs
 		namespace lemon {
 		  namespace _graph_to_eps_bits {
 		    template<class MT>
 		    class _NegY {
 		    public:
 		      typedef typename MT::Key Key;
 		      typedef typename MT::Value Value;
 		      const MT &map;
 		      int yscale;
 		      _NegY(const MT &m,bool b) : map(m), yscale(1-b*2) {}
 		      Value operator[](Key n) { return Value(map[n].x,map[n].y*yscale);}
 		    };
+		  }
 		///Default traits class of \ref GraphToEps
 		///Default traits class of \ref GraphToEps
 		///
 		///\c G is the type of the underlying graph.
 		template<class G>
 		struct DefaultGraphToEpsTraits
+		{
 		  typedef G Graph;
 		  typedef typename Graph::Node Node;
 		  typedef typename Graph::NodeIt NodeIt;
 		  typedef typename Graph::Arc Arc;
 		  typedef typename Graph::ArcIt ArcIt;
 		  typedef typename Graph::InArcIt InArcIt;
 		  typedef typename Graph::OutArcIt OutArcIt;
 		  const Graph &g;
 		  std::ostream& os;
 		  typedef ConstMap<typename Graph::Node,dim2::Point<double> > CoordsMapType;
 		  CoordsMapType _coords;
 		  ConstMap<typename Graph::Node,double > _nodeSizes;
 		  ConstMap<typename Graph::Node,int > _nodeShapes;
 		  ConstMap<typename Graph::Node,Color > _nodeColors;
 		  ConstMap<typename Graph::Arc,Color > _arcColors;
 		  ConstMap<typename Graph::Arc,double > _arcWidths;
 		  double _arcWidthScale;
 		  double _nodeScale;
 		  double _xBorder, _yBorder;
 		  double _scale;
 		  double _nodeBorderQuotient;
 		  bool _drawArrows;
 		  double _arrowLength, _arrowWidth;
 		  bool _showNodes, _showArcs;
 		  bool _enableParallel;
 		  double _parArcDist;
 		  bool _showNodeText;
 		  ConstMap<typename Graph::Node,bool > _nodeTexts;
 		  double _nodeTextSize;
 		  bool _showNodePsText;
 		  ConstMap<typename Graph::Node,bool > _nodePsTexts;
 		  char *_nodePsTextsPreamble;
 		  bool _undirected;
 		  bool _pleaseRemoveOsStream;
 		  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 is a reference to the graph to be printed
 		  ///\param _os is a reference to the output stream.
 		  ///\param _os is a 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.
 		  ///By default it is <tt>std::cout</tt>
 		  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)
 		  {}
 		};
 		///Auxiliary class to implement the named parameters of \ref graphToEps()
 		///Auxiliary class to implement the named parameters of \ref graphToEps()
 		template<class T> class GraphToEps : public T
+		{
 		  // Can't believe it is required by the C++ standard
 		  using T::g;
 		  using T::os;
 		  using T::_coords;
 		  using T::_nodeSizes;
 		  using T::_nodeShapes;
 		  using T::_nodeColors;
 		  using T::_arcColors;
 		  using T::_arcWidths;
 		  using T::_arcWidthScale;
 		  using T::_nodeScale;
 		  using T::_xBorder;
 		  using T::_yBorder;
 		  using T::_scale;
 		  using T::_nodeBorderQuotient;
 		  using T::_drawArrows;
 		  using T::_arrowLength;
 		  using T::_arrowWidth;
 		  using T::_showNodes;
 		  using T::_showArcs;
 		  using T::_enableParallel;
 		  using T::_parArcDist;
 		  using T::_showNodeText;
 		  using T::_nodeTexts;
 		  using T::_nodeTextSize;
 		  using T::_showNodePsText;
 		  using T::_nodePsTexts;
 		  using T::_nodePsTextsPreamble;
 		  using T::_undirected;
 		  using T::_pleaseRemoveOsStream;
 		  using T::_scaleToA4;
 		  using T::_title;
 		  using T::_copyright;
 		  using T::NodeTextColorType;
 		  using T::CUST_COL;
 		  using T::DIST_COL;
 		  using T::DIST_BW;
 		  using T::_nodeTextColorType;
 		  using T::_nodeTextColors;
 		  using T::_autoNodeScale;
 		  using T::_autoArcWidthScale;
 		  using T::_absoluteNodeSizes;
 		  using T::_absoluteArcWidths;
 		  using T::_negY;
 		  using T::_preScale;
 		  // dradnats ++C eht yb deriuqer si ti eveileb t'naC
 		  typedef typename T::Graph Graph;
 		  typedef typename Graph::Node Node;
 		  typedef typename Graph::NodeIt NodeIt;
 		  typedef typename Graph::Arc Arc;
 		  typedef typename Graph::ArcIt ArcIt;
 		  typedef typename Graph::InArcIt InArcIt;
 		  typedef typename Graph::OutArcIt OutArcIt;
 		  static const int INTERPOL_PREC;
 		  static const double A4HEIGHT;
 		  static const double A4WIDTH;
 		  static const double A4BORDER;
 		  bool dontPrint;
 		public:
 		  ///Node shapes
 		  ///Node shapes
 		  ///
 		  enum NodeShapes {
 		    /// = 0
 		    ///\image html nodeshape_0.png
 		    ///\image latex nodeshape_0.eps "CIRCLE shape (0)" width=2cm
 		    CIRCLE=0,
 		    /// = 1
 		    ///\image html nodeshape_1.png
 		    ///\image latex nodeshape_1.eps "SQUARE shape (1)" width=2cm
 		    ///
 		    SQUARE=1,
 		    /// = 2
 		    ///\image html nodeshape_2.png
 		    ///\image latex nodeshape_2.eps "DIAMOND shape (2)" width=2cm
 		    ///
 		    DIAMOND=2,
 		    /// = 3
 		    ///\image html nodeshape_3.png
 		    ///\image latex nodeshape_2.eps "MALE shape (4)" width=2cm
 		    ///
 		    MALE=3,
 		    /// = 4
 		    ///\image html nodeshape_4.png
 		    ///\image latex nodeshape_2.eps "FEMALE shape (4)" width=2cm
 		    ///
 		    FEMALE=4
 		  };
 		private:
 		  class arcLess {
 		    const Graph &g;
 		  public:
 		    arcLess(const Graph &_g) : g(_g) {}
 		    bool operator()(Arc a,Arc b) const
+		    {
 		      Node ai=std::min(g.source(a),g.target(a));
 		      Node aa=std::max(g.source(a),g.target(a));
 		      Node bi=std::min(g.source(b),g.target(b));
 		      Node ba=std::max(g.source(b),g.target(b));
 		      return ai<bi ||
 			(ai==bi && (aa < ba ||
 				    (aa==ba && ai==g.source(a) && bi==g.target(b))));
+		    }
 		  };
 		  bool isParallel(Arc e,Arc f) const
+		  {
 		    return (g.source(e)==g.source(f)&&
 			    g.target(e)==g.target(f)) ||
 		      (g.source(e)==g.target(f)&&
 		       g.target(e)==g.source(f));
+		  }
 		  template<class TT>
 		  static std::string psOut(const dim2::Point<TT> &p)
+		    {
 		      std::ostringstream os;
 		      os << p.x << ' ' << p.y;
 		      return os.str();
+		    }
 		  static std::string psOut(const Color &c)
+		    {
 		      std::ostringstream os;
 		      os << c.red() << ' ' << c.green() << ' ' << c.blue();
 		      return os.str();
+		    }
 		public:
 		  GraphToEps(const T &t) : T(t), dontPrint(false) {};
 		  template<class X> struct CoordsTraits : public T {
 		  typedef X CoordsMapType;
 		    const X &_coords;
 		    CoordsTraits(const T &t,const X &x) : T(t), _coords(x) {}
 		  };
 		  ///Sets the map of the node coordinates
 		  ///Sets the map of the node coordinates.
 		  ///\param x must be a node map with dim2::Point<double> or
 		  ///\ref dim2::Point "dim2::Point<int>" values.
 		  template<class X> GraphToEps<CoordsTraits<X> > coords(const X &x) {
 		    dontPrint=true;
 		    return GraphToEps<CoordsTraits<X> >(CoordsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeSizesTraits : public T {
 		    const X &_nodeSizes;
 		    NodeSizesTraits(const T &t,const X &x) : T(t), _nodeSizes(x) {}
 		  };
 		  ///Sets the map of the node sizes
 		  ///Sets the map of the node sizes
 		  ///\param x must be a node map with \c double (or convertible) values.
 		  template<class X> GraphToEps<NodeSizesTraits<X> > nodeSizes(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeSizesTraits<X> >(NodeSizesTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeShapesTraits : public T {
 		    const X &_nodeShapes;
 		    NodeShapesTraits(const T &t,const X &x) : T(t), _nodeShapes(x) {}
 		  };
 		  ///Sets the map of the node shapes
 		  ///Sets the map of the node shapes.
 		  ///The available shape values
 		  ///can be found in \ref NodeShapes "enum NodeShapes".
 		  ///\param x must be a node map with \c int (or convertible) values.
 		  ///\sa NodeShapes
 		  template<class X> GraphToEps<NodeShapesTraits<X> > nodeShapes(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeShapesTraits<X> >(NodeShapesTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeTextsTraits : public T {
 		    const X &_nodeTexts;
 		    NodeTextsTraits(const T &t,const X &x) : T(t), _nodeTexts(x) {}
 		  };
 		  ///Sets the text printed on the nodes
 		  ///Sets the text printed on the nodes
 		  ///\param x must be a node map with type that can be pushed to a standard
 		  ///ostream.
 		  template<class X> GraphToEps<NodeTextsTraits<X> > nodeTexts(const X &x)
+		  {
 		    dontPrint=true;
 		    _showNodeText=true;
 		    return GraphToEps<NodeTextsTraits<X> >(NodeTextsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodePsTextsTraits : public T {
 		    const X &_nodePsTexts;
 		    NodePsTextsTraits(const T &t,const X &x) : T(t), _nodePsTexts(x) {}
 		  };
 		  ///Inserts a PostScript block to the nodes
 		  ///With this command it is possible to insert a verbatim PostScript
 		  ///block to the nodes.
 		  ///The PS current point will be moved to the centre of the node before
 		  ///the PostScript block inserted.
 		  ///
 		  ///Before and after the block a newline character is inserted so you
 		  ///don't have to bother with the separators.
 		  ///
 		  ///\param x must be a node map with type that can be pushed to a standard
 		  ///ostream.
 		  ///
 		  ///\sa nodePsTextsPreamble()
 		  template<class X> GraphToEps<NodePsTextsTraits<X> > nodePsTexts(const X &x)
+		  {
 		    dontPrint=true;
 		    _showNodePsText=true;
 		    return GraphToEps<NodePsTextsTraits<X> >(NodePsTextsTraits<X>(*this,x));
+		  }
 		  template<class X> struct ArcWidthsTraits : public T {
 		    const X &_arcWidths;
 		    ArcWidthsTraits(const T &t,const X &x) : T(t), _arcWidths(x) {}
 		  };
 		  ///Sets the map of the arc widths
 		  ///Sets the map of the arc widths
 		  ///\param x must be a arc map with \c double (or convertible) values.
 		  template<class X> GraphToEps<ArcWidthsTraits<X> > arcWidths(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<ArcWidthsTraits<X> >(ArcWidthsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeColorsTraits : public T {
 		    const X &_nodeColors;
 		    NodeColorsTraits(const T &t,const X &x) : T(t), _nodeColors(x) {}
 		  };
 		  ///Sets the map of the node colors
 		  ///Sets the map of the node colors
 		  ///\param x must be a node map with \ref Color values.
 		  ///
 		  ///\sa Palette
 		  template<class X> GraphToEps<NodeColorsTraits<X> >
 		  nodeColors(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeColorsTraits<X> >(NodeColorsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeTextColorsTraits : public T {
 		    const X &_nodeTextColors;
 		    NodeTextColorsTraits(const T &t,const X &x) : T(t), _nodeTextColors(x) {}
 		  };
 		  ///Sets the map of the node text colors
 		  ///Sets the map of the node text colors
 		  ///\param x must be a node map with \ref Color values.
 		  ///
 		  ///\sa Palette
 		  template<class X> GraphToEps<NodeTextColorsTraits<X> >
 		  nodeTextColors(const X &x)
+		  {
 		    dontPrint=true;
 		    _nodeTextColorType=CUST_COL;
 		    return GraphToEps<NodeTextColorsTraits<X> >
 		      (NodeTextColorsTraits<X>(*this,x));
+		  }
 		  template<class X> struct ArcColorsTraits : public T {
 		    const X &_arcColors;
 		    ArcColorsTraits(const T &t,const X &x) : T(t), _arcColors(x) {}
 		  };
 		  ///Sets the map of the arc colors
 		  ///Sets the map of the arc colors
 		  ///\param x must be a arc map with \ref Color values.
 		  ///
 		  ///\sa Palette
 		  template<class X> GraphToEps<ArcColorsTraits<X> >
 		  arcColors(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<ArcColorsTraits<X> >(ArcColorsTraits<X>(*this,x));
+		  }
 		  ///Sets a global scale factor for node sizes
 		  ///Sets a global scale factor for node sizes.
 		  ///
 		  /// If nodeSizes() is not given, this function simply sets the node
 		  /// sizes to \c d.  If nodeSizes() is given, but
 		  /// autoNodeScale() is not, then the node size given by
 		  /// nodeSizes() will be multiplied by the value \c d.
 		  /// If both nodeSizes() and autoNodeScale() are used, then the
 		  /// node sizes will be scaled in such a way that the greatest size will be
 		  /// equal to \c d.
 		  /// \sa nodeSizes()
 		  /// \sa autoNodeScale()
 		  GraphToEps<T> &nodeScale(double d=.01) {_nodeScale=d;return *this;}
 		  ///Turns on/off the automatic node width scaling.
 		  ///Turns on/off the automatic node width scaling.
 		  ///
 		  ///\sa nodeScale()
 		  ///
 		  GraphToEps<T> &autoNodeScale(bool b=true) {
 		    _autoNodeScale=b;return *this;
+		  }
 		  ///Turns on/off the absolutematic node width scaling.
 		  ///Turns on/off the absolutematic node width scaling.
 		  ///
 		  ///\sa nodeScale()
 		  ///
 		  GraphToEps<T> &absoluteNodeSizes(bool b=true) {
 		    _absoluteNodeSizes=b;return *this;
+		  }
 		  ///Negates the Y coordinates.
 		  ///Negates the Y coordinates.
 		  ///
 		  GraphToEps<T> &negateY(bool b=true) {
 		    _negY=b;return *this;
+		  }
 		  ///Turn on/off pre-scaling
 		  ///By default graphToEps() rescales the whole image in order to avoid
 		  ///very big or very small bounding boxes.
 		  ///
 		  ///This (p)rescaling can be turned off with this function.
 		  ///
 		  GraphToEps<T> &preScale(bool b=true) {
 		    _preScale=b;return *this;
+		  }
 		  ///Sets a global scale factor for arc widths
 		  /// Sets a global scale factor for arc widths.
 		  ///
 		  /// If arcWidths() is not given, this function simply sets the arc
 		  /// widths to \c d.  If arcWidths() is given, but
 		  /// autoArcWidthScale() is not, then the arc withs given by
 		  /// arcWidths() will be multiplied by the value \c d.
 		  /// If both arcWidths() and autoArcWidthScale() are used, then the
 		  /// arc withs will be scaled in such a way that the greatest width will be
 		  /// equal to \c d.
 		  GraphToEps<T> &arcWidthScale(double d=.003) {_arcWidthScale=d;return *this;}
 		  ///Turns on/off the automatic arc width scaling.
 		  ///Turns on/off the automatic arc width scaling.
 		  ///
 		  ///\sa arcWidthScale()
 		  ///
 		  GraphToEps<T> &autoArcWidthScale(bool b=true) {
 		    _autoArcWidthScale=b;return *this;
+		  }
 		  ///Turns on/off the absolutematic arc width scaling.
 		  ///Turns on/off the absolutematic arc width scaling.
 		  ///
 		  ///\sa arcWidthScale()
 		  ///
 		  GraphToEps<T> &absoluteArcWidths(bool b=true) {
 		    _absoluteArcWidths=b;return *this;
+		  }
 		  ///Sets a global scale factor for the whole picture
 		  ///Sets a global scale factor for the whole picture
 		  ///
 		  GraphToEps<T> &scale(double d) {_scale=d;return *this;}
 		  ///Sets the width of the border around the picture
 		  ///Sets the width of the border around the picture
 		  ///
 		  GraphToEps<T> &border(double b=10) {_xBorder=_yBorder=b;return *this;}
 		  ///Sets the width of the border around the picture
 		  ///Sets the width of the border around the picture
 		  ///
 		  GraphToEps<T> &border(double x, double y) {
 		    _xBorder=x;_yBorder=y;return *this;
+		  }
 		  ///Sets whether to draw arrows
 		  ///Sets whether to draw arrows
 		  ///
 		  GraphToEps<T> &drawArrows(bool b=true) {_drawArrows=b;return *this;}
 		  ///Sets the length of the arrowheads
 		  ///Sets the length of the arrowheads
 		  ///
 		  GraphToEps<T> &arrowLength(double d=1.0) {_arrowLength*=d;return *this;}
 		  ///Sets the width of the arrowheads
 		  ///Sets the width of the arrowheads
 		  ///
 		  GraphToEps<T> &arrowWidth(double d=.3) {_arrowWidth*=d;return *this;}
 		  ///Scales the drawing to fit to A4 page
 		  ///Scales the drawing to fit to A4 page
 		  ///
 		  GraphToEps<T> &scaleToA4() {_scaleToA4=true;return *this;}
 		  ///Enables parallel arcs
 		  ///Enables parallel arcs
 		  GraphToEps<T> &enableParallel(bool b=true) {_enableParallel=b;return *this;}
 		  ///Sets the distance
 		  ///Sets the distance
 		  ///
 		  GraphToEps<T> &parArcDist(double d) {_parArcDist*=d;return *this;}
 		  ///Hides the arcs
 		  ///Hides the arcs
 		  ///
 		  GraphToEps<T> &hideArcs(bool b=true) {_showArcs=!b;return *this;}
 		  ///Hides the nodes
 		  ///Hides the nodes
 		  ///
 		  GraphToEps<T> &hideNodes(bool b=true) {_showNodes=!b;return *this;}
 		  ///Sets the size of the node texts
 		  ///Sets the size of the node texts
 		  ///
 		  GraphToEps<T> &nodeTextSize(double d) {_nodeTextSize=d;return *this;}
 		  ///Sets the color of the node texts to be different from the node color
 		  ///Sets the color of the node texts to be as different from the node color
 		  ///as it is possible
 		  ///
 		  GraphToEps<T> &distantColorNodeTexts()
 		  {_nodeTextColorType=DIST_COL;return *this;}
 		  ///Sets the color of the node texts to be black or white and always visible.
 		  ///Sets the color of the node texts to be black or white according to
 		  ///which is more
 		  ///different from the node color
 		  ///
 		  GraphToEps<T> &distantBWNodeTexts()
 		  {_nodeTextColorType=DIST_BW;return *this;}
 		  ///Gives a preamble block for node Postscript block.
 		  ///Gives a preamble block for node Postscript block.
 		  ///
 		  ///\sa nodePsTexts()
 		  GraphToEps<T> & nodePsTextsPreamble(const char *str) {
 		    _nodePsTextsPreamble=str ;return *this;
+		  }
 		  ///Sets whether the the graph is undirected
 		  ///Sets whether the the graph is undirected.
 		  ///
 		  ///This setting is the default for undirected graphs.
 		  ///
 		  ///\sa directed()
 		   GraphToEps<T> &undirected(bool b=true) {_undirected=b;return *this;}
 		  ///Sets whether the the graph is directed
 		  ///Sets whether the the graph is directed.
 		  ///Use it to show the edges as a pair of directed ones.
 		  ///
 		  ///This setting is the default for digraphs.
 		  ///
 		  ///\sa undirected()
 		  GraphToEps<T> &directed(bool b=true) {_undirected=!b;return *this;}
 		  ///Sets the title.
 		  ///Sets the title of the generated image,
 		  ///namely it inserts a <tt>%%Title:</tt> DSC field to the header of
 		  ///the EPS file.
 		  GraphToEps<T> &title(const std::string &t) {_title=t;return *this;}
 		  ///Sets the copyright statement.
 		  ///Sets the copyright statement of the generated image,
 		  ///namely it inserts a <tt>%%Copyright:</tt> DSC field to the header of
 		  ///the EPS file.
 		  GraphToEps<T> &copyright(const std::string &t) {_copyright=t;return *this;}
 		protected:
 		  bool isInsideNode(dim2::Point<double> p, double r,int t)
+		  {
 		    switch(t) {
 		    case CIRCLE:
 		    case MALE:
 		    case FEMALE:
 		      return p.normSquare()<=r*r;
 		    case SQUARE:
 		      return p.x<=r&&p.x>=-r&&p.y<=r&&p.y>=-r;
 		    case DIAMOND:
 		      return p.x+p.y<=r && p.x-p.y<=r && -p.x+p.y<=r && -p.x-p.y<=r;
+		    }
 		    return false;
+		  }
 		public:
 		  ~GraphToEps() { }
 		  ///Draws the graph.
 		  ///Like other functions using
 		  ///\ref named-templ-func-param "named template parameters",
 		  ///this function calls the algorithm itself, i.e. in this case
 		  ///it draws the graph.
 		  void run() {
 		    //\todo better 'epsilon' would be nice here.
 		    const double EPSILON=1e-9;
 		    if(dontPrint) return;
 		    _graph_to_eps_bits::_NegY<typename T::CoordsMapType>
 		      mycoords(_coords,_negY);
 		    os << "%!PS-Adobe-2.0 EPSF-2.0\n";
 		    if(_title.size()>0) os << "%%Title: " << _title << '\n';
 		     if(_copyright.size()>0) os << "%%Copyright: " << _copyright << '\n';
 		//        << "%%Copyright: XXXX\n"
 		    os << "%%Creator: LEMON, graphToEps()\n";
+		    {
 		#ifndef WIN32
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      char cbuf[26];
 		      ctime_r(&tv.tv_sec,cbuf);
 		      os << "%%CreationDate: " << cbuf;
 		#else
 		      SYSTEMTIME time;
 		      char buf1[11], buf2[9], buf3[5];
 		      GetSystemTime(&time);
 		      if (GetDateFormat(LOCALE_USER_DEFAULT, 0, &time,
 					"ddd MMM dd", buf1, 11) &&
 			  GetTimeFormat(LOCALE_USER_DEFAULT, 0, &time,
 					"HH':'mm':'ss", buf2, 9) &&
 			  GetDateFormat(LOCALE_USER_DEFAULT, 0, &time,
 						"yyyy", buf3, 5)) {
 			os << "%%CreationDate: " << buf1 << ' '
 			   << buf2 << ' ' << buf3 << std::endl;
+		      }
 		#endif
+		    }
 		    if (_autoArcWidthScale) {
 		      double max_w=0;
 		      for(ArcIt e(g);e!=INVALID;++e)
 			max_w=std::max(double(_arcWidths[e]),max_w);
 		      ///\todo better 'epsilon' would be nice here.
 		      if(max_w>EPSILON) {
 			_arcWidthScale/=max_w;
+		      }
+		    }
 		    if (_autoNodeScale) {
 		      double max_s=0;
 		      for(NodeIt n(g);n!=INVALID;++n)
 			max_s=std::max(double(_nodeSizes[n]),max_s);
 		      ///\todo better 'epsilon' would be nice here.
 		      if(max_s>EPSILON) {
 			_nodeScale/=max_s;
+		      }
+		    }
 		    double diag_len = 1;
 		    if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {
 		      dim2::BoundingBox<double> bb;
 		      for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);
 		      if (bb.empty()) {
 			bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
+		      }
 		      diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare());
 		      if(diag_len<EPSILON) diag_len = 1;
 		      if(!_absoluteNodeSizes) _nodeScale*=diag_len;
 		      if(!_absoluteArcWidths) _arcWidthScale*=diag_len;
+		    }
 		    dim2::BoundingBox<double> bb;
 		    for(NodeIt n(g);n!=INVALID;++n) {
 		      double ns=_nodeSizes[n]*_nodeScale;
 		      dim2::Point<double> p(ns,ns);
 		      switch(_nodeShapes[n]) {
 		      case CIRCLE:
 		      case SQUARE:
 		      case DIAMOND:
 			bb.add(p+mycoords[n]);
 			bb.add(-p+mycoords[n]);
 			break;
 		      case MALE:
 			bb.add(-p+mycoords[n]);
 			bb.add(dim2::Point<double>(1.5*ns,1.5*std::sqrt(3.0)*ns)+mycoords[n]);
 			break;
 		      case FEMALE:
 			bb.add(p+mycoords[n]);
 			bb.add(dim2::Point<double>(-ns,-3.01*ns)+mycoords[n]);
 			break;
+		      }
+		    }
 		    if (bb.empty()) {
 		      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";
 		    os << "/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def\n";
 		    //x y r
 		    os << "/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def\n";
 		    //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"
 		       << "      2 index 1 index sub 2 index 2 index sub lineto\n"
 		       << "      2 index 1 index add 2 index 2 index sub lineto\n"
 		       << "      closepath pop pop pop} bind def\n";
 		    //x y r
 		    os << "/di { newpath 2 index 1 index add 2 index moveto\n"
 		       << "      2 index             2 index 2 index add lineto\n"
 		       << "      2 index 1 index sub 2 index             lineto\n"
 		       << "      2 index             2 index 2 index sub lineto\n"
 		       << "      closepath pop pop pop} bind def\n";
 		    // x y r cr cg cb
 		    os << "/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill\n"
 		       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
 		       << "   } bind def\n";
 		    os << "/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill\n"
 		       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div sq fill\n"
 		       << "   } bind def\n";
 		    os << "/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill\n"
 		       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div di fill\n"
 		       << "   } bind def\n";
 		    os << "/nfemale { 0 0 0 setrgbcolor 3 index "
 		       << _nodeBorderQuotient/(1+_nodeBorderQuotient)
 		       << " 1.5 mul mul setlinewidth\n"
 		       << "  newpath 5 index 5 index moveto "
 		       << "5 index 5 index 5 index 3.01 mul sub\n"
 		       << "  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto\n"
 		       << "  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke\n"
 		       << "  5 index 5 index 5 index c fill\n"
 		       << "  setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
 		       << "  } bind def\n";
 		    os << "/nmale {\n"
 		       << "  0 0 0 setrgbcolor 3 index "
 		       << _nodeBorderQuotient/(1+_nodeBorderQuotient)
 		       <<" 1.5 mul mul setlinewidth\n"
 		       << "  newpath 5 index 5 index moveto\n"
 		       << "  5 index 4 index 1 mul 1.5 mul add\n"
 		       << "  5 index 5 index 3 sqrt 1.5 mul mul add\n"
 		       << "  1 index 1 index lineto\n"
 		       << "  1 index 1 index 7 index sub moveto\n"
 		       << "  1 index 1 index lineto\n"
 		       << "  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto\n"
 		       << "  stroke\n"
 		       << "  5 index 5 index 5 index c fill\n"
 		       << "  setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
 		       << "  } bind def\n";
 		    os << "/arrl " << _arrowLength << " def\n";
 		    os << "/arrw " << _arrowWidth << " def\n";
 		    // l dx_norm dy_norm
 		    os << "/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def\n";
 		    //len w dx_norm dy_norm x1 y1 cr cg cb
 		    os << "/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def\n"
 		       << "       /w exch def /len exch def\n"
 		      //	 << "       0.1 setlinewidth x1 y1 moveto dx len mul dy len mul rlineto stroke"
 		       << "       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto\n"
 		       << "       len w sub arrl sub dx dy lrl\n"
 		       << "       arrw dy dx neg lrl\n"
 		       << "       dx arrl w add mul dy w 2 div arrw add mul sub\n"
 		       << "       dy arrl w add mul dx w 2 div arrw add mul add rlineto\n"
 		       << "       dx arrl w add mul neg dy w 2 div arrw add mul sub\n"
 		       << "       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto\n"
 		       << "       arrw dy dx neg lrl\n"
 		       << "       len w sub arrl sub neg dx dy lrl\n"
 		       << "       closepath fill } bind def\n";
 		    os << "/cshow { 2 index 2 index moveto dup stringwidth pop\n"
 		       << "         neg 2 div fosi .35 mul neg rmoveto show pop pop} def\n";
 		    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));
 		 	  dim2::Point<double> m;
 		// 	  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)]));
 		 	  m=dim2::Point<double>(mycoords[g.source(*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";
+			    }
 			    else {
 			      os << mycoords[g.source(*e)].x << ' '
 				 << mycoords[g.source(*e)].y << ' '
 				 << mm.x << ' ' << mm.y << ' '
 				 << mycoords[g.target(*e)].x << ' '
 				 << mycoords[g.target(*e)].y << ' '
 				 << _arcColors[*e].red() << ' '
 				 << _arcColors[*e].green() << ' '
 				 << _arcColors[*e].blue() << ' '
 				 << _arcWidths[*e]*_arcWidthScale << " lb\n";
+			    }
 			    sw+=_arcWidths[*e]*_arcWidthScale/2.0+_parArcDist;
+			  }
+			}
+		      }
 		      else for(ArcIt e(g);e!=INVALID;++e)
 			if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0
 			   &&g.source(e)!=g.target(e))
 			  if(_drawArrows) {
 			    dim2::Point<double> d(mycoords[g.target(e)]-mycoords[g.source(e)]);
 			    double rn=_nodeSizes[g.target(e)]*_nodeScale;
 			    int node_shape=_nodeShapes[g.target(e)];
 			    double t1=0,t2=1;
 			    for(int i=0;i<INTERPOL_PREC;++i)
 			      if(isInsideNode((-(t1+t2)/2)*d,rn,node_shape)) t1=(t1+t2)/2;
 			      else t2=(t1+t2)/2;
 			    double l=std::sqrt(d.normSquare());
 			    d/=l;
 			    os << l*(1-(t1+t2)/2) << ' '
 			       << _arcWidths[e]*_arcWidthScale << ' '
 			       << d.x << ' ' << d.y << ' '
 			       << mycoords[g.source(e)].x << ' '
 			       << mycoords[g.source(e)].y << ' '
 			       << _arcColors[e].red() << ' '
 			       << _arcColors[e].green() << ' '
 			       << _arcColors[e].blue() << " arr\n";
+			  }
 			  else os << mycoords[g.source(e)].x << ' '
 				  << mycoords[g.source(e)].y << ' '
 				  << mycoords[g.target(e)].x << ' '
 				  << mycoords[g.target(e)].y << ' '
 				  << _arcColors[e].red() << ' '
 				  << _arcColors[e].green() << ' '
 				  << _arcColors[e].blue() << ' '
 				  << _arcWidths[e]*_arcWidthScale << " l\n";
 		      os << "grestore\n";
+		    }
 		    if(_showNodes) {
 		      os << "%Nodes:\ngsave\n";
 		      for(NodeIt n(g);n!=INVALID;++n) {
 			os << mycoords[n].x << ' ' << mycoords[n].y << ' '
 			   << _nodeSizes[n]*_nodeScale << ' '
 			   << _nodeColors[n].red() << ' '
 			   << _nodeColors[n].green() << ' '
 			   << _nodeColors[n].blue() << ' ';
 			switch(_nodeShapes[n]) {
 			case CIRCLE:
 			  os<< "nc";break;
 			case SQUARE:
 			  os<< "nsq";break;
 			case DIAMOND:
 			  os<< "ndi";break;
 			case MALE:
 			  os<< "nmale";break;
 			case FEMALE:
 			  os<< "nfemale";break;
+			}
 			os<<'\n';
+		      }
 		      os << "grestore\n";
+		    }
 		    if(_showNodeText) {
 		      os << "%Node texts:\ngsave\n";
 		      os << "/fosi " << _nodeTextSize << " def\n";
 		      os << "(Helvetica) findfont fosi scalefont setfont\n";
 		      for(NodeIt n(g);n!=INVALID;++n) {
 			switch(_nodeTextColorType) {
 			case DIST_COL:
 			  os << psOut(distantColor(_nodeColors[n])) << " setrgbcolor\n";
 			  break;
 			case DIST_BW:
 			  os << psOut(distantBW(_nodeColors[n])) << " setrgbcolor\n";
 			  break;
 			case CUST_COL:
 			  os << psOut(distantColor(_nodeTextColors[n])) << " setrgbcolor\n";
 			  break;
 			default:
 			  os << "0 0 0 setrgbcolor\n";
+			}
 			os << mycoords[n].x << ' ' << mycoords[n].y
 			   << " (" << _nodeTexts[n] << ") cshow\n";
+		      }
 		      os << "grestore\n";
+		    }
 		    if(_showNodePsText) {
 		      os << "%Node PS blocks:\ngsave\n";
 		      for(NodeIt n(g);n!=INVALID;++n)
 			os << mycoords[n].x << ' ' << mycoords[n].y
 			   << " moveto\n" << _nodePsTexts[n] << "\n";
 		      os << "grestore\n";
+		    }
 		    os << "grestore\nshowpage\n";
 		    //CleanUp:
 		    if(_pleaseRemoveOsStream) {delete &os;}
+		  }
 		  ///\name Aliases
 		  ///These are just some aliases to other parameter setting functions.
 		  ///@{
 		  ///An alias for arcWidths()
 		  ///An alias for arcWidths()
 		  ///
 		  template<class X> GraphToEps<ArcWidthsTraits<X> > edgeWidths(const X &x)
+		  {
 		    return arcWidths(x);
+		  }
 		  ///An alias for arcColors()
 		  ///An alias for arcColors()
 		  ///
 		  template<class X> GraphToEps<ArcColorsTraits<X> >
 		  edgeColors(const X &x)
+		  {
 		    return arcColors(x);
+		  }
 		  ///An alias for arcWidthScale()
 		  ///An alias for arcWidthScale()
 		  ///
 		  GraphToEps<T> &edgeWidthScale(double d) {return arcWidthScale(d);}
 		  ///An alias for autoArcWidthScale()
 		  ///An alias for autoArcWidthScale()
 		  ///
 		  GraphToEps<T> &autoEdgeWidthScale(bool b=true)
+		  {
 		    return autoArcWidthScale(b);
+		  }
 		  ///An alias for absoluteArcWidths()
 		  ///An alias for absoluteArcWidths()
 		  ///
 		  GraphToEps<T> &absoluteEdgeWidths(bool b=true)
+		  {
 		    return absoluteArcWidths(b);
+		  }
 		  ///An alias for parArcDist()
 		  ///An alias for parArcDist()
 		  ///
 		  GraphToEps<T> &parEdgeDist(double d) {return parArcDist(d);}
 		  ///An alias for hideArcs()
 		  ///An alias for hideArcs()
 		  ///
 		  GraphToEps<T> &hideEdges(bool b=true) {return hideArcs(b);}
 		  ///@}
 		};
 		template<class T>
 		const int GraphToEps<T>::INTERPOL_PREC = 20;
 		template<class T>
 		const double GraphToEps<T>::A4HEIGHT = 841.8897637795276;
 		template<class T>
 		const double GraphToEps<T>::A4WIDTH  = 595.275590551181;
 		template<class T>
 		const double GraphToEps<T>::A4BORDER = 15;
 		///Generates an EPS file from a graph
 		///\ingroup eps_io
 		///Generates an EPS file from a graph.
 		///\param g is a reference to the graph to be printed
 		///\param os is a reference to the output stream.
 		///By default it is <tt>std::cout</tt>
 		///
 		///This function also has a lot of
 		///\ref named-templ-func-param "named parameters",
 		///they are declared as the members of class \ref GraphToEps. The following
 		///example shows how to use these parameters.
 		///\code
 		/// graphToEps(g,os).scale(10).coords(coords)
 		///              .nodeScale(2).nodeSizes(sizes)
 		///              .arcWidthScale(.4).run();
 		///\endcode
 		///\warning Don't forget to put the \ref GraphToEps::run() "run()"
 		///to the end of the parameter list.
 		///\sa GraphToEps
 		///\sa graphToEps(G &g, const char *file_name)
 		template<class G>
 		GraphToEps<DefaultGraphToEpsTraits<G> >
 		graphToEps(G &g, std::ostream& os=std::cout)
+		{
 		  return
 		    GraphToEps<DefaultGraphToEpsTraits<G> >(DefaultGraphToEpsTraits<G>(g,os));
+		}
 		///Generates an EPS file from a graph
 		///\ingroup eps_io
 		///This function does the same as
 		///\ref graphToEps(G &g,std::ostream& os)
 		///but it writes its output into the file \c file_name
 		///instead of a stream.
 		///\sa graphToEps(G &g, std::ostream& os)
 		template<class G>
 		GraphToEps<DefaultGraphToEpsTraits<G> >
 		graphToEps(G &g,const char *file_name)
+		{
 		  return GraphToEps<DefaultGraphToEpsTraits<G> >
 		    (DefaultGraphToEpsTraits<G>(g,*new std::ofstream(file_name),true));
+		}
 		///Generates an EPS file from a graph
 		///\ingroup eps_io
 		///This function does the same as
 		///\ref graphToEps(G &g,std::ostream& os)
 		///but it writes its output into the file \c file_name
 		///instead of a stream.
 		///\sa graphToEps(G &g, std::ostream& os)
 		template<class G>
 		GraphToEps<DefaultGraphToEpsTraits<G> >
 		graphToEps(G &g,const std::string& file_name)
+		{
 		  return GraphToEps<DefaultGraphToEpsTraits<G> >
 		    (DefaultGraphToEpsTraits<G>(g,*new std::ofstream(file_name.c_str()),true));
+		}
 		} //END OF NAMESPACE LEMON
 		#endif // LEMON_GRAPH_TO_EPS_H

lemon/path.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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.
+		 *
 		 */
 		///\ingroup paths
 		///\file
 		///\brief Classes for representing paths in digraphs.
 		///
 		#ifndef LEMON_PATH_H
 		#define LEMON_PATH_H
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/error.h>
 		#include <lemon/bits/invalid.h>
 		#include <lemon/concepts/path.h>
 		namespace lemon {
 		  /// \addtogroup paths
 		  /// @{
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \param Digraph The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
 		  /// lemon path type stores just this list. As a consequence, it
 		  /// cannot enumerate the nodes of the path and the source node of
 		  /// a zero length path is undefined.
 		  ///
 		  /// This implementation is a back and front insertable and erasable
 		  /// path type. It can be indexed in O(1) time. The front and back
 		  /// insertion and erase is done in O(1) (amortized) time. The
 		  /// implementation uses two vectors for storing the front and back
 		  /// insertions.
 		  template <typename _Digraph>
 		  class Path {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    Path() {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This constuctor initializes the path from any other path type.
 		    /// It simply makes a copy of the given path.
 		    template <typename CPath>
 		    Path(const CPath& cpath) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This operator makes a copy of a path of any other type.
 		    template <typename CPath>
 		    Path& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Lemon style iterator for path arcs
 		    ///
 		    /// This class is used to iterate on the arcs of the paths.
 		    class ArcIt {
 		      friend class Path;
 		    public:
 		      /// \brief Default constructor
 		      ArcIt() {}
 		      /// \brief Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// \brief Initializate the iterator to the first arc of path
 		      ArcIt(const Path &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      ArcIt(const Path &_path, int _idx)
 		        : path(&_path), idx(_idx) {}
 		    public:
 		      /// \brief Conversion to Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// \brief Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// \brief Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// \brief Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// \brief Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const Path *path;
 		      int idx;
 		    };
 		    /// \brief Length of the path.
 		    int length() const { return head.size() + tail.size(); }
 		    /// \brief Return whether the path is empty.
 		    bool empty() const { return head.empty() && tail.empty(); }
 		    /// \brief Reset the path to an empty one.
 		    void clear() { head.clear(); tail.clear(); }
 		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return n < int(head.size()) ? *(head.rbegin() + n) :
 		        *(tail.begin() + (n - head.size()));
+		    }
 		    /// \brief Initialize arc iterator to point to the nth arc
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
 		    /// \brief The first arc of the path
 		    const Arc& front() const {
 		      return head.empty() ? tail.front() : head.back();
+		    }
 		    /// \brief Add a new arc before the current path
 		    void addFront(const Arc& arc) {
 		      head.push_back(arc);
+		    }
 		    /// \brief Erase the first arc of the path
 		    void eraseFront() {
 		      if (!head.empty()) {
 		        head.pop_back();
 		      } else {
 		        head.clear();
 		        int halfsize = tail.size() / 2;
 		        head.resize(halfsize);
 		        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
 		                  head.rbegin());
 		        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
 		        tail.resize(tail.size() - halfsize - 1);
+		      }
+		    }
 		    /// \brief The last arc of the path
 		    const Arc& back() const {
 		      return tail.empty() ? head.front() : tail.back();
+		    }
 		    /// \brief Add a new arc behind the current path
 		    void addBack(const Arc& arc) {
 		      tail.push_back(arc);
+		    }
 		    /// \brief Erase the last arc of the path
 		    void eraseBack() {
 		      if (!tail.empty()) {
 		        tail.pop_back();
 		      } else {
 		        int halfsize = head.size() / 2;
 		        tail.resize(halfsize);
 		        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
 		                  tail.rbegin());
 		        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
 		        head.resize(head.size() - halfsize - 1);
+		      }
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      int len = path.length();
 		      tail.reserve(len);
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        tail.push_back(it);
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      int len = path.length();
 		      head.reserve(len);
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        head.push_back(it);
+		      }
+		    }
 		  protected:
 		    typedef std::vector<Arc> Container;
 		    Container head, tail;
 		  };
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \param Digraph The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
 		  /// lemon path type stores just this list. As a consequence it
 		  /// cannot enumerate the nodes in the path and the zero length paths
 		  /// cannot store the source.
 		  ///
 		  /// This implementation is a just back insertable and erasable path
 		  /// type. It can be indexed in O(1) time. The back insertion and
 		  /// erasure is amortized O(1) time. This implementation is faster
 		  /// then the \c Path type because it use just one vector for the
 		  /// arcs.
 		  template <typename _Digraph>
 		  class SimplePath {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    SimplePath() {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    SimplePath(const CPath& cpath) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    SimplePath& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Iterator class to iterate on the arcs of the paths
 		    ///
 		    /// This class is used to iterate on the arcs of the paths
 		    ///
 		    /// Of course it converts to Digraph::Arc
 		    class ArcIt {
 		      friend class SimplePath;
 		    public:
 		      /// Default constructor
 		      ArcIt() {}
 		      /// Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// \brief Initializate the constructor to the first arc of path
 		      ArcIt(const SimplePath &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      /// Constructor with starting point
 		      ArcIt(const SimplePath &_path, int _idx)
 		        : idx(_idx), path(&_path) {}
 		    public:
 		      ///Conversion to Digraph::Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const SimplePath *path;
 		      int idx;
 		    };
 		    /// \brief Length of the path.
 		    int length() const { return data.size(); }
 		    /// \brief Return true if the path is empty.
 		    bool empty() const { return data.empty(); }
 		    /// \brief Reset the path to an empty one.
 		    void clear() { data.clear(); }
 		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return data[n];
+		    }
 		    /// \brief  Initializes arc iterator to point to the nth arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
 		    /// \brief The first arc of the path.
 		    const Arc& front() const {
 		      return data.front();
+		    }
 		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return data.back();
+		    }
 		    /// \brief Add a new arc behind the current path.
 		    void addBack(const Arc& arc) {
 		      data.push_back(arc);
+		    }
 		    /// \brief Erase the last arc of the path
 		    void eraseBack() {
 		      data.pop_back();
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      int len = path.length();
 		      data.resize(len);
 		      int index = 0;
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        data[index] = it;;
 		        ++index;
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      int len = path.length();
 		      data.resize(len);
 		      int index = len;
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        --index;
 		        data[index] = it;;
+		      }
+		    }
 		  protected:
 		    typedef std::vector<Arc> Container;
 		    Container data;
 		  };
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \param Digraph The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
 		  /// lemon path type stores just this list. As a consequence it
 		  /// cannot enumerate the nodes in the path and the zero length paths
 		  /// cannot store the source.
 		  ///
 		  /// This implementation is a back and front insertable and erasable
 		  /// path type. It can be indexed in O(k) time, where k is the rank
 		  /// of the arc in the path. The length can be computed in O(n)
 		  /// time. The front and back insertion and erasure is O(1) time
 		  /// and it can be splited and spliced in O(1) time.
 		  template <typename _Digraph>
 		  class ListPath {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		  protected:
 		    // the std::list<> is incompatible
 		    // hard to create invalid iterator
 		    struct Node {
 		      Arc arc;
 		      Node *next, *prev;
 		    };
 		    Node *first, *last;
 		    std::allocator<Node> alloc;
 		  public:
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    ListPath() : first(0), last(0) {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    ListPath(const CPath& cpath) : first(0), last(0) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Destructor of the path
 		    ///
 		    /// Destructor of the path
 		    ~ListPath() {
 		      clear();
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    ListPath& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Iterator class to iterate on the arcs of the paths
 		    ///
 		    /// This class is used to iterate on the arcs of the paths
 		    ///
 		    /// Of course it converts to Digraph::Arc
 		    class ArcIt {
 		      friend class ListPath;
 		    public:
 		      /// Default constructor
 		      ArcIt() {}
 		      /// Invalid constructor
 		      ArcIt(Invalid) : path(0), node(0) {}
 		      /// \brief Initializate the constructor to the first arc of path
 		      ArcIt(const ListPath &_path)
 		        : path(&_path), node(_path.first) {}
 		    protected:
 		      ArcIt(const ListPath &_path, Node *_node)
 		        : path(&_path), node(_node) {}
 		    public:
 		      ///Conversion to Digraph::Arc
 		      operator const Arc&() const {
 		        return node->arc;
+		      }
 		      /// Next arc
 		      ArcIt& operator++() {
 		        node = node->next;
 		        return *this;
+		      }
 		      /// Comparison operator
 		      bool operator==(const ArcIt& e) const { return node==e.node; }
 		      /// Comparison operator
 		      bool operator!=(const ArcIt& e) const { return node!=e.node; }
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return node<e.node; }
 		    private:
 		      const ListPath *path;
 		      Node *node;
 		    };
 		    /// \brief The nth arc.
 		    ///
 		    /// This function looks for the nth arc in O(n) time.
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      Node *node = first;
 		      for (int i = 0; i < n; ++i) {
 		        node = node->next;
+		      }
 		      return node->arc;
+		    }
 		    /// \brief Initializes arc iterator to point to the nth arc.
 		    ArcIt nthIt(int n) const {
 		      Node *node = first;
 		      for (int i = 0; i < n; ++i) {
 		        node = node->next;
+		      }
 		      return ArcIt(*this, node);
+		    }
 		    /// \brief Length of the path.
 		    int length() const {
 		      int len = 0;
 		      Node *node = first;
 		      while (node != 0) {
 		        node = node->next;
 		        ++len;
+		      }
 		      return len;
+		    }
 		    /// \brief Return true if the path is empty.
 		    bool empty() const { return first == 0; }
 		    /// \brief Reset the path to an empty one.
 		    void clear() {
 		      while (first != 0) {
 		        last = first->next;
 		        alloc.destroy(first);
 		        alloc.deallocate(first, 1);
 		        first = last;
+		      }
+		    }
 		    /// \brief The first arc of the path
 		    const Arc& front() const {
 		      return first->arc;
+		    }
 		    /// \brief Add a new arc before the current path
 		    void addFront(const Arc& arc) {
 		      Node *node = alloc.allocate(1);
 		      alloc.construct(node, Node());
 		      node->prev = 0;
 		      node->next = first;
 		      node->arc = arc;
 		      if (first) {
 		        first->prev = node;
 		        first = node;
 		      } else {
 		        first = last = node;
+		      }
+		    }
 		    /// \brief Erase the first arc of the path
 		    void eraseFront() {
 		      Node *node = first;
 		      first = first->next;
 		      if (first) {
 		        first->prev = 0;
 		      } else {
 		        last = 0;
+		      }
 		      alloc.destroy(node);
 		      alloc.deallocate(node, 1);
+		    }
 		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return last->arc;
+		    }
 		    /// \brief Add a new arc behind the current path.
 		    void addBack(const Arc& arc) {
 		      Node *node = alloc.allocate(1);
 		      alloc.construct(node, Node());
 		      node->next = 0;
 		      node->prev = last;
 		      node->arc = arc;
 		      if (last) {
 		        last->next = node;
 		        last = node;
 		      } else {
 		        last = first = node;
+		      }
+		    }
 		    /// \brief Erase the last arc of the path
 		    void eraseBack() {
 		      Node *node = last;
 		      last = last->prev;
 		      if (last) {
 		        last->next = 0;
 		      } else {
 		        first = 0;
+		      }
 		      alloc.destroy(node);
 		      alloc.deallocate(node, 1);
+		    }
 		    /// \brief Splice a path to the back of the current path.
 		    ///
 		    /// It splices \c tpath to the back of the current path and \c
 		    /// tpath becomes empty. The time complexity of this function is
 		    /// O(1).
 		    void spliceBack(ListPath& tpath) {
 		      if (first) {
 		        if (tpath.first) {
 		          last->next = tpath.first;
 		          tpath.first->prev = last;
 		          last = tpath.last;
+		        }
 		      } else {
 		        first = tpath.first;
 		        last = tpath.last;
+		      }
 		      tpath.first = tpath.last = 0;
+		    }
 		    /// \brief Splice a path to the front of the current path.
 		    ///
 		    /// It splices \c tpath before the current path and \c tpath
 		    /// becomes empty. The time complexity of this function
 		    /// is O(1).
 		    void spliceFront(ListPath& tpath) {
 		      if (first) {
 		        if (tpath.first) {
 		          first->prev = tpath.last;
 		          tpath.last->next = first;
 		          first = tpath.first;
+		        }
 		      } else {
 		        first = tpath.first;
 		        last = tpath.last;
+		      }
 		      tpath.first = tpath.last = 0;
+		    }
 		    /// \brief Splice a path into the current path.
 		    ///
 		    /// It splices the \c tpath into the current path before the
 		    /// position of \c it iterator and \c tpath becomes empty. The
 		    /// time complexity of this function is O(1). If the \c it is
 		    /// \c INVALID then it will splice behind the current path.
 		    void splice(ArcIt it, ListPath& tpath) {
 		      if (it.node) {
 		        if (tpath.first) {
 		          tpath.first->prev = it.node->prev;
 		          if (it.node->prev) {
 		            it.node->prev->next = tpath.first;
 		          } else {
 		            first = tpath.first;
+		          }
 		          it.node->prev = tpath.last;
 		          tpath.last->next = it.node;
+		        }
 		      } else {
 		        if (first) {
 		          if (tpath.first) {
 		            last->next = tpath.first;
 		            tpath.first->prev = last;
 		            last = tpath.last;
+		          }
 		        } else {
 		          first = tpath.first;
 		          last = tpath.last;
+		        }
+		      }
 		      tpath.first = tpath.last = 0;
+		    }
 		    /// \brief Split the current path.
 		    ///
 		    /// It splits the current path into two parts. The part before
 		    /// the iterator \c it will remain in the current path and the part
 		    /// starting with
 		    /// \c it will put into \c tpath. If \c tpath have arcs
 		    /// before the operation they are removed first.  The time
 		    /// complexity of this function is O(1) plus the the time of emtying
 		    /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
 		    void split(ArcIt it, ListPath& tpath) {
 		      tpath.clear();
 		      if (it.node) {
 		        tpath.first = it.node;
 		        tpath.last = last;
 		        if (it.node->prev) {
 		          last = it.node->prev;
 		          last->next = 0;
 		        } else {
 		          first = last = 0;
+		        }
 		        it.node->prev = 0;
+		      }
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        addBack(it);
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        addFront(it);
+		      }
+		    }
 		  };
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \param Digraph The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
 		  /// lemon path type stores just this list. As a consequence it
 		  /// cannot enumerate the nodes in the path and the source node of
 		  /// a zero length path is undefined.
 		  ///
 		  /// This implementation is completly static, i.e. it can be copy constucted
 		  /// or copy assigned from another path, but otherwise it cannot be
 		  /// modified.
 		  ///
 		  /// Being the the most memory efficient path type in LEMON,
 		  /// it is intented to be
 		  /// used when you want to store a large number of paths.
 		  template <typename _Digraph>
 		  class StaticPath {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    StaticPath() : len(0), arcs(0) {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized from any other path type.
 		    template <typename CPath>
 		    StaticPath(const CPath& cpath) : arcs(0) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Destructor of the path
 		    ///
 		    /// Destructor of the path
 		    ~StaticPath() {
 		      if (arcs) delete[] arcs;
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This path can be made equal to any other path type. It simply
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    StaticPath& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Iterator class to iterate on the arcs of the paths
 		    ///
 		    /// This class is used to iterate on the arcs of the paths
 		    ///
 		    /// Of course it converts to Digraph::Arc
 		    class ArcIt {
 		      friend class StaticPath;
 		    public:
 		      /// Default constructor
 		      ArcIt() {}
 		      /// Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// Initializate the constructor to the first arc of path
 		      ArcIt(const StaticPath &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      /// Constructor with starting point
 		      ArcIt(const StaticPath &_path, int _idx)
 		        : idx(_idx), path(&_path) {}
 		    public:
 		      ///Conversion to Digraph::Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const StaticPath *path;
 		      int idx;
 		    };
 		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return arcs[n];
+		    }
 		    /// \brief The arc iterator pointing to the nth arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
 		    /// \brief The length of the path.
 		    int length() const { return len; }
 		    /// \brief Return true when the path is empty.
 		    int empty() const { return len == 0; }
 		    /// \break Erase all arcs in the digraph.
 		    void clear() {
 		      len = 0;
 		      if (arcs) delete[] arcs;
 		      arcs = 0;
+		    }
 		    /// \brief The first arc of the path.
 		    const Arc& front() const {
 		      return arcs[0];
+		    }
 		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return arcs[len - 1];
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      len = path.length();
 		      arcs = new Arc[len];
 		      int index = 0;
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        arcs[index] = it;
 		        ++index;
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      len = path.length();
 		      arcs = new Arc[len];
 		      int index = len;
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        --index;
 		        arcs[index] = it;
+		      }
+		    }
 		  private:
 		    int len;
 		    Arc* arcs;
 		  };
 		  ///////////////////////////////////////////////////////////////////////
 		  // Additional utilities
 		  ///////////////////////////////////////////////////////////////////////
 		  namespace _path_bits {
 		    template <typename Path, typename Enable = void>
-		    struct RevTagIndicator {
+		    struct RevPathTagIndicator {
 		      static const bool value = false;
 		    };
 		    template <typename Digraph>
 		    struct RevTagIndicator<
 		      Digraph,
 		      typename enable_if<typename Digraph::RevTag, void>::type
 		    template <typename Path>
 		    struct RevPathTagIndicator<
 		      Path,
 		      typename enable_if<typename Path::RevPathTag, void>::type
 		      > {
 		      static const bool value = true;
 		    };
 		    template <typename Path, typename Enable = void>
 		    struct BuildTagIndicator {
 		      static const bool value = false;
 		    };
 		    template <typename Path>
 		    struct BuildTagIndicator<
 		      Path,
 		      typename enable_if<typename Path::BuildTag, void>::type
 		    > {
 		      static const bool value = true;
 		    };
 		    template <typename Target, typename Source,
-		              typename BuildEnable = void, typename RevEnable = void>
+			      bool buildEnable = BuildTagIndicator<Target>::value,
 			      bool revEnable = RevPathTagIndicator<Source>::value>
 		    struct PathCopySelector {
 		      static void copy(Target& target, const Source& source) {
 		        target.clear();
 		        for (typename Source::ArcIt it(source); it != INVALID; ++it) {
 		          target.addBack(it);
+		        }
+		      }
 		    };
 		    template <typename Target, typename Source, typename BuildEnable>
 		    struct PathCopySelector<
 		      Target, Source, BuildEnable,
 		      typename enable_if<typename Source::RevPathTag, void>::type> {
 		    template <typename Target, typename Source>
 		    struct PathCopySelector<Target, Source, false, true> {
 		      static void copy(Target& target, const Source& source) {
 		        target.clear();
 		        for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
 		          target.addFront(it);
+		        }
+		      }
 		    };
 		    template <typename Target, typename Source, typename RevEnable>
 		    struct PathCopySelector<
 		      Target, Source,
 		      typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
 		    template <typename Target, typename Source>
 		    struct PathCopySelector<Target, Source, true, false> {
 		      static void copy(Target& target, const Source& source) {
 		        target.clear();
 		        target.build(source);
+		      }
 		    };
 		    template <typename Target, typename Source>
 		    struct PathCopySelector<
 		      Target, Source,
 		      typename enable_if<typename Target::BuildTag, void>::type,
 		      typename enable_if<typename Source::RevPathTag, void>::type> {
 		    struct PathCopySelector<Target, Source, true, true> {
 		      static void copy(Target& target, const Source& source) {
 		        target.clear();
 		        target.buildRev(source);
+		      }
 		    };
+		  }
 		  /// \brief Make a copy of a path.
 		  ///
 		  ///  This function makes a copy of a path.
 		  template <typename Target, typename Source>
 		  void copyPath(Target& target, const Source& source) {
 		    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
 		    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
+		  }
 		  /// \brief Check the consistency of a path.
 		  ///
 		  /// This function checks that the target of each arc is the same
 		  /// as the source of the next one.
 		  ///
 		  template <typename Digraph, typename Path>
 		  bool checkPath(const Digraph& digraph, const Path& path) {
 		    typename Path::ArcIt it(path);
 		    if (it == INVALID) return true;
 		    typename Digraph::Node node = digraph.target(it);
 		    ++it;
 		    while (it != INVALID) {
 		      if (digraph.source(it) != node) return false;
 		      node = digraph.target(it);
 		      ++it;
+		    }
 		    return true;
+		  }
 		  /// \brief The source of a path
 		  ///
 		  /// This function returns the source of the given path.
 		  template <typename Digraph, typename Path>
 		  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
 		    return digraph.source(path.front());
+		  }
 		  /// \brief The target of a path
 		  ///
 		  /// This function returns the target of the given path.
 		  template <typename Digraph, typename Path>
 		  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
 		    return digraph.target(path.back());
+		  }
 		  /// \brief Class which helps to iterate through the nodes of a path
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
 		  /// lemon path type stores only this list. As a consequence, it
 		  /// cannot enumerate the nodes in the path and the zero length paths
 		  /// cannot have a source node.
 		  ///
 		  /// This class implements the node iterator of a path structure. To
 		  /// provide this feature, the underlying digraph should be passed to
 		  /// the constructor of the iterator.
 		  template <typename Path>
 		  class PathNodeIt {
 		  private:
 		    const typename Path::Digraph *_digraph;
 		    typename Path::ArcIt _it;
 		    typename Path::Digraph::Node _nd;
 		  public:
 		    typedef typename Path::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    /// Default constructor
 		    PathNodeIt() {}
 		    /// Invalid constructor
 		    PathNodeIt(Invalid)
 		      : _digraph(0), _it(INVALID), _nd(INVALID) {}
 		    /// Constructor
 		    PathNodeIt(const Digraph& digraph, const Path& path)
 		      : _digraph(&digraph), _it(path) {
 		      _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
+		    }
 		    /// Constructor
 		    PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
 		      : _digraph(&digraph), _it(path), _nd(src) {}
 		    ///Conversion to Digraph::Node
 		    operator Node() const {
 		      return _nd;
+		    }
 		    /// Next node
 		    PathNodeIt& operator++() {
 		      if (_it == INVALID) _nd = INVALID;
 		      else {
 			_nd = _digraph->target(_it);
 			++_it;
+		      }
 		      return *this;
+		    }
 		    /// Comparison operator
 		    bool operator==(const PathNodeIt& n) const {
 		      return _it == n._it && _nd == n._nd;
+		    }
 		    /// Comparison operator
 		    bool operator!=(const PathNodeIt& n) const {
 		      return _it != n._it || _nd != n._nd;
+		    }
 		    /// Comparison operator
 		    bool operator<(const PathNodeIt& n) const {
 		      return (_it < n._it && _nd != INVALID);
+		    }
 		  };
 		  ///@}
 		} // namespace lemon
 		#endif // LEMON_PATH_H

lemon/time_measure.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_TIME_MEASURE_H
 		#define LEMON_TIME_MEASURE_H
 		///\ingroup timecount
 		///\file
 		///\brief Tools for measuring cpu usage
 		#ifdef WIN32
 		#define WIN32_LEAN_AND_MEAN
 		#define NOMINMAX
 		#include <windows.h>
 		#include <cmath>
 		#else
 		#include <sys/times.h>
 		#include <sys/time.h>
 		#endif
 		#include <string>
 		#include <fstream>
 		#include <iostream>
 		namespace lemon {
 		  /// \addtogroup timecount
 		  /// @{
 		  /// A class to store (cpu)time instances.
 		  /// This class stores five time values.
 		  /// - a real time
 		  /// - a user cpu time
 		  /// - a system cpu time
 		  /// - a user cpu time of children
 		  /// - a system cpu time of children
 		  ///
 		  /// TimeStamp's can be added to or substracted from each other and
 		  /// they can be pushed to a stream.
 		  ///
 		  /// In most cases, perhaps the \ref Timer or the \ref TimeReport
 		  /// class is what you want to use instead.
 		  ///
 		  ///\author Alpar Juttner
 		  class TimeStamp
+		  {
 		    double utime;
 		    double stime;
 		    double cutime;
 		    double cstime;
 		    double rtime;
 		    void _reset() {
 		      utime = stime = cutime = cstime = rtime = 0;
+		    }
 		  public:
 		    ///Read the current time values of the process
 		    void stamp()
+		    {
 		#ifndef WIN32
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      rtime=tv.tv_sec+double(tv.tv_usec)/1e6;
 		      tms ts;
 		      double tck=sysconf(_SC_CLK_TCK);
 		      times(&ts);
 		      utime=ts.tms_utime/tck;
 		      stime=ts.tms_stime/tck;
 		      cutime=ts.tms_cutime/tck;
 		      cstime=ts.tms_cstime/tck;
 		#else
 		      static const double ch = 4294967296.0e-7;
 		      static const double cl = 1.0e-7;
 		      FILETIME system;
 		      GetSystemTimeAsFileTime(&system);
 		      rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime;
 		      FILETIME create, exit, kernel, user;
 		      if (GetProcessTimes(GetCurrentProcess(),&create, &exit, &kernel, &user)) {
 			utime = ch * user.dwHighDateTime + cl * user.dwLowDateTime;
 			stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime;
 			cutime = 0;
 			cstime = 0;
 		      } else {
 			rtime = 0;
 			utime = 0;
 			stime = 0;
 			cutime = 0;
 			cstime = 0;
+		      }
 		#endif
+		    }
 		    /// Constructor initializing with zero
 		    TimeStamp()
 		    { _reset(); }
 		    ///Constructor initializing with the current time values of the process
 		    TimeStamp(void *) { stamp();}
 		    ///Set every time value to zero
 		    TimeStamp &reset() {_reset();return *this;}
 		    ///\e
 		    TimeStamp &operator+=(const TimeStamp &b)
+		    {
 		      utime+=b.utime;
 		      stime+=b.stime;
 		      cutime+=b.cutime;
 		      cstime+=b.cstime;
 		      rtime+=b.rtime;
 		      return *this;
+		    }
 		    ///\e
 		    TimeStamp operator+(const TimeStamp &b) const
+		    {
 		      TimeStamp t(*this);
 		      return t+=b;
+		    }
 		    ///\e
 		    TimeStamp &operator-=(const TimeStamp &b)
+		    {
 		      utime-=b.utime;
 		      stime-=b.stime;
 		      cutime-=b.cutime;
 		      cstime-=b.cstime;
 		      rtime-=b.rtime;
 		      return *this;
+		    }
 		    ///\e
 		    TimeStamp operator-(const TimeStamp &b) const
+		    {
 		      TimeStamp t(*this);
 		      return t-=b;
+		    }
 		    ///\e
 		    TimeStamp &operator*=(double b)
+		    {
 		      utime*=b;
 		      stime*=b;
 		      cutime*=b;
 		      cstime*=b;
 		      rtime*=b;
 		      return *this;
+		    }
 		    ///\e
 		    TimeStamp operator*(double b) const
+		    {
 		      TimeStamp t(*this);
 		      return t*=b;
+		    }
 		    friend TimeStamp operator*(double b,const TimeStamp &t);
 		    ///\e
 		    TimeStamp &operator/=(double b)
+		    {
 		      utime/=b;
 		      stime/=b;
 		      cutime/=b;
 		      cstime/=b;
 		      rtime/=b;
 		      return *this;
+		    }
 		    ///\e
 		    TimeStamp operator/(double b) const
+		    {
 		      TimeStamp t(*this);
 		      return t/=b;
+		    }
 		    ///The time ellapsed since the last call of stamp()
 		    TimeStamp ellapsed() const
+		    {
 		      TimeStamp t(NULL);
 		      return t-*this;
+		    }
 		    friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
 		    ///Gives back the user time of the process
 		    double userTime() const
+		    {
 		      return utime;
+		    }
 		    ///Gives back the system time of the process
 		    double systemTime() const
+		    {
 		      return stime;
+		    }
 		    ///Gives back the user time of the process' children
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cUserTime() const
+		    {
 		      return cutime;
+		    }
 		    ///Gives back the user time of the process' children
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cSystemTime() const
+		    {
 		      return cstime;
+		    }
 		    ///Gives back the real time
 		    double realTime() const {return rtime;}
 		  };
 		  TimeStamp operator*(double b,const TimeStamp &t)
+		  {
 		    return t*b;
+		  }
 		  ///Prints the time counters
 		  ///Prints the time counters in the following form:
 		  ///
 		  /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
 		  ///
 		  /// where the values are the
 		  /// \li \c u: user cpu time,
 		  /// \li \c s: system cpu time,
 		  /// \li \c cu: user cpu time of children,
 		  /// \li \c cs: system cpu time of children,
 		  /// \li \c real: real time.
 		  /// \relates TimeStamp
 		  /// \note On <tt>WIN32</tt> platform the cummulative values are not
 		  /// calculated.
 		  inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
+		  {
 		    os << "u: " << t.userTime() <<
 		      "s, s: " << t.systemTime() <<
 		      "s, cu: " << t.cUserTime() <<
 		      "s, cs: " << t.cSystemTime() <<
 		      "s, real: " << t.realTime() << "s";
 		    return os;
+		  }
 		  ///Class for measuring the cpu time and real time usage of the process
 		  ///Class for measuring the cpu time and real time usage of the process.
 		  ///It is quite easy-to-use, here is a short example.
 		  ///\code
 		  /// #include<lemon/time_measure.h>
 		  /// #include<iostream>
 		  ///
 		  /// int main()
 		  /// {
 		  ///
 		  ///   ...
 		  ///
 		  ///   Timer t;
 		  ///   doSomething();
 		  ///   std::cout << t << '\n';
 		  ///   t.restart();
 		  ///   doSomethingElse();
 		  ///   std::cout << t << '\n';
 		  ///
 		  ///   ...
 		  ///
 		  /// }
 		  ///\endcode
 		  ///
 		  ///The \ref Timer can also be \ref stop() "stopped" and
 		  ///\ref start() "started" again, so it is possible to compute collected
 		  ///running times.
 		  ///
 		  ///\warning Depending on the operation system and its actual configuration
 		  ///the time counters have a certain (10ms on a typical Linux system)
 		  ///granularity.
 		  ///Therefore this tool is not appropriate to measure very short times.
 		  ///Also, if you start and stop the timer very frequently, it could lead to
 		  ///distorted results.
 		  ///
 		  ///\note If you want to measure the running time of the execution of a certain
 		  ///function, consider the usage of \ref TimeReport instead.
 		  ///
 		  ///\todo This shouldn't be Unix (Linux) specific.
 		  ///\sa TimeReport
 		  ///
 		  ///\author Alpar Juttner
 		  class Timer
+		  {
 		    int _running; //Timer is running iff _running>0; (_running>=0 always holds)
 		    TimeStamp start_time; //This is the relativ start-time if the timer
 		                          //is _running, the collected _running time otherwise.
 		    void _reset() {if(_running) start_time.stamp(); else start_time.reset();}
 		  public:
 		    ///Constructor.
 		    ///\param run indicates whether or not the timer starts immediately.
 		    ///
 		    Timer(bool run=true) :_running(run) {_reset();}
 		    ///\name Control the state of the timer
 		    ///Basically a Timer can be either running or stopped,
 		    ///but it provides a bit finer control on the execution.
 		    ///The \ref Timer also counts the number of \ref start()
 		    ///executions, and is stops only after the same amount (or more)
 		    ///\ref stop() "stop()"s. This can be useful e.g. to compute the running time
 		    ///of recursive functions.
 		    ///
 		    ///@{
 		    ///Reset and stop the time counters
 		    ///This function resets and stops the time counters
 		    ///\sa restart()
 		    void reset()
+		    {
 		      _running=0;
 		      _reset();
+		    }
 		    ///Start the time counters
 		    ///This function starts the time counters.
 		    ///
 		    ///If the timer is started more than ones, it will remain running
 		    ///until the same amount of \ref stop() is called.
 		    ///\sa stop()
 		    void start()
+		    {
 		      if(_running) _running++;
 		      else {
 			_running=1;
 			TimeStamp t;
 			t.stamp();
 			start_time=t-start_time;
+		      }
+		    }
 		    ///Stop the time counters
 		    ///This function stops the time counters. If start() was executed more than
 		    ///once, then the same number of stop() execution is necessary the really
 		    ///stop the timer.
 		    ///
 		    ///\sa halt()
 		    ///\sa start()
 		    ///\sa restart()
 		    ///\sa reset()
 		    void stop()
+		    {
 		      if(_running && !--_running) {
 			TimeStamp t;
 			t.stamp();
 			start_time=t-start_time;
+		      }
+		    }
 		    ///Halt (i.e stop immediately) the time counters
 		    ///This function stops immediately the time counters, i.e. <tt>t.halt()</tt>
 		    ///is a faster
 		    ///equivalent of the following.
 		    ///\code
 		    ///  while(t.running()) t.stop()
 		    ///\endcode
 		    ///
 		    ///
 		    ///\sa stop()
 		    ///\sa restart()
 		    ///\sa reset()
 		    void halt()
+		    {
 		      if(_running) {
 			_running=0;
 			TimeStamp t;
 			t.stamp();
 			start_time=t-start_time;
+		      }
+		    }
 		    ///Returns the running state of the timer
 		    ///This function returns the number of stop() exections that is
 		    ///necessary to really stop the timer.
 		    ///For example the timer
 		    ///is running if and only if the return value is \c true
 		    ///(i.e. greater than
 		    ///zero).
 		    int running()  { return _running; }
 		    ///Restart the time counters
 		    ///This function is a shorthand for
 		    ///a reset() and a start() calls.
 		    ///
 		    void restart()
+		    {
 		      reset();
 		      start();
+		    }
 		    ///@}
 		    ///\name Query Functions for the ellapsed time
 		    ///@{
 		    ///Gives back the ellapsed user time of the process
 		    double userTime() const
+		    {
 		      return operator TimeStamp().userTime();
+		    }
 		    ///Gives back the ellapsed system time of the process
 		    double systemTime() const
+		    {
 		      return operator TimeStamp().systemTime();
+		    }
 		    ///Gives back the ellapsed user time of the process' children
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cUserTime() const
+		    {
 		      return operator TimeStamp().cUserTime();
+		    }
 		    ///Gives back the ellapsed user time of the process' children
 		    ///\note On <tt>WIN32</tt> platform this value is not calculated.
 		    ///
 		    double cSystemTime() const
+		    {
 		      return operator TimeStamp().cSystemTime();
+		    }
 		    ///Gives back the ellapsed real time
 		    double realTime() const
+		    {
 		      return operator TimeStamp().realTime();
+		    }
 		    ///Computes the ellapsed time
 		    ///This conversion computes the ellapsed time, therefore you can print
 		    ///the ellapsed time like this.
 		    ///\code
 		    ///  Timer t;
 		    ///  doSomething();
 		    ///  std::cout << t << '\n';
 		    ///\endcode
 		    operator TimeStamp () const
+		    {
 		      TimeStamp t;
 		      t.stamp();
 		      return _running?t-start_time:start_time;
+		    }
 		    ///@}
 		  };
 		  ///Same as \ref Timer but prints a report on destruction.
 		  ///Same as \ref Timer but prints a report on destruction.
 		  ///This example shows its usage.
 		  ///\code
 		  ///  void myAlg(ListGraph &g,int n)
 		  ///  {
 		  ///    TimeReport tr("Running time of myAlg: ");
 		  ///    ... //Here comes the algorithm
 		  ///  }
 		  ///\endcode
 		  ///
 		  ///\sa Timer
 		  ///\sa NoTimeReport
 		  ///\todo There is no test case for this
 		  class TimeReport : public Timer
+		  {
 		    std::string _title;
 		    std::ostream &_os;
 		  public:
 		    ///\e
 		    ///\param title This text will be printed before the ellapsed time.
 		    ///\param os The stream to print the report to.
 		    ///\param run Sets whether the timer should start immediately.
 		    TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true)
 		      : Timer(run), _title(title), _os(os){}
 		    ///\e Prints the ellapsed time on destruction.
 		    ~TimeReport()
+		    {
 		      _os << _title << *this << std::endl;
+		    }
 		  };
 		  ///'Do nothing' version of \ref TimeReport
 		  ///\sa TimeReport
 		  ///
 		  class NoTimeReport
+		  {
 		  public:
 		    ///\e
 		    NoTimeReport(std::string,std::ostream &,bool) {}
 		    ///\e
 		    NoTimeReport(std::string,std::ostream &) {}
 		    ///\e
 		    NoTimeReport(std::string) {}
 		    ///\e Do nothing.
 		    ~NoTimeReport() {}
 		    operator TimeStamp () const { return TimeStamp(); }
 		    void reset() {}
 		    void start() {}
 		    void stop() {}
 		    void halt() {}
 		    int running() { return 0; }
 		    void restart() {}
 		    double userTime() const { return 0; }
 		    double systemTime() const { return 0; }
 		    double cUserTime() const { return 0; }
 		    double cSystemTime() const { return 0; }
 		    double realTime() const { return 0; }
 		  };
 		  ///Tool to measure the running time more exactly.
 		  ///This function calls \c f several times and returns the average
 		  ///running time. The number of the executions will be choosen in such a way
 		  ///that the full real running time will be roughly between \c min_time
 		  ///and <tt>2*min_time</tt>.
 		  ///\param f the function object to be measured.
 		  ///\param min_time the minimum total running time.
 		  ///\retval num if it is not \c NULL, then the actual
 		  ///        number of execution of \c f will be written into <tt>*num</tt>.
 		  ///\retval full_time if it is not \c NULL, then the actual
 		  ///        total running time will be written into <tt>*full_time</tt>.
 		  ///\return The average running time of \c f.
 		  template<class F>
 		  TimeStamp runningTimeTest(F f,double min_time=10,unsigned int *num = NULL,
 		                            TimeStamp *full_time=NULL)
+		  {
 		    TimeStamp full;
 		    unsigned int total=0;
 		    Timer t;
 		    for(unsigned int tn=1;tn <= 1U<<31 && full.realTime()<=min_time; tn*=2) {
 		      for(;total<tn;total++) f();
 		      full=t;
+		    }
 		    if(num) *num=total;
 		    if(full_time) *full_time=full;
 		    return full/total;
+		  }
 		  /// @}
 		} //namespace lemon
 		#endif //LEMON_TIME_MEASURE_H

benchmark/Makefile

Show inline comments

1		all:
2		$(MAKE) -C ..

demo/Makefile

Show inline comments

1		all:
2		$(MAKE) -C ..

doc/Makefile

Show inline comments

1		all:
2		$(MAKE) -C ..

lemon/Makefile

Show inline comments

1		all:
2		$(MAKE) -C ..

test/Makefile

Show inline comments

1		all:
2		$(MAKE) -C ..

tools/Makefile

Show inline comments

1		all:
2		$(MAKE) -C ..

0 comments (0 inline)

RhodeCode

Login to your account