LEMON/LEMON-official Changeset - r1128:426a704d7483

Repositories » LEMON » LEMON-official

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

Changeset - r1128:426a704d7483

« 1125:b87335
« 1124:b1744d

1129:9a3187 »

r1128:426a704d7483

Fri, 20 Jan 2012 19:23:48

[Not Reviewed]

0 comments (0 inline)

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

Merge Intel C++ compatibility fixes

0 7 0

merge default

6 files changed with 37 insertions and 6 deletions:

CMakeLists.txt

lemon/bfs.h

lemon/concepts/graph_components.h

lemon/concepts/heap.h

lemon/concepts/maps.h

lemon/concepts/path.h

lemon/dfs.h

↑ Collapse diff ↑

CMakeLists.txt

Show inline comments

 		CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
 		SET(PROJECT_NAME "LEMON")
 		PROJECT(${PROJECT_NAME})
 		INCLUDE(FindPythonInterp)
 		INCLUDE(FindWget)
 		IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
 		  INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
 		ELSEIF(DEFINED ENV{LEMON_VERSION})
 		  SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
 		ELSE()
 		  EXECUTE_PROCESS(
 		    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
 		    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
 		    OUTPUT_VARIABLE HG_REVISION_PATH
 		    ERROR_QUIET
 		    OUTPUT_STRIP_TRAILING_WHITESPACE
+		  )
 		  EXECUTE_PROCESS(
 		    COMMAND hg id -i
 		    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
 		    OUTPUT_VARIABLE HG_REVISION
 		    ERROR_QUIET
 		    OUTPUT_STRIP_TRAILING_WHITESPACE
+		  )
 		  IF(HG_REVISION STREQUAL "")
 		    SET(HG_REVISION_ID "hg-tip")
 		  ELSE()
 		    IF(HG_REVISION_PATH STREQUAL "")
 		      SET(HG_REVISION_ID ${HG_REVISION})
 		    ELSE()
 		      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
 		    ENDIF()
 		  ENDIF()
 		  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
 		ENDIF()
 		SET(PROJECT_VERSION ${LEMON_VERSION})
 		SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
 		FIND_PACKAGE(Doxygen)
 		FIND_PACKAGE(Ghostscript)
 		FIND_PACKAGE(GLPK 4.33)
 		FIND_PACKAGE(CPLEX)
 		FIND_PACKAGE(COIN)
 		IF(DEFINED ENV{LEMON_CXX_WARNING})
 		  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
 		ELSE()
 		  IF(CMAKE_COMPILER_IS_GNUCXX)
 		    SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
 		    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
 		    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
 		  ELSEIF(MSVC)
 		    # This part is unnecessary 'casue the same is set by the lemon/core.h.
 		    # Still keep it as an example.
 		    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
 		    # Suppressed warnings:
 		    # C4250: 'class1' : inherits 'class2::member' via dominance
 		    # C4355: 'this' : used in base member initializer list
 		    # C4503: 'function' : decorated name length exceeded, name was truncated
 		    # C4800: 'type' : forcing value to bool 'true' or 'false'
 		    #        (performance warning)
 		    # C4996: 'function': was declared deprecated
 		  ELSE()
-		    SET(CXX_WARNING "-Wall -W")
 		    SET(CXX_WARNING "-Wall")
 		  ENDIF()
 		ENDIF()
 		SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
 		SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
 		SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
+		SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
 		    "Flags used by the C++ compiler during maintainer builds."
 		    FORCE )
 		SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
+		SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
 		    "Flags used by the C compiler during maintainer builds."
 		    FORCE )
 		SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
 		    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
 		    "Flags used for linking binaries during maintainer builds."
 		    FORCE )
 		SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
 		    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
 		    "Flags used by the shared libraries linker during maintainer builds."
 		    FORCE )
 		MARK_AS_ADVANCED(
 		    CMAKE_CXX_FLAGS_MAINTAINER
 		    CMAKE_C_FLAGS_MAINTAINER
 		    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
 		    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
 		IF(CMAKE_CONFIGURATION_TYPES)
 		  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
 		  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
 		  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
 		      "Add the configurations that we need"
 		      FORCE)
 		 endif()
 		IF(NOT CMAKE_BUILD_TYPE)
 		  SET(CMAKE_BUILD_TYPE "Release")
 		ENDIF()
 		SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
 		    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
 		    FORCE )
 		INCLUDE(CheckTypeSize)
 		CHECK_TYPE_SIZE("long long" LONG_LONG)
 		SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
 		ENABLE_TESTING()
 		IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
 		  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
 		ELSE()
 		  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
 		ENDIF()
 		ADD_SUBDIRECTORY(lemon)
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		  ADD_SUBDIRECTORY(contrib)
 		  ADD_SUBDIRECTORY(demo)
 		  ADD_SUBDIRECTORY(tools)
 		  ADD_SUBDIRECTORY(doc)
 		  ADD_SUBDIRECTORY(test)
 		ENDIF()
 		CONFIGURE_FILE(
 		  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
 		  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		  @ONLY
+		)
 		IF(UNIX)
 		  INSTALL(
 		    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		    DESTINATION share/lemon/cmake
+		  )
 		ELSEIF(WIN32)
 		  INSTALL(
 		    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		    DESTINATION cmake
+		  )
 		ENDIF()
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
 		  SET(CPACK_PACKAGE_VENDOR "EGRES")
 		  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
 		    "LEMON - Library for Efficient Modeling and Optimization in Networks")
 		  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
 		  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
 		  SET(CPACK_PACKAGE_INSTALL_DIRECTORY
 		    "${PROJECT_NAME} ${PROJECT_VERSION}")
 		  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
 		    "${PROJECT_NAME} ${PROJECT_VERSION}")
 		  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
 		  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
 		  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
 		  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
 		  SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
 		    "C++ header files")
 		  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
 		    "DLL and import library")
 		  SET(CPACK_COMPONENT_BIN_DESCRIPTION
 		    "Command line utilities")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
 		    "Doxygen generated documentation")
 		  SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
 		  SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
 		  SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
 		  SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
 		    "Components needed to develop software using LEMON")
 		  SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
 		    "Documentation of LEMON")
 		  SET(CPACK_ALL_INSTALL_TYPES Full Developer)
 		  SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
 		  SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
 		  SET(CPACK_GENERATOR "NSIS")
 		  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
 		  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
 		  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
 		  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
 		  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
 		  SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
 		    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
 		    ")
 		  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
 		    !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
 		    Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
 		    ")
 		  INCLUDE(CPack)
 		ENDIF()

lemon/bfs.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BFS_H
 		#define LEMON_BFS_H
 		///\ingroup search
 		///\file
 		///\brief BFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///Default traits class of Bfs class.
 		  ///Default traits class of Bfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \c PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \c ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must conform to
 		    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \c ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \c DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref DistMap.
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%BFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %BFS algorithm.
 		  ///
 		  ///There is also a \ref bfs() "function-type interface" for the BFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default type is \ref ListDigraph.
 		  ///\tparam TR The traits class that defines various types used by the
 		  ///algorithm. By default, it is \ref BfsDefaultTraits
 		  ///"BfsDefaultTraits<GR>".
 		  ///In most cases, this parameter should not be set directly,
 		  ///consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=BfsDefaultTraits<GR> >
 		#endif
 		  class Bfs {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::Node> _queue;
 		    int _queue_head,_queue_tail,_queue_next_dist;
 		    int _curr_dist;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Bfs() {}
 		  public:
 		    typedef Bfs Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 		      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "DistMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///It must conform to
 		    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
 		    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ProcessedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap :
 		      public Bfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param g The digraph the algorithm runs on.
 		    Bfs(const Digraph &g) :
 		      G(&g),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _reached(NULL), local_reached(false),
 		      _processed(NULL), local_processed(false)
 		    { }
 		    ///Destructor.
 		    ~Bfs()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_reached) delete _reached;
 		      if(local_processed) delete _processed;
+		    }
 		    ///Sets the map that stores the predecessor arcs.
 		    ///Sets the map that stores the predecessor arcs.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are reached.
 		    ///Sets the map that indicates which nodes are reached.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &reachedMap(ReachedMap &m)
+		    {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are processed.
 		    ///Sets the map that indicates which nodes are processed.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &processedMap(ProcessedMap &m)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
+		      }
 		      _processed = &m;
 		      return *this;
+		    }
 		    ///Sets the map that stores the distances of the nodes.
 		    ///Sets the map that stores the distances of the nodes calculated by
 		    ///the algorithm.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &distMap(DistMap &m)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;
+		    }
 		  public:
 		    ///\name Execution Control
 		    ///The simplest way to execute the BFS algorithm is to use one of the
 		    ///member functions called \ref run(Node) "run()".\n
 		    ///If you need better control on the execution, you have to call
 		    ///\ref init() first, then you can add several source nodes with
 		    ///\ref addSource(). Finally the actual path computation can be
 		    ///performed with one of the \ref start() functions.
 		    ///@{
 		    ///\brief Initializes the internal data structures.
 		    ///
 		    ///Initializes the internal data structures.
 		    void init()
+		    {
 		      create_maps();
 		      _queue.resize(countNodes(*G));
 		      _queue_head=_queue_tail=0;
 		      _curr_dist=1;
 		      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 		        _pred->set(u,INVALID);
 		        _reached->set(u,false);
 		        _processed->set(u,false);
+		      }
+		    }
 		    ///Adds a new source node.
 		    ///Adds a new source node to the set of nodes to be processed.
 		    ///
 		    void addSource(Node s)
+		    {
 		      if(!(*_reached)[s])
+		        {
 		          _reached->set(s,true);
 		          _pred->set(s,INVALID);
 		          _dist->set(s,0);
 		          _queue[_queue_head++]=s;
 		          _queue_next_dist=_queue_head;
+		        }
+		    }
 		    ///Processes the next node.
 		    ///Processes the next node.
 		    ///
 		    ///\return The processed node.
 		    ///
 		    ///\pre The queue must not be empty.
 		    Node processNextNode()
+		    {
 		      if(_queue_tail==_queue_next_dist) {
 		        _curr_dist++;
 		        _queue_next_dist=_queue_head;
+		      }
 		      Node n=_queue[_queue_tail++];
 		      _processed->set(n,true);
 		      Node m;
 		      for(OutArcIt e(*G,n);e!=INVALID;++e)
 		        if(!(*_reached)[m=G->target(e)]) {
 		          _queue[_queue_head++]=m;
 		          _reached->set(m,true);
 		          _pred->set(m,e);
 		          _dist->set(m,_curr_dist);
+		        }
 		      return n;
+		    }
 		    ///Processes the next node.
 		    ///Processes the next node and checks if the given target node
 		    ///is reached. If the target node is reachable from the processed
 		    ///node, then the \c reach parameter will be set to \c true.
 		    ///
 		    ///\param target The target node.
 		    ///\retval reach Indicates if the target node is reached.
 		    ///It should be initially \c false.
 		    ///
 		    ///\return The processed node.
 		    ///
 		    ///\pre The queue must not be empty.
 		    Node processNextNode(Node target, bool& reach)
+		    {
 		      if(_queue_tail==_queue_next_dist) {
 		        _curr_dist++;
 		        _queue_next_dist=_queue_head;
+		      }
 		      Node n=_queue[_queue_tail++];
 		      _processed->set(n,true);
 		      Node m;
 		      for(OutArcIt e(*G,n);e!=INVALID;++e)
 		        if(!(*_reached)[m=G->target(e)]) {
 		          _queue[_queue_head++]=m;
 		          _reached->set(m,true);
 		          _pred->set(m,e);
 		          _dist->set(m,_curr_dist);
 		          reach = reach || (target == m);
+		        }
 		      return n;
+		    }
 		    ///Processes the next node.
 		    ///Processes the next node and checks if at least one of reached
 		    ///nodes has \c true value in the \c nm node map. If one node
 		    ///with \c true value is reachable from the processed node, then the
 		    ///\c rnode parameter will be set to the first of such nodes.
 		    ///
 		    ///\param nm A \c bool (or convertible) node map that indicates the
 		    ///possible targets.
 		    ///\retval rnode The reached target node.
 		    ///It should be initially \c INVALID.
 		    ///
 		    ///\return The processed node.
 		    ///
 		    ///\pre The queue must not be empty.
 		    template<class NM>
 		    Node processNextNode(const NM& nm, Node& rnode)
+		    {
 		      if(_queue_tail==_queue_next_dist) {
 		        _curr_dist++;
 		        _queue_next_dist=_queue_head;
+		      }
 		      Node n=_queue[_queue_tail++];
 		      _processed->set(n,true);
 		      Node m;
 		      for(OutArcIt e(*G,n);e!=INVALID;++e)
 		        if(!(*_reached)[m=G->target(e)]) {
 		          _queue[_queue_head++]=m;
 		          _reached->set(m,true);
 		          _pred->set(m,e);
 		          _dist->set(m,_curr_dist);
 		          if (nm[m] && rnode == INVALID) rnode = m;
+		        }
 		      return n;
+		    }
 		    ///The next node to be processed.
 		    ///Returns the next node to be processed or \c INVALID if the queue
 		    ///is empty.
 		    Node nextNode() const
+		    {
 		      return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
+		    }
 		    ///Returns \c false if there are nodes to be processed.
 		    ///Returns \c false if there are nodes to be processed
 		    ///in the queue.
 		    bool emptyQueue() const { return _queue_tail==_queue_head; }
 		    ///Returns the number of the nodes to be processed.
 		    ///Returns the number of the nodes to be processed
 		    ///in the queue.
 		    int queueSize() const { return _queue_head-_queue_tail; }
 		    ///Executes the algorithm.
 		    ///Executes the algorithm.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s)
 		    ///in order to compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree (forest),
 		    ///- the distance of each node from the root(s).
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>b.start()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  while ( !b.emptyQueue() ) {
 		    ///    b.processNextNode();
 		    ///  }
 		    ///\endcode
 		    void start()
+		    {
 		      while ( !emptyQueue() ) processNextNode();
+		    }
 		    ///Executes the algorithm until the given target node is reached.
 		    ///Executes the algorithm until the given target node is reached.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s)
 		    ///in order to compute the shortest path to \c t.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path to \c t,
 		    ///- the distance of \c t from the root(s).
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  bool reach = false;
 		    ///  while ( !b.emptyQueue() && !reach ) {
 		    ///    b.processNextNode(t, reach);
 		    ///  }
 		    ///\endcode
 		    void start(Node t)
+		    {
 		      bool reach = false;
 		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
 		    ///Executes the algorithm until a condition is met.
 		    ///Executes the algorithm until a condition is met.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s) in
 		    ///order to compute the shortest path to a node \c v with
 		    /// <tt>nm[v]</tt> true, if such a node can be found.
 		    ///
 		    ///\param nm A \c bool (or convertible) node map. The algorithm
 		    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
 		    ///
 		    ///\return The reached node \c v with <tt>nm[v]</tt> true or
 		    ///\c INVALID if no such node was found.
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  Node rnode = INVALID;
 		    ///  while ( !b.emptyQueue() && rnode == INVALID ) {
 		    ///    b.processNextNode(nm, rnode);
 		    ///  }
 		    ///  return rnode;
 		    ///\endcode
 		    template<class NodeBoolMap>
 		    Node start(const NodeBoolMap &nm)
+		    {
 		      Node rnode = INVALID;
 		      while ( !emptyQueue() && rnode == INVALID ) {
 		        processNextNode(nm, rnode);
+		      }
 		      return rnode;
+		    }
 		    ///Runs the algorithm from the given source node.
 		    ///This method runs the %BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree,
 		    ///- the distance of each node from the root.
 		    ///
 		    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  b.addSource(s);
 		    ///  b.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs the %BFS algorithm from node \c s
 		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    ///
 		    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
 		    ///shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  b.addSource(s);
 		    ///  b.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    ///Runs the algorithm to visit all nodes in the digraph.
 		    ///This method runs the %BFS algorithm in order to visit all nodes
 		    ///in the digraph.
 		    ///
 		    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  for (NodeIt n(gr); n != INVALID; ++n) {
 		    ///    if (!b.reached(n)) {
 		    ///      b.addSource(n);
 		    ///      b.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt n(*G); n != INVALID; ++n) {
 		        if (!reached(n)) {
 		          addSource(n);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The results of the BFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref run(Node) "run()" or \ref start() should be called
 		    ///before using them.
 		    ///@{
 		    ///The shortest path to the given node.
 		    ///Returns the shortest path to the given node from the root(s).
 		    ///
 		    ///\warning \c t should be reached from the root(s).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///The distance of the given node from the root(s).
 		    ///Returns the distance of the given node from the root(s).
 		    ///
 		    ///\warning If node \c v is not reached from the root(s), then
 		    ///the return value of this function is undefined.
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///\brief Returns the 'previous arc' of the shortest path tree for
 		    ///the given node.
 		    ///
 		    ///This function returns the 'previous arc' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last arc of a
 		    ///shortest path from a root to \c v. It is \c INVALID if \c v
 		    ///is not reached from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predNode() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///\brief Returns the 'previous node' of the shortest path tree for
 		    ///the given node.
 		    ///
 		    ///This function returns the 'previous node' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last but one node
 		    ///of a shortest path from a root to \c v. It is \c INVALID
 		    ///if \c v is not reached from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predArc() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->source((*_pred)[v]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    /// distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the distances
 		    ///of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the shortest path tree (forest).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if the given node is reached from the root(s).
 		    ///Returns \c true if \c v is reached from the root(s).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of bfs() function.
 		  ///Default traits class of bfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsWizardDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
 		    ///This function instantiates a ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must conform to
 		    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a ReachedMap.
 		    ///This function instantiates a ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a DistMap.
 		    ///This function instantiates a DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the DistMap
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
 		    ///It must conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by BfsWizard
 		  /// Default traits class used by BfsWizard.
 		  /// \tparam GR The type of the digraph.
 		  template<class GR>
 		  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
+		  {
 		    typedef BfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the shortest path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    int *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, it initiates
 		    /// all of the attributes to \c 0.
 		    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires one parameter,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    BfsWizardBase(const GR &g) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of BFS algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
 		  /// It does not have own \ref run(Node) "run()" method, it uses the
 		  /// functions and features of the plain \ref Bfs.
 		  ///
 		  /// This class should only be used through the \ref bfs() function,
 		  /// which makes it easier to use the algorithm.
 		  ///
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm.
 		  template<class TR>
 		  class BfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::ReachedMap ReachedMap;
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    BfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param g The digraph the algorithm runs on.
 		    BfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
 		    BfsWizard(const TR &b) : TR(b) {}
 		    ~BfsWizard() {}
 		    ///Runs BFS algorithm from the given source node.
 		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    void run(Node s)
+		    {
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if (s!=INVALID)
 		        alg.run(s);
 		      else
 		        alg.run();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)
+		    {
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      alg.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
 		      if (Base::_di)
 		        *Base::_di = alg.dist(t);
 		      return alg.reached(t);
+		    }
 		    ///Runs BFS algorithm to visit all nodes in the digraph.
 		    ///This method runs BFS algorithm in order to visit all nodes
 		    ///in the digraph.
 		    void run()
+		    {
 		      run(INVALID);
+		    }
 		    template<class T>
 		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the predecessor map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the reached map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are reached.
 		    template<class T>
 		    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the distance map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the distances of the nodes calculated
 		    ///by the algorithm.
 		    template<class T>
 		    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetDistMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter" for setting
 		    ///the processed map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are processed.
 		    template<class T>
 		    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetPathBase : public Base {
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the shortest path to the target node.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the shortest path to the target node.
 		    template<class T>
 		    BfsWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetPathBase<T> >(*this);
+		    }
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the distance of the target node.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the distance of the target node.
 		    BfsWizard dist(const int &d)
+		    {
 		      Base::_di=const_cast<int*>(&d);
 		      return *this;
+		    }
 		  };
 		  ///Function-type interface for BFS algorithm.
 		  /// \ingroup search
 		  ///Function-type interface for BFS algorithm.
 		  ///
 		  ///This function also has several \ref named-func-param "named parameters",
 		  ///they are declared as the members of class \ref BfsWizard.
 		  ///The following examples show how to use these parameters.
 		  ///\code
 		  ///  // Compute shortest path from node s to each node
 		  ///  bfs(g).predMap(preds).distMap(dists).run(s);
 		  ///
 		  ///  // Compute shortest path from s to t
 		  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
 		  ///to the end of the parameter list.
 		  ///\sa BfsWizard
 		  ///\sa Bfs
 		  template<class GR>
 		  BfsWizard<BfsWizardBase<GR> >
 		  bfs(const GR &digraph)
+		  {
 		    return BfsWizard<BfsWizardBase<GR> >(digraph);
+		  }
 		#ifdef DOXYGEN
 		  /// \brief Visitor class for BFS.
 		  ///
 		  /// This class defines the interface of the BfsVisit events, and
 		  /// it could be the base of a real visitor class.
 		  template <typename GR>
 		  struct BfsVisitor {
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    /// \brief Called for the source node(s) of the BFS.
 		    ///
 		    /// This function is called for the source node(s) of the BFS.
 		    void start(const Node& node) {}
 		    /// \brief Called when a node is reached first time.
 		    ///
 		    /// This function is called when a node is reached first time.
 		    void reach(const Node& node) {}
 		    /// \brief Called when a node is processed.
 		    ///
 		    /// This function is called when a node is processed.
 		    void process(const Node& node) {}
 		    /// \brief Called when an arc reaches a new node.
 		    ///
 		    /// This function is called when the BFS finds an arc whose target node
 		    /// is not reached yet.
 		    void discover(const Arc& arc) {}
 		    /// \brief Called when an arc is examined but its target node is
 		    /// already discovered.
 		    ///
 		    /// This function is called when an arc is examined but its target node is
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		  };
 		#else
 		  template <typename GR>
 		  struct BfsVisitor {
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    void start(const Node&) {}
 		    void reach(const Node&) {}
 		    void process(const Node&) {}
 		    void discover(const Arc&) {}
 		    void examine(const Arc&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 		        Arc arc;
 		        Node node;
 		        visitor.start(node);
 		        visitor.reach(node);
 		        visitor.process(node);
 		        visitor.discover(arc);
 		        visitor.examine(arc);
+		      }
 		      _Visitor& visitor;
 		      Constraints() {}
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of BfsVisit class.
 		  ///
 		  /// Default traits class of BfsVisit class.
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  template<class GR>
 		  struct BfsVisitDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that indicates which nodes are reached.
 		    ///
 		    /// The type of the map that indicates which nodes are reached.
 		    /// It must conform to
 		    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a ReachedMap.
 		    ///
 		    /// This function instantiates a ReachedMap.
 		    /// \param digraph is the digraph, to which
 		    /// we would like to define the ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &digraph) {
 		      return new ReachedMap(digraph);
+		    }
 		  };
 		  /// \ingroup search
 		  ///
 		  /// \brief BFS algorithm class with visitor interface.
 		  ///
 		  /// This class provides an efficient implementation of the BFS algorithm
 		  /// with visitor interface.
 		  ///
 		  /// The BfsVisit class provides an alternative interface to the Bfs
 		  /// class. It works with callback mechanism, the BfsVisit object calls
 		  /// the member functions of the \c Visitor class on every BFS event.
 		  ///
 		  /// This interface of the BFS algorithm should be used in special cases
 		  /// when extra actions have to be performed in connection with certain
 		  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
 		  /// instead.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// The default type is \ref ListDigraph.
 		  /// The value of GR is not used directly by \ref BfsVisit,
 		  /// it is only passed to \ref BfsVisitDefaultTraits.
 		  /// \tparam VS The Visitor type that is used by the algorithm.
 		  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
 		  /// does not observe the BFS events. If you want to observe the BFS
 		  /// events, you should implement your own visitor class.
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref BfsVisitDefaultTraits
 		  /// "BfsVisitDefaultTraits<GR>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename VS, typename TR>
 		#else
 		  template <typename GR = ListDigraph,
 		            typename VS = BfsVisitor<GR>,
 		            typename TR = BfsVisitDefaultTraits<GR> >
 		#endif
 		  class BfsVisit {
 		  public:
 		    ///The traits class.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The visitor type used by the algorithm.
 		    typedef VS Visitor;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename Traits::ReachedMap ReachedMap;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *_digraph;
 		    //Pointer to the visitor object.
 		    Visitor *_visitor;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Node> _list;
 		    int _list_front, _list_back;
 		    //Creates the maps if necessary.
 		    void create_maps() {
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*_digraph);
+		      }
+		    }
 		  protected:
 		    BfsVisit() {}
 		  public:
 		    typedef BfsVisit Create;
 		    /// \name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public BfsVisit< Digraph, Visitor,
 		                                            SetReachedMapTraits<T> > {
 		      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param visitor The visitor object of the algorithm.
 		    BfsVisit(const Digraph& digraph, Visitor& visitor)
 		      : _digraph(&digraph), _visitor(&visitor),
 		        _reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ~BfsVisit() {
 		      if(local_reached) delete _reached;
+		    }
 		    /// \brief Sets the map that indicates which nodes are reached.
 		    ///
 		    /// Sets the map that indicates which nodes are reached.
 		    /// If you don't use this function before calling \ref run(Node) "run()"
 		    /// or \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt> (*this) </tt>
 		    BfsVisit &reachedMap(ReachedMap &m) {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached = false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  public:
 		    /// \name Execution Control
 		    /// The simplest way to execute the BFS algorithm is to use one of the
 		    /// member functions called \ref run(Node) "run()".\n
 		    /// If you need better control on the execution, you have to call
 		    /// \ref init() first, then you can add several source nodes with
 		    /// \ref addSource(). Finally the actual path computation can be
 		    /// performed with one of the \ref start() functions.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    void init() {
 		      create_maps();
 		      _list.resize(countNodes(*_digraph));
 		      _list_front = _list_back = -1;
 		      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
 		        _reached->set(u, false);
+		      }
+		    }
 		    /// \brief Adds a new source node.
 		    ///
 		    /// Adds a new source node to the set of nodes to be processed.
 		    void addSource(Node s) {
 		      if(!(*_reached)[s]) {
 		          _reached->set(s,true);
 		          _visitor->start(s);
 		          _visitor->reach(s);
 		          _list[++_list_back] = s;
+		        }
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    Node processNextNode() {
 		      Node n = _list[++_list_front];
 		      _visitor->process(n);
 		      Arc e;
 		      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 		        Node m = _digraph->target(e);
 		        if (!(*_reached)[m]) {
 		          _visitor->discover(e);
 		          _visitor->reach(m);
 		          _reached->set(m, true);
 		          _list[++_list_back] = m;
 		        } else {
 		          _visitor->examine(e);
+		        }
+		      }
 		      return n;
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node and checks if the given target node
 		    /// is reached. If the target node is reachable from the processed
 		    /// node, then the \c reach parameter will be set to \c true.
 		    ///
 		    /// \param target The target node.
 		    /// \retval reach Indicates if the target node is reached.
 		    /// It should be initially \c false.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    Node processNextNode(Node target, bool& reach) {
 		      Node n = _list[++_list_front];
 		      _visitor->process(n);
 		      Arc e;
 		      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 		        Node m = _digraph->target(e);
 		        if (!(*_reached)[m]) {
 		          _visitor->discover(e);
 		          _visitor->reach(m);
 		          _reached->set(m, true);
 		          _list[++_list_back] = m;
 		          reach = reach || (target == m);
 		        } else {
 		          _visitor->examine(e);
+		        }
+		      }
 		      return n;
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node and checks if at least one of reached
 		    /// nodes has \c true value in the \c nm node map. If one node
 		    /// with \c true value is reachable from the processed node, then the
 		    /// \c rnode parameter will be set to the first of such nodes.
 		    ///
 		    /// \param nm A \c bool (or convertible) node map that indicates the
 		    /// possible targets.
 		    /// \retval rnode The reached target node.
 		    /// It should be initially \c INVALID.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    template <typename NM>
 		    Node processNextNode(const NM& nm, Node& rnode) {
 		      Node n = _list[++_list_front];
 		      _visitor->process(n);
 		      Arc e;
 		      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 		        Node m = _digraph->target(e);
 		        if (!(*_reached)[m]) {
 		          _visitor->discover(e);
 		          _visitor->reach(m);
 		          _reached->set(m, true);
 		          _list[++_list_back] = m;
 		          if (nm[m] && rnode == INVALID) rnode = m;
 		        } else {
 		          _visitor->examine(e);
+		        }
+		      }
 		      return n;
+		    }
 		    /// \brief The next node to be processed.
 		    ///
 		    /// Returns the next node to be processed or \c INVALID if the queue
 		    /// is empty.
 		    Node nextNode() const {
 		      return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
+		    }
 		    /// \brief Returns \c false if there are nodes
 		    /// to be processed.
 		    ///
 		    /// Returns \c false if there are nodes
 		    /// to be processed in the queue.
 		    bool emptyQueue() const { return _list_front == _list_back; }
 		    /// \brief Returns the number of the nodes to be processed.
 		    ///
 		    /// Returns the number of the nodes to be processed in the queue.
 		    int queueSize() const { return _list_back - _list_front; }
 		    /// \brief Executes the algorithm.
 		    ///
 		    /// Executes the algorithm.
 		    ///
 		    /// This method runs the %BFS algorithm from the root node(s)
 		    /// in order to compute the shortest path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree (forest),
 		    /// - the distance of each node from the root(s).
 		    ///
 		    /// \pre init() must be called and at least one root node should be added
 		    /// with addSource() before using this function.
 		    ///
 		    /// \note <tt>b.start()</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   while ( !b.emptyQueue() ) {
 		    ///     b.processNextNode();
 		    ///   }
 		    /// \endcode
 		    void start() {
 		      while ( !emptyQueue() ) processNextNode();
+		    }
 		    /// \brief Executes the algorithm until the given target node is reached.
 		    ///
 		    /// Executes the algorithm until the given target node is reached.
 		    ///
 		    /// This method runs the %BFS algorithm from the root node(s)
 		    /// in order to compute the shortest path to \c t.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path to \c t,
 		    /// - the distance of \c t from the root(s).
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    ///
 		    /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   bool reach = false;
 		    ///   while ( !b.emptyQueue() && !reach ) {
 		    ///     b.processNextNode(t, reach);
 		    ///   }
 		    /// \endcode
 		    void start(Node t) {
 		      bool reach = false;
 		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
 		    /// \brief Executes the algorithm until a condition is met.
 		    ///
 		    /// Executes the algorithm until a condition is met.
 		    ///
 		    /// This method runs the %BFS algorithm from the root node(s) in
 		    /// order to compute the shortest path to a node \c v with
 		    /// <tt>nm[v]</tt> true, if such a node can be found.
 		    ///
 		    /// \param nm must be a bool (or convertible) node map. The
 		    /// algorithm will stop when it reaches a node \c v with
 		    /// <tt>nm[v]</tt> true.
 		    ///
 		    /// \return The reached node \c v with <tt>nm[v]</tt> true or
 		    /// \c INVALID if no such node was found.
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    ///
 		    /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   Node rnode = INVALID;
 		    ///   while ( !b.emptyQueue() && rnode == INVALID ) {
 		    ///     b.processNextNode(nm, rnode);
 		    ///   }
 		    ///   return rnode;
 		    /// \endcode
 		    template <typename NM>
 		    Node start(const NM &nm) {
 		      Node rnode = INVALID;
 		      while ( !emptyQueue() && rnode == INVALID ) {
 		        processNextNode(nm, rnode);
+		      }
 		      return rnode;
+		    }
 		    /// \brief Runs the algorithm from the given source node.
 		    ///
 		    /// This method runs the %BFS algorithm from node \c s
 		    /// in order to compute the shortest path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree,
 		    /// - the distance of each node from the root.
 		    ///
 		    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///   b.init();
 		    ///   b.addSource(s);
 		    ///   b.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    /// \brief Finds the shortest path between \c s and \c t.
 		    ///
 		    /// This method runs the %BFS algorithm from node \c s
 		    /// in order to compute the shortest path to node \c t
 		    /// (it stops searching when \c t is processed).
 		    ///
 		    /// \return \c true if \c t is reachable form \c s.
 		    ///
 		    /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
 		    /// shortcut of the following code.
 		    ///\code
 		    ///   b.init();
 		    ///   b.addSource(s);
 		    ///   b.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    /// \brief Runs the algorithm to visit all nodes in the digraph.
 		    ///
 		    /// This method runs the %BFS algorithm in order to visit all nodes
 		    /// in the digraph.
 		    ///
 		    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  for (NodeIt n(gr); n != INVALID; ++n) {
 		    ///    if (!b.reached(n)) {
 		    ///      b.addSource(n);
 		    ///      b.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt it(*_digraph); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    /// \name Query Functions
 		    /// The results of the BFS algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either \ref run(Node) "run()" or \ref start() should be called
 		    /// before using them.
 		    ///@{
 		    /// \brief Checks if the given node is reached from the root(s).
 		    ///
 		    /// Returns \c true if \c v is reached from the root(s).
 		    ///
 		    /// \pre Either \ref run(Node) "run()" or \ref init()
 		    /// must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif

lemon/concepts/graph_components.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * 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 graph_concepts
 		///\file
 		///\brief The concepts of graph components.
 		#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 		#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 		#include <lemon/core.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/bits/alteration_notifier.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
 		    ///
 		    /// This class describes the concept of \c Node, \c Arc and \c Edge
 		    /// subtypes of digraph and graph types.
 		    ///
 		    /// \note This class is a template class so that we can use it to
 		    /// create graph skeleton classes. The reason for this is that \c Node
 		    /// and \c Arc (or \c Edge) types should \e not derive from the same
 		    /// base class. For \c Node you should instantiate it with character
 		    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
 		#ifndef DOXYGEN
 		    template <char sel = '0'>
 		#endif
 		    class GraphItem {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
 		      /// \warning The default constructor is not required to set
 		      /// the item to some well-defined value. So you should consider it
 		      /// as uninitialized.
 		      GraphItem() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      GraphItem(const GraphItem &) {}
 		      /// \brief Constructor for conversion from \c INVALID.
 		      ///
 		      /// Constructor for conversion from \c INVALID.
 		      /// It initializes the item to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphItem(Invalid) {}
 		      /// \brief Assignment operator.
 		      ///
 		      /// Assignment operator for the item.
 		      GraphItem& operator=(const GraphItem&) { return *this; }
 		      /// \brief Assignment operator for INVALID.
 		      ///
 		      /// This operator makes the item invalid.
 		      GraphItem& operator=(Invalid) { return *this; }
 		      /// \brief Equality operator.
 		      ///
 		      /// Equality operator.
 		      bool operator==(const GraphItem&) const { return false; }
 		      /// \brief Inequality operator.
 		      ///
 		      /// Inequality operator.
 		      bool operator!=(const GraphItem&) const { return false; }
 		      /// \brief Ordering operator.
 		      ///
 		      /// This operator defines an ordering of the items.
 		      /// It makes possible to use graph item types as key types in
 		      /// associative containers (e.g. \c std::map).
 		      ///
 		      /// \note This operator only has to define some strict ordering of
 		      /// the items; this order has nothing to do with the iteration
 		      /// ordering of the items.
 		      bool operator<(const GraphItem&) const { return false; }
 		      template<typename _GraphItem>
 		      struct Constraints {
 		        void constraints() {
 		          _GraphItem i1;
 		          i1=INVALID;
 		          _GraphItem i2 = i1;
 		          _GraphItem i3 = INVALID;
 		          i1 = i2 = i3;
 		          bool b;
 		          b = (ia == ib) && (ia != ib);
 		          b = (ia == INVALID) && (ib != INVALID);
 		          b = (ia < ib);
+		        }
 		        const _GraphItem &ia;
 		        const _GraphItem &ib;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Base skeleton class for directed graphs.
 		    ///
 		    /// This class describes the base interface of directed graph types.
 		    /// All digraph %concepts have to conform to this class.
 		    /// It just provides types for nodes and arcs and functions
 		    /// to get the source and the target nodes of arcs.
 		    class BaseDigraphComponent {
 		    public:
 		      typedef BaseDigraphComponent Digraph;
 		      /// \brief Node class of the digraph.
 		      ///
 		      /// This class represents the nodes of the digraph.
 		      typedef GraphItem<'n'> Node;
 		      /// \brief Arc class of the digraph.
 		      ///
 		      /// This class represents the arcs of the digraph.
 		      typedef GraphItem<'a'> Arc;
 		      /// \brief Return the source node of an arc.
 		      ///
 		      /// This function returns the source node of an arc.
 		      Node source(const Arc&) const { return INVALID; }
 		      /// \brief Return the target node of an arc.
 		      ///
 		      /// This function returns the target node of an arc.
 		      Node target(const Arc&) const { return INVALID; }
 		      /// \brief Return the opposite node on the given arc.
 		      ///
 		      /// This function returns the opposite node on the given arc.
 		      Node oppositeNode(const Node&, const Arc&) const {
 		        return INVALID;
+		      }
 		      template <typename _Digraph>
 		      struct Constraints {
 		        typedef typename _Digraph::Node Node;
 		        typedef typename _Digraph::Arc Arc;
 		        void constraints() {
 		          checkConcept<GraphItem<'n'>, Node>();
 		          checkConcept<GraphItem<'a'>, Arc>();
+		          {
 		            Node n;
 		            Arc e(INVALID);
 		            n = digraph.source(e);
 		            n = digraph.target(e);
 		            n = digraph.oppositeNode(n, e);
+		          }
+		        }
 		        const _Digraph& digraph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Base skeleton class for undirected graphs.
 		    ///
 		    /// This class describes the base interface of undirected graph types.
 		    /// All graph %concepts have to conform to this class.
 		    /// It extends the interface of \ref BaseDigraphComponent with an
 		    /// \c Edge type and functions to get the end nodes of edges,
 		    /// to convert from arcs to edges and to get both direction of edges.
 		    class BaseGraphComponent : public BaseDigraphComponent {
 		    public:
 		      typedef BaseGraphComponent Graph;
 		      typedef BaseDigraphComponent::Node Node;
 		      typedef BaseDigraphComponent::Arc Arc;
 		      /// \brief Undirected edge class of the graph.
 		      ///
 		      /// This class represents the undirected edges of the graph.
 		      /// Undirected graphs can be used as directed graphs, each edge is
 		      /// represented by two opposite directed arcs.
 		      class Edge : public GraphItem<'e'> {
 		        typedef GraphItem<'e'> Parent;
 		      public:
 		        /// \brief Default constructor.
 		        ///
 		        /// Default constructor.
 		        /// \warning The default constructor is not required to set
 		        /// the item to some well-defined value. So you should consider it
 		        /// as uninitialized.
 		        Edge() {}
 		        /// \brief Copy constructor.
 		        ///
 		        /// Copy constructor.
 		        Edge(const Edge &) : Parent() {}
 		        /// \brief Constructor for conversion from \c INVALID.
 		        ///
 		        /// Constructor for conversion from \c INVALID.
 		        /// It initializes the item to be invalid.
 		        /// \sa Invalid for more details.
 		        Edge(Invalid) {}
 		        /// \brief Constructor for conversion from an arc.
 		        ///
 		        /// Constructor for conversion from an arc.
 		        /// Besides the core graph item functionality each arc should
 		        /// be convertible to the represented edge.
 		        Edge(const Arc&) {}
 		     };
 		      /// \brief Return one end node of an edge.
 		      ///
 		      /// This function returns one end node of an edge.
 		      Node u(const Edge&) const { return INVALID; }
 		      /// \brief Return the other end node of an edge.
 		      ///
 		      /// This function returns the other end node of an edge.
 		      Node v(const Edge&) const { return INVALID; }
 		      /// \brief Return a directed arc related to an edge.
 		      ///
 		      /// This function returns a directed arc from its direction and the
 		      /// represented edge.
 		      Arc direct(const Edge&, bool) const { return INVALID; }
 		      /// \brief Return a directed arc related to an edge.
 		      ///
 		      /// This function returns a directed arc from its source node and the
 		      /// represented edge.
 		      Arc direct(const Edge&, const Node&) const { return INVALID; }
 		      /// \brief Return the direction of the arc.
 		      ///
 		      /// Returns the direction of the arc. Each arc represents an
 		      /// edge with a direction. It gives back the
 		      /// direction.
 		      bool direction(const Arc&) const { return true; }
 		      /// \brief Return the opposite arc.
 		      ///
 		      /// This function returns the opposite arc, i.e. the arc representing
 		      /// the same edge and has opposite direction.
 		      Arc oppositeArc(const Arc&) const { return INVALID; }
 		      template <typename _Graph>
 		      struct Constraints {
 		        typedef typename _Graph::Node Node;
 		        typedef typename _Graph::Arc Arc;
 		        typedef typename _Graph::Edge Edge;
 		        void constraints() {
 		          checkConcept<BaseDigraphComponent, _Graph>();
 		          checkConcept<GraphItem<'e'>, Edge>();
+		          {
 		            Node n;
 		            Edge ue(INVALID);
 		            Arc e;
 		            n = graph.u(ue);
 		            n = graph.v(ue);
 		            e = graph.direct(ue, true);
 		            e = graph.direct(ue, false);
 		            e = graph.direct(ue, n);
 		            e = graph.oppositeArc(e);
 		            ue = e;
 		            bool d = graph.direction(e);
 		            ignore_unused_variable_warning(d);
+		          }
+		        }
 		        const _Graph& graph;
 		      Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for \e idable directed graphs.
 		    ///
 		    /// This class describes the interface of \e idable directed graphs.
 		    /// It extends \ref BaseDigraphComponent with the core ID functions.
 		    /// The ids of the items must be unique and immutable.
 		    /// This concept is part of the Digraph concept.
 		    template <typename BAS = BaseDigraphComponent>
 		    class IDableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// \brief Return a unique integer id for the given node.
 		      ///
 		      /// This function returns a unique integer id for the given node.
 		      int id(const Node&) const { return -1; }
 		      /// \brief Return the node by its unique id.
 		      ///
 		      /// This function returns the node by its unique id.
 		      /// If the digraph does not contain a node with the given id,
 		      /// then the result of the function is undefined.
 		      Node nodeFromId(int) const { return INVALID; }
 		      /// \brief Return a unique integer id for the given arc.
 		      ///
 		      /// This function returns a unique integer id for the given arc.
 		      int id(const Arc&) const { return -1; }
 		      /// \brief Return the arc by its unique id.
 		      ///
 		      /// This function returns the arc by its unique id.
 		      /// If the digraph does not contain an arc with the given id,
 		      /// then the result of the function is undefined.
 		      Arc arcFromId(int) const { return INVALID; }
 		      /// \brief Return an integer greater or equal to the maximum
 		      /// node id.
 		      ///
 		      /// This function returns an integer greater or equal to the
 		      /// maximum node id.
 		      int maxNodeId() const { return -1; }
 		      /// \brief Return an integer greater or equal to the maximum
 		      /// arc id.
 		      ///
 		      /// This function returns an integer greater or equal to the
 		      /// maximum arc id.
 		      int maxArcId() const { return -1; }
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph >();
 		          typename _Digraph::Node node;
 		          node=INVALID;
 		          int nid = digraph.id(node);
 		          nid = digraph.id(node);
 		          node = digraph.nodeFromId(nid);
 		          typename _Digraph::Arc arc;
 		          arc=INVALID;
 		          int eid = digraph.id(arc);
 		          eid = digraph.id(arc);
 		          arc = digraph.arcFromId(eid);
 		          nid = digraph.maxNodeId();
 		          ignore_unused_variable_warning(nid);
 		          eid = digraph.maxArcId();
 		          ignore_unused_variable_warning(eid);
+		        }
 		        const _Digraph& digraph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for \e idable undirected graphs.
 		    ///
 		    /// This class describes the interface of \e idable undirected
 		    /// graphs. It extends \ref IDableDigraphComponent with the core ID
 		    /// functions of undirected graphs.
 		    /// The ids of the items must be unique and immutable.
 		    /// This concept is part of the Graph concept.
 		    template <typename BAS = BaseGraphComponent>
 		    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Edge Edge;
 		      using IDableDigraphComponent<Base>::id;
 		      /// \brief Return a unique integer id for the given edge.
 		      ///
 		      /// This function returns a unique integer id for the given edge.
 		      int id(const Edge&) const { return -1; }
 		      /// \brief Return the edge by its unique id.
 		      ///
 		      /// This function returns the edge by its unique id.
 		      /// If the graph does not contain an edge with the given id,
 		      /// then the result of the function is undefined.
 		      Edge edgeFromId(int) const { return INVALID; }
 		      /// \brief Return an integer greater or equal to the maximum
 		      /// edge id.
 		      ///
 		      /// This function returns an integer greater or equal to the
 		      /// maximum edge id.
 		      int maxEdgeId() const { return -1; }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<IDableDigraphComponent<Base>, _Graph >();
 		          typename _Graph::Edge edge;
 		          int ueid = graph.id(edge);
 		          ueid = graph.id(edge);
 		          edge = graph.edgeFromId(ueid);
 		          ueid = graph.maxEdgeId();
 		          ignore_unused_variable_warning(ueid);
+		        }
 		        const _Graph& graph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
 		    ///
 		    /// This class describes the concept of \c NodeIt, \c ArcIt and
 		    /// \c EdgeIt subtypes of digraph and graph types.
 		    template <typename GR, typename Item>
 		    class GraphItemIt : public Item {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
 		      /// \warning The default constructor is not required to set
 		      /// the iterator to some well-defined value. So you should consider it
 		      /// as uninitialized.
 		      GraphItemIt() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      GraphItemIt(const GraphItemIt& it) : Item(it) {}
 		      /// \brief Constructor that sets the iterator to the first item.
 		      ///
 		      /// Constructor that sets the iterator to the first item.
 		      explicit GraphItemIt(const GR&) {}
 		      /// \brief Constructor for conversion from \c INVALID.
 		      ///
 		      /// Constructor for conversion from \c INVALID.
 		      /// It initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphItemIt(Invalid) {}
 		      /// \brief Assignment operator.
 		      ///
 		      /// Assignment operator for the iterator.
 		      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
 		      /// \brief Increment the iterator.
 		      ///
 		      /// This operator increments the iterator, i.e. assigns it to the
 		      /// next item.
 		      GraphItemIt& operator++() { return *this; }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator.
 		      /// Two iterators are equal if and only if they point to the
 		      /// same object or both are invalid.
 		      bool operator==(const GraphItemIt&) const { return true;}
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator.
 		      /// Two iterators are equal if and only if they point to the
 		      /// same object or both are invalid.
 		      bool operator!=(const GraphItemIt&) const { return true;}
 		      template<typename _GraphItemIt>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<GraphItem<>, _GraphItemIt>();
 		          _GraphItemIt it1(g);
 		          _GraphItemIt it2;
 		          _GraphItemIt it3 = it1;
 		          _GraphItemIt it4 = INVALID;
 		          it2 = ++it1;
 		          ++it2 = it1;
 		          ++(++it1);
 		          Item bi = it1;
 		          bi = it2;
+		        }
 		        const GR& g;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Concept class for \c InArcIt, \c OutArcIt and
 		    /// \c IncEdgeIt types.
 		    ///
 		    /// This class describes the concept of \c InArcIt, \c OutArcIt
 		    /// and \c IncEdgeIt subtypes of digraph and graph types.
 		    ///
 		    /// \note Since these iterator classes do not inherit from the same
 		    /// base class, there is an additional template parameter (selector)
 		    /// \c sel. For \c InArcIt you should instantiate it with character
 		    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
 		    template <typename GR,
 		              typename Item = typename GR::Arc,
 		              typename Base = typename GR::Node,
 		              char sel = '0'>
 		    class GraphIncIt : public Item {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
 		      /// \warning The default constructor is not required to set
 		      /// the iterator to some well-defined value. So you should consider it
 		      /// as uninitialized.
 		      GraphIncIt() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      GraphIncIt(const GraphIncIt& it) : Item(it) {}
 		      /// \brief Constructor that sets the iterator to the first
 		      /// incoming or outgoing arc.
 		      ///
 		      /// Constructor that sets the iterator to the first arc
 		      /// incoming to or outgoing from the given node.
 		      explicit GraphIncIt(const GR&, const Base&) {}
 		      /// \brief Constructor for conversion from \c INVALID.
 		      ///
 		      /// Constructor for conversion from \c INVALID.
 		      /// It initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphIncIt(Invalid) {}
 		      /// \brief Assignment operator.
 		      ///
 		      /// Assignment operator for the iterator.
 		      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
 		      /// \brief Increment the iterator.
 		      ///
 		      /// This operator increments the iterator, i.e. assigns it to the
 		      /// next arc incoming to or outgoing from the given node.
 		      GraphIncIt& operator++() { return *this; }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator.
 		      /// Two iterators are equal if and only if they point to the
 		      /// same object or both are invalid.
 		      bool operator==(const GraphIncIt&) const { return true;}
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator.
 		      /// Two iterators are equal if and only if they point to the
 		      /// same object or both are invalid.
 		      bool operator!=(const GraphIncIt&) const { return true;}
 		      template <typename _GraphIncIt>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<GraphItem<sel>, _GraphIncIt>();
 		          _GraphIncIt it1(graph, node);
 		          _GraphIncIt it2;
 		          _GraphIncIt it3 = it1;
 		          _GraphIncIt it4 = INVALID;
 		          it2 = ++it1;
 		          ++it2 = it1;
 		          ++(++it1);
 		          Item e = it1;
 		          e = it2;
+		        }
 		        const Base& node;
 		        const GR& graph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for iterable directed graphs.
 		    ///
 		    /// This class describes the interface of iterable directed
 		    /// graphs. It extends \ref BaseDigraphComponent with the core
 		    /// iterable interface.
 		    /// This concept is part of the Digraph concept.
 		    template <typename BAS = BaseDigraphComponent>
 		    class IterableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      typedef IterableDigraphComponent Digraph;
 		      /// \name Base Iteration
 		      ///
 		      /// This interface provides functions for iteration on digraph items.
 		      ///
 		      /// @{
 		      /// \brief Return the first node.
 		      ///
 		      /// This function gives back the first node in the iteration order.
 		      void first(Node&) const {}
 		      /// \brief Return the next node.
 		      ///
 		      /// This function gives back the next node in the iteration order.
 		      void next(Node&) const {}
 		      /// \brief Return the first arc.
 		      ///
 		      /// This function gives back the first arc in the iteration order.
 		      void first(Arc&) const {}
 		      /// \brief Return the next arc.
 		      ///
 		      /// This function gives back the next arc in the iteration order.
 		      void next(Arc&) const {}
 		      /// \brief Return the first arc incomming to the given node.
 		      ///
 		      /// This function gives back the first arc incomming to the
 		      /// given node.
 		      void firstIn(Arc&, const Node&) const {}
 		      /// \brief Return the next arc incomming to the given node.
 		      ///
 		      /// This function gives back the next arc incomming to the
 		      /// given node.
 		      void nextIn(Arc&) const {}
 		      /// \brief Return the first arc outgoing form the given node.
 		      ///
 		      /// This function gives back the first arc outgoing form the
 		      /// given node.
 		      void firstOut(Arc&, const Node&) const {}
 		      /// \brief Return the next arc outgoing form the given node.
 		      ///
 		      /// This function gives back the next arc outgoing form the
 		      /// given node.
 		      void nextOut(Arc&) const {}
 		      /// @}
 		      /// \name Class Based Iteration
 		      ///
 		      /// This interface provides iterator classes for digraph items.
 		      ///
 		      /// @{
 		      /// \brief This iterator goes through each node.
 		      ///
 		      /// This iterator goes through each node.
 		      ///
 		      typedef GraphItemIt<Digraph, Node> NodeIt;
 		      /// \brief This iterator goes through each arc.
 		      ///
 		      /// This iterator goes through each arc.
 		      ///
 		      typedef GraphItemIt<Digraph, Arc> ArcIt;
 		      /// \brief This iterator goes trough the incoming arcs of a node.
 		      ///
 		      /// This iterator goes trough the \e incoming arcs of a certain node
 		      /// of a digraph.
 		      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
 		      /// \brief This iterator goes trough the outgoing arcs of a node.
 		      ///
 		      /// This iterator goes trough the \e outgoing arcs of a certain node
 		      /// of a digraph.
 		      typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// This function gives back the base node of the iterator.
 		      /// It is always the target node of the pointed arc.
 		      Node baseNode(const InArcIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// This function gives back the running node of the iterator.
 		      /// It is always the source node of the pointed arc.
 		      Node runningNode(const InArcIt&) const { return INVALID; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// This function gives back the base node of the iterator.
 		      /// It is always the source node of the pointed arc.
 		      Node baseNode(const OutArcIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// This function gives back the running node of the iterator.
 		      /// It is always the target node of the pointed arc.
 		      Node runningNode(const OutArcIt&) const { return INVALID; }
 		      /// @}
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
+		          {
 		            typename _Digraph::Node node(INVALID);
 		            typename _Digraph::Arc arc(INVALID);
+		            {
 		              digraph.first(node);
 		              digraph.next(node);
+		            }
+		            {
 		              digraph.first(arc);
 		              digraph.next(arc);
+		            }
+		            {
 		              digraph.firstIn(arc, node);
 		              digraph.nextIn(arc);
+		            }
+		            {
 		              digraph.firstOut(arc, node);
 		              digraph.nextOut(arc);
+		            }
+		          }
+		          {
 		            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
 		              typename _Digraph::ArcIt >();
 		            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
 		              typename _Digraph::NodeIt >();
 		            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
 		              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
 		            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
 		              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
 		            typename _Digraph::Node n;
 		            const typename _Digraph::InArcIt iait(INVALID);
 		            const typename _Digraph::OutArcIt oait(INVALID);
 		            n = digraph.baseNode(iait);
 		            n = digraph.runningNode(iait);
 		            n = digraph.baseNode(oait);
 		            n = digraph.runningNode(oait);
 		            ignore_unused_variable_warning(n);
+		          }
+		        }
 		        const _Digraph& digraph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for iterable undirected graphs.
 		    ///
 		    /// This class describes the interface of iterable undirected
 		    /// graphs. It extends \ref IterableDigraphComponent with the core
 		    /// iterable interface of undirected graphs.
 		    /// This concept is part of the Graph concept.
 		    template <typename BAS = BaseGraphComponent>
 		    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      typedef typename Base::Edge Edge;
 		      typedef IterableGraphComponent Graph;
 		      /// \name Base Iteration
 		      ///
 		      /// This interface provides functions for iteration on edges.
 		      ///
 		      /// @{
 		      using IterableDigraphComponent<Base>::first;
 		      using IterableDigraphComponent<Base>::next;
 		      /// \brief Return the first edge.
 		      ///
 		      /// This function gives back the first edge in the iteration order.
 		      void first(Edge&) const {}
 		      /// \brief Return the next edge.
 		      ///
 		      /// This function gives back the next edge in the iteration order.
 		      void next(Edge&) const {}
 		      /// \brief Return the first edge incident to the given node.
 		      ///
 		      /// This function gives back the first edge incident to the given
 		      /// node. The bool parameter gives back the direction for which the
 		      /// source node of the directed arc representing the edge is the
 		      /// given node.
 		      void firstInc(Edge&, bool&, const Node&) const {}
 		      /// \brief Gives back the next of the edges from the
 		      /// given node.
 		      ///
 		      /// This function gives back the next edge incident to the given
 		      /// node. The bool parameter should be used as \c firstInc() use it.
 		      void nextInc(Edge&, bool&) const {}
 		      using IterableDigraphComponent<Base>::baseNode;
 		      using IterableDigraphComponent<Base>::runningNode;
 		      /// @}
 		      /// \name Class Based Iteration
 		      ///
 		      /// This interface provides iterator classes for edges.
 		      ///
 		      /// @{
 		      /// \brief This iterator goes through each edge.
 		      ///
 		      /// This iterator goes through each edge.
 		      typedef GraphItemIt<Graph, Edge> EdgeIt;
 		      /// \brief This iterator goes trough the incident edges of a
 		      /// node.
 		      ///
 		      /// This iterator goes trough the incident edges of a certain
 		      /// node of a graph.
 		      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// This function gives back the base node of the iterator.
 		      Node baseNode(const IncEdgeIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// This function gives back the running node of the iterator.
 		      Node runningNode(const IncEdgeIt&) const { return INVALID; }
 		      /// @}
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<IterableDigraphComponent<Base>, _Graph>();
+		          {
 		            typename _Graph::Node node(INVALID);
 		            typename _Graph::Edge edge(INVALID);
 		            bool dir;
+		            {
 		              graph.first(edge);
 		              graph.next(edge);
+		            }
+		            {
 		              graph.firstInc(edge, dir, node);
 		              graph.nextInc(edge, dir);
+		            }
+		          }
+		          {
 		            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
 		              typename _Graph::EdgeIt >();
 		            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
 		              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
 		            typename _Graph::Node n;
 		            const typename _Graph::IncEdgeIt ieit(INVALID);
 		            n = graph.baseNode(ieit);
 		            n = graph.runningNode(ieit);
+		          }
+		        }
 		        const _Graph& graph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for alterable directed graphs.
 		    ///
 		    /// This class describes the interface of alterable directed
 		    /// graphs. It extends \ref BaseDigraphComponent with the alteration
 		    /// notifier interface. It implements
 		    /// an observer-notifier pattern for each digraph item. More
 		    /// obsevers can be registered into the notifier and whenever an
 		    /// alteration occured in the digraph all the observers will be
 		    /// notified about it.
 		    template <typename BAS = BaseDigraphComponent>
 		    class AlterableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// Node alteration notifier class.
 		      typedef AlterationNotifier<AlterableDigraphComponent, Node>
 		      NodeNotifier;
 		      /// Arc alteration notifier class.
 		      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
 		      ArcNotifier;
 		      /// \brief Return the node alteration notifier.
 		      ///
 		      /// This function gives back the node alteration notifier.
 		      NodeNotifier& notifier(Node) const {
 		         return NodeNotifier();
+		      }
 		      /// \brief Return the arc alteration notifier.
 		      ///
 		      /// This function gives back the arc alteration notifier.
 		      ArcNotifier& notifier(Arc) const {
 		        return ArcNotifier();
+		      }
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          typename _Digraph::NodeNotifier& nn
 		            = digraph.notifier(typename _Digraph::Node());
 		          typename _Digraph::ArcNotifier& en
 		            = digraph.notifier(typename _Digraph::Arc());
 		          ignore_unused_variable_warning(nn);
 		          ignore_unused_variable_warning(en);
+		        }
 		        const _Digraph& digraph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for alterable undirected graphs.
 		    ///
 		    /// This class describes the interface of alterable undirected
 		    /// graphs. It extends \ref AlterableDigraphComponent with the alteration
 		    /// notifier interface of undirected graphs. It implements
 		    /// an observer-notifier pattern for the edges. More
 		    /// obsevers can be registered into the notifier and whenever an
 		    /// alteration occured in the graph all the observers will be
 		    /// notified about it.
 		    template <typename BAS = BaseGraphComponent>
 		    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Edge Edge;
 		      /// Edge alteration notifier class.
 		      typedef AlterationNotifier<AlterableGraphComponent, Edge>
 		      EdgeNotifier;
 		      /// \brief Return the edge alteration notifier.
 		      ///
 		      /// This function gives back the edge alteration notifier.
 		      EdgeNotifier& notifier(Edge) const {
 		        return EdgeNotifier();
+		      }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<AlterableDigraphComponent<Base>, _Graph>();
 		          typename _Graph::EdgeNotifier& uen
 		            = graph.notifier(typename _Graph::Edge());
 		          ignore_unused_variable_warning(uen);
+		        }
 		        const _Graph& graph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Concept class for standard graph maps.
 		    ///
 		    /// This class describes the concept of standard graph maps, i.e.
 		    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
 		    /// graph types, which can be used for associating data to graph items.
 		    /// The standard graph maps must conform to the ReferenceMap concept.
 		    template <typename GR, typename K, typename V>
 		    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
 		      typedef ReferenceMap<K, V, V&, const V&> Parent;
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// The value type of the map.
 		      typedef V Value;
 		      /// The reference type of the map.
 		      typedef Value& Reference;
 		      /// The const reference type of the map.
 		      typedef const Value& ConstReference;
 		      // The reference map tag.
 		      typedef True ReferenceMapTag;
 		      /// \brief Construct a new map.
 		      ///
 		      /// Construct a new map for the graph.
 		      explicit GraphMap(const GR&) {}
 		      /// \brief Construct a new map with default value.
 		      ///
 		      /// Construct a new map for the graph and initalize the values.
 		      GraphMap(const GR&, const Value&) {}
 		    private:
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy Constructor.
 		      GraphMap(const GraphMap&) : Parent() {}
 		      /// \brief Assignment operator.
 		      ///
 		      /// Assignment operator. It does not mofify the underlying graph,
 		      /// it just iterates on the current item set and set the  map
 		      /// with the value returned by the assigned map.
 		      template <typename CMap>
 		      GraphMap& operator=(const CMap&) {
 		        checkConcept<ReadMap<Key, Value>, CMap>();
 		        return *this;
+		      }
 		    public:
 		      template<typename _Map>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept
 		            <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
 		          _Map m1(g);
 		          _Map m2(g,t);
 		          // Copy constructor
 		          // _Map m3(m);
 		          // Assignment operator
 		          // ReadMap<Key, Value> cmap;
 		          // m3 = cmap;
 		          ignore_unused_variable_warning(m1);
 		          ignore_unused_variable_warning(m2);
 		          // ignore_unused_variable_warning(m3);
+		        }
 		        const _Map &m;
 		        const GR &g;
 		        const typename GraphMap::Value &t;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for mappable directed graphs.
 		    ///
 		    /// This class describes the interface of mappable directed graphs.
 		    /// It extends \ref BaseDigraphComponent with the standard digraph
 		    /// map classes, namely \c NodeMap and \c ArcMap.
 		    /// This concept is part of the Digraph concept.
 		    template <typename BAS = BaseDigraphComponent>
 		    class MappableDigraphComponent : public BAS  {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      typedef MappableDigraphComponent Digraph;
 		      /// \brief Standard graph map for the nodes.
 		      ///
 		      /// Standard graph map for the nodes.
 		      /// It conforms to the ReferenceMap concept.
 		      template <typename V>
 		      class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
 		        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
 		      public:
 		        /// \brief Construct a new map.
 		        ///
 		        /// Construct a new map for the digraph.
 		        explicit NodeMap(const MappableDigraphComponent& digraph)
 		          : Parent(digraph) {}
 		        /// \brief Construct a new map with default value.
 		        ///
 		        /// Construct a new map for the digraph and initalize the values.
 		        NodeMap(const MappableDigraphComponent& digraph, const V& value)
 		          : Parent(digraph, value) {}
 		      private:
 		        /// \brief Copy constructor.
 		        ///
 		        /// Copy Constructor.
 		        NodeMap(const NodeMap& nm) : Parent(nm) {}
 		        /// \brief Assignment operator.
 		        ///
 		        /// Assignment operator.
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, V>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \brief Standard graph map for the arcs.
 		      ///
 		      /// Standard graph map for the arcs.
 		      /// It conforms to the ReferenceMap concept.
 		      template <typename V>
 		      class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
 		        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
 		      public:
 		        /// \brief Construct a new map.
 		        ///
 		        /// Construct a new map for the digraph.
 		        explicit ArcMap(const MappableDigraphComponent& digraph)
 		          : Parent(digraph) {}
 		        /// \brief Construct a new map with default value.
 		        ///
 		        /// Construct a new map for the digraph and initalize the values.
 		        ArcMap(const MappableDigraphComponent& digraph, const V& value)
 		          : Parent(digraph, value) {}
 		      private:
 		        /// \brief Copy constructor.
 		        ///
 		        /// Copy Constructor.
 		        ArcMap(const ArcMap& nm) : Parent(nm) {}
 		        /// \brief Assignment operator.
 		        ///
 		        /// Assignment operator.
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, V>, CMap>();
 		          return *this;
+		        }
 		      };
 		      template <typename _Digraph>
 		      struct Constraints {
 		        struct Dummy {
 		          int value;
 		          Dummy() : value(0) {}
 		          Dummy(int _v) : value(_v) {}
 		        };
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          { // int map test
 		            typedef typename _Digraph::template NodeMap<int> IntNodeMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
 		              IntNodeMap >();
 		          } { // bool map test
 		            typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
 		              BoolNodeMap >();
 		          } { // Dummy map test
 		            typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
 		              DummyNodeMap >();
+		          }
 		          { // int map test
 		            typedef typename _Digraph::template ArcMap<int> IntArcMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
 		              IntArcMap >();
 		          } { // bool map test
 		            typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
 		              BoolArcMap >();
 		          } { // Dummy map test
 		            typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
 		              DummyArcMap >();
+		          }
+		        }
 		        const _Digraph& digraph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for mappable undirected graphs.
 		    ///
 		    /// This class describes the interface of mappable undirected graphs.
 		    /// It extends \ref MappableDigraphComponent with the standard graph
 		    /// map class for edges (\c EdgeMap).
 		    /// This concept is part of the Graph concept.
 		    template <typename BAS = BaseGraphComponent>
 		    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Edge Edge;
 		      typedef MappableGraphComponent Graph;
 		      /// \brief Standard graph map for the edges.
 		      ///
 		      /// Standard graph map for the edges.
 		      /// It conforms to the ReferenceMap concept.
 		      template <typename V>
 		      class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
 		        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
 		      public:
 		        /// \brief Construct a new map.
 		        ///
 		        /// Construct a new map for the graph.
 		        explicit EdgeMap(const MappableGraphComponent& graph)
 		          : Parent(graph) {}
 		        /// \brief Construct a new map with default value.
 		        ///
 		        /// Construct a new map for the graph and initalize the values.
 		        EdgeMap(const MappableGraphComponent& graph, const V& value)
 		          : Parent(graph, value) {}
 		      private:
 		        /// \brief Copy constructor.
 		        ///
 		        /// Copy Constructor.
 		        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
 		        /// \brief Assignment operator.
 		        ///
 		        /// Assignment operator.
 		        template <typename CMap>
 		        EdgeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Edge, V>, CMap>();
 		          return *this;
+		        }
 		      };
 		      template <typename _Graph>
 		      struct Constraints {
 		        struct Dummy {
 		          int value;
 		          Dummy() : value(0) {}
 		          Dummy(int _v) : value(_v) {}
 		        };
 		        void constraints() {
 		          checkConcept<MappableDigraphComponent<Base>, _Graph>();
 		          { // int map test
 		            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
 		            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
 		              IntEdgeMap >();
 		          } { // bool map test
 		            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
 		            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
 		              BoolEdgeMap >();
 		          } { // Dummy map test
 		            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
 		            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
 		              DummyEdgeMap >();
+		          }
+		        }
 		        const _Graph& graph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for extendable directed graphs.
 		    ///
 		    /// This class describes the interface of extendable directed graphs.
 		    /// It extends \ref BaseDigraphComponent with functions for adding
 		    /// nodes and arcs to the digraph.
 		    /// This concept requires \ref AlterableDigraphComponent.
 		    template <typename BAS = BaseDigraphComponent>
 		    class ExtendableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// \brief Add a new node to the digraph.
 		      ///
 		      /// This function adds a new node to the digraph.
 		      Node addNode() {
 		        return INVALID;
+		      }
 		      /// \brief Add a new arc connecting the given two nodes.
 		      ///
 		      /// This function adds a new arc connecting the given two nodes
 		      /// of the digraph.
 		      Arc addArc(const Node&, const Node&) {
 		        return INVALID;
+		      }
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          typename _Digraph::Node node_a, node_b;
 		          node_a = digraph.addNode();
 		          node_b = digraph.addNode();
 		          typename _Digraph::Arc arc;
 		          arc = digraph.addArc(node_a, node_b);
+		        }
 		        _Digraph& digraph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for extendable undirected graphs.
 		    ///
 		    /// This class describes the interface of extendable undirected graphs.
 		    /// It extends \ref BaseGraphComponent with functions for adding
 		    /// nodes and edges to the graph.
 		    /// This concept requires \ref AlterableGraphComponent.
 		    template <typename BAS = BaseGraphComponent>
 		    class ExtendableGraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Edge Edge;
 		      /// \brief Add a new node to the digraph.
 		      ///
 		      /// This function adds a new node to the digraph.
 		      Node addNode() {
 		        return INVALID;
+		      }
 		      /// \brief Add a new edge connecting the given two nodes.
 		      ///
 		      /// This function adds a new edge connecting the given two nodes
 		      /// of the graph.
 		      Edge addEdge(const Node&, const Node&) {
 		        return INVALID;
+		      }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Graph>();
 		          typename _Graph::Node node_a, node_b;
 		          node_a = graph.addNode();
 		          node_b = graph.addNode();
 		          typename _Graph::Edge edge;
 		          edge = graph.addEdge(node_a, node_b);
+		        }
 		        _Graph& graph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for erasable directed graphs.
 		    ///
 		    /// This class describes the interface of erasable directed graphs.
 		    /// It extends \ref BaseDigraphComponent with functions for removing
 		    /// nodes and arcs from the digraph.
 		    /// This concept requires \ref AlterableDigraphComponent.
 		    template <typename BAS = BaseDigraphComponent>
 		    class ErasableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// \brief Erase a node from the digraph.
 		      ///
 		      /// This function erases the given node from the digraph and all arcs
 		      /// connected to the node.
 		      void erase(const Node&) {}
 		      /// \brief Erase an arc from the digraph.
 		      ///
 		      /// This function erases the given arc from the digraph.
 		      void erase(const Arc&) {}
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          const typename _Digraph::Node node(INVALID);
 		          digraph.erase(node);
 		          const typename _Digraph::Arc arc(INVALID);
 		          digraph.erase(arc);
+		        }
 		        _Digraph& digraph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for erasable undirected graphs.
 		    ///
 		    /// This class describes the interface of erasable undirected graphs.
 		    /// It extends \ref BaseGraphComponent with functions for removing
 		    /// nodes and edges from the graph.
 		    /// This concept requires \ref AlterableGraphComponent.
 		    template <typename BAS = BaseGraphComponent>
 		    class ErasableGraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Edge Edge;
 		      /// \brief Erase a node from the graph.
 		      ///
 		      /// This function erases the given node from the graph and all edges
 		      /// connected to the node.
 		      void erase(const Node&) {}
 		      /// \brief Erase an edge from the digraph.
 		      ///
 		      /// This function erases the given edge from the digraph.
 		      void erase(const Edge&) {}
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Graph>();
 		          const typename _Graph::Node node(INVALID);
 		          graph.erase(node);
 		          const typename _Graph::Edge edge(INVALID);
 		          graph.erase(edge);
+		        }
 		        _Graph& graph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for clearable directed graphs.
 		    ///
 		    /// This class describes the interface of clearable directed graphs.
 		    /// It extends \ref BaseDigraphComponent with a function for clearing
 		    /// the digraph.
 		    /// This concept requires \ref AlterableDigraphComponent.
 		    template <typename BAS = BaseDigraphComponent>
 		    class ClearableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      /// \brief Erase all nodes and arcs from the digraph.
 		      ///
 		      /// This function erases all nodes and arcs from the digraph.
 		      void clear() {}
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          digraph.clear();
+		        }
 		        _Digraph& digraph;
 		        Constraints() {}
 		      };
 		    };
 		    /// \brief Skeleton class for clearable undirected graphs.
 		    ///
 		    /// This class describes the interface of clearable undirected graphs.
 		    /// It extends \ref BaseGraphComponent with a function for clearing
 		    /// the graph.
 		    /// This concept requires \ref AlterableGraphComponent.
 		    template <typename BAS = BaseGraphComponent>
 		    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
 		    public:
 		      typedef BAS Base;
 		      /// \brief Erase all nodes and edges from the graph.
 		      ///
 		      /// This function erases all nodes and edges from the graph.
 		      void clear() {}
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Graph>();
 		          graph.clear();
+		        }
 		        _Graph& graph;
 		        Constraints() {}
 		      };
 		    };
+		  }
+		}
 		#endif

lemon/concepts/heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * 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_CONCEPTS_HEAP_H
 		#define LEMON_CONCEPTS_HEAP_H
 		///\ingroup concept
 		///\file
 		///\brief The concept of heaps.
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief The heap concept.
 		    ///
 		    /// This concept class describes the main interface of heaps.
 		    /// The various \ref heaps "heap structures" are efficient
 		    /// implementations of the abstract data type \e priority \e queue.
 		    /// They store items with specified values called \e priorities
 		    /// in such a way that finding and removing the item with minimum
 		    /// priority are efficient. The basic operations are adding and
 		    /// erasing items, changing the priority of an item, etc.
 		    ///
 		    /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
 		    /// Any class that conforms to this concept can be used easily in such
 		    /// algorithms.
 		    ///
 		    /// \tparam PR Type of the priorities of the items.
 		    /// \tparam IM A read-writable item map with \c int values, used
 		    /// internally to handle the cross references.
 		    /// \tparam CMP A functor class for comparing the priorities.
 		    /// The default is \c std::less<PR>.
 		#ifdef DOXYGEN
 		    template <typename PR, typename IM, typename CMP>
 		#else
 		    template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
 		    class Heap {
 		    public:
 		      /// Type of the item-int map.
 		      typedef IM ItemIntMap;
 		      /// Type of the priorities.
 		      typedef PR Prio;
 		      /// Type of the items stored in the heap.
 		      typedef typename ItemIntMap::Key Item;
 		      /// \brief Type to represent the states of the items.
 		      ///
 		      /// Each item has a state associated to it. It can be "in heap",
 		      /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		      /// heap's point of view, but may be useful to the user.
 		      ///
 		      /// The item-int map must be initialized in such way that it assigns
 		      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		      enum State {
 		        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
 		        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
 		        POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
 		      };
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor.
 		      /// \param map A map that assigns \c int values to keys of type
 		      /// \c Item. It is used internally by the heap implementations to
 		      /// handle the cross references. The assigned value must be
 		      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
 		#ifdef DOXYGEN
 		      explicit Heap(ItemIntMap &map) {}
 		#else
 		      explicit Heap(ItemIntMap&) {}
 		#endif
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor.
 		      /// \param map A map that assigns \c int values to keys of type
 		      /// \c Item. It is used internally by the heap implementations to
 		      /// handle the cross references. The assigned value must be
 		      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
 		      /// \param comp The function object used for comparing the priorities.
 		#ifdef DOXYGEN
 		      explicit Heap(ItemIntMap &map, const CMP &comp) {}
 		#else
 		      explicit Heap(ItemIntMap&, const CMP&) {}
 		#endif
 		      /// \brief The number of items stored in the heap.
 		      ///
 		      /// This function returns the number of items stored in the heap.
 		      int size() const { return 0; }
 		      /// \brief Check if the heap is empty.
 		      ///
 		      /// This function returns \c true if the heap is empty.
 		      bool empty() const { return false; }
 		      /// \brief Make the heap empty.
 		      ///
 		      /// This functon makes the heap empty.
 		      /// It does not change the cross reference map. If you want to reuse
 		      /// a heap that is not surely empty, you should first clear it and
 		      /// then you should set the cross reference map to \c PRE_HEAP
 		      /// for each item.
 		      void clear() {}
 		      /// \brief Insert an item into the heap with the given priority.
 		      ///
 		      /// This function inserts the given item into the heap with the
 		      /// given priority.
 		      /// \param i The item to insert.
 		      /// \param p The priority of the item.
 		      /// \pre \e i must not be stored in the heap.
 		#ifdef DOXYGEN
 		      void push(const Item &i, const Prio &p) {}
 		#else
 		      void push(const Item&, const Prio&) {}
 		#endif
 		      /// \brief Return the item having minimum priority.
 		      ///
 		      /// This function returns the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Item top() const { return Item(); }
 		      /// \brief The minimum priority.
 		      ///
 		      /// This function returns the minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Prio prio() const { return Prio(); }
 		      /// \brief Remove the item having minimum priority.
 		      ///
 		      /// This function removes the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      void pop() {}
 		      /// \brief Remove the given item from the heap.
 		      ///
 		      /// This function removes the given item from the heap if it is
 		      /// already stored.
 		      /// \param i The item to delete.
 		      /// \pre \e i must be in the heap.
 		#ifdef DOXYGEN
 		      void erase(const Item &i) {}
 		#else
 		      void erase(const Item&) {}
 		#endif
 		      /// \brief The priority of the given item.
 		      ///
 		      /// This function returns the priority of the given item.
 		      /// \param i The item.
 		      /// \pre \e i must be in the heap.
 		#ifdef DOXYGEN
 		      Prio operator[](const Item &i) const {}
 		#else
 		      Prio operator[](const Item&) const { return Prio(); }
 		#endif
 		      /// \brief Set the priority of an item or insert it, if it is
 		      /// not stored in the heap.
 		      ///
 		      /// This method sets the priority of the given item if it is
 		      /// already stored in the heap. Otherwise it inserts the given
 		      /// item into the heap with the given priority.
 		      ///
 		      /// \param i The item.
 		      /// \param p The priority.
 		#ifdef DOXYGEN
 		      void set(const Item &i, const Prio &p) {}
 		#else
 		      void set(const Item&, const Prio&) {}
 		#endif
 		      /// \brief Decrease the priority of an item to the given value.
 		      ///
 		      /// This function decreases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      /// \pre \e i must be stored in the heap with priority at least \e p.
 		#ifdef DOXYGEN
 		      void decrease(const Item &i, const Prio &p) {}
 		#else
 		      void decrease(const Item&, const Prio&) {}
 		#endif
 		      /// \brief Increase the priority of an item to the given value.
 		      ///
 		      /// This function increases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      /// \pre \e i must be stored in the heap with priority at most \e p.
 		#ifdef DOXYGEN
 		      void increase(const Item &i, const Prio &p) {}
 		#else
 		      void increase(const Item&, const Prio&) {}
 		#endif
 		      /// \brief Return the state of an item.
 		      ///
 		      /// This method returns \c PRE_HEAP if the given item has never
 		      /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		      /// and \c POST_HEAP otherwise.
 		      /// In the latter case it is possible that the item will get back
 		      /// to the heap again.
 		      /// \param i The item.
 		#ifdef DOXYGEN
 		      State state(const Item &i) const {}
 		#else
 		      State state(const Item&) const { return PRE_HEAP; }
 		#endif
 		      /// \brief Set the state of an item in the heap.
 		      ///
 		      /// This function sets the state of the given item in the heap.
 		      /// It can be used to manually clear the heap when it is important
 		      /// to achive better time complexity.
 		      /// \param i The item.
 		      /// \param st The state. It should not be \c IN_HEAP.
 		#ifdef DOXYGEN
 		      void state(const Item& i, State st) {}
 		#else
 		      void state(const Item&, State) {}
 		#endif
 		      template <typename _Heap>
 		      struct Constraints {
 		      public:
 		        void constraints() {
 		          typedef typename _Heap::Item OwnItem;
 		          typedef typename _Heap::Prio OwnPrio;
 		          typedef typename _Heap::State OwnState;
 		          Item item;
 		          Prio prio;
 		          item=Item();
 		          prio=Prio();
 		          ignore_unused_variable_warning(item);
 		          ignore_unused_variable_warning(prio);
 		          OwnItem own_item;
 		          OwnPrio own_prio;
 		          OwnState own_state;
 		          own_item=Item();
 		          own_prio=Prio();
 		          ignore_unused_variable_warning(own_item);
 		          ignore_unused_variable_warning(own_prio);
 		          ignore_unused_variable_warning(own_state);
 		          _Heap heap1(map);
 		          _Heap heap2 = heap1;
 		          ignore_unused_variable_warning(heap1);
 		          ignore_unused_variable_warning(heap2);
 		          int s = heap.size();
 		          ignore_unused_variable_warning(s);
 		          bool e = heap.empty();
 		          ignore_unused_variable_warning(e);
 		          prio = heap.prio();
 		          item = heap.top();
 		          prio = heap[item];
 		          own_prio = heap.prio();
 		          own_item = heap.top();
 		          own_prio = heap[own_item];
 		          heap.push(item, prio);
 		          heap.push(own_item, own_prio);
 		          heap.pop();
 		          heap.set(item, prio);
 		          heap.decrease(item, prio);
 		          heap.increase(item, prio);
 		          heap.set(own_item, own_prio);
 		          heap.decrease(own_item, own_prio);
 		          heap.increase(own_item, own_prio);
 		          heap.erase(item);
 		          heap.erase(own_item);
 		          heap.clear();
 		          own_state = heap.state(own_item);
 		          heap.state(own_item, own_state);
 		          own_state = _Heap::PRE_HEAP;
 		          own_state = _Heap::IN_HEAP;
 		          own_state = _Heap::POST_HEAP;
+		        }
 		        _Heap& heap;
 		        ItemIntMap& map;
 		        Constraints() {}
 		      };
 		    };
 		    /// @}
 		  } // namespace lemon
+		}
 		#endif

lemon/concepts/maps.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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_CONCEPTS_MAPS_H
 		#define LEMON_CONCEPTS_MAPS_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		///\ingroup map_concepts
 		///\file
 		///\brief The concept of maps.
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup map_concepts
 		    /// @{
 		    /// Readable map concept
 		    /// Readable map concept.
 		    ///
 		    template<typename K, typename T>
 		    class ReadMap
+		    {
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// \brief The value type of the map.
 		      /// (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// Returns the value associated with the given key.
 		      Value operator[](const Key &) const {
 		        return *static_cast<Value *>(0);
+		      }
 		      template<typename _ReadMap>
 		      struct Constraints {
 		        void constraints() {
 		          Value val = m[key];
 		          val = m[key];
 		          typename _ReadMap::Value own_val = m[own_key];
 		          own_val = m[own_key];
 		          ignore_unused_variable_warning(key);
 		          ignore_unused_variable_warning(val);
 		          ignore_unused_variable_warning(own_key);
 		          ignore_unused_variable_warning(own_val);
+		        }
 		        const Key& key;
 		        const typename _ReadMap::Key& own_key;
 		        const _ReadMap& m;
 		        Constraints() {}
 		      };
 		    };
 		    /// Writable map concept
 		    /// Writable map concept.
 		    ///
 		    template<typename K, typename T>
 		    class WriteMap
+		    {
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// \brief The value type of the map.
 		      /// (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// Sets the value associated with the given key.
 		      void set(const Key &, const Value &) {}
 		      /// Default constructor.
 		      WriteMap() {}
 		      template <typename _WriteMap>
 		      struct Constraints {
 		        void constraints() {
 		          m.set(key, val);
 		          m.set(own_key, own_val);
 		          ignore_unused_variable_warning(key);
 		          ignore_unused_variable_warning(val);
 		          ignore_unused_variable_warning(own_key);
 		          ignore_unused_variable_warning(own_val);
+		        }
 		        const Key& key;
 		        const Value& val;
 		        const typename _WriteMap::Key& own_key;
 		        const typename _WriteMap::Value& own_val;
 		        _WriteMap& m;
 		        Constraints() {}
 		      };
 		    };
 		    /// Read/writable map concept
 		    /// Read/writable map concept.
 		    ///
 		    template<typename K, typename T>
 		    class ReadWriteMap : public ReadMap<K,T>,
 		                         public WriteMap<K,T>
+		    {
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// \brief The value type of the map.
 		      /// (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// Returns the value associated with the given key.
 		      Value operator[](const Key &) const {
-		        return *static_cast<Value *>(0);
+		        Value *r = 0;
 		        return *r;
+		      }
 		      /// Sets the value associated with the given key.
 		      void set(const Key &, const Value &) {}
 		      template<typename _ReadWriteMap>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<ReadMap<K, T>, _ReadWriteMap >();
 		          checkConcept<WriteMap<K, T>, _ReadWriteMap >();
+		        }
 		      };
 		    };
 		    /// Dereferable map concept
 		    /// Dereferable map concept.
 		    ///
 		    template<typename K, typename T, typename R, typename CR>
 		    class ReferenceMap : public ReadWriteMap<K,T>
+		    {
 		    public:
 		      /// Tag for reference maps.
 		      typedef True ReferenceMapTag;
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// \brief The value type of the map.
 		      /// (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// The reference type of the map.
 		      typedef R Reference;
 		      /// The const reference type of the map.
 		      typedef CR ConstReference;
 		    public:
 		      /// Returns a reference to the value associated with the given key.
 		      Reference operator[](const Key &) {
-		        return *static_cast<Value *>(0);
+		        Value *r = 0;
 		        return *r;
+		      }
 		      /// Returns a const reference to the value associated with the given key.
 		      ConstReference operator[](const Key &) const {
-		        return *static_cast<Value *>(0);
+		        Value *r = 0;
 		        return *r;
+		      }
 		      /// Sets the value associated with the given key.
 		      void set(const Key &k,const Value &t) { operator[](k)=t; }
 		      template<typename _ReferenceMap>
 		      struct Constraints {
 		        typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
 		        constraints() {
 		          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
 		          ref = m[key];
 		          m[key] = val;
 		          m[key] = ref;
 		          m[key] = cref;
 		          own_ref = m[own_key];
 		          m[own_key] = own_val;
 		          m[own_key] = own_ref;
 		          m[own_key] = own_cref;
 		          m[key] = m[own_key];
 		          m[own_key] = m[key];
+		        }
 		        const Key& key;
 		        Value& val;
 		        Reference ref;
 		        ConstReference cref;
 		        const typename _ReferenceMap::Key& own_key;
 		        typename _ReferenceMap::Value& own_val;
 		        typename _ReferenceMap::Reference own_ref;
 		        typename _ReferenceMap::ConstReference own_cref;
 		        _ReferenceMap& m;
 		        Constraints() {}
 		      };
 		    };
 		    // @}
 		  } //namespace concepts
 		} //namespace lemon
 		#endif

lemon/concepts/path.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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 concept
 		///\file
 		///\brief The concept of paths
 		///
 		#ifndef LEMON_CONCEPTS_PATH_H
 		#define LEMON_CONCEPTS_PATH_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief A skeleton structure for representing directed paths in
 		    /// a digraph.
 		    ///
 		    /// A skeleton structure for representing directed paths in a
 		    /// digraph.
 		    /// In a sense, a path can be treated as a list of arcs.
 		    /// LEMON path types just store this list. As a consequence, they cannot
 		    /// enumerate the nodes on the path directly and a zero length path
 		    /// cannot store its source node.
 		    ///
 		    /// The arcs of a path should be stored in the order of their directions,
 		    /// i.e. the target node of each arc should be the same as the source
 		    /// node of the next arc. This consistency could be checked using
 		    /// \ref checkPath().
 		    /// The source and target nodes of a (consistent) path can be obtained
 		    /// using \ref pathSource() and \ref pathTarget().
 		    ///
 		    /// A path can be constructed from another path of any type using the
 		    /// copy constructor or the assignment operator.
 		    ///
 		    /// \tparam GR The digraph type in which the path is.
 		    template <typename GR>
 		    class Path {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef GR Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
 		      class ArcIt;
 		      /// \brief Default constructor
 		      Path() {}
 		      /// \brief Template copy constructor
 		      template <typename CPath>
 		      Path(const CPath& cpath) {}
 		      /// \brief Template assigment operator
 		      template <typename CPath>
 		      Path& operator=(const CPath& cpath) {
 		        ignore_unused_variable_warning(cpath);
 		        return *this;
+		      }
 		      /// Length of the path, i.e. the number of arcs on the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// Resets the path to an empty path.
 		      void clear() {}
 		      /// \brief LEMON style iterator for enumerating the arcs of a path.
 		      ///
 		      /// LEMON style iterator class for enumerating the arcs of a path.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
 		        /// Sets the iterator to the first arc of the given path
 		        ArcIt(const Path &) {}
 		        /// Conversion to \c Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          Path<Digraph> pc;
 		          _Path p, pp(pc);
 		          int l = p.length();
 		          int e = p.empty();
 		          p.clear();
 		          p = pc;
 		          typename _Path::ArcIt id, ii(INVALID), i(p);
 		          ++i;
 		          typename Digraph::Arc ed = i;
 		          e = (i == ii);
 		          e = (i != ii);
 		          e = (i < ii);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(pp);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ii);
 		          ignore_unused_variable_warning(ed);
+		        }
 		      };
 		    };
 		    namespace _path_bits {
 		      template <typename _Digraph, typename _Path, typename RevPathTag = void>
 		      struct PathDumperConstraints {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::ArcIt id, i(p);
 		          ++i;
 		          typename _Digraph::Arc ed = i;
 		          e = (i == INVALID);
 		          e = (i != INVALID);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ed);
+		        }
 		        _Path& p;
 		        PathDumperConstraints() {}
 		      };
 		      template <typename _Digraph, typename _Path>
 		      struct PathDumperConstraints<
 		        _Digraph, _Path,
 		        typename enable_if<typename _Path::RevPathTag, void>::type
 		      > {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::RevArcIt id, i(p);
 		          ++i;
 		          typename _Digraph::Arc ed = i;
 		          e = (i == INVALID);
 		          e = (i != INVALID);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ed);
+		        }
 		        _Path& p;
 		        PathDumperConstraints() {}
 		      };
+		    }
 		    /// \brief A skeleton structure for path dumpers.
 		    ///
 		    /// A skeleton structure for path dumpers. The path dumpers are
 		    /// the generalization of the paths, they can enumerate the arcs
 		    /// of the path either in forward or in backward order.
 		    /// These classes are typically not used directly, they are rather
 		    /// used to be assigned to a real path type.
 		    ///
 		    /// The main purpose of this concept is that the shortest path
 		    /// algorithms can enumerate the arcs easily in reverse order.
 		    /// In LEMON, such algorithms give back a (reverse) path dumper that
 		    /// can be assigned to a real path. The dumpers can be implemented as
 		    /// an adaptor class to the predecessor map.
 		    ///
 		    /// \tparam GR The digraph type in which the path is.
 		    template <typename GR>
 		    class PathDumper {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef GR Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
 		      /// Length of the path, i.e. the number of arcs on the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// \brief Forward or reverse dumping
 		      ///
 		      /// If this tag is defined to be \c True, then reverse dumping
 		      /// is provided in the path dumper. In this case, \c RevArcIt
 		      /// iterator should be implemented instead of \c ArcIt iterator.
 		      typedef False RevPathTag;
 		      /// \brief LEMON style iterator for enumerating the arcs of a path.
 		      ///
 		      /// LEMON style iterator class for enumerating the arcs of a path.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
 		        /// Sets the iterator to the first arc of the given path
 		        ArcIt(const PathDumper&) {}
 		        /// Conversion to \c Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
 		      /// \brief LEMON style iterator for enumerating the arcs of a path
 		      /// in reverse direction.
 		      ///
 		      /// LEMON style iterator class for enumerating the arcs of a path
 		      /// in reverse direction.
 		      class RevArcIt {
 		      public:
 		        /// Default constructor
 		        RevArcIt() {}
 		        /// Invalid constructor
 		        RevArcIt(Invalid) {}
 		        /// Sets the iterator to the last arc of the given path
 		        RevArcIt(const PathDumper &) {}
 		        /// Conversion to \c Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        RevArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const RevArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const RevArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const RevArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          function_requires<_path_bits::
 		            PathDumperConstraints<Digraph, _Path> >();
+		        }
 		      };
 		    };
 		    ///@}
+		  }
 		} // namespace lemon
 		#endif

lemon/dfs.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * 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_DFS_H
 		#define LEMON_DFS_H
 		///\ingroup search
 		///\file
 		///\brief DFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///Default traits class of Dfs class.
 		  ///Default traits class of Dfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \c PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \c ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must conform to
 		    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \c ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \c DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref DistMap.
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%DFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %DFS algorithm.
 		  ///
 		  ///There is also a \ref dfs() "function-type interface" for the DFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default type is \ref ListDigraph.
 		  ///\tparam TR The traits class that defines various types used by the
 		  ///algorithm. By default, it is \ref DfsDefaultTraits
 		  ///"DfsDefaultTraits<GR>".
 		  ///In most cases, this parameter should not be set directly,
 		  ///consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=DfsDefaultTraits<GR> >
 		#endif
 		  class Dfs {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::OutArcIt> _stack;
 		    int _stack_head;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Dfs() {}
 		  public:
 		    typedef Dfs Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 		      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "DistMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///It must conform to
 		    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
 		    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ProcessedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap :
 		      public Dfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param g The digraph the algorithm runs on.
 		    Dfs(const Digraph &g) :
 		      G(&g),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _reached(NULL), local_reached(false),
 		      _processed(NULL), local_processed(false)
 		    { }
 		    ///Destructor.
 		    ~Dfs()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_reached) delete _reached;
 		      if(local_processed) delete _processed;
+		    }
 		    ///Sets the map that stores the predecessor arcs.
 		    ///Sets the map that stores the predecessor arcs.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are reached.
 		    ///Sets the map that indicates which nodes are reached.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &reachedMap(ReachedMap &m)
+		    {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are processed.
 		    ///Sets the map that indicates which nodes are processed.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &processedMap(ProcessedMap &m)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
+		      }
 		      _processed = &m;
 		      return *this;
+		    }
 		    ///Sets the map that stores the distances of the nodes.
 		    ///Sets the map that stores the distances of the nodes calculated by
 		    ///the algorithm.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &distMap(DistMap &m)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;
+		    }
 		  public:
 		    ///\name Execution Control
 		    ///The simplest way to execute the DFS algorithm is to use one of the
 		    ///member functions called \ref run(Node) "run()".\n
 		    ///If you need better control on the execution, you have to call
 		    ///\ref init() first, then you can add a source node with \ref addSource()
 		    ///and perform the actual computation with \ref start().
 		    ///This procedure can be repeated if there are nodes that have not
 		    ///been reached.
 		    ///@{
 		    ///\brief Initializes the internal data structures.
 		    ///
 		    ///Initializes the internal data structures.
 		    void init()
+		    {
 		      create_maps();
 		      _stack.resize(countNodes(*G));
 		      _stack_head=-1;
 		      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 		        _pred->set(u,INVALID);
 		        _reached->set(u,false);
 		        _processed->set(u,false);
+		      }
+		    }
 		    ///Adds a new source node.
 		    ///Adds a new source node to the set of nodes to be processed.
 		    ///
 		    ///\pre The stack must be empty. Otherwise the algorithm gives
 		    ///wrong results. (One of the outgoing arcs of all the source nodes
 		    ///except for the last one will not be visited and distances will
 		    ///also be wrong.)
 		    void addSource(Node s)
+		    {
 		      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
 		      if(!(*_reached)[s])
+		        {
 		          _reached->set(s,true);
 		          _pred->set(s,INVALID);
 		          OutArcIt e(*G,s);
 		          if(e!=INVALID) {
 		            _stack[++_stack_head]=e;
 		            _dist->set(s,_stack_head);
+		          }
 		          else {
 		            _processed->set(s,true);
 		            _dist->set(s,0);
+		          }
+		        }
+		    }
 		    ///Processes the next arc.
 		    ///Processes the next arc.
 		    ///
 		    ///\return The processed arc.
 		    ///
 		    ///\pre The stack must not be empty.
 		    Arc processNextArc()
+		    {
 		      Node m;
 		      Arc e=_stack[_stack_head];
 		      if(!(*_reached)[m=G->target(e)]) {
 		        _pred->set(m,e);
 		        _reached->set(m,true);
 		        ++_stack_head;
 		        _stack[_stack_head] = OutArcIt(*G, m);
 		        _dist->set(m,_stack_head);
+		      }
 		      else {
 		        m=G->source(e);
 		        ++_stack[_stack_head];
+		      }
 		      while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
 		        _processed->set(m,true);
 		        --_stack_head;
 		        if(_stack_head>=0) {
 		          m=G->source(_stack[_stack_head]);
 		          ++_stack[_stack_head];
+		        }
+		      }
 		      return e;
+		    }
 		    ///Next arc to be processed.
 		    ///Next arc to be processed.
 		    ///
 		    ///\return The next arc to be processed or \c INVALID if the stack
 		    ///is empty.
 		    OutArcIt nextArc() const
+		    {
 		      return _stack_head>=0?_stack[_stack_head]:INVALID;
+		    }
 		    ///Returns \c false if there are nodes to be processed.
 		    ///Returns \c false if there are nodes to be processed
 		    ///in the queue (stack).
 		    bool emptyQueue() const { return _stack_head<0; }
 		    ///Returns the number of the nodes to be processed.
 		    ///Returns the number of the nodes to be processed
 		    ///in the queue (stack).
 		    int queueSize() const { return _stack_head+1; }
 		    ///Executes the algorithm.
 		    ///Executes the algorithm.
 		    ///
 		    ///This method runs the %DFS algorithm from the root node
 		    ///in order to compute the DFS path to each node.
 		    ///
 		    /// The algorithm computes
 		    ///- the %DFS tree,
 		    ///- the distance of each node from the root in the %DFS tree.
 		    ///
 		    ///\pre init() must be called and a root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  while ( !d.emptyQueue() ) {
 		    ///    d.processNextArc();
 		    ///  }
 		    ///\endcode
 		    void start()
+		    {
 		      while ( !emptyQueue() ) processNextArc();
+		    }
 		    ///Executes the algorithm until the given target node is reached.
 		    ///Executes the algorithm until the given target node is reached.
 		    ///
 		    ///This method runs the %DFS algorithm from the root node
 		    ///in order to compute the DFS path to \c t.
 		    ///
 		    ///The algorithm computes
 		    ///- the %DFS path to \c t,
 		    ///- the distance of \c t from the root in the %DFS tree.
 		    ///
 		    ///\pre init() must be called and a root node should be
 		    ///added with addSource() before using this function.
 		    void start(Node t)
+		    {
 		      while ( !emptyQueue() && !(*_reached)[t] )
 		        processNextArc();
+		    }
 		    ///Executes the algorithm until a condition is met.
 		    ///Executes the algorithm until a condition is met.
 		    ///
 		    ///This method runs the %DFS algorithm from the root node
 		    ///until an arc \c a with <tt>am[a]</tt> true is found.
 		    ///
 		    ///\param am A \c bool (or convertible) arc map. The algorithm
 		    ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
 		    ///
 		    ///\return The reached arc \c a with <tt>am[a]</tt> true or
 		    ///\c INVALID if no such arc was found.
 		    ///
 		    ///\pre init() must be called and a root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
 		    ///not a node map.
 		    template<class ArcBoolMap>
 		    Arc start(const ArcBoolMap &am)
+		    {
 		      while ( !emptyQueue() && !am[_stack[_stack_head]] )
 		        processNextArc();
 		      return emptyQueue() ? INVALID : _stack[_stack_head];
+		    }
 		    ///Runs the algorithm from the given source node.
 		    ///This method runs the %DFS algorithm from node \c s
 		    ///in order to compute the DFS path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the %DFS tree,
 		    ///- the distance of each node from the root in the %DFS tree.
 		    ///
 		    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///Finds the %DFS path between \c s and \c t.
 		    ///This method runs the %DFS algorithm from node \c s
 		    ///in order to compute the DFS path to node \c t
 		    ///(it stops searching when \c t is processed)
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    ///
 		    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
 		    ///just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    ///Runs the algorithm to visit all nodes in the digraph.
 		    ///This method runs the %DFS algorithm in order to visit all nodes
 		    ///in the digraph.
 		    ///
 		    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  for (NodeIt n(digraph); n != INVALID; ++n) {
 		    ///    if (!d.reached(n)) {
 		    ///      d.addSource(n);
 		    ///      d.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt it(*G); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The results of the DFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref run(Node) "run()" or \ref start() should be called
 		    ///before using them.
 		    ///@{
 		    ///The DFS path to the given node.
 		    ///Returns the DFS path to the given node from the root(s).
 		    ///
 		    ///\warning \c t should be reached from the root(s).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///The distance of the given node from the root(s).
 		    ///Returns the distance of the given node from the root(s).
 		    ///
 		    ///\warning If node \c v is not reached from the root(s), then
 		    ///the return value of this function is undefined.
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the %DFS tree for the given node.
 		    ///This function returns the 'previous arc' of the %DFS tree for the
 		    ///node \c v, i.e. it returns the last arc of a %DFS path from a
 		    ///root to \c v. It is \c INVALID if \c v is not reached from the
 		    ///root(s) or if \c v is a root.
 		    ///
 		    ///The %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predNode() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///Returns the 'previous node' of the %DFS tree for the given node.
 		    ///This function returns the 'previous node' of the %DFS
 		    ///tree for the node \c v, i.e. it returns the last but one node
 		    ///of a %DFS path from a root to \c v. It is \c INVALID
 		    ///if \c v is not reached from the root(s) or if \c v is a root.
 		    ///
 		    ///The %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predArc() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->source((*_pred)[v]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the
 		    ///distances of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the DFS tree (forest).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if the given node. node is reached from the root(s).
 		    ///Returns \c true if \c v is reached from the root(s).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of dfs() function.
 		  ///Default traits class of dfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsWizardDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
 		    ///This function instantiates a ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must conform to
 		    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a ReachedMap.
 		    ///This function instantiates a ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a DistMap.
 		    ///This function instantiates a DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the DistMap
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		    ///The type of the DFS paths.
 		    ///The type of the DFS paths.
 		    ///It must conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by DfsWizard
 		  /// Default traits class used by DfsWizard.
 		  /// \tparam GR The type of the digraph.
 		  template<class GR>
 		  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
+		  {
 		    typedef DfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the DFS path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    int *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, it initiates
 		    /// all of the attributes to \c 0.
 		    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires one parameter,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    DfsWizardBase(const GR &g) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of DFS algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
 		  /// It does not have own \ref run(Node) "run()" method, it uses the
 		  /// functions and features of the plain \ref Dfs.
 		  ///
 		  /// This class should only be used through the \ref dfs() function,
 		  /// which makes it easier to use the algorithm.
 		  ///
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm.
 		  template<class TR>
 		  class DfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::ReachedMap ReachedMap;
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    DfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param g The digraph the algorithm runs on.
 		    DfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
 		    DfsWizard(const TR &b) : TR(b) {}
 		    ~DfsWizard() {}
 		    ///Runs DFS algorithm from the given source node.
 		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS path to each node.
 		    void run(Node s)
+		    {
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if (s!=INVALID)
 		        alg.run(s);
 		      else
 		        alg.run();
+		    }
 		    ///Finds the DFS path between \c s and \c t.
 		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)
+		    {
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      alg.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
 		      if (Base::_di)
 		        *Base::_di = alg.dist(t);
 		      return alg.reached(t);
+		      }
 		    ///Runs DFS algorithm to visit all nodes in the digraph.
 		    ///This method runs DFS algorithm in order to visit all nodes
 		    ///in the digraph.
 		    void run()
+		    {
 		      run(INVALID);
+		    }
 		    template<class T>
 		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the predecessor map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the reached map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are reached.
 		    template<class T>
 		    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the distance map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the distances of the nodes calculated
 		    ///by the algorithm.
 		    template<class T>
 		    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetDistMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter" for setting
 		    ///the processed map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are processed.
 		    template<class T>
 		    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetPathBase : public Base {
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the DFS path to the target node.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the DFS path to the target node.
 		    template<class T>
 		    DfsWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetPathBase<T> >(*this);
+		    }
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the distance of the target node.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the distance of the target node.
 		    DfsWizard dist(const int &d)
+		    {
 		      Base::_di=const_cast<int*>(&d);
 		      return *this;
+		    }
 		  };
 		  ///Function-type interface for DFS algorithm.
 		  ///\ingroup search
 		  ///Function-type interface for DFS algorithm.
 		  ///
 		  ///This function also has several \ref named-func-param "named parameters",
 		  ///they are declared as the members of class \ref DfsWizard.
 		  ///The following examples show how to use these parameters.
 		  ///\code
 		  ///  // Compute the DFS tree
 		  ///  dfs(g).predMap(preds).distMap(dists).run(s);
 		  ///
 		  ///  // Compute the DFS path from s to t
 		  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
 		  ///to the end of the parameter list.
 		  ///\sa DfsWizard
 		  ///\sa Dfs
 		  template<class GR>
 		  DfsWizard<DfsWizardBase<GR> >
 		  dfs(const GR &digraph)
+		  {
 		    return DfsWizard<DfsWizardBase<GR> >(digraph);
+		  }
 		#ifdef DOXYGEN
 		  /// \brief Visitor class for DFS.
 		  ///
 		  /// This class defines the interface of the DfsVisit events, and
 		  /// it could be the base of a real visitor class.
 		  template <typename GR>
 		  struct DfsVisitor {
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    /// \brief Called for the source node of the DFS.
 		    ///
 		    /// This function is called for the source node of the DFS.
 		    void start(const Node& node) {}
 		    /// \brief Called when the source node is leaved.
 		    ///
 		    /// This function is called when the source node is leaved.
 		    void stop(const Node& node) {}
 		    /// \brief Called when a node is reached first time.
 		    ///
 		    /// This function is called when a node is reached first time.
 		    void reach(const Node& node) {}
 		    /// \brief Called when an arc reaches a new node.
 		    ///
 		    /// This function is called when the DFS finds an arc whose target node
 		    /// is not reached yet.
 		    void discover(const Arc& arc) {}
 		    /// \brief Called when an arc is examined but its target node is
 		    /// already discovered.
 		    ///
 		    /// This function is called when an arc is examined but its target node is
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		    /// \brief Called when the DFS steps back from a node.
 		    ///
 		    /// This function is called when the DFS steps back from a node.
 		    void leave(const Node& node) {}
 		    /// \brief Called when the DFS steps back on an arc.
 		    ///
 		    /// This function is called when the DFS steps back on an arc.
 		    void backtrack(const Arc& arc) {}
 		  };
 		#else
 		  template <typename GR>
 		  struct DfsVisitor {
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    void start(const Node&) {}
 		    void stop(const Node&) {}
 		    void reach(const Node&) {}
 		    void discover(const Arc&) {}
 		    void examine(const Arc&) {}
 		    void leave(const Node&) {}
 		    void backtrack(const Arc&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 		        Arc arc;
 		        Node node;
 		        visitor.start(node);
 		        visitor.stop(arc);
 		        visitor.reach(node);
 		        visitor.discover(arc);
 		        visitor.examine(arc);
 		        visitor.leave(node);
 		        visitor.backtrack(arc);
+		      }
 		      _Visitor& visitor;
 		      Constraints() {}
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of DfsVisit class.
 		  ///
 		  /// Default traits class of DfsVisit class.
 		  /// \tparam _Digraph The type of the digraph the algorithm runs on.
 		  template<class GR>
 		  struct DfsVisitDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that indicates which nodes are reached.
 		    ///
 		    /// The type of the map that indicates which nodes are reached.
 		    /// It must conform to the
 		    /// \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a ReachedMap.
 		    ///
 		    /// This function instantiates a ReachedMap.
 		    /// \param digraph is the digraph, to which
 		    /// we would like to define the ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &digraph) {
 		      return new ReachedMap(digraph);
+		    }
 		  };
 		  /// \ingroup search
 		  ///
 		  /// \brief DFS algorithm class with visitor interface.
 		  ///
 		  /// This class provides an efficient implementation of the DFS algorithm
 		  /// with visitor interface.
 		  ///
 		  /// The DfsVisit class provides an alternative interface to the Dfs
 		  /// class. It works with callback mechanism, the DfsVisit object calls
 		  /// the member functions of the \c Visitor class on every DFS event.
 		  ///
 		  /// This interface of the DFS algorithm should be used in special cases
 		  /// when extra actions have to be performed in connection with certain
 		  /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
 		  /// instead.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// The default type is \ref ListDigraph.
 		  /// The value of GR is not used directly by \ref DfsVisit,
 		  /// it is only passed to \ref DfsVisitDefaultTraits.
 		  /// \tparam VS The Visitor type that is used by the algorithm.
 		  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
 		  /// does not observe the DFS events. If you want to observe the DFS
 		  /// events, you should implement your own visitor class.
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
 		  /// "DfsVisitDefaultTraits<GR>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename VS, typename TR>
 		#else
 		  template <typename GR = ListDigraph,
 		            typename VS = DfsVisitor<GR>,
 		            typename TR = DfsVisitDefaultTraits<GR> >
 		#endif
 		  class DfsVisit {
 		  public:
 		    ///The traits class.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The visitor type used by the algorithm.
 		    typedef VS Visitor;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename Traits::ReachedMap ReachedMap;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *_digraph;
 		    //Pointer to the visitor object.
 		    Visitor *_visitor;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Arc> _stack;
 		    int _stack_head;
 		    //Creates the maps if necessary.
 		    void create_maps() {
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*_digraph);
+		      }
+		    }
 		  protected:
 		    DfsVisit() {}
 		  public:
 		    typedef DfsVisit Create;
 		    /// \name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public DfsVisit< Digraph, Visitor,
 		                                            SetReachedMapTraits<T> > {
 		      typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param visitor The visitor object of the algorithm.
 		    DfsVisit(const Digraph& digraph, Visitor& visitor)
 		      : _digraph(&digraph), _visitor(&visitor),
 		        _reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ~DfsVisit() {
 		      if(local_reached) delete _reached;
+		    }
 		    /// \brief Sets the map that indicates which nodes are reached.
 		    ///
 		    /// Sets the map that indicates which nodes are reached.
 		    /// If you don't use this function before calling \ref run(Node) "run()"
 		    /// or \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt> (*this) </tt>
 		    DfsVisit &reachedMap(ReachedMap &m) {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  public:
 		    /// \name Execution Control
 		    /// The simplest way to execute the DFS algorithm is to use one of the
 		    /// member functions called \ref run(Node) "run()".\n
 		    /// If you need better control on the execution, you have to call
 		    /// \ref init() first, then you can add a source node with \ref addSource()
 		    /// and perform the actual computation with \ref start().
 		    /// This procedure can be repeated if there are nodes that have not
 		    /// been reached.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    void init() {
 		      create_maps();
 		      _stack.resize(countNodes(*_digraph));
 		      _stack_head = -1;
 		      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
 		        _reached->set(u, false);
+		      }
+		    }
 		    /// \brief Adds a new source node.
 		    ///
 		    /// Adds a new source node to the set of nodes to be processed.
 		    ///
 		    /// \pre The stack must be empty. Otherwise the algorithm gives
 		    /// wrong results. (One of the outgoing arcs of all the source nodes
 		    /// except for the last one will not be visited and distances will
 		    /// also be wrong.)
 		    void addSource(Node s)
+		    {
 		      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
 		      if(!(*_reached)[s]) {
 		          _reached->set(s,true);
 		          _visitor->start(s);
 		          _visitor->reach(s);
 		          Arc e;
 		          _digraph->firstOut(e, s);
 		          if (e != INVALID) {
 		            _stack[++_stack_head] = e;
 		          } else {
 		            _visitor->leave(s);
 		            _visitor->stop(s);
+		          }
+		        }
+		    }
 		    /// \brief Processes the next arc.
 		    ///
 		    /// Processes the next arc.
 		    ///
 		    /// \return The processed arc.
 		    ///
 		    /// \pre The stack must not be empty.
 		    Arc processNextArc() {
 		      Arc e = _stack[_stack_head];
 		      Node m = _digraph->target(e);
 		      if(!(*_reached)[m]) {
 		        _visitor->discover(e);
 		        _visitor->reach(m);
 		        _reached->set(m, true);
 		        _digraph->firstOut(_stack[++_stack_head], m);
 		      } else {
 		        _visitor->examine(e);
 		        m = _digraph->source(e);
 		        _digraph->nextOut(_stack[_stack_head]);
+		      }
 		      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
 		        _visitor->leave(m);
 		        --_stack_head;
 		        if (_stack_head >= 0) {
 		          _visitor->backtrack(_stack[_stack_head]);
 		          m = _digraph->source(_stack[_stack_head]);
 		          _digraph->nextOut(_stack[_stack_head]);
 		        } else {
 		          _visitor->stop(m);
+		        }
+		      }
 		      return e;
+		    }
 		    /// \brief Next arc to be processed.
 		    ///
 		    /// Next arc to be processed.
 		    ///
 		    /// \return The next arc to be processed or INVALID if the stack is
 		    /// empty.
 		    Arc nextArc() const {
 		      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
+		    }
 		    /// \brief Returns \c false if there are nodes
 		    /// to be processed.
 		    ///
 		    /// Returns \c false if there are nodes
 		    /// to be processed in the queue (stack).
 		    bool emptyQueue() const { return _stack_head < 0; }
 		    /// \brief Returns the number of the nodes to be processed.
 		    ///
 		    /// Returns the number of the nodes to be processed in the queue (stack).
 		    int queueSize() const { return _stack_head + 1; }
 		    /// \brief Executes the algorithm.
 		    ///
 		    /// Executes the algorithm.
 		    ///
 		    /// This method runs the %DFS algorithm from the root node
 		    /// in order to compute the %DFS path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the %DFS tree,
 		    /// - the distance of each node from the root in the %DFS tree.
 		    ///
 		    /// \pre init() must be called and a root node should be
 		    /// added with addSource() before using this function.
 		    ///
 		    /// \note <tt>d.start()</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   while ( !d.emptyQueue() ) {
 		    ///     d.processNextArc();
 		    ///   }
 		    /// \endcode
 		    void start() {
 		      while ( !emptyQueue() ) processNextArc();
+		    }
 		    /// \brief Executes the algorithm until the given target node is reached.
 		    ///
 		    /// Executes the algorithm until the given target node is reached.
 		    ///
 		    /// This method runs the %DFS algorithm from the root node
 		    /// in order to compute the DFS path to \c t.
 		    ///
 		    /// The algorithm computes
 		    /// - the %DFS path to \c t,
 		    /// - the distance of \c t from the root in the %DFS tree.
 		    ///
 		    /// \pre init() must be called and a root node should be added
 		    /// with addSource() before using this function.
 		    void start(Node t) {
 		      while ( !emptyQueue() && !(*_reached)[t] )
 		        processNextArc();
+		    }
 		    /// \brief Executes the algorithm until a condition is met.
 		    ///
 		    /// Executes the algorithm until a condition is met.
 		    ///
 		    /// This method runs the %DFS algorithm from the root node
 		    /// until an arc \c a with <tt>am[a]</tt> true is found.
 		    ///
 		    /// \param am A \c bool (or convertible) arc map. The algorithm
 		    /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
 		    ///
 		    /// \return The reached arc \c a with <tt>am[a]</tt> true or
 		    /// \c INVALID if no such arc was found.
 		    ///
 		    /// \pre init() must be called and a root node should be added
 		    /// with addSource() before using this function.
 		    ///
 		    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
 		    /// not a node map.
 		    template <typename AM>
 		    Arc start(const AM &am) {
 		      while ( !emptyQueue() && !am[_stack[_stack_head]] )
 		        processNextArc();
 		      return emptyQueue() ? INVALID : _stack[_stack_head];
+		    }
 		    /// \brief Runs the algorithm from the given source node.
 		    ///
 		    /// This method runs the %DFS algorithm from node \c s.
 		    /// in order to compute the DFS path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the %DFS tree,
 		    /// - the distance of each node from the root in the %DFS tree.
 		    ///
 		    /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///   d.init();
 		    ///   d.addSource(s);
 		    ///   d.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    /// \brief Finds the %DFS path between \c s and \c t.
 		    /// This method runs the %DFS algorithm from node \c s
 		    /// in order to compute the DFS path to node \c t
 		    /// (it stops searching when \c t is processed).
 		    ///
 		    /// \return \c true if \c t is reachable form \c s.
 		    ///
 		    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
 		    /// just a shortcut of the following code.
 		    ///\code
 		    ///   d.init();
 		    ///   d.addSource(s);
 		    ///   d.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    /// \brief Runs the algorithm to visit all nodes in the digraph.
 		    /// This method runs the %DFS algorithm in order to visit all nodes
 		    /// in the digraph.
 		    ///
 		    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///   d.init();
 		    ///   for (NodeIt n(digraph); n != INVALID; ++n) {
 		    ///     if (!d.reached(n)) {
 		    ///       d.addSource(n);
 		    ///       d.start();
 		    ///     }
 		    ///   }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt it(*_digraph); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    /// \name Query Functions
 		    /// The results of the DFS algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either \ref run(Node) "run()" or \ref start() should be called
 		    /// before using them.
 		    ///@{
 		    /// \brief Checks if the given node is reached from the root(s).
 		    ///
 		    /// Returns \c true if \c v is reached from the root(s).
 		    ///
 		    /// \pre Either \ref run(Node) "run()" or \ref init()
 		    /// must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif

0 comments (0 inline)

RhodeCode

Login to your account