Changes in / [547:17cabb114d52:1106:7c4ba7daaf5f] in lemon

Files:

• .hgignore (modified) (2 diffs)
• AUTHORS (modified) (1 diff)
• CMakeLists.txt (modified) (4 diffs)
• INSTALL (modified) (4 diffs)
• LICENSE (modified) (3 diffs)
• Makefile.am (modified) (3 diffs)
• NEWS (modified) (1 diff)
• README (modified) (1 diff)
• cmake/FindCOIN.cmake (added)
• cmake/FindCPLEX.cmake (added)
• cmake/FindGLPK.cmake (added)
• cmake/FindGhostscript.cmake (modified) (1 diff)
• cmake/LEMONConfig.cmake.in (added)
• cmake/nsis/lemon.ico (modified) (previous)
• cmake/version.cmake.in (added)
• configure.ac (modified) (5 diffs)
• demo/CMakeLists.txt (modified) (1 diff)
• demo/Makefile.am (modified) (1 diff)
• demo/graph_to_eps_demo.cc (modified) (1 diff)
• doc/CMakeLists.txt (modified) (1 diff)
• doc/Doxyfile.in (modified) (15 diffs)
• doc/DoxygenLayout.xml (modified) (1 diff)
• doc/Makefile.am (modified) (5 diffs)
• doc/groups.dox (modified) (34 diffs)
• doc/images/bipartite_matching.eps (added)
• doc/images/bipartite_partitions.eps (added)
• doc/images/connected_components.eps (added)
• doc/images/edge_biconnected_components.eps (added)
• doc/images/node_biconnected_components.eps (added)
• doc/images/strongly_connected_components.eps (added)
• doc/lgf.dox (modified) (2 diffs)
• doc/mainpage.dox (deleted)
• doc/mainpage.dox.in (added)
• doc/min_cost_flow.dox (added)
• lemon/CMakeLists.txt (modified) (2 diffs)
• lemon/Makefile.am (modified) (5 diffs)
• lemon/adaptors.h (modified) (132 diffs)
• lemon/base.cc (modified) (1 diff)
• lemon/bfs.h (modified) (16 diffs)
• lemon/bin_heap.h (modified) (20 diffs)
• lemon/bits/array_map.h (modified) (5 diffs)
• lemon/bits/base_extender.h (deleted)
• lemon/bits/default_map.h (modified) (3 diffs)
• lemon/bits/edge_set_extender.h (added)
• lemon/bits/graph_adaptor_extender.h (modified) (2 diffs)
• lemon/bits/graph_extender.h (modified) (7 diffs)
• lemon/bits/map_extender.h (modified) (8 diffs)
• lemon/bits/path_dump.h (modified) (3 diffs)
• lemon/bits/solver_bits.h (modified) (1 diff)
• lemon/bits/traits.h (modified) (4 diffs)
• lemon/bits/vector_map.h (modified) (6 diffs)
• lemon/bits/windows.cc (added)
• lemon/bits/windows.h (added)
• lemon/bucket_heap.h (added)
• lemon/cbc.cc (added)
• lemon/cbc.h (added)
• lemon/circulation.h (modified) (28 diffs)
• lemon/clp.cc (added)
• lemon/clp.h (added)
• lemon/concepts/digraph.h (modified) (7 diffs)
• lemon/concepts/graph.h (modified) (12 diffs)
• lemon/concepts/graph_components.h (modified) (55 diffs)
• lemon/concepts/heap.h (modified) (6 diffs)
• lemon/concepts/maps.h (modified) (3 diffs)
• lemon/concepts/path.h (modified) (5 diffs)
• lemon/config.h.cmake (added)
• lemon/config.h.in (modified) (1 diff)
• lemon/connectivity.h (modified) (29 diffs)
• lemon/core.h (modified) (30 diffs)
• lemon/cplex.cc (added)
• lemon/cplex.h (added)
• lemon/dfs.h (modified) (19 diffs)
• lemon/dijkstra.h (modified) (28 diffs)
• lemon/dimacs.h (modified) (20 diffs)
• lemon/edge_set.h (added)
• lemon/elevator.h (modified) (43 diffs)
• lemon/euler.h (added)
• lemon/fib_heap.h (added)
• lemon/full_graph.h (modified) (7 diffs)
• lemon/glpk.cc (added)
• lemon/glpk.h (added)
• lemon/gomory_hu.h (added)
• lemon/graph_to_eps.h (modified) (13 diffs)
• lemon/grid_graph.h (modified) (1 diff)
• lemon/hao_orlin.h (modified) (53 diffs)
• lemon/hypercube_graph.h (modified) (1 diff)
• lemon/kruskal.h (modified) (5 diffs)
• lemon/lemon.pc.cmake (added)
• lemon/lemon.pc.in (modified) (1 diff)
• lemon/lgf_reader.h (modified) (42 diffs)
• lemon/lgf_writer.h (modified) (36 diffs)
• lemon/list_graph.h (modified) (9 diffs)
• lemon/lp.h (modified) (5 diffs)
• lemon/lp_base.cc (modified) (1 diff)
• lemon/lp_base.h (modified) (26 diffs)
• lemon/lp_clp.cc (deleted)
• lemon/lp_clp.h (deleted)
• lemon/lp_cplex.cc (deleted)
• lemon/lp_cplex.h (deleted)
• lemon/lp_glpk.cc (deleted)
• lemon/lp_glpk.h (deleted)
• lemon/lp_skeleton.cc (modified) (3 diffs)
• lemon/lp_skeleton.h (modified) (3 diffs)
• lemon/lp_soplex.cc (deleted)
• lemon/lp_soplex.h (deleted)
• lemon/maps.h (modified) (74 diffs)
• lemon/matching.h (added)
• lemon/math.h (modified) (1 diff)
• lemon/max_matching.h (deleted)
• lemon/min_cost_arborescence.h (added)
• lemon/network_simplex.h (added)
• lemon/path.h (modified) (24 diffs)
• lemon/preflow.h (modified) (41 diffs)
• lemon/radix_heap.h (added)
• lemon/radix_sort.h (modified) (2 diffs)
• lemon/random.h (modified) (15 diffs)
• lemon/smart_graph.h (modified) (9 diffs)
• lemon/soplex.cc (added)
• lemon/soplex.h (added)
• lemon/suurballe.h (modified) (16 diffs)
• lemon/time_measure.h (modified) (5 diffs)
• lemon/tolerance.h (modified) (4 diffs)
• lemon/unionfind.h (modified) (9 diffs)
• m4/lx_check_clp.m4 (deleted)
• m4/lx_check_coin.m4 (added)
• m4/lx_check_cplex.m4 (modified) (1 diff)
• m4/lx_check_glpk.m4 (modified) (1 diff)
• m4/lx_check_soplex.m4 (modified) (3 diffs)
• scripts/mk-release.sh (added)
• scripts/unify-sources.sh (modified) (3 diffs)
• test/CMakeLists.txt (modified) (3 diffs)
• test/Makefile.am (modified) (6 diffs)
• test/adaptors_test.cc (added)
• test/bfs_test.cc (modified) (3 diffs)
• test/circulation_test.cc (modified) (3 diffs)
• test/connectivity_test.cc (added)
• test/counter_test.cc (modified) (3 diffs)
• test/dfs_test.cc (modified) (7 diffs)
• test/dijkstra_test.cc (modified) (3 diffs)
• test/edge_set_test.cc (added)
• test/euler_test.cc (added)
• test/gomory_hu_test.cc (added)
• test/graph_adaptor_test.cc (deleted)
• test/graph_copy_test.cc (modified) (8 diffs)
• test/graph_utils_test.cc (modified) (4 diffs)
• test/hao_orlin_test.cc (modified) (2 diffs)
• test/heap_test.cc (modified) (2 diffs)
• test/kruskal_test.cc (modified) (1 diff)
• test/lgf_test.cc (added)
• test/lp_test.cc (modified) (8 diffs)
• test/maps_test.cc (modified) (5 diffs)
• test/matching_test.cc (added)
• test/max_matching_test.cc (deleted)
• test/min_cost_arborescence_test.cc (added)
• test/min_cost_flow_test.cc (added)
• test/mip_test.cc (modified) (8 diffs)
• test/preflow_test.cc (modified) (4 diffs)
• test/suurballe_test.cc (modified) (7 diffs)
• test/time_measure_test.cc (modified) (1 diff)
• tools/CMakeLists.txt (added)
• tools/Makefile.am (modified) (2 diffs)
• tools/dimacs-solver.cc (added)
• tools/dimacs-to-lgf.cc (modified) (3 diffs)
• tools/lemon-0.x-to-1.x.sh (modified) (3 diffs)
• tools/lgf-gen.cc (added)

.hgignore

@@ -23 +23 @@
 lemon/stamp-h2
 doc/Doxyfile
+cmake/version.cmake
 .dirstamp
 .libs/*
@@ -40 +41 @@
 ^autom4te.cache/.*
 ^build-aux/.*
-^objs.*/.*
+^.*objs.*/.*
 ^test/[a-z_]*$
 ^tools/[a-z-_]*$
 ^demo/.*_demo$
-^build/.*
+^.*build.*/.*
 ^doc/gen-images/.*
 CMakeFiles

AUTHORS

@@ -24 +24 @@
 
 Again, please visit the history of the old LEMON repository for more
-details: http://lemon.cs.elte.hu/svn/lemon/trunk
+details: http://lemon.cs.elte.hu/hg/lemon-0.x

CMakeLists.txt

@@ -2 +2 @@
 
 SET(PROJECT_NAME "LEMON")
-SET(PROJECT_VERSION "hg-tip" CACHE STRING "The version string.")
-
 PROJECT(${PROJECT_NAME})
 
-SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
-
-INCLUDE(FindDoxygen)
-INCLUDE(FindGhostscript)
+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")
+  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
+    "Flags used by the C++ compiler during maintainer builds."
+    FORCE )
+SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" 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)
-ADD_SUBDIRECTORY(demo)
-ADD_SUBDIRECTORY(doc)
-ADD_SUBDIRECTORY(test)
-
-IF(WIN32)
-  INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico
-    DESTINATION bin)
-ENDIF(WIN32)
-
-IF(WIN32)
+IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
+  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 - Egervary Research Group on Combinatorial Optimization")
+  SET(CPACK_PACKAGE_VENDOR "EGRES")
   SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
-    "LEMON - Library of Efficient Models and Optimization in Networks")
-  SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
+    "LEMON - Library for Efficient Modeling and Optimization in Networks")
+  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
 
   SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
@@ -38 +162 @@
     "${PROJECT_NAME} ${PROJECT_VERSION}")
 
-  # Variables to generate a component-based installer.
-  #SET(CPACK_COMPONENTS_ALL headers library html_documentation)
-
-  #SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
-  #SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Static library")
-  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
-
-  #SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
-  #  "C++ header files for use with the LEMON library")
-  #SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
-  #  "Static library used to build programs with LEMON")
-  #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_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 "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
-  SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
-  #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
+  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}")
@@ -79 +205 @@
   SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
   SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
-    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\"
+    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
     ")
   SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
@@ -87 +213 @@
 
   INCLUDE(CPack)
-ENDIF(WIN32)
+ENDIF()

INSTALL

@@ -5 +5 @@
 tarballs and successfully extracted it. The latest version of LEMON is
 available at our web page (http://lemon.cs.elte.hu/).
+
+LEMON provides two different build environments, one is based on "autotool",
+while the other is based on "cmake". This file contains instructions only for
+the former one, which is the recommended build environment on Linux, Mac OSX
+and other unices or if you use Cygwin on Windows. For cmake installation
+instructions visit http://lemon.cs.elte.hu.
 
 In order to install LEMON from the extracted source tarball you have to
@@ -22 +28 @@
 
       This command compiles the non-template part of LEMON into libemon.a
-      file. It also compiles the programs in the tools and demo subdirectories
-      when enabled.
+      file. It also compiles the programs in the tools subdirectory by
+      default.
 
    4. `make check'
@@ -69 +75 @@
 
   Set the installation prefix to PREFIX. By default it is /usr/local.
-
---enable-demo
-
-   Build the examples in the demo subdirectory.
-
---disable-demo
-
-   Do not build the examples in the demo subdirectory (default).
 
 --enable-tools
@@ -153 +151 @@
 
    Disable SoPlex support.
+
+--with-coin[=PREFIX]
+
+   Enable support for COIN-OR solvers (CLP and CBC). You should
+   specify the prefix too. (by default, COIN-OR tools install
+   themselves to the source code directory). This command enables the
+   solvers that are actually found.
+
+--with-coin-includedir=DIR
+
+   The directory where the COIN-OR header files are located. This is
+   only useful when the COIN-OR headers and libraries are not under
+   the same prefix (which is unlikely).
+
+--with-coin-libdir=DIR
+
+   The directory where the COIN-OR libraries are located. This is only
+   useful when the COIN-OR headers and libraries are not under the
+   same prefix (which is unlikely).
+
+--without-coin
+
+   Disable COIN-OR support.

LICENSE

@@ -1 @@
-LEMON code without an explicit copyright is covered by the following
+LEMON code without an explicit copyright notice is covered by the following
 copyright/license.
 
@@ -5 +5 @@
 Kutatocsoport (Egervary Combinatorial Optimization Research Group,
 EGRES).
+
+===========================================================================
+Boost Software License, Version 1.0
+===========================================================================
 
 Permission is hereby granted, free of charge, to any person or organization
@@ -27 +31 @@
 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 DEALINGS IN THE SOFTWARE.
-
-===========================================================================
-This license is a verbatim copy of the Boost Software License, Version 1.0.
-
-

Makefile.am

@@ -12 +12 @@
         m4/lx_check_glpk.m4 \
         m4/lx_check_soplex.m4 \
+        m4/lx_check_coin.m4 \
         CMakeLists.txt \
-        cmake
+        cmake/FindGhostscript.cmake \
+        cmake/FindCPLEX.cmake \
+        cmake/FindGLPK.cmake \
+        cmake/FindCOIN.cmake \
+        cmake/LEMONConfig.cmake.in \
+        cmake/version.cmake.in \
+        cmake/version.cmake \
+        cmake/nsis/lemon.ico \
+        cmake/nsis/uninstall.ico
 
 pkgconfigdir = $(libdir)/pkgconfig
@@ -35 +44 @@
 include test/Makefile.am
 include doc/Makefile.am
-include demo/Makefile.am
 include tools/Makefile.am
+
+DIST_SUBDIRS = demo
+
+demo:
+        $(MAKE) $(AM_MAKEFLAGS) -C demo
 
 MRPROPERFILES = \
@@ -64 +77 @@
         bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
 
-.PHONY: mrproper dist-bz2 distcheck-bz2
+.PHONY: demo mrproper dist-bz2 distcheck-bz2

NEWS

@@ +1 @@
+2009-05-13 Version 1.1 released
+
+        This is the second stable release of the 1.x series. It
+        features a better coverage of the tools available in the 0.x
+        series, a thoroughly reworked LP/MIP interface plus various
+        improvements in the existing tools.
+
+        * Much improved M$ Windows support
+          * Various improvements in the CMAKE build system
+          * Compilation warnings are fixed/suppressed
+        * Support IBM xlC compiler
+        * New algorithms
+          * Connectivity related algorithms (#61)
+          * Euler walks (#65)
+          * Preflow push-relabel max. flow algorithm (#176)
+          * Circulation algorithm (push-relabel based) (#175)
+          * Suurballe algorithm (#47)
+          * Gomory-Hu algorithm (#66)
+          * Hao-Orlin algorithm (#58)
+          * Edmond's maximum cardinality and weighted matching algorithms
+            in general graphs (#48,#265)
+          * Minimum cost arborescence/branching (#60)
+          * Network Simplex min. cost flow algorithm (#234)
+        * New data structures
+          * Full graph structure (#57)
+          * Grid graph structure (#57)
+          * Hypercube graph structure (#57)
+          * Graph adaptors (#67)
+          * ArcSet and EdgeSet classes (#67)
+          * Elevator class (#174)
+        * Other new tools
+          * LP/MIP interface (#44)
+            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
+          * Reader for the Nauty file format (#55)
+          * DIMACS readers (#167)
+          * Radix sort algorithms (#72)
+          * RangeIdMap and CrossRefMap (#160)
+        * New command line tools
+          * DIMACS to LGF converter (#182)
+          * lgf-gen - a graph generator (#45)
+          * DIMACS solver utility (#226)
+        * Other code improvements
+          * Lognormal distribution added to Random (#102)
+          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
+          * The standard maps of graphs are guaranteed to be
+            reference maps (#190)
+        * Miscellaneous
+          * Various doc improvements
+          * Improved 0.x -> 1.x converter script
+
+        * Several bugfixes (compared to release 1.0):
+          #170: Bugfix SmartDigraph::split()
+          #171: Bugfix in SmartGraph::restoreSnapshot()
+          #172: Extended test cases for graphs and digraphs
+          #173: Bugfix in Random
+                * operator()s always return a double now
+                * the faulty real<Num>(Num) and real<Num>(Num,Num)
+                  have been removed
+          #187: Remove DijkstraWidestPathOperationTraits
+          #61:  Bugfix in DfsVisit
+          #193: Bugfix in GraphReader::skipSection()
+          #195: Bugfix in ConEdgeIt()
+          #197: Bugfix in heap unionfind
+                * This bug affects Edmond's general matching algorithms
+          #207: Fix 'make install' without 'make html' using CMAKE
+          #208: Suppress or fix VS2008 compilation warnings
+          ----: Update the LEMON icon
+          ----: Enable the component-based installer
+                (in installers made by CPACK)
+          ----: Set the proper version for CMAKE in the tarballs
+                (made by autotools)
+          ----: Minor clarification in the LICENSE file
+          ----: Add missing unistd.h include to time_measure.h
+          #204: Compilation bug fixed in graph_to_eps.h with VS2005
+          #214,#215: windows.h should never be included by lemon headers
+          #230: Build systems check the availability of 'long long' type
+          #229: Default implementation of Tolerance<> is used for integer types
+          #211,#212: Various fixes for compiling on AIX
+          ----: Improvements in CMAKE config
+                - docs is installed in share/doc/
+                - detects newer versions of Ghostscript
+          #239: Fix missing 'inline' specifier in time_measure.h
+          #274,#280: Install lemon/config.h
+          #275: Prefix macro names with LEMON_ in lemon/config.h
+          ----: Small script for making the release tarballs added
+          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
+
+2009-03-27 LEMON joins to the COIN-OR initiative
+
+        COIN-OR (Computational Infrastructure for Operations Research,
+        http://www.coin-or.org) project is an initiative to spur the
+        development of open-source software for the operations research
+        community.
+
 2008-10-13 Version 1.0 released
 

README

@@ -1 @@
-==================================================================
-LEMON - a Library of Efficient Models and Optimization in Networks
-==================================================================
+=====================================================================
+LEMON - a Library for Efficient Modeling and Optimization in Networks
+=====================================================================
 
 LEMON is an open source library written in C++. It provides

cmake/FindGhostscript.cmake

@@ -4 +4 @@
   NAMES gs gswin32c
   PATHS "$ENV{ProgramFiles}/gs"
-  PATH_SUFFIXES gs8.61/bin gs8.62/bin
+  PATH_SUFFIXES gs8.61/bin gs8.62/bin gs8.63/bin gs8.64/bin gs8.65/bin
   DOC "Ghostscript: PostScript and PDF language interpreter and previewer."
 )

configure.ac

@@ -3 +3 @@
 dnl Version information.
 m4_define([lemon_version_number],
-        [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
+          [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
 dnl m4_define([lemon_version_number], [])
 m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
-m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
+m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i 2> /dev/null]))])
 m4_define([lemon_version], [ifelse(lemon_version_number(),
-                           [],
-                           [lemon_hg_path().lemon_hg_revision()],
-                           [lemon_version_number()])])
+                           [],
+                           [ifelse(lemon_hg_revision(),
+                           [],
+                           [hg-tip],
+                           [lemon_hg_path().lemon_hg_revision()])],
+                           [lemon_version_number()])])
 
 AC_PREREQ([2.59])
@@ -20 +23 @@
 AC_CONFIG_HEADERS([config.h lemon/config.h])
 
+AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string])
+
 dnl Do compilation tests using the C++ compiler.
 AC_LANG([C++])
+
+dnl Check the existence of long long type.
+AC_CHECK_TYPE(long long, [long_long_found=yes], [long_long_found=no])
+if test x"$long_long_found" = x"yes"; then
+  AC_DEFINE([LEMON_HAVE_LONG_LONG], [1], [Define to 1 if you have long long.])
+fi
 
 dnl Checks for programs.
@@ -54 +65 @@
 LX_CHECK_CPLEX
 LX_CHECK_SOPLEX
-LX_CHECK_CLP
+LX_CHECK_COIN
 
 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
-
-dnl Disable/enable building the demo programs.
-AC_ARG_ENABLE([demo],
-AS_HELP_STRING([--enable-demo], [build the demo programs])
-AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
-              [], [enable_demo=no])
-AC_MSG_CHECKING([whether to build the demo programs])
-if test x"$enable_demo" != x"no"; then
-  AC_MSG_RESULT([yes])
-else
-  AC_MSG_RESULT([no])
-fi
-AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
 
 dnl Disable/enable building the binary tools.
@@ -101 +99 @@
 dnl Add dependencies on files generated by configure.
 AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
-  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in'])
+  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
 
 AC_CONFIG_FILES([
 Makefile
+demo/Makefile
+cmake/version.cmake
 doc/Doxyfile
+doc/mainpage.dox
 lemon/lemon.pc
 ])
@@ -119 +120 @@
 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
 echo
+echo Compiler supports long long... : $long_long_found
+echo
 echo GLPK support.................. : $lx_glpk_found
 echo CPLEX support................. : $lx_cplex_found
 echo SOPLEX support................ : $lx_soplex_found
 echo CLP support................... : $lx_clp_found
+echo CBC support................... : $lx_cbc_found
 echo
-echo Build demo programs........... : $enable_demo
 echo Build additional tools........ : $enable_tools
 echo

demo/CMakeLists.txt

@@ -1 @@
-INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
+INCLUDE_DIRECTORIES(
+  ${PROJECT_SOURCE_DIR}
+  ${PROJECT_BINARY_DIR}
+)
 
-LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
+LINK_DIRECTORIES(
+  ${PROJECT_BINARY_DIR}/lemon
+)
 
 SET(DEMOS
   arg_parser_demo
   graph_to_eps_demo
-  lgf_demo)
+  lgf_demo
+)
 
 FOREACH(DEMO_NAME ${DEMOS})
   ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc)
   TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
-ENDFOREACH(DEMO_NAME)
+ENDFOREACH()

demo/Makefile.am

@@ -1 @@
-EXTRA_DIST += \
-        demo/CMakeLists.txt \
-        demo/digraph.lgf
+AM_CXXFLAGS = $(WARNINGCXXFLAGS)
 
-if WANT_DEMO
+AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
+LDADD = $(top_builddir)/lemon/libemon.la
 
-noinst_PROGRAMS += \
-        demo/arg_parser_demo \
-        demo/graph_to_eps_demo \
-        demo/lgf_demo
+EXTRA_DIST = \
+        CMakeLists.txt \
+        digraph.lgf
 
-endif WANT_DEMO
+noinst_PROGRAMS = \
+        arg_parser_demo \
+        graph_to_eps_demo \
+        lgf_demo
 
-demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc
-demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc
-demo_lgf_demo_SOURCES = demo/lgf_demo.cc
+arg_parser_demo_SOURCES = arg_parser_demo.cc
+graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
+lgf_demo_SOURCES = lgf_demo.cc

demo/graph_to_eps_demo.cc

@@ -183 +183 @@
   ListDigraph::NodeMap<Point> hcoords(h);
 
-  int cols=int(sqrt(double(palette.size())));
+  int cols=int(std::sqrt(double(palette.size())));
   for(int i=0;i<int(paletteW.size());i++) {
     Node n=h.addNode();

doc/CMakeLists.txt

@@ -1 +1 @@
 SET(PACKAGE_NAME ${PROJECT_NAME})
 SET(PACKAGE_VERSION ${PROJECT_VERSION})
-SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
-SET(abs_top_builddir ${CMAKE_BINARY_DIR})
+SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
+SET(abs_top_builddir ${PROJECT_BINARY_DIR})
+
+SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
 
 CONFIGURE_FILE(
-  ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
-  ${CMAKE_BINARY_DIR}/doc/Doxyfile
-  @ONLY)
+  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
+  ${PROJECT_BINARY_DIR}/doc/Doxyfile
+  @ONLY
+)
+
+CONFIGURE_FILE(
+  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
+  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
+  @ONLY
+)
 
 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
+  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
+  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
+  ADD_CUSTOM_TARGET(html
+    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
+    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
+    COMMAND ${CMAKE_COMMAND} -E remove_directory html
+    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
+    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+  )
+
+  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
+
   IF(UNIX)
-    ADD_CUSTOM_TARGET(html
-      COMMAND rm -rf gen-images
-      COMMAND mkdir gen-images
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
-      COMMAND rm -rf html
-      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
-      WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
+    INSTALL(
+      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
+      DESTINATION share/doc/lemon/html
+      COMPONENT html_documentation
+    )
   ELSEIF(WIN32)
-    ADD_CUSTOM_TARGET(html
-      COMMAND if exist gen-images rmdir /s /q gen-images
-      COMMAND mkdir gen-images
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
-      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
-      COMMAND if exist html rmdir /s /q html
-      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
-      WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
-  ENDIF(UNIX)
-ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
+    INSTALL(
+      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
+      DESTINATION doc
+      COMPONENT html_documentation
+    )
+  ENDIF()
 
-INSTALL(
-  DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
-  DESTINATION doc
-  COMPONENT html_documentation)
+ENDIF()
+
+IF(WGET_FOUND)
+ADD_CUSTOM_TARGET(update-external-tags
+  COMMAND ${CMAKE_COMMAND} -E make_directory dl
+  # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
+  COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
+  COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
+  COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
+  COMMAND ${CMAKE_COMMAND} -E remove_directory dl
+  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+  )
+ENDIF()

doc/Doxyfile.in

@@ -1 @@
-# Doxyfile 1.5.7.1
+# Doxyfile 1.7.3
 
 #---------------------------------------------------------------------------
@@ -5 +5 @@
 #---------------------------------------------------------------------------
 DOXYFILE_ENCODING      = UTF-8
-PROJECT_NAME           = @PACKAGE_NAME@
-PROJECT_NUMBER         = @PACKAGE_VERSION@
+PROJECT_NAME           = 
+PROJECT_NUMBER         = 
+PROJECT_BRIEF          =
+PROJECT_LOGO           =
 OUTPUT_DIRECTORY       = 
 CREATE_SUBDIRS         = NO
@@ -22 +24 @@
 QT_AUTOBRIEF           = NO
 MULTILINE_CPP_IS_BRIEF = NO
-DETAILS_AT_TOP         = YES
 INHERIT_DOCS           = NO
 SEPARATE_MEMBER_PAGES  = NO
@@ -31 +32 @@
 OPTIMIZE_FOR_FORTRAN   = NO
 OPTIMIZE_OUTPUT_VHDL   = NO
+EXTENSION_MAPPING      =
 BUILTIN_STL_SUPPORT    = YES
 CPP_CLI_SUPPORT        = NO
@@ -56 +58 @@
 HIDE_SCOPE_NAMES       = YES
 SHOW_INCLUDE_FILES     = YES
+FORCE_LOCAL_INCLUDES   = NO
 INLINE_INFO            = YES
 SORT_MEMBER_DOCS       = NO
 SORT_BRIEF_DOCS        = NO
+SORT_MEMBERS_CTORS_1ST = NO
 SORT_GROUP_NAMES       = NO
 SORT_BY_SCOPE_NAME     = NO
+STRICT_PROTO_MATCHING  = NO
 GENERATE_TODOLIST      = YES
 GENERATE_TESTLIST      = YES
@@ -72 +77 @@
 SHOW_NAMESPACES        = YES
 FILE_VERSION_FILTER    = 
-LAYOUT_FILE            = DoxygenLayout.xml
+LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
 #---------------------------------------------------------------------------
 # configuration options related to warning and progress messages
@@ -92 +97 @@
                          "@abs_top_srcdir@/demo" \
                          "@abs_top_srcdir@/tools" \
-                         "@abs_top_srcdir@/test/test_tools.h"
+                         "@abs_top_srcdir@/test/test_tools.h" \
+                         "@abs_top_builddir@/doc/mainpage.dox"
 INPUT_ENCODING         = UTF-8
 FILE_PATTERNS          = *.h \
@@ -112 +118 @@
 FILTER_PATTERNS        = 
 FILTER_SOURCE_FILES    = NO
+FILTER_SOURCE_PATTERNS =
 #---------------------------------------------------------------------------
 # configuration options related to source browsing
 #---------------------------------------------------------------------------
-SOURCE_BROWSER         = NO
+SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
 INLINE_SOURCES         = NO
 STRIP_CODE_COMMENTS    = YES
@@ -138 +145 @@
 HTML_FOOTER            = 
 HTML_STYLESHEET        = 
+HTML_COLORSTYLE_HUE    = 220
+HTML_COLORSTYLE_SAT    = 100
+HTML_COLORSTYLE_GAMMA  = 80
+HTML_TIMESTAMP         = YES
 HTML_ALIGN_MEMBERS     = YES
-HTML_DYNAMIC_SECTIONS  = NO
+HTML_DYNAMIC_SECTIONS  = YES
 GENERATE_DOCSET        = NO
 DOCSET_FEEDNAME        = "Doxygen generated docs"
 DOCSET_BUNDLE_ID       = org.doxygen.Project
+DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
+DOCSET_PUBLISHER_NAME  = Publisher
 GENERATE_HTMLHELP      = NO
 CHM_FILE               = 
@@ -154 +167 @@
 QHP_NAMESPACE          = org.doxygen.Project
 QHP_VIRTUAL_FOLDER     = doc
+QHP_CUST_FILTER_NAME   =
+QHP_CUST_FILTER_ATTRS  =
+QHP_SECT_FILTER_ATTRS  =
 QHG_LOCATION           = 
+GENERATE_ECLIPSEHELP   = NO
+ECLIPSE_DOC_ID         = org.doxygen.Project
 DISABLE_INDEX          = NO
 ENUM_VALUES_PER_LINE   = 4
 GENERATE_TREEVIEW      = NO
+USE_INLINE_TREES       = NO
 TREEVIEW_WIDTH         = 250
+EXT_LINKS_IN_WINDOW    = NO
 FORMULA_FONTSIZE       = 10
+FORMULA_TRANSPARENT    = YES
+USE_MATHJAX            = NO
+MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
+SEARCHENGINE           = YES
+SERVER_BASED_SEARCH    = NO
 #---------------------------------------------------------------------------
 # configuration options related to the LaTeX output
@@ -176 +201 @@
 LATEX_BATCHMODE        = NO
 LATEX_HIDE_INDICES     = NO
+LATEX_SOURCE_CODE      = NO
 #---------------------------------------------------------------------------
 # configuration options related to the RTF output
@@ -224 +250 @@
 SKIP_FUNCTION_MACROS   = YES
 #---------------------------------------------------------------------------
-# Configuration::additions related to external references   
-#---------------------------------------------------------------------------
-TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
+# Configuration::additions related to external references
+#---------------------------------------------------------------------------
+TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
 GENERATE_TAGFILE       = html/lemon.tag
 ALLEXTERNALS           = NO
@@ -238 +264 @@
 HIDE_UNDOC_RELATIONS   = YES
 HAVE_DOT               = YES
+DOT_NUM_THREADS        = 0
 DOT_FONTNAME           = FreeSans
 DOT_FONTSIZE           = 10
@@ -255 +282 @@
 DOT_PATH               = 
 DOTFILE_DIRS           = 
+MSCFILE_DIRS           =
 DOT_GRAPH_MAX_NODES    = 50
 MAX_DOT_GRAPH_DEPTH    = 0
@@ -261 +289 @@
 GENERATE_LEGEND        = YES
 DOT_CLEANUP            = YES
-#---------------------------------------------------------------------------
-# Configuration::additions related to the search engine   
-#---------------------------------------------------------------------------
-SEARCHENGINE           = NO

doc/DoxygenLayout.xml

@@ -3 +3 @@
   <navindex>
     <tab type="mainpage" visible="yes" title=""/>
-    <tab type="modules" visible="yes" title=""/>
+    <tab type="modules" visible="yes" title="" intro=""/>
     <tab type="classes" visible="yes" title="">
-      <tab type="classes" visible="yes" title=""/>
-      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/> 
-      <tab type="hierarchy" visible="yes" title=""/>
-      <tab type="classmembers" visible="yes" title=""/>
+      <tab type="classes" visible="yes" title="" intro=""/>
+      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/>
+      <tab type="hierarchy" visible="yes" title="" intro=""/>
+      <tab type="classmembers" visible="yes" title="" intro=""/>
     </tab>
     <tab type="namespaces" visible="yes" title="">
-      <tab type="namespaces" visible="yes" title=""/>
-      <tab type="namespacemembers" visible="yes" title=""/>
+      <tab type="namespaces" visible="yes" title="" intro=""/>
+      <tab type="namespacemembers" visible="yes" title="" intro=""/>
     </tab>
     <tab type="files" visible="yes" title="">
-      <tab type="files" visible="yes" title=""/>
-      <tab type="globals" visible="yes" title=""/>
+      <tab type="files" visible="yes" title="" intro=""/>
+      <tab type="globals" visible="yes" title="" intro=""/>
     </tab>
-    <tab type="dirs" visible="yes" title=""/>
-    <tab type="examples" visible="yes" title=""/>  
-    <tab type="pages" visible="yes" title=""/>
+    <tab type="dirs" visible="yes" title="" intro=""/>
+    <tab type="examples" visible="yes" title="" intro=""/>
+    <tab type="pages" visible="yes" title="" intro=""/>
   </navindex>
 

doc/Makefile.am

@@ -9 +9 @@
         doc/mainpage.dox \
         doc/migration.dox \
+        doc/min_cost_flow.dox \
         doc/named-param.dox \
         doc/namespaces.dox \
@@ -22 +23 @@
         nodeshape_4.eps
 
+DOC_EPS_IMAGES27 = \
+        bipartite_matching.eps \
+        bipartite_partitions.eps \
+        connected_components.eps \
+        edge_biconnected_components.eps \
+        node_biconnected_components.eps \
+        strongly_connected_components.eps
+
 DOC_EPS_IMAGES = \
-        $(DOC_EPS_IMAGES18)
+        $(DOC_EPS_IMAGES18) \
+        $(DOC_EPS_IMAGES27)
 
 DOC_PNG_IMAGES = \
@@ -39 +49 @@
         if test ${gs_found} = yes; then \
           $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \
+        else \
+          echo; \
+          echo "Ghostscript not found."; \
+          echo; \
+          exit 1; \
+        fi
+
+$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
+        -mkdir doc/gen-images
+        if test ${gs_found} = yes; then \
+          $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \
         else \
           echo; \
@@ -71 +92 @@
 install-html-local: doc/html
         @$(NORMAL_INSTALL)
-        $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
+        $(mkinstalldirs) $(DESTDIR)$(htmldir)/html
         for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
           f="`echo $$p | sed -e 's|^.*/||'`"; \
-          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
-          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
+          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
+          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
         done
 
@@ -82 +103 @@
         for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
           f="`echo $$p | sed -e 's|^.*/||'`"; \
-          echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
-          rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
+          echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
+          rm -f $(DESTDIR)$(htmldir)/html/$$f; \
         done
 

doc/groups.dox

@@ -21 +21 @@
 /**
 @defgroup datas Data Structures
-This group describes the several data structures implemented in LEMON.
+This group contains the several data structures implemented in LEMON.
 */
 
@@ -139 +139 @@
 
 /**
-@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
-@ingroup graphs
-\brief Graph types between real graphs and graph adaptors.
-
-This group describes some graph types between real graphs and graph adaptors.
-These classes wrap graphs to give new functionality as the adaptors do it.
-On the other hand they are not light-weight structures as the adaptors.
-*/
-
-/**
 @defgroup maps Maps
 @ingroup datas
 \brief Map structures implemented in LEMON.
 
-This group describes the map structures implemented in LEMON.
+This group contains the map structures implemented in LEMON.
 
 LEMON provides several special purpose maps and map adaptors that e.g. combine
@@ -166 +156 @@
 \brief Special graph-related maps.
 
-This group describes maps that are specifically designed to assign
+This group contains maps that are specifically designed to assign
 values to the nodes and arcs/edges of graphs.
 
@@ -178 +168 @@
 \brief Tools to create new maps from existing ones
 
-This group describes map adaptors that are used to create "implicit"
+This group contains map adaptors that are used to create "implicit"
 maps from other maps.
 
@@ -241 +231 @@
 \brief Two dimensional data storages implemented in LEMON.
 
-This group describes two dimensional data storages implemented in LEMON.
+This group contains two dimensional data storages implemented in LEMON.
 */
 
@@ -249 +239 @@
 \brief %Path structures implemented in LEMON.
 
-This group describes the path structures implemented in LEMON.
+This group contains the path structures implemented in LEMON.
 
 LEMON provides flexible data structures to work with paths.
@@ -265 +255 @@
 \brief Auxiliary data structures implemented in LEMON.
 
-This group describes some data structures implemented in LEMON in
+This group contains some data structures implemented in LEMON in
 order to make it easier to implement combinatorial algorithms.
 */
@@ -271 +261 @@
 /**
 @defgroup algs Algorithms
-\brief This group describes the several algorithms
+\brief This group contains the several algorithms
 implemented in LEMON.
 
-This group describes the several algorithms
+This group contains the several algorithms
 implemented in LEMON.
 */
@@ -283 +273 @@
 \brief Common graph search algorithms.
 
-This group describes the common graph search algorithms, namely
+This group contains the common graph search algorithms, namely
 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
 */
@@ -292 +282 @@
 \brief Algorithms for finding shortest paths.
 
-This group describes the algorithms for finding shortest paths in digraphs.
+This group contains the algorithms for finding shortest paths in digraphs.
 
  - \ref Dijkstra algorithm for finding shortest paths from a source node
@@ -313 +303 @@
 \brief Algorithms for finding maximum flows.
 
-This group describes the algorithms for finding maximum flows and
+This group contains the algorithms for finding maximum flows and
 feasible circulations.
 
 The \e maximum \e flow \e problem is to find a flow of maximum value between
 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
-digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
+digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
 \f$s, t \in V\f$ source and target nodes.
-A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
+A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
 following optimization problem.
 
-\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
-\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
-    \qquad \forall v\in V\setminus\{s,t\} \f]
-\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
+\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
+\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
+    \quad \forall u\in V\setminus\{s,t\} \f]
+\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 
 LEMON contains several algorithms for solving maximum flow problems:
@@ -336 +326 @@
 In most cases the \ref Preflow "Preflow" algorithm provides the
 fastest method for computing a maximum flow. All implementations
-provides functions to also query the minimum cut, which is the dual
-problem of the maximum flow.
-*/
-
-/**
-@defgroup min_cost_flow Minimum Cost Flow Algorithms
+also provide functions to query the minimum cut, which is the dual
+problem of maximum flow.
+
+\ref Circulation is a preflow push-relabel algorithm implemented directly 
+for finding feasible circulations, which is a somewhat different problem,
+but it is strongly related to maximum flow.
+For more information, see \ref Circulation.
+*/
+
+/**
+@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
 @ingroup algs
 
 \brief Algorithms for finding minimum cost flows and circulations.
 
-This group describes the algorithms for finding minimum cost flows and
-circulations.
-
-The \e minimum \e cost \e flow \e problem is to find a feasible flow of
-minimum total cost from a set of supply nodes to a set of demand nodes
-in a network with capacity constraints and arc costs.
-Formally, let \f$G=(V,A)\f$ be a digraph,
-\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
-upper bounds for the flow values on the arcs,
-\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
-on the arcs, and
-\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
-of the nodes.
-A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
-the following optimization problem.
-
-\f[ \min\sum_{a\in A} f(a) cost(a) \f]
-\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
-    supply(v) \qquad \forall v\in V \f]
-\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
-
-LEMON contains several algorithms for solving minimum cost flow problems:
- - \ref CycleCanceling Cycle-canceling algorithms.
- - \ref CapacityScaling Successive shortest path algorithm with optional
+This group contains the algorithms for finding minimum cost flows and
+circulations. For more information about this problem and its dual
+solution see \ref min_cost_flow "Minimum Cost Flow Problem".
+
+LEMON contains several algorithms for this problem.
+ - \ref NetworkSimplex Primal Network Simplex algorithm with various
+   pivot strategies.
+ - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
+   cost scaling.
+ - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    capacity scaling.
- - \ref CostScaling Push-relabel and augment-relabel algorithms based on
-   cost scaling.
- - \ref NetworkSimplex Primal network simplex algorithm with various
-   pivot strategies.
+ - \ref CancelAndTighten The Cancel and Tighten algorithm.
+ - \ref CycleCanceling Cycle-Canceling algorithms.
+
+In general NetworkSimplex is the most efficient implementation,
+but in special cases other algorithms could be faster.
+For example, if the total supply and/or capacities are rather small,
+CapacityScaling is usually the fastest algorithm (without effective scaling).
 */
 
@@ -383 +367 @@
 \brief Algorithms for finding minimum cut in graphs.
 
-This group describes the algorithms for finding minimum cut in graphs.
+This group contains the algorithms for finding minimum cut in graphs.
 
 The \e minimum \e cut \e problem is to find a non-empty and non-complete
@@ -400 +384 @@
 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
   calculating minimum cut in undirected graphs.
-- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
+- \ref GomoryHu "Gomory-Hu tree computation" for calculating
   all-pairs minimum cut in undirected graphs.
 
@@ -408 +392 @@
 
 /**
-@defgroup graph_prop Connectivity and Other Graph Properties
+@defgroup graph_properties Connectivity and Other Graph Properties
 @ingroup algs
 \brief Algorithms for discovering the graph properties
 
-This group describes the algorithms for discovering the graph properties
+This group contains the algorithms for discovering the graph properties
 like connectivity, bipartiteness, euler property, simplicity etc.
 
@@ -424 +408 @@
 \brief Algorithms for planarity checking, embedding and drawing
 
-This group describes the algorithms for planarity checking,
+This group contains the algorithms for planarity checking,
 embedding and drawing.
 
@@ -436 +420 @@
 \brief Algorithms for finding matchings in graphs and bipartite graphs.
 
-This group contains algorithm objects and functions to calculate
+This group contains the algorithms for calculating
 matchings in graphs and bipartite graphs. The general matching problem is
-finding a subset of the arcs which does not shares common endpoints.
+finding a subset of the edges for which each node has at most one incident
+edge.
 
 There are several different algorithms for calculate matchings in
@@ -473 +458 @@
 @defgroup spantree Minimum Spanning Tree Algorithms
 @ingroup algs
-\brief Algorithms for finding a minimum cost spanning tree in a graph.
-
-This group describes the algorithms for finding a minimum cost spanning
-tree in a graph.
+\brief Algorithms for finding minimum cost spanning trees and arborescences.
+
+This group contains the algorithms for finding minimum cost spanning
+trees and arborescences.
 */
 
@@ -484 +469 @@
 \brief Auxiliary algorithms implemented in LEMON.
 
-This group describes some algorithms implemented in LEMON
+This group contains some algorithms implemented in LEMON
 in order to make it easier to implement complex algorithms.
 */
@@ -493 +478 @@
 \brief Approximation algorithms.
 
-This group describes the approximation and heuristic algorithms
+This group contains the approximation and heuristic algorithms
 implemented in LEMON.
 */
@@ -499 +484 @@
 /**
 @defgroup gen_opt_group General Optimization Tools
-\brief This group describes some general optimization frameworks
+\brief This group contains some general optimization frameworks
 implemented in LEMON.
 
-This group describes some general optimization frameworks
+This group contains some general optimization frameworks
 implemented in LEMON.
 */
@@ -511 +496 @@
 \brief Lp and Mip solver interfaces for LEMON.
 
-This group describes Lp and Mip solver interfaces for LEMON. The
+This group contains Lp and Mip solver interfaces for LEMON. The
 various LP solvers could be used in the same manner with this
 interface.
@@ -530 +515 @@
 \brief Metaheuristics for LEMON library.
 
-This group describes some metaheuristic optimization tools.
+This group contains some metaheuristic optimization tools.
 */
 
@@ -545 +530 @@
 \brief Simple basic graph utilities.
 
-This group describes some simple basic graph utilities.
+This group contains some simple basic graph utilities.
 */
 
@@ -553 +538 @@
 \brief Tools for development, debugging and testing.
 
-This group describes several useful tools for development,
+This group contains several useful tools for development,
 debugging and testing.
 */
@@ -562 +547 @@
 \brief Simple tools for measuring the performance of algorithms.
 
-This group describes simple tools for measuring the performance
+This group contains simple tools for measuring the performance
 of algorithms.
 */
@@ -571 +556 @@
 \brief Exceptions defined in LEMON.
 
-This group describes the exceptions defined in LEMON.
+This group contains the exceptions defined in LEMON.
 */
 
@@ -578 +563 @@
 \brief Graph Input-Output methods
 
-This group describes the tools for importing and exporting graphs
+This group contains the tools for importing and exporting graphs
 and graph related data. Now it supports the \ref lgf-format
 "LEMON Graph Format", the \c DIMACS format and the encapsulated
@@ -589 +574 @@
 \brief Reading and writing LEMON Graph Format.
 
-This group describes methods for reading and writing
+This group contains methods for reading and writing
 \ref lgf-format "LEMON Graph Format".
 */
@@ -598 +583 @@
 \brief General \c EPS drawer and graph exporter
 
-This group describes general \c EPS drawing methods and special
+This group contains general \c EPS drawing methods and special
 graph exporting tools.
 */
@@ -622 +607 @@
 \brief Skeleton classes and concept checking classes
 
-This group describes the data/algorithm skeletons and concept checking
+This group contains the data/algorithm skeletons and concept checking
 classes implemented in LEMON.
 
@@ -652 +637 @@
 \brief Skeleton and concept checking classes for graph structures
 
-This group describes the skeletons and concept checking classes of LEMON's
+This group contains the skeletons and concept checking classes of LEMON's
 graph structures and helper classes used to implement these.
 */
@@ -661 +646 @@
 \brief Skeleton and concept checking classes for maps
 
-This group describes the skeletons and concept checking classes of maps.
+This group contains the skeletons and concept checking classes of maps.
 */
 
@@ -672 +657 @@
 the \c demo subdirectory of the source tree.
 
-It order to compile them, use <tt>--enable-demo</tt> configure option when
-build the library.
+In order to compile them, use the <tt>make demo</tt> or the
+<tt>make check</tt> commands.
 */
 

doc/lgf.dox

@@ -64 +64 @@
 \endcode
 
-The \c \@arcs section is very similar to the \c \@nodes section,
-it again starts with a header line describing the names of the maps,
-but the \c "label" map is not obligatory here. The following lines
-describe the arcs. The first two tokens of each line are
-the source and the target node of the arc, respectively, then come the map
+The \c \@arcs section is very similar to the \c \@nodes section, it
+again starts with a header line describing the names of the maps, but
+the \c "label" map is not obligatory here. The following lines
+describe the arcs. The first two tokens of each line are the source
+and the target node of the arc, respectively, then come the map
 values. The source and target tokens must be node labels.
 
@@ -79 +79 @@
 \endcode
 
+If there is no map in the \c \@arcs section at all, then it must be
+indicated by a sole '-' sign in the first line.
+
+\code
+ @arcs
+         -
+ 1   2
+ 1   3
+ 2   3
+\endcode
+
 The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
 also store the edge set of an undirected graph. In such case there is
 a conventional method for store arc maps in the file, if two columns
-has the same caption with \c '+' and \c '-' prefix, then these columns
+have the same caption with \c '+' and \c '-' prefix, then these columns
 can be regarded as the values of an arc map.
 

lemon/CMakeLists.txt

@@ -1 @@
-INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
+INCLUDE_DIRECTORIES(
+  ${PROJECT_SOURCE_DIR}
+  ${PROJECT_BINARY_DIR}
+)
 
-ADD_LIBRARY(lemon
+CONFIGURE_FILE(
+  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
+  ${CMAKE_CURRENT_BINARY_DIR}/config.h
+)
+
+CONFIGURE_FILE(
+  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
+  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
+  @ONLY
+)
+
+SET(LEMON_SOURCES
   arg_parser.cc
   base.cc
   color.cc
-  random.cc)
+  lp_base.cc
+  lp_skeleton.cc
+  random.cc
+  bits/windows.cc
+)
+
+IF(LEMON_HAVE_GLPK)
+  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
+  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
+  IF(WIN32)
+    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
+    INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
+    INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
+  ENDIF()
+ENDIF()
+
+IF(LEMON_HAVE_CPLEX)
+  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
+  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
+ENDIF()
+
+IF(LEMON_HAVE_CLP)
+  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
+  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
+ENDIF()
+
+IF(LEMON_HAVE_CBC)
+  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
+  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
+ENDIF()
+
+ADD_LIBRARY(lemon ${LEMON_SOURCES})
+IF(UNIX)
+  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
+ENDIF()
 
 INSTALL(
   TARGETS lemon
   ARCHIVE DESTINATION lib
-  COMPONENT library)
+  COMPONENT library
+)
 
 INSTALL(
@@ -16 +65 @@
   DESTINATION include/lemon
   COMPONENT headers
-  FILES_MATCHING PATTERN "*.h")
+  FILES_MATCHING PATTERN "*.h"
+)
+
+INSTALL(
+  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
+  DESTINATION include/lemon
+  COMPONENT headers
+)
+
+INSTALL(
+  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
+  DESTINATION lib/pkgconfig
+)
+

lemon/Makefile.am

@@ -1 +1 @@
 EXTRA_DIST += \
         lemon/lemon.pc.in \
-        lemon/CMakeLists.txt
+        lemon/lemon.pc.cmake \
+        lemon/CMakeLists.txt \
+        lemon/config.h.cmake
 
 pkgconfig_DATA += lemon/lemon.pc
@@ -13 +15 @@
         lemon/lp_base.cc \
         lemon/lp_skeleton.cc \
-        lemon/random.cc
+        lemon/random.cc \
+        lemon/bits/windows.cc
 
+nodist_lemon_HEADERS = lemon/config.h   
 
 lemon_libemon_la_CXXFLAGS = \
+        $(AM_CXXFLAGS) \
         $(GLPK_CFLAGS) \
         $(CPLEX_CFLAGS) \
         $(SOPLEX_CXXFLAGS) \
-        $(CLP_CXXFLAGS)
+        $(CLP_CXXFLAGS) \
+        $(CBC_CXXFLAGS)
 
 lemon_libemon_la_LDFLAGS = \
@@ -26 +32 @@
         $(CPLEX_LIBS) \
         $(SOPLEX_LIBS) \
-        $(CLP_LIBS)
+        $(CLP_LIBS) \
+        $(CBC_LIBS)
 
 if HAVE_GLPK
-lemon_libemon_la_SOURCES += lemon/lp_glpk.cc
+lemon_libemon_la_SOURCES += lemon/glpk.cc
 endif
 
 if HAVE_CPLEX
-lemon_libemon_la_SOURCES += lemon/lp_cplex.cc
+lemon_libemon_la_SOURCES += lemon/cplex.cc
 endif
 
 if HAVE_SOPLEX
-lemon_libemon_la_SOURCES += lemon/lp_soplex.cc
+lemon_libemon_la_SOURCES += lemon/soplex.cc
 endif
 
 if HAVE_CLP
-lemon_libemon_la_SOURCES += lemon/lp_clp.cc
+lemon_libemon_la_SOURCES += lemon/clp.cc
+endif
+
+if HAVE_CBC
+lemon_libemon_la_SOURCES += lemon/cbc.cc
 endif
 
@@ -50 +61 @@
         lemon/bfs.h \
         lemon/bin_heap.h \
+        lemon/bucket_heap.h \
+        lemon/cbc.h \
         lemon/circulation.h \
+        lemon/clp.h \
         lemon/color.h \
         lemon/concept_check.h \
+        lemon/connectivity.h \
         lemon/counter.h \
         lemon/core.h \
+        lemon/cplex.h \
         lemon/dfs.h \
         lemon/dijkstra.h \
         lemon/dim2.h \
         lemon/dimacs.h \
+        lemon/edge_set.h \
         lemon/elevator.h \
         lemon/error.h \
+        lemon/euler.h \
+        lemon/fib_heap.h \
         lemon/full_graph.h \
+        lemon/glpk.h \
+        lemon/gomory_hu.h \
         lemon/graph_to_eps.h \
         lemon/grid_graph.h \
@@ -72 +93 @@
         lemon/lp.h \
         lemon/lp_base.h \
-        lemon/lp_clp.h \
-        lemon/lp_cplex.h \
-        lemon/lp_glpk.h \
         lemon/lp_skeleton.h \
-        lemon/lp_soplex.h \
         lemon/maps.h \
+        lemon/matching.h \
         lemon/math.h \
-        lemon/max_matching.h \
+        lemon/min_cost_arborescence.h \
         lemon/nauty_reader.h \
+        lemon/network_simplex.h \
         lemon/path.h \
         lemon/preflow.h \
+        lemon/radix_heap.h \
         lemon/radix_sort.h \
         lemon/random.h \
         lemon/smart_graph.h \
+        lemon/soplex.h \
         lemon/suurballe.h \
         lemon/time_measure.h \
         lemon/tolerance.h \
-        lemon/unionfind.h
+        lemon/unionfind.h \
+        lemon/bits/windows.h
 
 bits_HEADERS += \
         lemon/bits/alteration_notifier.h \
         lemon/bits/array_map.h \
-        lemon/bits/base_extender.h \
         lemon/bits/bezier.h \
         lemon/bits/default_map.h \
+        lemon/bits/edge_set_extender.h \
         lemon/bits/enable_if.h \
         lemon/bits/graph_adaptor_extender.h \

lemon/adaptors.h

@@ -31 +31 @@
 
 #include <lemon/bits/graph_adaptor_extender.h>
+#include <lemon/bits/map_extender.h>
 #include <lemon/tolerance.h>
 
@@ -37 +38 @@
 namespace lemon {
 
-  template<typename _Digraph>
+#ifdef _MSC_VER
+#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED
+#else
+#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED
+#endif
+
+  template<typename DGR>
   class DigraphAdaptorBase {
   public:
-    typedef _Digraph Digraph;
+    typedef DGR Digraph;
     typedef DigraphAdaptorBase Adaptor;
-    typedef Digraph ParentDigraph;
 
   protected:
-    Digraph* _digraph;
+    DGR* _digraph;
     DigraphAdaptorBase() : _digraph(0) { }
-    void setDigraph(Digraph& digraph) { _digraph = &digraph; }
-
-  public:
-    DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
-
-    typedef typename Digraph::Node Node;
-    typedef typename Digraph::Arc Arc;
+    void initialize(DGR& digraph) { _digraph = &digraph; }
+
+  public:
+    DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }
+
+    typedef typename DGR::Node Node;
+    typedef typename DGR::Arc Arc;
 
     void first(Node& i) const { _digraph->first(i); }
@@ -68 +74 @@
     Node target(const Arc& a) const { return _digraph->target(a); }
 
-    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
+    typedef NodeNumTagIndicator<DGR> NodeNumTag;
     int nodeNum() const { return _digraph->nodeNum(); }
 
-    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
+    typedef ArcNumTagIndicator<DGR> ArcNumTag;
     int arcNum() const { return _digraph->arcNum(); }
 
-    typedef FindArcTagIndicator<Digraph> FindArcTag;
+    typedef FindArcTagIndicator<DGR> FindArcTag;
     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
       return _digraph->findArc(u, v, prev);
@@ -96 +102 @@
     int maxArcId() const { return _digraph->maxArcId(); }
 
-    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
+    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
 
-    typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
+    typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
 
-    template <typename _Value>
-    class NodeMap : public Digraph::template NodeMap<_Value> {
+    template <typename V>
+    class NodeMap : public DGR::template NodeMap<V> {
+      typedef typename DGR::template NodeMap<V> Parent;
+
     public:
-
-      typedef typename Digraph::template NodeMap<_Value> Parent;
-
       explicit NodeMap(const Adaptor& adaptor)
         : Parent(*adaptor._digraph) {}
-
-      NodeMap(const Adaptor& adaptor, const _Value& value)
+      NodeMap(const Adaptor& adaptor, const V& value)
         : Parent(*adaptor._digraph, value) { }
 
@@ -127 +131 @@
     };
 
-    template <typename _Value>
-    class ArcMap : public Digraph::template ArcMap<_Value> {
+    template <typename V>
+    class ArcMap : public DGR::template ArcMap<V> {
+      typedef typename DGR::template ArcMap<V> Parent;
+
     public:
-
-      typedef typename Digraph::template ArcMap<_Value> Parent;
-
-      explicit ArcMap(const Adaptor& adaptor)
+      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
         : Parent(*adaptor._digraph) {}
-
-      ArcMap(const Adaptor& adaptor, const _Value& value)
+      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
         : Parent(*adaptor._digraph, value) {}
 
@@ -154 +156 @@
   };
 
-  template<typename _Graph>
+  template<typename GR>
   class GraphAdaptorBase {
   public:
-    typedef _Graph Graph;
-    typedef Graph ParentGraph;
+    typedef GR Graph;
 
   protected:
-    Graph* _graph;
+    GR* _graph;
 
     GraphAdaptorBase() : _graph(0) {}
 
-    void setGraph(Graph& graph) { _graph = &graph; }
-
-  public:
-    GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
-
-    typedef typename Graph::Node Node;
-    typedef typename Graph::Arc Arc;
-    typedef typename Graph::Edge Edge;
+    void initialize(GR& graph) { _graph = &graph; }
+
+  public:
+    GraphAdaptorBase(GR& graph) : _graph(&graph) {}
+
+    typedef typename GR::Node Node;
+    typedef typename GR::Arc Arc;
+    typedef typename GR::Edge Edge;
 
     void first(Node& i) const { _graph->first(i); }
@@ -240 +241 @@
     int maxEdgeId() const { return _graph->maxEdgeId(); }
 
-    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
     NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 
-    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
+    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 
-    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
+    typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
     EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
 
-    template <typename _Value>
-    class NodeMap : public Graph::template NodeMap<_Value> {
+    template <typename V>
+    class NodeMap : public GR::template NodeMap<V> {
+      typedef typename GR::template NodeMap<V> Parent;
+
     public:
-      typedef typename Graph::template NodeMap<_Value> Parent;
-      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
+      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
         : Parent(*adapter._graph) {}
-      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
+      NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
         : Parent(*adapter._graph, value) {}
 
@@ -271 +273 @@
     };
 
-    template <typename _Value>
-    class ArcMap : public Graph::template ArcMap<_Value> {
+    template <typename V>
+    class ArcMap : public GR::template ArcMap<V> {
+      typedef typename GR::template ArcMap<V> Parent;
+
     public:
-      typedef typename Graph::template ArcMap<_Value> Parent;
-      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
+      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
         : Parent(*adapter._graph) {}
-      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
+      ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
         : Parent(*adapter._graph, value) {}
 
@@ -292 +295 @@
     };
 
-    template <typename _Value>
-    class EdgeMap : public Graph::template EdgeMap<_Value> {
+    template <typename V>
+    class EdgeMap : public GR::template EdgeMap<V> {
+      typedef typename GR::template EdgeMap<V> Parent;
+
     public:
-      typedef typename Graph::template EdgeMap<_Value> Parent;
-      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
+      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
         : Parent(*adapter._graph) {}
-      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
+      EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
         : Parent(*adapter._graph, value) {}
 
@@ -315 +319 @@
   };
 
-  template <typename _Digraph>
-  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
-  public:
-    typedef _Digraph Digraph;
-    typedef DigraphAdaptorBase<_Digraph> Parent;
+  template <typename DGR>
+  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
+    typedef DigraphAdaptorBase<DGR> Parent;
+  public:
+    typedef DGR Digraph;
   protected:
     ReverseDigraphBase() : Parent() { }
@@ -337 +341 @@
     Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
 
-    typedef FindArcTagIndicator<Digraph> FindArcTag;
+    typedef FindArcTagIndicator<DGR> FindArcTag;
     Arc findArc(const Node& u, const Node& v,
                 const Arc& prev = INVALID) const {
@@ -357 +361 @@
   /// parameter is set to be \c const.
   ///
-  /// \tparam GR The type of the adapted digraph.
+  /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   /// It can also be specified to be \c const.
@@ -363 +367 @@
   /// \note The \c Node and \c Arc types of this adaptor and the adapted
   /// digraph are convertible to each other.
-  template<typename GR>
+  template<typename DGR>
 #ifdef DOXYGEN
   class ReverseDigraph {
 #else
   class ReverseDigraph :
-    public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {
+    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
 #endif
+    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
   public:
     /// The type of the adapted digraph.
-    typedef GR Digraph;
-    typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;
+    typedef DGR Digraph;
   protected:
     ReverseDigraph() { }
@@ -381 +385 @@
     ///
     /// Creates a reverse digraph adaptor for the given digraph.
-    explicit ReverseDigraph(Digraph& digraph) {
-      Parent::setDigraph(digraph);
+    explicit ReverseDigraph(DGR& digraph) {
+      Parent::initialize(digraph);
     }
   };
@@ -391 +395 @@
   /// \ingroup graph_adaptors
   /// \relates ReverseDigraph
-  template<typename GR>
-  ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {
-    return ReverseDigraph<const GR>(digraph);
+  template<typename DGR>
+  ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
+    return ReverseDigraph<const DGR>(digraph);
   }
 
 
-  template <typename _Digraph, typename _NodeFilterMap,
-            typename _ArcFilterMap, bool _checked = true>
-  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
-  public:
-    typedef _Digraph Digraph;
-    typedef _NodeFilterMap NodeFilterMap;
-    typedef _ArcFilterMap ArcFilterMap;
+  template <typename DGR, typename NF, typename AF, bool ch = true>
+  class SubDigraphBase : public DigraphAdaptorBase<DGR> {
+    typedef DigraphAdaptorBase<DGR> Parent;
+  public:
+    typedef DGR Digraph;
+    typedef NF NodeFilterMap;
+    typedef AF ArcFilterMap;
 
     typedef SubDigraphBase Adaptor;
-    typedef DigraphAdaptorBase<_Digraph> Parent;
   protected:
-    NodeFilterMap* _node_filter;
-    ArcFilterMap* _arc_filter;
+    NF* _node_filter;
+    AF* _arc_filter;
     SubDigraphBase()
       : Parent(), _node_filter(0), _arc_filter(0) { }
 
-    void setNodeFilterMap(NodeFilterMap& node_filter) {
+    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
+      Parent::initialize(digraph);
       _node_filter = &node_filter;
-    }
-    void setArcFilterMap(ArcFilterMap& arc_filter) {
-      _arc_filter = &arc_filter;
+      _arc_filter = &arc_filter;      
     }
 
@@ -488 +490 @@
     typedef False ArcNumTag;
 
-    typedef FindArcTagIndicator<Digraph> FindArcTag;
+    typedef FindArcTagIndicator<DGR> FindArcTag;
     Arc findArc(const Node& source, const Node& target,
                 const Arc& prev = INVALID) const {
@@ -501 +503 @@
     }
 
-    template <typename _Value>
-    class NodeMap : public SubMapExtender<Adaptor,
-      typename Parent::template NodeMap<_Value> > {
+  public:
+
+    template <typename V>
+    class NodeMap 
+      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
+              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
+      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
+        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, typename Parent::
-                             template NodeMap<Value> > MapParent;
-
-      NodeMap(const Adaptor& adaptor)
-        : MapParent(adaptor) {}
-      NodeMap(const Adaptor& adaptor, const Value& value)
-        : MapParent(adaptor, value) {}
+      typedef V Value;
+
+      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
+        : Parent(adaptor) {}
+      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
+        : Parent(adaptor, value) {}
 
     private:
@@ -521 +527 @@
       template <typename CMap>
       NodeMap& operator=(const CMap& cmap) {
-        MapParent::operator=(cmap);
+        Parent::operator=(cmap);
         return *this;
       }
     };
 
-    template <typename _Value>
-    class ArcMap : public SubMapExtender<Adaptor,
-      typename Parent::template ArcMap<_Value> > {
+    template <typename V>
+    class ArcMap 
+      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
+              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
+      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
+        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, typename Parent::
-                             template ArcMap<Value> > MapParent;
-
-      ArcMap(const Adaptor& adaptor)
-        : MapParent(adaptor) {}
-      ArcMap(const Adaptor& adaptor, const Value& value)
-        : MapParent(adaptor, value) {}
+      typedef V Value;
+
+      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
+        : Parent(adaptor) {}
+      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
+        : Parent(adaptor, value) {}
 
     private:
@@ -546 +554 @@
       template <typename CMap>
       ArcMap& operator=(const CMap& cmap) {
-        MapParent::operator=(cmap);
+        Parent::operator=(cmap);
         return *this;
       }
@@ -553 +561 @@
   };
 
-  template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
-  class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
-    : public DigraphAdaptorBase<_Digraph> {
-  public:
-    typedef _Digraph Digraph;
-    typedef _NodeFilterMap NodeFilterMap;
-    typedef _ArcFilterMap ArcFilterMap;
+  template <typename DGR, typename NF, typename AF>
+  class SubDigraphBase<DGR, NF, AF, false>
+    : public DigraphAdaptorBase<DGR> {
+    typedef DigraphAdaptorBase<DGR> Parent;
+  public:
+    typedef DGR Digraph;
+    typedef NF NodeFilterMap;
+    typedef AF ArcFilterMap;
 
     typedef SubDigraphBase Adaptor;
-    typedef DigraphAdaptorBase<Digraph> Parent;
   protected:
-    NodeFilterMap* _node_filter;
-    ArcFilterMap* _arc_filter;
+    NF* _node_filter;
+    AF* _arc_filter;
     SubDigraphBase()
       : Parent(), _node_filter(0), _arc_filter(0) { }
 
-    void setNodeFilterMap(NodeFilterMap& node_filter) {
+    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
+      Parent::initialize(digraph);
       _node_filter = &node_filter;
-    }
-    void setArcFilterMap(ArcFilterMap& arc_filter) {
-      _arc_filter = &arc_filter;
+      _arc_filter = &arc_filter;      
     }
 
@@ -628 +635 @@
     typedef False ArcNumTag;
 
-    typedef FindArcTagIndicator<Digraph> FindArcTag;
+    typedef FindArcTagIndicator<DGR> FindArcTag;
     Arc findArc(const Node& source, const Node& target,
                 const Arc& prev = INVALID) const {
@@ -641 +648 @@
     }
 
-    template <typename _Value>
-    class NodeMap : public SubMapExtender<Adaptor,
-      typename Parent::template NodeMap<_Value> > {
+    template <typename V>
+    class NodeMap 
+      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
+          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
+      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
+        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, typename Parent::
-                             template NodeMap<Value> > MapParent;
-
-      NodeMap(const Adaptor& adaptor)
-        : MapParent(adaptor) {}
-      NodeMap(const Adaptor& adaptor, const Value& value)
-        : MapParent(adaptor, value) {}
+      typedef V Value;
+
+      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
+        : Parent(adaptor) {}
+      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
+        : Parent(adaptor, value) {}
 
     private:
@@ -661 +670 @@
       template <typename CMap>
       NodeMap& operator=(const CMap& cmap) {
-        MapParent::operator=(cmap);
+        Parent::operator=(cmap);
         return *this;
       }
     };
 
-    template <typename _Value>
-    class ArcMap : public SubMapExtender<Adaptor,
-      typename Parent::template ArcMap<_Value> > {
+    template <typename V>
+    class ArcMap 
+      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
+          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
+      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
+        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, typename Parent::
-                             template ArcMap<Value> > MapParent;
-
-      ArcMap(const Adaptor& adaptor)
-        : MapParent(adaptor) {}
-      ArcMap(const Adaptor& adaptor, const Value& value)
-        : MapParent(adaptor, value) {}
+      typedef V Value;
+
+      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
+        : Parent(adaptor) {}
+      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
+        : Parent(adaptor, value) {}
 
     private:
@@ -686 +697 @@
       template <typename CMap>
       ArcMap& operator=(const CMap& cmap) {
-        MapParent::operator=(cmap);
+        Parent::operator=(cmap);
         return *this;
       }
@@ -709 +720 @@
   /// parameter is set to be \c const.
   ///
-  /// \tparam GR The type of the adapted digraph.
+  /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   /// It can also be specified to be \c const.
@@ -715 +726 @@
   /// It must be a \c bool (or convertible) node map of the
   /// adapted digraph. The default type is
-  /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>".
+  /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".
   /// \tparam AF The type of the arc filter map.
   /// It must be \c bool (or convertible) arc map of the
   /// adapted digraph. The default type is
-  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
+  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
   ///
   /// \note The \c Node and \c Arc types of this adaptor and the adapted
@@ -727 +738 @@
   /// \see FilterArcs
 #ifdef DOXYGEN
-  template<typename GR, typename NF, typename AF>
+  template<typename DGR, typename NF, typename AF>
   class SubDigraph {
 #else
-  template<typename GR,
-           typename NF = typename GR::template NodeMap<bool>,
-           typename AF = typename GR::template ArcMap<bool> >
+  template<typename DGR,
+           typename NF = typename DGR::template NodeMap<bool>,
+           typename AF = typename DGR::template ArcMap<bool> >
   class SubDigraph :
-    public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {
+    public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {
 #endif
   public:
     /// The type of the adapted digraph.
-    typedef GR Digraph;
+    typedef DGR Digraph;
     /// The type of the node filter map.
     typedef NF NodeFilterMap;
@@ -744 +755 @@
     typedef AF ArcFilterMap;
 
-    typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> >
+    typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >
       Parent;
 
@@ -758 +769 @@
     /// Creates a subdigraph for the given digraph with the
     /// given node and arc filter maps.
-    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
-               ArcFilterMap& arc_filter) {
-      setDigraph(digraph);
-      setNodeFilterMap(node_filter);
-      setArcFilterMap(arc_filter);
+    SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
+      Parent::initialize(digraph, node_filter, arc_filter);
     }
 
@@ -824 +832 @@
   /// \ingroup graph_adaptors
   /// \relates SubDigraph
-  template<typename GR, typename NF, typename AF>
-  SubDigraph<const GR, NF, AF>
-  subDigraph(const GR& digraph,
-             NF& node_filter_map, AF& arc_filter_map) {
-    return SubDigraph<const GR, NF, AF>
-      (digraph, node_filter_map, arc_filter_map);
+  template<typename DGR, typename NF, typename AF>
+  SubDigraph<const DGR, NF, AF>
+  subDigraph(const DGR& digraph,
+             NF& node_filter, AF& arc_filter) {
+    return SubDigraph<const DGR, NF, AF>
+      (digraph, node_filter, arc_filter);
   }
 
-  template<typename GR, typename NF, typename AF>
-  SubDigraph<const GR, const NF, AF>
-  subDigraph(const GR& digraph,
-             const NF& node_filter_map, AF& arc_filter_map) {
-    return SubDigraph<const GR, const NF, AF>
-      (digraph, node_filter_map, arc_filter_map);
+  template<typename DGR, typename NF, typename AF>
+  SubDigraph<const DGR, const NF, AF>
+  subDigraph(const DGR& digraph,
+             const NF& node_filter, AF& arc_filter) {
+    return SubDigraph<const DGR, const NF, AF>
+      (digraph, node_filter, arc_filter);
   }
 
-  template<typename GR, typename NF, typename AF>
-  SubDigraph<const GR, NF, const AF>
-  subDigraph(const GR& digraph,
-             NF& node_filter_map, const AF& arc_filter_map) {
-    return SubDigraph<const GR, NF, const AF>
-      (digraph, node_filter_map, arc_filter_map);
+  template<typename DGR, typename NF, typename AF>
+  SubDigraph<const DGR, NF, const AF>
+  subDigraph(const DGR& digraph,
+             NF& node_filter, const AF& arc_filter) {
+    return SubDigraph<const DGR, NF, const AF>
+      (digraph, node_filter, arc_filter);
   }
 
-  template<typename GR, typename NF, typename AF>
-  SubDigraph<const GR, const NF, const AF>
-  subDigraph(const GR& digraph,
-             const NF& node_filter_map, const AF& arc_filter_map) {
-    return SubDigraph<const GR, const NF, const AF>
-      (digraph, node_filter_map, arc_filter_map);
+  template<typename DGR, typename NF, typename AF>
+  SubDigraph<const DGR, const NF, const AF>
+  subDigraph(const DGR& digraph,
+             const NF& node_filter, const AF& arc_filter) {
+    return SubDigraph<const DGR, const NF, const AF>
+      (digraph, node_filter, arc_filter);
   }
 
 
-  template <typename _Graph, typename _NodeFilterMap,
-            typename _EdgeFilterMap, bool _checked = true>
-  class SubGraphBase : public GraphAdaptorBase<_Graph> {
-  public:
-    typedef _Graph Graph;
-    typedef _NodeFilterMap NodeFilterMap;
-    typedef _EdgeFilterMap EdgeFilterMap;
+  template <typename GR, typename NF, typename EF, bool ch = true>
+  class SubGraphBase : public GraphAdaptorBase<GR> {
+    typedef GraphAdaptorBase<GR> Parent;
+  public:
+    typedef GR Graph;
+    typedef NF NodeFilterMap;
+    typedef EF EdgeFilterMap;
 
     typedef SubGraphBase Adaptor;
-    typedef GraphAdaptorBase<_Graph> Parent;
   protected:
 
-    NodeFilterMap* _node_filter_map;
-    EdgeFilterMap* _edge_filter_map;
+    NF* _node_filter;
+    EF* _edge_filter;
 
     SubGraphBase()
-      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
-
-    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
-      _node_filter_map=&node_filter_map;
-    }
-    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
-      _edge_filter_map=&edge_filter_map;
+      : Parent(), _node_filter(0), _edge_filter(0) { }
+
+    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
+      Parent::initialize(graph);
+      _node_filter = &node_filter;
+      _edge_filter = &edge_filter;
     }
 
@@ -890 +896 @@
     void first(Node& i) const {
       Parent::first(i);
-      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
     }
 
     void first(Arc& i) const {
       Parent::first(i);
-      while (i!=INVALID && (!(*_edge_filter_map)[i]
-                            || !(*_node_filter_map)[Parent::source(i)]
-                            || !(*_node_filter_map)[Parent::target(i)]))
+      while (i!=INVALID && (!(*_edge_filter)[i]
+                            || !(*_node_filter)[Parent::source(i)]
+                            || !(*_node_filter)[Parent::target(i)]))
         Parent::next(i);
     }
@@ -903 +909 @@
     void first(Edge& i) const {
       Parent::first(i);
-      while (i!=INVALID && (!(*_edge_filter_map)[i]
-                            || !(*_node_filter_map)[Parent::u(i)]
-                            || !(*_node_filter_map)[Parent::v(i)]))
+      while (i!=INVALID && (!(*_edge_filter)[i]
+                            || !(*_node_filter)[Parent::u(i)]
+                            || !(*_node_filter)[Parent::v(i)]))
         Parent::next(i);
     }
@@ -911 +917 @@
     void firstIn(Arc& i, const Node& n) const {
       Parent::firstIn(i, n);
-      while (i!=INVALID && (!(*_edge_filter_map)[i]
-                            || !(*_node_filter_map)[Parent::source(i)]))
+      while (i!=INVALID && (!(*_edge_filter)[i]
+                            || !(*_node_filter)[Parent::source(i)]))
         Parent::nextIn(i);
     }
@@ -918 +924 @@
     void firstOut(Arc& i, const Node& n) const {
       Parent::firstOut(i, n);
-      while (i!=INVALID && (!(*_edge_filter_map)[i]
-                            || !(*_node_filter_map)[Parent::target(i)]))
+      while (i!=INVALID && (!(*_edge_filter)[i]
+                            || !(*_node_filter)[Parent::target(i)]))
         Parent::nextOut(i);
     }
@@ -925 +931 @@
     void firstInc(Edge& i, bool& d, const Node& n) const {
       Parent::firstInc(i, d, n);
-      while (i!=INVALID && (!(*_edge_filter_map)[i]
-                            || !(*_node_filter_map)[Parent::u(i)]
-                            || !(*_node_filter_map)[Parent::v(i)]))
+      while (i!=INVALID && (!(*_edge_filter)[i]
+                            || !(*_node_filter)[Parent::u(i)]
+                            || !(*_node_filter)[Parent::v(i)]))
         Parent::nextInc(i, d);
     }
@@ -933 +939 @@
     void next(Node& i) const {
       Parent::next(i);
-      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
     }
 
     void next(Arc& i) const {
       Parent::next(i);
-      while (i!=INVALID && (!(*_edge_filter_map)[i]
-                            || !(*_node_filter_map)[Parent::source(i)]
-                            || !(*_node_filter_map)[Parent::target(i)]))
+      while (i!=INVALID && (!(*_edge_filter)[i]
+                            || !(*_node_filter)[Parent::source(i)]
+                            || !(*_node_filter)[Parent::target(i)]))
         Parent::next(i);
     }
@@ -946 +952 @@
     void next(Edge& i) const {
       Parent::next(i);
-      while (i!=INVALID && (!(*_edge_filter_map)[i]
-                            || !(*_node_filter_map)[Parent::u(i)]
-                            || !(*_node_filter_map)[Parent::v(i)]))
+      while (i!=INVALID && (!(*_edge_filter)[i]
+                            || !(*_node_filter)[Parent::u(i)]
+                            || !(*_node_filter)[Parent::v(i)]))
         Parent::next(i);
     }
@@ -954 +960 @@
     void nextIn(Arc& i) const {
       Parent::nextIn(i);
-      while (i!=INVALID && (!(*_edge_filter_map)[i]
-                            || !(*_node_filter_map)[Parent::source(i)]))
+      while (i!=INVALID && (!(*_edge_filter)[i]
+                            || !(*_node_filter)[Parent::source(i)]))
         Parent::nextIn(i);
     }
@@ -961 +967 @@
     void nextOut(Arc& i) const {
       Parent::nextOut(i);
-      while (i!=INVALID && (!(*_edge_filter_map)[i]
-                            || !(*_node_filter_map)[Parent::target(i)]))
+      while (i!=INVALID && (!(*_edge_filter)[i]
+                            || !(*_node_filter)[Parent::target(i)]))
         Parent::nextOut(i);
     }
@@ -968 +974 @@
     void nextInc(Edge& i, bool& d) const {
       Parent::nextInc(i, d);
-      while (i!=INVALID && (!(*_edge_filter_map)[i]
-                            || !(*_node_filter_map)[Parent::u(i)]
-                            || !(*_node_filter_map)[Parent::v(i)]))
+      while (i!=INVALID && (!(*_edge_filter)[i]
+                            || !(*_node_filter)[Parent::u(i)]
+                            || !(*_node_filter)[Parent::v(i)]))
         Parent::nextInc(i, d);
     }
 
-    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
-    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
-
-    bool status(const Node& n) const { return (*_node_filter_map)[n]; }
-    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
+    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
+    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
+
+    bool status(const Node& n) const { return (*_node_filter)[n]; }
+    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
 
     typedef False NodeNumTag;
@@ -987 +993 @@
     Arc findArc(const Node& u, const Node& v,
                 const Arc& prev = INVALID) const {
-      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
+      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
         return INVALID;
       }
       Arc arc = Parent::findArc(u, v, prev);
-      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
+      while (arc != INVALID && !(*_edge_filter)[arc]) {
         arc = Parent::findArc(u, v, arc);
       }
@@ -1000 +1006 @@
     Edge findEdge(const Node& u, const Node& v,
                   const Edge& prev = INVALID) const {
-      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
+      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
         return INVALID;
       }
       Edge edge = Parent::findEdge(u, v, prev);
-      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
+      while (edge != INVALID && !(*_edge_filter)[edge]) {
         edge = Parent::findEdge(u, v, edge);
       }
@@ -1010 +1016 @@
     }
 
-    template <typename _Value>
-    class NodeMap : public SubMapExtender<Adaptor,
-      typename Parent::template NodeMap<_Value> > {
+    template <typename V>
+    class NodeMap 
+      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
+          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
+        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, typename Parent::
-                             template NodeMap<Value> > MapParent;
-
-      NodeMap(const Adaptor& adaptor)
-        : MapParent(adaptor) {}
-      NodeMap(const Adaptor& adaptor, const Value& value)
-        : MapParent(adaptor, value) {}
+      typedef V Value;
+
+      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
+        : Parent(adaptor) {}
+      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
+        : Parent(adaptor, value) {}
 
     private:
@@ -1030 +1038 @@
       template <typename CMap>
       NodeMap& operator=(const CMap& cmap) {
-        MapParent::operator=(cmap);
+        Parent::operator=(cmap);
         return *this;
       }
     };
 
-    template <typename _Value>
-    class ArcMap : public SubMapExtender<Adaptor,
-      typename Parent::template ArcMap<_Value> > {
+    template <typename V>
+    class ArcMap 
+      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
+          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
+        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, typename Parent::
-                             template ArcMap<Value> > MapParent;
-
-      ArcMap(const Adaptor& adaptor)
-        : MapParent(adaptor) {}
-      ArcMap(const Adaptor& adaptor, const Value& value)
-        : MapParent(adaptor, value) {}
+      typedef V Value;
+
+      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
+        : Parent(adaptor) {}
+      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
+        : Parent(adaptor, value) {}
 
     private:
@@ -1055 +1065 @@
       template <typename CMap>
       ArcMap& operator=(const CMap& cmap) {
-        MapParent::operator=(cmap);
+        Parent::operator=(cmap);
         return *this;
       }
     };
 
-    template <typename _Value>
-    class EdgeMap : public SubMapExtender<Adaptor,
-      typename Parent::template EdgeMap<_Value> > {
+    template <typename V>
+    class EdgeMap 
+      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
+        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
+        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, typename Parent::
-                             template EdgeMap<Value> > MapParent;
-
-      EdgeMap(const Adaptor& adaptor)
-        : MapParent(adaptor) {}
-
-      EdgeMap(const Adaptor& adaptor, const Value& value)
-        : MapParent(adaptor, value) {}
+      typedef V Value;
+
+      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
+        : Parent(adaptor) {}
+
+      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
+        : Parent(adaptor, value) {}
 
     private:
@@ -1081 +1093 @@
       template <typename CMap>
       EdgeMap& operator=(const CMap& cmap) {
-        MapParent::operator=(cmap);
+        Parent::operator=(cmap);
         return *this;
       }
@@ -1088 +1100 @@
   };
 
-  template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
-  class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
-    : public GraphAdaptorBase<_Graph> {
-  public:
-    typedef _Graph Graph;
-    typedef _NodeFilterMap NodeFilterMap;
-    typedef _EdgeFilterMap EdgeFilterMap;
+  template <typename GR, typename NF, typename EF>
+  class SubGraphBase<GR, NF, EF, false>
+    : public GraphAdaptorBase<GR> {
+    typedef GraphAdaptorBase<GR> Parent;
+  public:
+    typedef GR Graph;
+    typedef NF NodeFilterMap;
+    typedef EF EdgeFilterMap;
 
     typedef SubGraphBase Adaptor;
-    typedef GraphAdaptorBase<_Graph> Parent;
   protected:
-    NodeFilterMap* _node_filter_map;
-    EdgeFilterMap* _edge_filter_map;
-    SubGraphBase() : Parent(),
-                     _node_filter_map(0), _edge_filter_map(0) { }
-
-    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
-      _node_filter_map=&node_filter_map;
-    }
-    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
-      _edge_filter_map=&edge_filter_map;
+    NF* _node_filter;
+    EF* _edge_filter;
+    SubGraphBase() 
+          : Parent(), _node_filter(0), _edge_filter(0) { }
+
+    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
+      Parent::initialize(graph);
+      _node_filter = &node_filter;
+      _edge_filter = &edge_filter;
     }
 
@@ -1119 +1130 @@
     void first(Node& i) const {
       Parent::first(i);
-      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
     }
 
     void first(Arc& i) const {
       Parent::first(i);
-      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
     }
 
     void first(Edge& i) const {
       Parent::first(i);
-      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
     }
 
     void firstIn(Arc& i, const Node& n) const {
       Parent::firstIn(i, n);
-      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
+      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
     }
 
     void firstOut(Arc& i, const Node& n) const {
       Parent::firstOut(i, n);
-      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
+      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
     }
 
     void firstInc(Edge& i, bool& d, const Node& n) const {
       Parent::firstInc(i, d, n);
-      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
+      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
     }
 
     void next(Node& i) const {
       Parent::next(i);
-      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
     }
     void next(Arc& i) const {
       Parent::next(i);
-      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
     }
     void next(Edge& i) const {
       Parent::next(i);
-      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
     }
     void nextIn(Arc& i) const {
       Parent::nextIn(i);
-      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
+      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
     }
 
     void nextOut(Arc& i) const {
       Parent::nextOut(i);
-      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
+      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
     }
     void nextInc(Edge& i, bool& d) const {
       Parent::nextInc(i, d);
-      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
-    }
-
-    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
-    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
-
-    bool status(const Node& n) const { return (*_node_filter_map)[n]; }
-    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
+      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
+    }
+
+    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
+    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
+
+    bool status(const Node& n) const { return (*_node_filter)[n]; }
+    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
 
     typedef False NodeNumTag;
@@ -1187 +1198 @@
                 const Arc& prev = INVALID) const {
       Arc arc = Parent::findArc(u, v, prev);
-      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
+      while (arc != INVALID && !(*_edge_filter)[arc]) {
         arc = Parent::findArc(u, v, arc);
       }
@@ -1197 +1208 @@
                   const Edge& prev = INVALID) const {
       Edge edge = Parent::findEdge(u, v, prev);
-      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
+      while (edge != INVALID && !(*_edge_filter)[edge]) {
         edge = Parent::findEdge(u, v, edge);
       }
@@ -1203 +1214 @@
     }
 
-    template <typename _Value>
-    class NodeMap : public SubMapExtender<Adaptor,
-      typename Parent::template NodeMap<_Value> > {
+    template <typename V>
+    class NodeMap 
+      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
+          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
+        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, typename Parent::
-                             template NodeMap<Value> > MapParent;
-
-      NodeMap(const Adaptor& adaptor)
-        : MapParent(adaptor) {}
-      NodeMap(const Adaptor& adaptor, const Value& value)
-        : MapParent(adaptor, value) {}
+      typedef V Value;
+
+      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
+        : Parent(adaptor) {}
+      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
+        : Parent(adaptor, value) {}
 
     private:
@@ -1223 +1236 @@
       template <typename CMap>
       NodeMap& operator=(const CMap& cmap) {
-        MapParent::operator=(cmap);
+        Parent::operator=(cmap);
         return *this;
       }
     };
 
-    template <typename _Value>
-    class ArcMap : public SubMapExtender<Adaptor,
-      typename Parent::template ArcMap<_Value> > {
+    template <typename V>
+    class ArcMap 
+      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
+          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
+        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, typename Parent::
-                             template ArcMap<Value> > MapParent;
-
-      ArcMap(const Adaptor& adaptor)
-        : MapParent(adaptor) {}
-      ArcMap(const Adaptor& adaptor, const Value& value)
-        : MapParent(adaptor, value) {}
+      typedef V Value;
+
+      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
+        : Parent(adaptor) {}
+      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
+        : Parent(adaptor, value) {}
 
     private:
@@ -1248 +1263 @@
       template <typename CMap>
       ArcMap& operator=(const CMap& cmap) {
-        MapParent::operator=(cmap);
+        Parent::operator=(cmap);
         return *this;
       }
     };
 
-    template <typename _Value>
-    class EdgeMap : public SubMapExtender<Adaptor,
-      typename Parent::template EdgeMap<_Value> > {
+    template <typename V>
+    class EdgeMap 
+      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
+        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
+        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, typename Parent::
-                             template EdgeMap<Value> > MapParent;
-
-      EdgeMap(const Adaptor& adaptor)
-        : MapParent(adaptor) {}
-
-      EdgeMap(const Adaptor& adaptor, const _Value& value)
-        : MapParent(adaptor, value) {}
+      typedef V Value;
+
+      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
+        : Parent(adaptor) {}
+
+      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
+        : Parent(adaptor, value) {}
 
     private:
@@ -1274 +1291 @@
       template <typename CMap>
       EdgeMap& operator=(const CMap& cmap) {
-        MapParent::operator=(cmap);
+        Parent::operator=(cmap);
         return *this;
       }
@@ -1333 +1350 @@
     typedef EF EdgeFilterMap;
 
-    typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> >
+    typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> >
       Parent;
 
@@ -1347 +1364 @@
     /// Creates a subgraph for the given graph with the given node
     /// and edge filter maps.
-    SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
-             EdgeFilterMap& edge_filter_map) {
-      setGraph(graph);
-      setNodeFilterMap(node_filter_map);
-      setEdgeFilterMap(edge_filter_map);
+    SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
+      initialize(graph, node_filter, edge_filter);
     }
 
@@ -1415 +1429 @@
   template<typename GR, typename NF, typename EF>
   SubGraph<const GR, NF, EF>
-  subGraph(const GR& graph,
-           NF& node_filter_map, EF& edge_filter_map) {
+  subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {
     return SubGraph<const GR, NF, EF>
-      (graph, node_filter_map, edge_filter_map);
+      (graph, node_filter, edge_filter);
   }
 
   template<typename GR, typename NF, typename EF>
   SubGraph<const GR, const NF, EF>
-  subGraph(const GR& graph,
-           const NF& node_filter_map, EF& edge_filter_map) {
+  subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {
     return SubGraph<const GR, const NF, EF>
-      (graph, node_filter_map, edge_filter_map);
+      (graph, node_filter, edge_filter);
   }
 
   template<typename GR, typename NF, typename EF>
   SubGraph<const GR, NF, const EF>
-  subGraph(const GR& graph,
-           NF& node_filter_map, const EF& edge_filter_map) {
+  subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {
     return SubGraph<const GR, NF, const EF>
-      (graph, node_filter_map, edge_filter_map);
+      (graph, node_filter, edge_filter);
   }
 
   template<typename GR, typename NF, typename EF>
   SubGraph<const GR, const NF, const EF>
-  subGraph(const GR& graph,
-           const NF& node_filter_map, const EF& edge_filter_map) {
+  subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {
     return SubGraph<const GR, const NF, const EF>
-      (graph, node_filter_map, edge_filter_map);
+      (graph, node_filter, edge_filter);
   }
 
@@ -1482 +1492 @@
   class FilterNodes :
     public DigraphAdaptorExtender<
-      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {
+      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
+                     true> > {
 #endif
+    typedef DigraphAdaptorExtender<
+      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
+                     true> > Parent;
+
   public:
 
@@ -1489 +1504 @@
     typedef NF NodeFilterMap;
 
-    typedef DigraphAdaptorExtender<
-      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >
-      Parent;
-
     typedef typename Parent::Node Node;
 
   protected:
-    ConstMap<typename Digraph::Arc, bool> const_true_map;
-
-    FilterNodes() : const_true_map(true) {
-      Parent::setArcFilterMap(const_true_map);
-    }
+    ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
+
+    FilterNodes() : const_true_map() {}
 
   public:
@@ -1508 +1517 @@
     /// Creates a subgraph for the given digraph or graph with the
     /// given node filter map.
-    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
-      Parent(), const_true_map(true)
+    FilterNodes(GR& graph, NF& node_filter) 
+      : Parent(), const_true_map()
     {
-      Parent::setDigraph(graph);
-      Parent::setNodeFilterMap(node_filter);
-      Parent::setArcFilterMap(const_true_map);
+      Parent::initialize(graph, node_filter, const_true_map);
     }
 
@@ -1548 +1555 @@
                     typename enable_if<UndirectedTagIndicator<GR> >::type> :
     public GraphAdaptorExtender<
-      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {
-
-  public:
+      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
+                   true> > {
+
+    typedef GraphAdaptorExtender<
+      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
+                   true> > Parent;
+
+  public:
+
     typedef GR Graph;
     typedef NF NodeFilterMap;
-    typedef GraphAdaptorExtender<
-      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >
-      Parent;
 
     typedef typename Parent::Node Node;
+
   protected:
-    ConstMap<typename Graph::Edge, bool> const_true_map;
-
-    FilterNodes() : const_true_map(true) {
-      Parent::setEdgeFilterMap(const_true_map);
-    }
-
-  public:
-
-    FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
-      Parent(), const_true_map(true) {
-      Parent::setGraph(_graph);
-      Parent::setNodeFilterMap(node_filter_map);
-      Parent::setEdgeFilterMap(const_true_map);
+    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
+
+    FilterNodes() : const_true_map() {}
+
+  public:
+
+    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
+      Parent(), const_true_map() {
+      Parent::initialize(graph, node_filter, const_true_map);
     }
 
@@ -1589 +1596 @@
   template<typename GR, typename NF>
   FilterNodes<const GR, NF>
-  filterNodes(const GR& graph, NF& node_filter_map) {
-    return FilterNodes<const GR, NF>(graph, node_filter_map);
+  filterNodes(const GR& graph, NF& node_filter) {
+    return FilterNodes<const GR, NF>(graph, node_filter);
   }
 
   template<typename GR, typename NF>
   FilterNodes<const GR, const NF>
-  filterNodes(const GR& graph, const NF& node_filter_map) {
-    return FilterNodes<const GR, const NF>(graph, node_filter_map);
+  filterNodes(const GR& graph, const NF& node_filter) {
+    return FilterNodes<const GR, const NF>(graph, node_filter);
   }
 
@@ -1613 +1620 @@
   /// parameter is set to be \c const.
   ///
-  /// \tparam GR The type of the adapted digraph.
+  /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   /// It can also be specified to be \c const.
@@ -1619 +1626 @@
   /// It must be a \c bool (or convertible) arc map of the
   /// adapted digraph. The default type is
-  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
+  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
   ///
   /// \note The \c Node and \c Arc types of this adaptor and the adapted
   /// digraph are convertible to each other.
 #ifdef DOXYGEN
-  template<typename GR,
+  template<typename DGR,
            typename AF>
   class FilterArcs {
 #else
-  template<typename GR,
-           typename AF = typename GR::template ArcMap<bool> >
+  template<typename DGR,
+           typename AF = typename DGR::template ArcMap<bool> >
   class FilterArcs :
     public DigraphAdaptorExtender<
-      SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > {
+      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
+                     AF, false> > {
 #endif
-  public:
+    typedef DigraphAdaptorExtender<
+      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
+                     AF, false> > Parent;
+
+  public:
+
     /// The type of the adapted digraph.
-    typedef GR Digraph;
+    typedef DGR Digraph;
     /// The type of the arc filter map.
     typedef AF ArcFilterMap;
 
-    typedef DigraphAdaptorExtender<
-      SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >
-      Parent;
-
     typedef typename Parent::Arc Arc;
 
   protected:
-    ConstMap<typename Digraph::Node, bool> const_true_map;
-
-    FilterArcs() : const_true_map(true) {
-      Parent::setNodeFilterMap(const_true_map);
-    }
+    ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
+
+    FilterArcs() : const_true_map() {}
 
   public:
@@ -1659 +1666 @@
     /// Creates a subdigraph for the given digraph with the given arc
     /// filter map.
-    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
-      : Parent(), const_true_map(true) {
-      Parent::setDigraph(digraph);
-      Parent::setNodeFilterMap(const_true_map);
-      Parent::setArcFilterMap(arc_filter);
+    FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
+      : Parent(), const_true_map() {
+      Parent::initialize(digraph, const_true_map, arc_filter);
     }
 
@@ -1699 +1704 @@
   /// \ingroup graph_adaptors
   /// \relates FilterArcs
-  template<typename GR, typename AF>
-  FilterArcs<const GR, AF>
-  filterArcs(const GR& digraph, AF& arc_filter_map) {
-    return FilterArcs<const GR, AF>(digraph, arc_filter_map);
+  template<typename DGR, typename AF>
+  FilterArcs<const DGR, AF>
+  filterArcs(const DGR& digraph, AF& arc_filter) {
+    return FilterArcs<const DGR, AF>(digraph, arc_filter);
   }
 
-  template<typename GR, typename AF>
-  FilterArcs<const GR, const AF>
-  filterArcs(const GR& digraph, const AF& arc_filter_map) {
-    return FilterArcs<const GR, const AF>(digraph, arc_filter_map);
+  template<typename DGR, typename AF>
+  FilterArcs<const DGR, const AF>
+  filterArcs(const DGR& digraph, const AF& arc_filter) {
+    return FilterArcs<const DGR, const AF>(digraph, arc_filter);
   }
 
@@ -1744 +1749 @@
   class FilterEdges :
     public GraphAdaptorExtender<
-      SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > {
+      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
+                   EF, false> > {
 #endif
-  public:
+    typedef GraphAdaptorExtender<
+      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
+                   EF, false> > Parent;
+
+  public:
+
     /// The type of the adapted graph.
     typedef GR Graph;
@@ -1752 +1763 @@
     typedef EF EdgeFilterMap;
 
-    typedef GraphAdaptorExtender<
-      SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> >
-      Parent;
-
     typedef typename Parent::Edge Edge;
 
   protected:
-    ConstMap<typename Graph::Node, bool> const_true_map;
+    ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
 
     FilterEdges() : const_true_map(true) {
@@ -1771 +1778 @@
     /// Creates a subgraph for the given graph with the given edge
     /// filter map.
-    FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
-      Parent(), const_true_map(true) {
-      Parent::setGraph(graph);
-      Parent::setNodeFilterMap(const_true_map);
-      Parent::setEdgeFilterMap(edge_filter_map);
+    FilterEdges(GR& graph, EF& edge_filter) 
+      : Parent(), const_true_map() {
+      Parent::initialize(graph, const_true_map, edge_filter);
     }
 
@@ -1813 +1818 @@
   template<typename GR, typename EF>
   FilterEdges<const GR, EF>
-  filterEdges(const GR& graph, EF& edge_filter_map) {
-    return FilterEdges<const GR, EF>(graph, edge_filter_map);
+  filterEdges(const GR& graph, EF& edge_filter) {
+    return FilterEdges<const GR, EF>(graph, edge_filter);
   }
 
   template<typename GR, typename EF>
   FilterEdges<const GR, const EF>
-  filterEdges(const GR& graph, const EF& edge_filter_map) {
-    return FilterEdges<const GR, const EF>(graph, edge_filter_map);
+  filterEdges(const GR& graph, const EF& edge_filter) {
+    return FilterEdges<const GR, const EF>(graph, edge_filter);
   }
 
 
-  template <typename _Digraph>
+  template <typename DGR>
   class UndirectorBase {
   public:
-    typedef _Digraph Digraph;
+    typedef DGR Digraph;
     typedef UndirectorBase Adaptor;
 
@@ -1835 +1840 @@
     typedef typename Digraph::Node Node;
 
-    class Arc : public Edge {
+    class Arc {
       friend class UndirectorBase;
     protected:
+      Edge _edge;
       bool _forward;
 
-      Arc(const Edge& edge, bool forward) :
-        Edge(edge), _forward(forward) {}
+      Arc(const Edge& edge, bool forward) 
+        : _edge(edge), _forward(forward) {}
 
     public:
       Arc() {}
 
-      Arc(Invalid) : Edge(INVALID), _forward(true) {}
+      Arc(Invalid) : _edge(INVALID), _forward(true) {}
+
+      operator const Edge&() const { return _edge; }
 
       bool operator==(const Arc &other) const {
-        return _forward == other._forward &&
-          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
+        return _forward == other._forward && _edge == other._edge;
       }
       bool operator!=(const Arc &other) const {
-        return _forward != other._forward ||
-          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
+        return _forward != other._forward || _edge != other._edge;
       }
       bool operator<(const Arc &other) const {
         return _forward < other._forward ||
-          (_forward == other._forward &&
-           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
+          (_forward == other._forward && _edge < other._edge);
       }
     };
@@ -1872 +1877 @@
 
     void first(Arc& a) const {
-      _digraph->first(a);
+      _digraph->first(a._edge);
       a._forward = true;
     }
@@ -1880 +1885 @@
         a._forward = false;
       } else {
-        _digraph->next(a);
+        _digraph->next(a._edge);
         a._forward = true;
       }
@@ -1894 +1899 @@
 
     void firstOut(Arc& a, const Node& n) const {
-      _digraph->firstIn(a, n);
-      if( static_cast<const Edge&>(a) != INVALID ) {
+      _digraph->firstIn(a._edge, n);
+      if (a._edge != INVALID ) {
         a._forward = false;
       } else {
-        _digraph->firstOut(a, n);
+        _digraph->firstOut(a._edge, n);
         a._forward = true;
       }
@@ -1904 +1909 @@
     void nextOut(Arc &a) const {
       if (!a._forward) {
-        Node n = _digraph->target(a);
-        _digraph->nextIn(a);
-        if (static_cast<const Edge&>(a) == INVALID ) {
-          _digraph->firstOut(a, n);
+        Node n = _digraph->target(a._edge);
+        _digraph->nextIn(a._edge);
+        if (a._edge == INVALID) {
+          _digraph->firstOut(a._edge, n);
           a._forward = true;
         }
       }
       else {
-        _digraph->nextOut(a);
+        _digraph->nextOut(a._edge);
       }
     }
 
     void firstIn(Arc &a, const Node &n) const {
-      _digraph->firstOut(a, n);
-      if (static_cast<const Edge&>(a) != INVALID ) {
+      _digraph->firstOut(a._edge, n);
+      if (a._edge != INVALID ) {
         a._forward = false;
       } else {
-        _digraph->firstIn(a, n);
+        _digraph->firstIn(a._edge, n);
         a._forward = true;
       }
@@ -1927 +1932 @@
     void nextIn(Arc &a) const {
       if (!a._forward) {
-        Node n = _digraph->source(a);
-        _digraph->nextOut(a);
-        if( static_cast<const Edge&>(a) == INVALID ) {
-          _digraph->firstIn(a, n);
+        Node n = _digraph->source(a._edge);
+        _digraph->nextOut(a._edge);
+        if (a._edge == INVALID ) {
+          _digraph->firstIn(a._edge, n);
           a._forward = true;
         }
       }
       else {
-        _digraph->nextIn(a);
+        _digraph->nextIn(a._edge);
       }
     }
@@ -1968 +1973 @@
 
     Node source(const Arc &a) const {
-      return a._forward ? _digraph->source(a) : _digraph->target(a);
+      return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
     }
 
     Node target(const Arc &a) const {
-      return a._forward ? _digraph->target(a) : _digraph->source(a);
+      return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
     }
 
     static Arc direct(const Edge &e, bool d) {
       return Arc(e, d);
-    }
-    Arc direct(const Edge &e, const Node& n) const {
-      return Arc(e, _digraph->source(e) == n);
     }
 
@@ -2063 +2065 @@
   private:
 
-    template <typename _Value>
+    template <typename V>
     class ArcMapBase {
     private:
 
-      typedef typename Digraph::template ArcMap<_Value> MapImpl;
+      typedef typename DGR::template ArcMap<V> MapImpl;
 
     public:
@@ -2073 +2075 @@
       typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
 
-      typedef _Value Value;
+      typedef V Value;
       typedef Arc Key;
       typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
@@ -2080 +2082 @@
       typedef typename MapTraits<MapImpl>::ReturnValue Reference;
 
-      ArcMapBase(const Adaptor& adaptor) :
+      ArcMapBase(const UndirectorBase<DGR>& adaptor) :
         _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
 
-      ArcMapBase(const Adaptor& adaptor, const Value& v)
-        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
-
-      void set(const Arc& a, const Value& v) {
+      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
+        : _forward(*adaptor._digraph, value), 
+          _backward(*adaptor._digraph, value) {}
+
+      void set(const Arc& a, const V& value) {
         if (direction(a)) {
-          _forward.set(a, v);
+          _forward.set(a, value);
         } else {
-          _backward.set(a, v);
+          _backward.set(a, value);
         }
       }
@@ -2118 +2121 @@
   public:
 
-    template <typename _Value>
-    class NodeMap : public Digraph::template NodeMap<_Value> {
+    template <typename V>
+    class NodeMap : public DGR::template NodeMap<V> {
+      typedef typename DGR::template NodeMap<V> Parent;
+
     public:
-
-      typedef _Value Value;
-      typedef typename Digraph::template NodeMap<Value> Parent;
-
-      explicit NodeMap(const Adaptor& adaptor)
+      typedef V Value;
+
+      explicit NodeMap(const UndirectorBase<DGR>& adaptor)
         : Parent(*adaptor._digraph) {}
 
-      NodeMap(const Adaptor& adaptor, const _Value& value)
+      NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
         : Parent(*adaptor._digraph, value) { }
 
@@ -2144 +2147 @@
     };
 
-    template <typename _Value>
+    template <typename V>
     class ArcMap
-      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
-    {
+      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
+      typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
-
-      explicit ArcMap(const Adaptor& adaptor)
+      typedef V Value;
+
+      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
         : Parent(adaptor) {}
 
-      ArcMap(const Adaptor& adaptor, const Value& value)
+      ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
         : Parent(adaptor, value) {}
 
@@ -2170 +2173 @@
     };
 
-    template <typename _Value>
-    class EdgeMap : public Digraph::template ArcMap<_Value> {
+    template <typename V>
+    class EdgeMap : public Digraph::template ArcMap<V> {
+      typedef typename Digraph::template ArcMap<V> Parent;
+
     public:
-
-      typedef _Value Value;
-      typedef typename Digraph::template ArcMap<Value> Parent;
-
-      explicit EdgeMap(const Adaptor& adaptor)
+      typedef V Value;
+
+      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
         : Parent(*adaptor._digraph) {}
 
-      EdgeMap(const Adaptor& adaptor, const Value& value)
+      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
         : Parent(*adaptor._digraph, value) {}
 
@@ -2196 +2199 @@
     };
 
-    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
+    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
 
-    typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
+    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
     EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
+    
+    typedef EdgeNotifier ArcNotifier;
+    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
 
   protected:
@@ -2206 +2212 @@
     UndirectorBase() : _digraph(0) {}
 
-    Digraph* _digraph;
-
-    void setDigraph(Digraph& digraph) {
+    DGR* _digraph;
+
+    void initialize(DGR& digraph) {
       _digraph = &digraph;
     }
@@ -2227 +2233 @@
   /// parameter is set to be \c const.
   ///
-  /// \tparam GR The type of the adapted digraph.
+  /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   /// It can also be specified to be \c const.
@@ -2237 +2243 @@
   /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
   /// of the adapted digraph.)
-  template<typename GR>
+  template<typename DGR>
 #ifdef DOXYGEN
   class Undirector {
 #else
   class Undirector :
-    public GraphAdaptorExtender<UndirectorBase<GR> > {
+    public GraphAdaptorExtender<UndirectorBase<DGR> > {
 #endif
+    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
   public:
     /// The type of the adapted digraph.
-    typedef GR Digraph;
-    typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent;
+    typedef DGR Digraph;
   protected:
     Undirector() { }
@@ -2255 +2261 @@
     ///
     /// Creates an undirected graph from the given digraph.
-    Undirector(Digraph& digraph) {
-      setDigraph(digraph);
+    Undirector(DGR& digraph) {
+      initialize(digraph);
     }
 
@@ -2263 +2269 @@
     /// This map adaptor class adapts two arc maps of the underlying
     /// digraph to get an arc map of the undirected graph.
-    /// Its value type is inherited from the first arc map type
-    /// (\c %ForwardMap).
-    template <typename ForwardMap, typename BackwardMap>
+    /// Its value type is inherited from the first arc map type (\c FW).
+    /// \tparam FW The type of the "foward" arc map.
+    /// \tparam BK The type of the "backward" arc map.
+    template <typename FW, typename BK>
     class CombinedArcMap {
     public:
@@ -2272 +2279 @@
       typedef typename Parent::Arc Key;
       /// The value type of the map
-      typedef typename ForwardMap::Value Value;
-
-      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
-
-      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
-      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
-      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
-      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
+      typedef typename FW::Value Value;
+
+      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
+
+      typedef typename MapTraits<FW>::ReturnValue ReturnValue;
+      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
+      typedef typename MapTraits<FW>::ReturnValue Reference;
+      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
 
       /// Constructor
-      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
+      CombinedArcMap(FW& forward, BK& backward)
         : _forward(&forward), _backward(&backward) {}
 
@@ -2314 +2321 @@
     protected:
 
-      ForwardMap* _forward;
-      BackwardMap* _backward;
+      FW* _forward;
+      BK* _backward;
 
     };
@@ -2322 +2329 @@
     ///
     /// This function just returns a combined arc map.
-    template <typename ForwardMap, typename BackwardMap>
-    static CombinedArcMap<ForwardMap, BackwardMap>
-    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
-      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
-    }
-
-    template <typename ForwardMap, typename BackwardMap>
-    static CombinedArcMap<const ForwardMap, BackwardMap>
-    combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
-      return CombinedArcMap<const ForwardMap,
-        BackwardMap>(forward, backward);
-    }
-
-    template <typename ForwardMap, typename BackwardMap>
-    static CombinedArcMap<ForwardMap, const BackwardMap>
-    combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
-      return CombinedArcMap<ForwardMap,
-        const BackwardMap>(forward, backward);
-    }
-
-    template <typename ForwardMap, typename BackwardMap>
-    static CombinedArcMap<const ForwardMap, const BackwardMap>
-    combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
-      return CombinedArcMap<const ForwardMap,
-        const BackwardMap>(forward, backward);
+    template <typename FW, typename BK>
+    static CombinedArcMap<FW, BK>
+    combinedArcMap(FW& forward, BK& backward) {
+      return CombinedArcMap<FW, BK>(forward, backward);
+    }
+
+    template <typename FW, typename BK>
+    static CombinedArcMap<const FW, BK>
+    combinedArcMap(const FW& forward, BK& backward) {
+      return CombinedArcMap<const FW, BK>(forward, backward);
+    }
+
+    template <typename FW, typename BK>
+    static CombinedArcMap<FW, const BK>
+    combinedArcMap(FW& forward, const BK& backward) {
+      return CombinedArcMap<FW, const BK>(forward, backward);
+    }
+
+    template <typename FW, typename BK>
+    static CombinedArcMap<const FW, const BK>
+    combinedArcMap(const FW& forward, const BK& backward) {
+      return CombinedArcMap<const FW, const BK>(forward, backward);
     }
 
@@ -2356 +2360 @@
   /// \ingroup graph_adaptors
   /// \relates Undirector
-  template<typename GR>
-  Undirector<const GR> undirector(const GR& digraph) {
-    return Undirector<const GR>(digraph);
+  template<typename DGR>
+  Undirector<const DGR> undirector(const DGR& digraph) {
+    return Undirector<const DGR>(digraph);
   }
 
 
-  template <typename _Graph, typename _DirectionMap>
+  template <typename GR, typename DM>
   class OrienterBase {
   public:
 
-    typedef _Graph Graph;
-    typedef _DirectionMap DirectionMap;
-
-    typedef typename Graph::Node Node;
-    typedef typename Graph::Edge Arc;
+    typedef GR Graph;
+    typedef DM DirectionMap;
+
+    typedef typename GR::Node Node;
+    typedef typename GR::Edge Arc;
 
     void reverseArc(const Arc& arc) {
@@ -2449 +2453 @@
     int maxArcId() const { return _graph->maxEdgeId(); }
 
-    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
+    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
     NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 
-    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
+    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 
-    template <typename _Value>
-    class NodeMap : public _Graph::template NodeMap<_Value> {
+    template <typename V>
+    class NodeMap : public GR::template NodeMap<V> {
+      typedef typename GR::template NodeMap<V> Parent;
+
     public:
 
-      typedef typename _Graph::template NodeMap<_Value> Parent;
-
-      explicit NodeMap(const OrienterBase& adapter)
+      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
         : Parent(*adapter._graph) {}
 
-      NodeMap(const OrienterBase& adapter, const _Value& value)
+      NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
         : Parent(*adapter._graph, value) {}
 
@@ -2480 +2484 @@
     };
 
-    template <typename _Value>
-    class ArcMap : public _Graph::template EdgeMap<_Value> {
+    template <typename V>
+    class ArcMap : public GR::template EdgeMap<V> {
+      typedef typename Graph::template EdgeMap<V> Parent;
+
     public:
 
-      typedef typename Graph::template EdgeMap<_Value> Parent;
-
-      explicit ArcMap(const OrienterBase& adapter)
+      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
         : Parent(*adapter._graph) { }
 
-      ArcMap(const OrienterBase& adapter, const _Value& value)
+      ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
         : Parent(*adapter._graph, value) { }
 
@@ -2508 +2512 @@
   protected:
     Graph* _graph;
-    DirectionMap* _direction;
-
-    void setDirectionMap(DirectionMap& direction) {
+    DM* _direction;
+
+    void initialize(GR& graph, DM& direction) {
+      _graph = &graph;
       _direction = &direction;
-    }
-
-    void setGraph(Graph& graph) {
-      _graph = &graph;
     }
 
@@ -2557 +2558 @@
     public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
 #endif
+    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
   public:
 
@@ -2564 +2566 @@
     typedef DM DirectionMap;
 
-    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
     typedef typename Parent::Arc Arc;
+
   protected:
     Orienter() { }
+
   public:
 
@@ -2573 +2576 @@
     ///
     /// Constructor of the adaptor.
-    Orienter(Graph& graph, DirectionMap& direction) {
-      setGraph(graph);
-      setDirectionMap(direction);
+    Orienter(GR& graph, DM& direction) {
+      Parent::initialize(graph, direction);
     }
 
@@ -2595 +2597 @@
   template<typename GR, typename DM>
   Orienter<const GR, DM>
-  orienter(const GR& graph, DM& direction_map) {
-    return Orienter<const GR, DM>(graph, direction_map);
+  orienter(const GR& graph, DM& direction) {
+    return Orienter<const GR, DM>(graph, direction);
   }
 
   template<typename GR, typename DM>
   Orienter<const GR, const DM>
-  orienter(const GR& graph, const DM& direction_map) {
-    return Orienter<const GR, const DM>(graph, direction_map);
+  orienter(const GR& graph, const DM& direction) {
+    return Orienter<const GR, const DM>(graph, direction);
   }
 
   namespace _adaptor_bits {
 
-    template<typename Digraph,
-             typename CapacityMap,
-             typename FlowMap,
-             typename Tolerance>
+    template <typename DGR, typename CM, typename FM, typename TL>
     class ResForwardFilter {
     public:
 
-      typedef typename Digraph::Arc Key;
+      typedef typename DGR::Arc Key;
       typedef bool Value;
 
     private:
 
-      const CapacityMap* _capacity;
-      const FlowMap* _flow;
-      Tolerance _tolerance;
+      const CM* _capacity;
+      const FM* _flow;
+      TL _tolerance;
+
     public:
 
-      ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
-                       const Tolerance& tolerance = Tolerance())
+      ResForwardFilter(const CM& capacity, const FM& flow,
+                       const TL& tolerance = TL())
         : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
 
-      bool operator[](const typename Digraph::Arc& a) const {
+      bool operator[](const typename DGR::Arc& a) const {
         return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
       }
     };
 
-    template<typename Digraph,
-             typename CapacityMap,
-             typename FlowMap,
-             typename Tolerance>
+    template<typename DGR,typename CM, typename FM, typename TL>
     class ResBackwardFilter {
     public:
 
-      typedef typename Digraph::Arc Key;
+      typedef typename DGR::Arc Key;
       typedef bool Value;
 
     private:
 
-      const CapacityMap* _capacity;
-      const FlowMap* _flow;
-      Tolerance _tolerance;
+      const CM* _capacity;
+      const FM* _flow;
+      TL _tolerance;
 
     public:
 
-      ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
-                        const Tolerance& tolerance = Tolerance())
+      ResBackwardFilter(const CM& capacity, const FM& flow,
+                        const TL& tolerance = TL())
         : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
 
-      bool operator[](const typename Digraph::Arc& a) const {
+      bool operator[](const typename DGR::Arc& a) const {
         return _tolerance.positive((*_flow)[a]);
       }
@@ -2667 +2664 @@
   /// flow and circulation problems.
   ///
-  /// Residual can be used for composing the \e residual digraph for directed
-  /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
-  /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
-  /// functions on the arcs.
+  /// ResidualDigraph can be used for composing the \e residual digraph
+  /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
+  /// be a directed graph and let \f$ F \f$ be a number type.
+  /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
   /// This adaptor implements a digraph structure with node set \f$ V \f$
   /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
@@ -2682 +2679 @@
   /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
   ///
-  /// \tparam GR The type of the adapted digraph.
+  /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   /// It is implicitly \c const.
@@ -2704 +2701 @@
   /// is convertible to the \c Arc type of the adapted digraph.
 #ifdef DOXYGEN
-  template<typename GR, typename CM, typename FM, typename TL>
-  class Residual
+  template<typename DGR, typename CM, typename FM, typename TL>
+  class ResidualDigraph
 #else
-  template<typename GR,
-           typename CM = typename GR::template ArcMap<int>,
+  template<typename DGR,
+           typename CM = typename DGR::template ArcMap<int>,
            typename FM = CM,
            typename TL = Tolerance<typename CM::Value> >
-  class Residual :
-    public FilterArcs<
-      Undirector<const GR>,
-      typename Undirector<const GR>::template CombinedArcMap<
-        _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,
-        _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >
+  class ResidualDigraph 
+    : public SubDigraph<
+        Undirector<const DGR>,
+        ConstMap<typename DGR::Node, Const<bool, true> >,
+        typename Undirector<const DGR>::template CombinedArcMap<
+          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
+          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
 #endif
   {
@@ -2722 +2720 @@
 
     /// The type of the underlying digraph.
-    typedef GR Digraph;
+    typedef DGR Digraph;
     /// The type of the capacity map.
     typedef CM CapacityMap;
@@ -2731 +2729 @@
 
     typedef typename CapacityMap::Value Value;
-    typedef Residual Adaptor;
+    typedef ResidualDigraph Adaptor;
 
   protected:
@@ -2737 +2735 @@
     typedef Undirector<const Digraph> Undirected;
 
-    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
-                                            FlowMap, Tolerance> ForwardFilter;
-
-    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
-                                             FlowMap, Tolerance> BackwardFilter;
+    typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
+
+    typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
+                                            FM, TL> ForwardFilter;
+
+    typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
+                                             FM, TL> BackwardFilter;
 
     typedef typename Undirected::
       template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
 
-    typedef FilterArcs<Undirected, ArcFilter> Parent;
+    typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
 
     const CapacityMap* _capacity;
@@ -2752 +2752 @@
 
     Undirected _graph;
+    NodeFilter _node_filter;
     ForwardFilter _forward_filter;
     BackwardFilter _backward_filter;
@@ -2762 +2763 @@
     /// Constructor of the residual digraph adaptor. The parameters are the
     /// digraph, the capacity map, the flow map, and a tolerance object.
-    Residual(const Digraph& digraph, const CapacityMap& capacity,
-             FlowMap& flow, const Tolerance& tolerance = Tolerance())
-      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
+    ResidualDigraph(const DGR& digraph, const CM& capacity,
+                    FM& flow, const TL& tolerance = Tolerance())
+      : Parent(), _capacity(&capacity), _flow(&flow), 
+        _graph(digraph), _node_filter(),
         _forward_filter(capacity, flow, tolerance),
         _backward_filter(capacity, flow, tolerance),
         _arc_filter(_forward_filter, _backward_filter)
     {
-      Parent::setDigraph(_graph);
-      Parent::setArcFilterMap(_arc_filter);
+      Parent::initialize(_graph, _node_filter, _arc_filter);
     }
 
@@ -2846 +2847 @@
 
       /// Constructor
-      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
+      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
+        : _adaptor(&adaptor) {}
 
       /// Returns the value associated with the given residual arc
@@ -2866 +2868 @@
   /// \brief Returns a (read-only) Residual adaptor
   ///
-  /// This function just returns a (read-only) \ref Residual adaptor.
+  /// This function just returns a (read-only) \ref ResidualDigraph adaptor.
   /// \ingroup graph_adaptors
-  /// \relates Residual
-  template<typename GR, typename CM, typename FM>
-  Residual<GR, CM, FM> residual(const GR& digraph,
-                                const CM& capacity_map,
-                                FM& flow_map) {
-    return Residual<GR, CM, FM> (digraph, capacity_map, flow_map);
+  /// \relates ResidualDigraph
+    template<typename DGR, typename CM, typename FM>
+  ResidualDigraph<DGR, CM, FM>
+  residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
+    return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
   }
 
 
-  template <typename _Digraph>
+  template <typename DGR>
   class SplitNodesBase {
-  public:
-
-    typedef _Digraph Digraph;
-    typedef DigraphAdaptorBase<const _Digraph> Parent;
+    typedef DigraphAdaptorBase<const DGR> Parent;
+
+  public:
+
+    typedef DGR Digraph;
     typedef SplitNodesBase Adaptor;
 
-    typedef typename Digraph::Node DigraphNode;
-    typedef typename Digraph::Arc DigraphArc;
+    typedef typename DGR::Node DigraphNode;
+    typedef typename DGR::Arc DigraphArc;
 
     class Node;
@@ -3150 +3152 @@
   private:
 
-    template <typename _Value>
+    template <typename V>
     class NodeMapBase
-      : public MapTraits<typename Parent::template NodeMap<_Value> > {
-      typedef typename Parent::template NodeMap<_Value> NodeImpl;
+      : public MapTraits<typename Parent::template NodeMap<V> > {
+      typedef typename Parent::template NodeMap<V> NodeImpl;
     public:
       typedef Node Key;
-      typedef _Value Value;
+      typedef V Value;
       typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
       typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
@@ -3163 +3165 @@
       typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
 
-      NodeMapBase(const Adaptor& adaptor)
+      NodeMapBase(const SplitNodesBase<DGR>& adaptor)
         : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
-      NodeMapBase(const Adaptor& adaptor, const Value& value)
+      NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
         : _in_map(*adaptor._digraph, value),
           _out_map(*adaptor._digraph, value) {}
 
-      void set(const Node& key, const Value& val) {
-        if (Adaptor::inNode(key)) { _in_map.set(key, val); }
+      void set(const Node& key, const V& val) {
+        if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
         else {_out_map.set(key, val); }
       }
 
       ReturnValue operator[](const Node& key) {
-        if (Adaptor::inNode(key)) { return _in_map[key]; }
+        if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
         else { return _out_map[key]; }
       }
@@ -3188 +3190 @@
     };
 
-    template <typename _Value>
+    template <typename V>
     class ArcMapBase
-      : public MapTraits<typename Parent::template ArcMap<_Value> > {
-      typedef typename Parent::template ArcMap<_Value> ArcImpl;
-      typedef typename Parent::template NodeMap<_Value> NodeImpl;
+      : public MapTraits<typename Parent::template ArcMap<V> > {
+      typedef typename Parent::template ArcMap<V> ArcImpl;
+      typedef typename Parent::template NodeMap<V> NodeImpl;
     public:
       typedef Arc Key;
-      typedef _Value Value;
+      typedef V Value;
       typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
       typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
@@ -3202 +3204 @@
       typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
 
-      ArcMapBase(const Adaptor& adaptor)
+      ArcMapBase(const SplitNodesBase<DGR>& adaptor)
         : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
-      ArcMapBase(const Adaptor& adaptor, const Value& value)
+      ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
         : _arc_map(*adaptor._digraph, value),
           _node_map(*adaptor._digraph, value) {}
 
-      void set(const Arc& key, const Value& val) {
-        if (Adaptor::origArc(key)) {
-          _arc_map.set(key._item.first(), val);
+      void set(const Arc& key, const V& val) {
+        if (SplitNodesBase<DGR>::origArc(key)) {
+          _arc_map.set(static_cast<const DigraphArc&>(key), val);
         } else {
-          _node_map.set(key._item.second(), val);
+          _node_map.set(static_cast<const DigraphNode&>(key), val);
         }
       }
 
       ReturnValue operator[](const Arc& key) {
-        if (Adaptor::origArc(key)) {
-          return _arc_map[key._item.first()];
+        if (SplitNodesBase<DGR>::origArc(key)) {
+          return _arc_map[static_cast<const DigraphArc&>(key)];
         } else {
-          return _node_map[key._item.second()];
+          return _node_map[static_cast<const DigraphNode&>(key)];
         }
       }
 
       ConstReturnValue operator[](const Arc& key) const {
-        if (Adaptor::origArc(key)) {
-          return _arc_map[key._item.first()];
+        if (SplitNodesBase<DGR>::origArc(key)) {
+          return _arc_map[static_cast<const DigraphArc&>(key)];
         } else {
-          return _node_map[key._item.second()];
+          return _node_map[static_cast<const DigraphNode&>(key)];
         }
       }
@@ -3239 +3241 @@
   public:
 
-    template <typename _Value>
+    template <typename V>
     class NodeMap
-      : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
-    {
+      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
+      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
-
-      NodeMap(const Adaptor& adaptor)
+      typedef V Value;
+
+      NodeMap(const SplitNodesBase<DGR>& adaptor)
         : Parent(adaptor) {}
 
-      NodeMap(const Adaptor& adaptor, const Value& value)
+      NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
         : Parent(adaptor, value) {}
 
@@ -3265 +3267 @@
     };
 
-    template <typename _Value>
+    template <typename V>
     class ArcMap
-      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
-    {
+      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
+      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
+
     public:
-      typedef _Value Value;
-      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
-
-      ArcMap(const Adaptor& adaptor)
+      typedef V Value;
+
+      ArcMap(const SplitNodesBase<DGR>& adaptor)
         : Parent(adaptor) {}
 
-      ArcMap(const Adaptor& adaptor, const Value& value)
+      ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
         : Parent(adaptor, value) {}
 
@@ -3295 +3297 @@
     SplitNodesBase() : _digraph(0) {}
 
-    Digraph* _digraph;
-
-    void setDigraph(Digraph& digraph) {
+    DGR* _digraph;
+
+    void initialize(Digraph& digraph) {
       _digraph = &digraph;
     }
@@ -3324 +3326 @@
   /// in the adaptor.
   ///
-  /// \tparam GR The type of the adapted digraph.
+  /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   /// It is implicitly \c const.
@@ -3330 +3332 @@
   /// \note The \c Node type of this adaptor is converible to the \c Node
   /// type of the adapted digraph.
-  template <typename GR>
+  template <typename DGR>
 #ifdef DOXYGEN
   class SplitNodes {
 #else
   class SplitNodes
-    : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
+    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
 #endif
-  public:
-    typedef GR Digraph;
-    typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
-
-    typedef typename Digraph::Node DigraphNode;
-    typedef typename Digraph::Arc DigraphArc;
+    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
+
+  public:
+    typedef DGR Digraph;
+
+    typedef typename DGR::Node DigraphNode;
+    typedef typename DGR::Arc DigraphArc;
 
     typedef typename Parent::Node Node;
@@ -3350 +3353 @@
     ///
     /// Constructor of the adaptor.
-    SplitNodes(const Digraph& g) {
-      Parent::setDigraph(g);
+    SplitNodes(const DGR& g) {
+      Parent::initialize(g);
     }
 
@@ -3420 +3423 @@
     /// This map adaptor class adapts two node maps of the original digraph
     /// to get a node map of the split digraph.
-    /// Its value type is inherited from the first node map type
-    /// (\c InNodeMap).
-    template <typename InNodeMap, typename OutNodeMap>
+    /// Its value type is inherited from the first node map type (\c IN).
+    /// \tparam IN The type of the node map for the in-nodes. 
+    /// \tparam OUT The type of the node map for the out-nodes.
+    template <typename IN, typename OUT>
     class CombinedNodeMap {
     public:
@@ -3429 +3433 @@
       typedef Node Key;
       /// The value type of the map
-      typedef typename InNodeMap::Value Value;
-
-      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
-      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
-      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
-      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
-      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
+      typedef typename IN::Value Value;
+
+      typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
+      typedef typename MapTraits<IN>::ReturnValue ReturnValue;
+      typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
+      typedef typename MapTraits<IN>::ReturnValue Reference;
+      typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
 
       /// Constructor
-      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
+      CombinedNodeMap(IN& in_map, OUT& out_map)
         : _in_map(in_map), _out_map(out_map) {}
 
       /// Returns the value associated with the given key.
       Value operator[](const Key& key) const {
-        if (Parent::inNode(key)) {
+        if (SplitNodesBase<const DGR>::inNode(key)) {
           return _in_map[key];
         } else {
@@ -3452 +3456 @@
       /// Returns a reference to the value associated with the given key.
       Value& operator[](const Key& key) {
-        if (Parent::inNode(key)) {
+        if (SplitNodesBase<const DGR>::inNode(key)) {
           return _in_map[key];
         } else {
@@ -3461 +3465 @@
       /// Sets the value associated with the given key.
       void set(const Key& key, const Value& value) {
-        if (Parent::inNode(key)) {
+        if (SplitNodesBase<const DGR>::inNode(key)) {
           _in_map.set(key, value);
         } else {
@@ -3470 +3474 @@
     private:
 
-      InNodeMap& _in_map;
-      OutNodeMap& _out_map;
+      IN& _in_map;
+      OUT& _out_map;
 
     };
@@ -3479 +3483 @@
     ///
     /// This function just returns a combined node map.
-    template <typename InNodeMap, typename OutNodeMap>
-    static CombinedNodeMap<InNodeMap, OutNodeMap>
-    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
-      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
-    }
-
-    template <typename InNodeMap, typename OutNodeMap>
-    static CombinedNodeMap<const InNodeMap, OutNodeMap>
-    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
-      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
-    }
-
-    template <typename InNodeMap, typename OutNodeMap>
-    static CombinedNodeMap<InNodeMap, const OutNodeMap>
-    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
-      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
-    }
-
-    template <typename InNodeMap, typename OutNodeMap>
-    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
-    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
-      return CombinedNodeMap<const InNodeMap,
-        const OutNodeMap>(in_map, out_map);
+    template <typename IN, typename OUT>
+    static CombinedNodeMap<IN, OUT>
+    combinedNodeMap(IN& in_map, OUT& out_map) {
+      return CombinedNodeMap<IN, OUT>(in_map, out_map);
+    }
+
+    template <typename IN, typename OUT>
+    static CombinedNodeMap<const IN, OUT>
+    combinedNodeMap(const IN& in_map, OUT& out_map) {
+      return CombinedNodeMap<const IN, OUT>(in_map, out_map);
+    }
+
+    template <typename IN, typename OUT>
+    static CombinedNodeMap<IN, const OUT>
+    combinedNodeMap(IN& in_map, const OUT& out_map) {
+      return CombinedNodeMap<IN, const OUT>(in_map, out_map);
+    }
+
+    template <typename IN, typename OUT>
+    static CombinedNodeMap<const IN, const OUT>
+    combinedNodeMap(const IN& in_map, const OUT& out_map) {
+      return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
     }
 
@@ -3509 +3512 @@
     /// This map adaptor class adapts an arc map and a node map of the
     /// original digraph to get an arc map of the split digraph.
-    /// Its value type is inherited from the original arc map type
-    /// (\c ArcMap).
-    template <typename ArcMap, typename NodeMap>
+    /// Its value type is inherited from the original arc map type (\c AM).
+    /// \tparam AM The type of the arc map.
+    /// \tparam NM the type of the node map.
+    template <typename AM, typename NM>
     class CombinedArcMap {
     public:
@@ -3518 +3522 @@
       typedef Arc Key;
       /// The value type of the map
-      typedef typename ArcMap::Value Value;
-
-      typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
-      typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
-      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
-      typedef typename MapTraits<ArcMap>::ReturnValue Reference;
-      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
+      typedef typename AM::Value Value;
+
+      typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
+      typedef typename MapTraits<AM>::ReturnValue ReturnValue;
+      typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
+      typedef typename MapTraits<AM>::ReturnValue Reference;
+      typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
 
       /// Constructor
-      CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
+      CombinedArcMap(AM& arc_map, NM& node_map)
         : _arc_map(arc_map), _node_map(node_map) {}
 
       /// Returns the value associated with the given key.
       Value operator[](const Key& arc) const {
-        if (Parent::origArc(arc)) {
+        if (SplitNodesBase<const DGR>::origArc(arc)) {
           return _arc_map[arc];
         } else {
@@ -3541 +3545 @@
       /// Returns a reference to the value associated with the given key.
       Value& operator[](const Key& arc) {
-        if (Parent::origArc(arc)) {
+        if (SplitNodesBase<const DGR>::origArc(arc)) {
           return _arc_map[arc];
         } else {
@@ -3550 +3554 @@
       /// Sets the value associated with the given key.
       void set(const Arc& arc, const Value& val) {
-        if (Parent::origArc(arc)) {
+        if (SplitNodesBase<const DGR>::origArc(arc)) {
           _arc_map.set(arc, val);
         } else {
@@ -3558 +3562 @@
 
     private:
-      ArcMap& _arc_map;
-      NodeMap& _node_map;
+
+      AM& _arc_map;
+      NM& _node_map;
+
     };
 
@@ -3596 +3602 @@
   /// \ingroup graph_adaptors
   /// \relates SplitNodes
-  template<typename GR>
-  SplitNodes<GR>
-  splitNodes(const GR& digraph) {
-    return SplitNodes<GR>(digraph);
+  template<typename DGR>
+  SplitNodes<DGR>
+  splitNodes(const DGR& digraph) {
+    return SplitNodes<DGR>(digraph);
   }
 
+#undef LEMON_SCOPE_FIX
+
 } //namespace lemon
 

lemon/base.cc

@@ -24 +24 @@
 namespace lemon {
 
-  float Tolerance<float>::def_epsilon = 1e-4;
+  float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
   double Tolerance<double>::def_epsilon = 1e-10;
   long double Tolerance<long double>::def_epsilon = 1e-14;

lemon/bfs.h

@@ -50 +50 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
-    ///Instantiates a PredMap.
-
-    ///This function instantiates a PredMap.
+    ///Instantiates a \c PredMap.
+
+    ///This function instantiates a \ref PredMap.
     ///\param g is the digraph, to which we would like to define the
-    ///PredMap.
+    ///\ref PredMap.
     static PredMap *createPredMap(const Digraph &g)
     {
@@ -65 +65 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
-    ///Instantiates a ProcessedMap.
-
-    ///This function instantiates a ProcessedMap.
+    ///Instantiates a \c ProcessedMap.
+
+    ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
-    ///we would like to define the ProcessedMap
+    ///we would like to define the \ref ProcessedMap
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const Digraph &g)
@@ -84 +84 @@
     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
-    ///Instantiates a ReachedMap.
-
-    ///This function instantiates a ReachedMap.
+    ///Instantiates a \c ReachedMap.
+
+    ///This function instantiates a \ref ReachedMap.
     ///\param g is the digraph, to which
-    ///we would like to define the ReachedMap.
+    ///we would like to define the \ref ReachedMap.
     static ReachedMap *createReachedMap(const Digraph &g)
     {
@@ -99 +99 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
-    ///Instantiates a DistMap.
-
-    ///This function instantiates a DistMap.
+    ///Instantiates a \c DistMap.
+
+    ///This function instantiates a \ref DistMap.
     ///\param g is the digraph, to which we would like to define the
-    ///DistMap.
+    ///\ref DistMap.
     static DistMap *createDistMap(const Digraph &g)
     {
@@ -222 +222 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///PredMap type.
+    ///\c PredMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///PredMap type.
+    ///\c PredMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -242 +242 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///DistMap type.
+    ///\c DistMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///DistMap type.
+    ///\c DistMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -262 +262 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ReachedMap type.
+    ///\c ReachedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ReachedMap type.
+    ///\c ReachedMap type.
     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     template <class T>
@@ -282 +282 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type.
+    ///\c ProcessedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type.
+    ///\c ProcessedMap type.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
@@ -301 +301 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///
     ///\ref named-templ-param "Named parameter" for setting
-    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///If you don't set it explicitly, it will be automatically allocated.
     struct SetStandardProcessedMap :
@@ -1195 +1195 @@
   /// This class defines the interface of the BfsVisit events, and
   /// it could be the base of a real visitor class.
-  template <typename _Digraph>
+  template <typename GR>
   struct BfsVisitor {
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
@@ -1225 +1225 @@
   };
 #else
-  template <typename _Digraph>
+  template <typename GR>
   struct BfsVisitor {
-    typedef _Digraph Digraph;
+    typedef GR Digraph;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
@@ -1255 +1255 @@
   ///
   /// Default traits class of BfsVisit class.
-  /// \tparam _Digraph The type of the digraph the algorithm runs on.
-  template<class _Digraph>
+  /// \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 _Digraph Digraph;
+    typedef GR Digraph;
 
     /// \brief The type of the map that indicates which nodes are reached.
@@ -1281 +1281 @@
   /// \ingroup search
   ///
-  /// \brief %BFS algorithm class with visitor interface.
+  /// \brief BFS algorithm class with visitor interface.
   ///
-  /// This class provides an efficient implementation of the %BFS algorithm
+  /// This class provides an efficient implementation of the BFS algorithm
   /// with visitor interface.
   ///
-  /// The %BfsVisit class provides an alternative interface to the Bfs
+  /// 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.
@@ -1295 +1295 @@
   /// instead.
   ///
-  /// \tparam _Digraph The type of the digraph the algorithm runs on.
-  /// The default value is
-  /// \ref ListDigraph. The value of _Digraph is not used directly by
-  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
-  /// \tparam _Visitor The Visitor type that is used by the algorithm.
-  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
+  /// \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 _Traits Traits class to set various data types used by the
+  /// \tparam TR Traits class to set various data types used by the
   /// algorithm. The default traits class is
-  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
+  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
   /// See \ref BfsVisitDefaultTraits for the documentation of
   /// a BFS visit traits class.
 #ifdef DOXYGEN
-  template <typename _Digraph, typename _Visitor, typename _Traits>
+  template <typename GR, typename VS, typename TR>
 #else
-  template <typename _Digraph = ListDigraph,
-            typename _Visitor = BfsVisitor<_Digraph>,
-            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
+  template <typename GR = ListDigraph,
+            typename VS = BfsVisitor<GR>,
+            typename TR = BfsVisitDefaultTraits<GR> >
 #endif
   class BfsVisit {
@@ -1319 +1319 @@
 
     ///The traits class.
-    typedef _Traits Traits;
+    typedef TR Traits;
 
     ///The type of the digraph the algorithm runs on.
@@ -1325 +1325 @@
 
     ///The visitor type used by the algorithm.
-    typedef _Visitor Visitor;
+    typedef VS Visitor;
 
     ///The type of the map that indicates which nodes are reached.

lemon/bin_heap.h

@@ -34 +34 @@
   ///\brief A Binary Heap implementation.
   ///
-  ///This class implements the \e binary \e heap data structure. A \e heap
-  ///is a data structure for storing items with specified values called \e
-  ///priorities in such a way that finding the item with minimum priority is
-  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
-  ///one can change the priority of an item, add or erase an item, etc.
-  ///
-  ///\tparam _Prio Type of the priority of the items.
-  ///\tparam _ItemIntMap A read and writable Item int map, used internally
+  ///This class implements the \e binary \e heap data structure.
+  ///
+  ///A \e heap is a data structure for storing items with specified values
+  ///called \e priorities in such a way that finding the item with minimum
+  ///priority is efficient. \c CMP specifies the ordering of the priorities.
+  ///In a heap one can change the priority of an item, add or erase an
+  ///item, etc.
+  ///
+  ///\tparam PR Type of the priority of the items.
+  ///\tparam IM A read and writable item map with int values, used internally
   ///to handle the cross references.
-  ///\tparam _Compare A class for the ordering of the priorities. The
-  ///default is \c std::less<_Prio>.
+  ///\tparam CMP A functor class for the ordering of the priorities.
+  ///The default is \c std::less<PR>.
   ///
   ///\sa FibHeap
   ///\sa Dijkstra
-  template <typename _Prio, typename _ItemIntMap,
-            typename _Compare = std::less<_Prio> >
+  template <typename PR, typename IM, typename CMP = std::less<PR> >
   class BinHeap {
 
   public:
     ///\e
-    typedef _ItemIntMap ItemIntMap;
-    ///\e
-    typedef _Prio Prio;
+    typedef IM ItemIntMap;
+    ///\e
+    typedef PR Prio;
     ///\e
     typedef typename ItemIntMap::Key Item;
@@ -62 +63 @@
     typedef std::pair<Item,Prio> Pair;
     ///\e
-    typedef _Compare Compare;
+    typedef CMP Compare;
 
     /// \brief Type to represent the items states.
@@ -70 +71 @@
     /// heap's point of view, but may be useful to the user.
     ///
-    /// The ItemIntMap \e should be initialized in such way that it maps
-    /// PRE_HEAP (-1) to any element to be put in the heap...
+    /// 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,
-      PRE_HEAP = -1,
-      POST_HEAP = -2
+      IN_HEAP = 0,    ///< = 0.
+      PRE_HEAP = -1,  ///< = -1.
+      POST_HEAP = -2  ///< = -2.
     };
 
   private:
-    std::vector<Pair> data;
-    Compare comp;
-    ItemIntMap &iim;
+    std::vector<Pair> _data;
+    Compare _comp;
+    ItemIntMap &_iim;
 
   public:
@@ -87 +88 @@
     ///
     /// The constructor.
-    /// \param _iim should be given to the constructor, since it is used
+    /// \param map should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
+    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
+
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param map should be given to the constructor, since it is used
     /// internally to handle the cross references. The value of the map
     /// should be PRE_HEAP (-1) for each element.
-    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
-
-    /// \brief The constructor.
-    ///
-    /// The constructor.
-    /// \param _iim should be given to the constructor, since it is used
-    /// internally to handle the cross references. The value of the map
-    /// should be PRE_HEAP (-1) for each element.
-    ///
-    /// \param _comp The comparator function object.
-    BinHeap(ItemIntMap &_iim, const Compare &_comp)
-      : iim(_iim), comp(_comp) {}
+    ///
+    /// \param comp The comparator function object.
+    BinHeap(ItemIntMap &map, const Compare &comp)
+      : _iim(map), _comp(comp) {}
 
 
@@ -107 +108 @@
     ///
     /// \brief Returns the number of items stored in the heap.
-    int size() const { return data.size(); }
+    int size() const { return _data.size(); }
 
     /// \brief Checks if the heap stores no items.
     ///
     /// Returns \c true if and only if the heap stores no items.
-    bool empty() const { return data.empty(); }
+    bool empty() const { return _data.empty(); }
 
     /// \brief Make empty this heap.
@@ -121 +122 @@
     /// each item to \c PRE_HEAP.
     void clear() {
-      data.clear();
+      _data.clear();
     }
 
@@ -129 +130 @@
     static int second_child(int i) { return 2*i+2; }
     bool less(const Pair &p1, const Pair &p2) const {
-      return comp(p1.second, p2.second);
+      return _comp(p1.second, p2.second);
     }
 
     int bubble_up(int hole, Pair p) {
       int par = parent(hole);
-      while( hole>0 && less(p,data[par]) ) {
-        move(data[par],hole);
+      while( hole>0 && less(p,_data[par]) ) {
+        move(_data[par],hole);
         hole = par;
         par = parent(hole);
@@ -146 +147 @@
       int child = second_child(hole);
       while(child < length) {
-        if( less(data[child-1], data[child]) ) {
+        if( less(_data[child-1], _data[child]) ) {
           --child;
         }
-        if( !less(data[child], p) )
+        if( !less(_data[child], p) )
           goto ok;
-        move(data[child], hole);
+        move(_data[child], hole);
         hole = child;
         child = second_child(hole);
       }
       child--;
-      if( child<length && less(data[child], p) ) {
-        move(data[child], hole);
+      if( child<length && less(_data[child], p) ) {
+        move(_data[child], hole);
         hole=child;
       }
@@ -166 +167 @@
 
     void move(const Pair &p, int i) {
-      data[i] = p;
-      iim.set(p.first, i);
+      _data[i] = p;
+      _iim.set(p.first, i);
     }
 
@@ -176 +177 @@
     /// \param p The pair to insert.
     void push(const Pair &p) {
-      int n = data.size();
-      data.resize(n+1);
+      int n = _data.size();
+      _data.resize(n+1);
       bubble_up(n, p);
     }
@@ -194 +195 @@
     /// \pre The heap must be nonempty.
     Item top() const {
-      return data[0].first;
+      return _data[0].first;
     }
 
@@ -202 +203 @@
     /// \pre The heap must be nonempty.
     Prio prio() const {
-      return data[0].second;
+      return _data[0].second;
     }
 
@@ -211 +212 @@
     /// \pre The heap must be non-empty.
     void pop() {
-      int n = data.size()-1;
-      iim.set(data[0].first, POST_HEAP);
+      int n = _data.size()-1;
+      _iim.set(_data[0].first, POST_HEAP);
       if (n > 0) {
-        bubble_down(0, data[n], n);
-      }
-      data.pop_back();
+        bubble_down(0, _data[n], n);
+      }
+      _data.pop_back();
     }
 
@@ -225 +226 @@
     /// \pre The item should be in the heap.
     void erase(const Item &i) {
-      int h = iim[i];
-      int n = data.size()-1;
-      iim.set(data[h].first, POST_HEAP);
+      int h = _iim[i];
+      int n = _data.size()-1;
+      _iim.set(_data[h].first, POST_HEAP);
       if( h < n ) {
-        if ( bubble_up(h, data[n]) == h) {
-          bubble_down(h, data[n], n);
+        if ( bubble_up(h, _data[n]) == h) {
+          bubble_down(h, _data[n], n);
         }
       }
-      data.pop_back();
+      _data.pop_back();
     }
 
@@ -240 +241 @@
     ///
     /// This function returns the priority of item \c i.
+    /// \param i The item.
     /// \pre \c i must be in the heap.
-    /// \param i The item.
     Prio operator[](const Item &i) const {
-      int idx = iim[i];
-      return data[idx].second;
+      int idx = _iim[i];
+      return _data[idx].second;
     }
 
@@ -255 +256 @@
     /// \param p The priority.
     void set(const Item &i, const Prio &p) {
-      int idx = iim[i];
+      int idx = _iim[i];
       if( idx < 0 ) {
         push(i,p);
       }
-      else if( comp(p, data[idx].second) ) {
+      else if( _comp(p, _data[idx].second) ) {
         bubble_up(idx, Pair(i,p));
       }
       else {
-        bubble_down(idx, Pair(i,p), data.size());
+        bubble_down(idx, Pair(i,p), _data.size());
       }
     }
@@ -270 +271 @@
     ///
     /// This method decreases the priority of item \c i to \c p.
+    /// \param i The item.
+    /// \param p The priority.
     /// \pre \c i must be stored in the heap with priority at least \c
     /// p relative to \c Compare.
+    void decrease(const Item &i, const Prio &p) {
+      int idx = _iim[i];
+      bubble_up(idx, Pair(i,p));
+    }
+
+    /// \brief Increases the priority of \c i to \c p.
+    ///
+    /// This method sets the priority of item \c i to \c p.
     /// \param i The item.
     /// \param p The priority.
-    void decrease(const Item &i, const Prio &p) {
-      int idx = iim[i];
-      bubble_up(idx, Pair(i,p));
-    }
-
-    /// \brief Increases the priority of \c i to \c p.
-    ///
-    /// This method sets the priority of item \c i to \c p.
     /// \pre \c i must be stored in the heap with priority at most \c
     /// p relative to \c Compare.
-    /// \param i The item.
-    /// \param p The priority.
     void increase(const Item &i, const Prio &p) {
-      int idx = iim[i];
-      bubble_down(idx, Pair(i,p), data.size());
+      int idx = _iim[i];
+      bubble_down(idx, Pair(i,p), _data.size());
     }
 
@@ -300 +301 @@
     /// \param i The item.
     State state(const Item &i) const {
-      int s = iim[i];
+      int s = _iim[i];
       if( s>=0 )
         s=0;
@@ -320 +321 @@
           erase(i);
         }
-        iim[i] = st;
+        _iim[i] = st;
         break;
       case IN_HEAP:
@@ -334 +335 @@
     /// with the same prioriority as prevoiusly the \c i item.
     void replace(const Item& i, const Item& j) {
-      int idx = iim[i];
-      iim.set(i, iim[j]);
-      iim.set(j, idx);
-      data[idx].first = j;
+      int idx = _iim[i];
+      _iim.set(i, _iim[j]);
+      _iim.set(j, idx);
+      _data[idx].first = j;
     }
 

lemon/bits/array_map.h

@@ -48 +48 @@
   public:
     // The graph type.
-    typedef _Graph Graph;
+    typedef _Graph GraphType;
     // The item type.
     typedef _Item Item;
@@ -64 +64 @@
     typedef _Value& Reference;
 
+    // The map type.
+    typedef ArrayMap Map;
+
     // The notifier type.
     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
 
+  private:
+  
     // The MapBase of the Map which imlements the core regisitry function.
     typedef typename Notifier::ObserverBase Parent;
 
-  private:
     typedef std::allocator<Value> Allocator;
 
@@ -78 +82 @@
     //
     // Graph initialized map constructor.
-    explicit ArrayMap(const Graph& graph) {
+    explicit ArrayMap(const GraphType& graph) {
       Parent::attach(graph.notifier(Item()));
       allocate_memory();
@@ -92 +96 @@
     //
     // It constructs a map and initialize all of the the map.
-    ArrayMap(const Graph& graph, const Value& value) {
+    ArrayMap(const GraphType& graph, const Value& value) {
       Parent::attach(graph.notifier(Item()));
       allocate_memory();
@@ -136 +140 @@
     // \brief Template assign operator.
     //
-    // The given parameter should be conform to the ReadMap
+    // The given parameter should conform to the ReadMap
     // concecpt and could be indiced by the current item set of
     // the NodeMap. In this case the value for each item

lemon/bits/default_map.h

@@ -20 +20 @@
 #define LEMON_BITS_DEFAULT_MAP_H
 
+#include <lemon/config.h>
 #include <lemon/bits/array_map.h>
 #include <lemon/bits/vector_map.h>
@@ -97 +98 @@
 
 
-#if defined __GNUC__ && !defined __STRICT_ANSI__
+#if defined LEMON_HAVE_LONG_LONG
 
   // long long
@@ -153 +154 @@
   class DefaultMap
     : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
+    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
+
   public:
-    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     typedef DefaultMap<_Graph, _Item, _Value> Map;
-
-    typedef typename Parent::Graph Graph;
+    
+    typedef typename Parent::GraphType GraphType;
     typedef typename Parent::Value Value;
 
-    explicit DefaultMap(const Graph& graph) : Parent(graph) {}
-    DefaultMap(const Graph& graph, const Value& value)
+    explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
+    DefaultMap(const GraphType& graph, const Value& value)
       : Parent(graph, value) {}
 

lemon/bits/graph_adaptor_extender.h

@@ -23 +23 @@
 #include <lemon/error.h>
 
-#include <lemon/bits/default_map.h>
-
 namespace lemon {
 
   template <typename _Digraph>
   class DigraphAdaptorExtender : public _Digraph {
+    typedef _Digraph Parent;
+
   public:
 
-    typedef _Digraph Parent;
     typedef _Digraph Digraph;
     typedef DigraphAdaptorExtender Adaptor;
@@ -176 +175 @@
   template <typename _Graph>
   class GraphAdaptorExtende