COIN-OR::LEMON - Graph Library

Ignore:
Files:
46 added
13 deleted
95 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r479 r610  
    2323lemon/stamp-h2
    2424doc/Doxyfile
     25cmake/version.cmake
    2526.dirstamp
    2627.libs/*
     
    4041^autom4te.cache/.*
    4142^build-aux/.*
    42 ^objs.*/.*
     43^.*objs.*/.*
    4344^test/[a-z_]*$
    4445^tools/[a-z-_]*$
    4546^demo/.*_demo$
    46 ^build/.*
     47^.*build.*/.*
    4748^doc/gen-images/.*
    4849CMakeFiles
  • CMakeLists.txt

    r274 r727  
    22
    33SET(PROJECT_NAME "LEMON")
    4 SET(PROJECT_VERSION "hg-tip" CACHE STRING "The version string.")
    5 
    64PROJECT(${PROJECT_NAME})
    75
    8 SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
     6IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     7  INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     8ELSEIF(DEFINED ENV{LEMON_VERSION})
     9  SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
     10ELSE()
     11  EXECUTE_PROCESS(
     12    COMMAND hg id -i
     13    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     14    OUTPUT_VARIABLE HG_REVISION
     15    ERROR_QUIET
     16    OUTPUT_STRIP_TRAILING_WHITESPACE
     17  )
     18  IF(HG_REVISION STREQUAL "")
     19    SET(HG_REVISION "hg-tip")
     20  ENDIF()
     21  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
     22ENDIF()
    923
    10 INCLUDE(FindDoxygen)
    11 INCLUDE(FindGhostscript)
     24SET(PROJECT_VERSION ${LEMON_VERSION})
     25
     26SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
     27
     28FIND_PACKAGE(Doxygen)
     29FIND_PACKAGE(Ghostscript)
     30FIND_PACKAGE(GLPK 4.33)
     31FIND_PACKAGE(CPLEX)
     32FIND_PACKAGE(COIN)
     33
     34INCLUDE(CheckTypeSize)
     35CHECK_TYPE_SIZE("long long" LONG_LONG)
     36SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    1237
    1338ENABLE_TESTING()
    1439
    1540ADD_SUBDIRECTORY(lemon)
    16 ADD_SUBDIRECTORY(demo)
    17 ADD_SUBDIRECTORY(doc)
    18 ADD_SUBDIRECTORY(test)
     41IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     42  ADD_SUBDIRECTORY(demo)
     43  ADD_SUBDIRECTORY(tools)
     44  ADD_SUBDIRECTORY(doc)
     45  ADD_SUBDIRECTORY(test)
     46ENDIF()
    1947
    20 IF(WIN32)
    21   INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico
    22     DESTINATION bin)
    23 ENDIF(WIN32)
     48CONFIGURE_FILE(
     49  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
     50  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     51  @ONLY
     52)
     53IF(UNIX)
     54  INSTALL(
     55    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     56    DESTINATION share/lemon/cmake
     57  )
     58ELSEIF(WIN32)
     59  INSTALL(
     60    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     61    DESTINATION cmake
     62  )
     63ENDIF()
    2464
    25 IF(WIN32)
     65IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
    2666  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    27   SET(CPACK_PACKAGE_VENDOR
    28     "EGRES - Egervary Research Group on Combinatorial Optimization")
     67  SET(CPACK_PACKAGE_VENDOR "EGRES")
    2968  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
    30     "LEMON - Library of Efficient Models and Optimization in Networks")
    31   SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
     69    "LEMON - Library for Efficient Modeling and Optimization in Networks")
     70  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
    3271
    3372  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     
    3877    "${PROJECT_NAME} ${PROJECT_VERSION}")
    3978
    40   # Variables to generate a component-based installer.
    41   #SET(CPACK_COMPONENTS_ALL headers library html_documentation)
     79  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
    4280
    43   #SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    44   #SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Static library")
    45   #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
     81  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
     82  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     83  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
     84  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    4685
    47   #SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
    48   #  "C++ header files for use with the LEMON library")
    49   #SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    50   #  "Static library used to build programs with LEMON")
    51   #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    52   #  "Doxygen generated documentation")
     86  SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
     87    "C++ header files")
     88  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     89    "DLL and import library")
     90  SET(CPACK_COMPONENT_BIN_DESCRIPTION
     91    "Command line utilities")
     92  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     93    "Doxygen generated documentation")
    5394
    54   #SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     95  SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
    5596
    56   #SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
    57   #SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
    58   #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     97  SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     98  SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     99  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
    59100
    60   #SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
    61   #  "Components needed to develop software using LEMON")
    62   #SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
    63   #  "Documentation of LEMON")
     101  SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
     102    "Components needed to develop software using LEMON")
     103  SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
     104    "Documentation of LEMON")
    64105
    65   #SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     106  SET(CPACK_ALL_INSTALL_TYPES Full Developer)
    66107
    67   #SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
    68   #SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
    69   #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
     108  SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
     109  SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
     110  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
    70111
    71112  SET(CPACK_GENERATOR "NSIS")
    72   SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
    73   SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
    74   #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
     113  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
     114  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     115  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
    75116  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    76117  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     
    79120  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
    80121  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
    81     CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\"
     122    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
    82123    ")
    83124  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
     
    87128
    88129  INCLUDE(CPack)
    89 ENDIF(WIN32)
     130ENDIF()
  • INSTALL

    r318 r615  
    55tarballs and successfully extracted it. The latest version of LEMON is
    66available at our web page (http://lemon.cs.elte.hu/).
     7
     8LEMON provides two different build environments, one is based on "autotool",
     9while the other is based on "cmake". This file contains instructions only for
     10the former one, which is the recommended build environment on Linux, Mac OSX
     11and other unices or if you use Cygwin on Windows. For cmake installation
     12instructions visit http://lemon.cs.elte.hu.
    713
    814In order to install LEMON from the extracted source tarball you have to
     
    2228
    2329      This command compiles the non-template part of LEMON into libemon.a
    24       file. It also compiles the programs in the tools and demo subdirectories
    25       when enabled.
     30      file. It also compiles the programs in the tools subdirectory by
     31      default.
    2632
    2733   4. `make check'
     
    6975
    7076  Set the installation prefix to PREFIX. By default it is /usr/local.
    71 
    72 --enable-demo
    73 
    74    Build the examples in the demo subdirectory.
    75 
    76 --disable-demo
    77 
    78    Do not build the examples in the demo subdirectory (default).
    7977
    8078--enable-tools
     
    153151
    154152   Disable SoPlex support.
     153
     154--with-coin[=PREFIX]
     155
     156   Enable support for COIN-OR solvers (CLP and CBC). You should
     157   specify the prefix too. (by default, COIN-OR tools install
     158   themselves to the source code directory). This command enables the
     159   solvers that are actually found.
     160
     161--with-coin-includedir=DIR
     162
     163   The directory where the COIN-OR header files are located. This is
     164   only useful when the COIN-OR headers and libraries are not under
     165   the same prefix (which is unlikely).
     166
     167--with-coin-libdir=DIR
     168
     169   The directory where the COIN-OR libraries are located. This is only
     170   useful when the COIN-OR headers and libraries are not under the
     171   same prefix (which is unlikely).
     172
     173--without-coin
     174
     175   Disable COIN-OR support.
  • LICENSE

    r463 r600  
    1 LEMON code without an explicit copyright is covered by the following
     1LEMON code without an explicit copyright notice is covered by the following
    22copyright/license.
    33
     
    55Kutatocsoport (Egervary Combinatorial Optimization Research Group,
    66EGRES).
     7
     8===========================================================================
     9Boost Software License, Version 1.0
     10===========================================================================
    711
    812Permission is hereby granted, free of charge, to any person or organization
     
    2731ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
    2832DEALINGS IN THE SOFTWARE.
    29 
    30 ===========================================================================
    31 This license is a verbatim copy of the Boost Software License, Version 1.0.
    32 
    33 
  • Makefile.am

    r375 r676  
    1212        m4/lx_check_glpk.m4 \
    1313        m4/lx_check_soplex.m4 \
     14        m4/lx_check_coin.m4 \
    1415        CMakeLists.txt \
    15         cmake
     16        cmake/FindGhostscript.cmake \
     17        cmake/FindCPLEX.cmake \
     18        cmake/FindGLPK.cmake \
     19        cmake/FindCOIN.cmake \
     20        cmake/version.cmake.in \
     21        cmake/version.cmake \
     22        cmake/nsis/lemon.ico \
     23        cmake/nsis/uninstall.ico
    1624
    1725pkgconfigdir = $(libdir)/pkgconfig
     
    3543include test/Makefile.am
    3644include doc/Makefile.am
    37 include demo/Makefile.am
    3845include tools/Makefile.am
     46
     47DIST_SUBDIRS = demo
     48
     49demo:
     50        $(MAKE) $(AM_MAKEFLAGS) -C demo
    3951
    4052MRPROPERFILES = \
     
    6476        bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
    6577
    66 .PHONY: mrproper dist-bz2 distcheck-bz2
     78.PHONY: demo mrproper dist-bz2 distcheck-bz2
  • NEWS

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

    r318 r705  
    1 ==================================================================
    2 LEMON - a Library of Efficient Models and Optimization in Networks
    3 ==================================================================
     1=====================================================================
     2LEMON - a Library for Efficient Modeling and Optimization in Networks
     3=====================================================================
    44
    55LEMON is an open source library written in C++. It provides
  • cmake/FindGhostscript.cmake

    r225 r520  
    44  NAMES gs gswin32c
    55  PATHS "$ENV{ProgramFiles}/gs"
    6   PATH_SUFFIXES gs8.61/bin gs8.62/bin
     6  PATH_SUFFIXES gs8.61/bin gs8.62/bin gs8.63/bin gs8.64/bin gs8.65/bin
    77  DOC "Ghostscript: PostScript and PDF language interpreter and previewer."
    88)
  • configure.ac

    r482 r727  
    33dnl Version information.
    44m4_define([lemon_version_number],
    5         [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
     5          [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
    66dnl m4_define([lemon_version_number], [])
    77m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
    8 m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
     8m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i 2> /dev/null]))])
    99m4_define([lemon_version], [ifelse(lemon_version_number(),
    10                            [],
    11                            [lemon_hg_path().lemon_hg_revision()],
    12                            [lemon_version_number()])])
     10                           [],
     11                           [ifelse(lemon_hg_revision(),
     12                           [],
     13                           [hg-tip],
     14                           [lemon_hg_path().lemon_hg_revision()])],
     15                           [lemon_version_number()])])
    1316
    1417AC_PREREQ([2.59])
     
    2023AC_CONFIG_HEADERS([config.h lemon/config.h])
    2124
     25AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string])
     26
    2227dnl Do compilation tests using the C++ compiler.
    2328AC_LANG([C++])
     29
     30dnl Check the existence of long long type.
     31AC_CHECK_TYPE(long long, [long_long_found=yes], [long_long_found=no])
     32if test x"$long_long_found" = x"yes"; then
     33  AC_DEFINE([LEMON_HAVE_LONG_LONG], [1], [Define to 1 if you have long long.])
     34fi
    2435
    2536dnl Checks for programs.
     
    5465LX_CHECK_CPLEX
    5566LX_CHECK_SOPLEX
    56 LX_CHECK_CLP
     67LX_CHECK_COIN
    5768
    5869AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
    5970AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
    60 
    61 dnl Disable/enable building the demo programs.
    62 AC_ARG_ENABLE([demo],
    63 AS_HELP_STRING([--enable-demo], [build the demo programs])
    64 AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
    65               [], [enable_demo=no])
    66 AC_MSG_CHECKING([whether to build the demo programs])
    67 if test x"$enable_demo" != x"no"; then
    68   AC_MSG_RESULT([yes])
    69 else
    70   AC_MSG_RESULT([no])
    71 fi
    72 AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
    7371
    7472dnl Disable/enable building the binary tools.
     
    10199dnl Add dependencies on files generated by configure.
    102100AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
    103   ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in'])
     101  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
    104102
    105103AC_CONFIG_FILES([
    106104Makefile
     105demo/Makefile
     106cmake/version.cmake
    107107doc/Doxyfile
    108108lemon/lemon.pc
     
    119119echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    120120echo
     121echo Compiler supports long long... : $long_long_found
     122echo
    121123echo GLPK support.................. : $lx_glpk_found
    122124echo CPLEX support................. : $lx_cplex_found
    123125echo SOPLEX support................ : $lx_soplex_found
    124126echo CLP support................... : $lx_clp_found
     127echo CBC support................... : $lx_cbc_found
    125128echo
    126 echo Build demo programs........... : $enable_demo
    127129echo Build additional tools........ : $enable_tools
    128130echo
  • demo/CMakeLists.txt

    r225 r726  
    1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(
     2  ${PROJECT_SOURCE_DIR}
     3  ${PROJECT_BINARY_DIR}
     4)
    25
    3 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
     6LINK_DIRECTORIES(
     7  ${PROJECT_BINARY_DIR}/lemon
     8)
    49
    510SET(DEMOS
    611  arg_parser_demo
    712  graph_to_eps_demo
    8   lgf_demo)
     13  lgf_demo
     14)
    915
    1016FOREACH(DEMO_NAME ${DEMOS})
    1117  ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc)
    1218  TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
    13 ENDFOREACH(DEMO_NAME)
     19ENDFOREACH()
  • demo/Makefile.am

    r415 r611  
    1 EXTRA_DIST += \
    2         demo/CMakeLists.txt \
    3         demo/digraph.lgf
     1AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    42
    5 if WANT_DEMO
     3AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
     4LDADD = $(top_builddir)/lemon/libemon.la
    65
    7 noinst_PROGRAMS += \
    8         demo/arg_parser_demo \
    9         demo/graph_to_eps_demo \
    10         demo/lgf_demo
     6EXTRA_DIST = \
     7        CMakeLists.txt \
     8        digraph.lgf
    119
    12 endif WANT_DEMO
     10noinst_PROGRAMS = \
     11        arg_parser_demo \
     12        graph_to_eps_demo \
     13        lgf_demo
    1314
    14 demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc
    15 demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc
    16 demo_lgf_demo_SOURCES = demo/lgf_demo.cc
     15arg_parser_demo_SOURCES = arg_parser_demo.cc
     16graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
     17lgf_demo_SOURCES = lgf_demo.cc
  • demo/graph_to_eps_demo.cc

    r463 r659  
    183183  ListDigraph::NodeMap<Point> hcoords(h);
    184184
    185   int cols=int(sqrt(double(palette.size())));
     185  int cols=int(std::sqrt(double(palette.size())));
    186186  for(int i=0;i<int(paletteW.size());i++) {
    187187    Node n=h.addNode();
  • doc/CMakeLists.txt

    r347 r726  
    11SET(PACKAGE_NAME ${PROJECT_NAME})
    22SET(PACKAGE_VERSION ${PROJECT_VERSION})
    3 SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
    4 SET(abs_top_builddir ${CMAKE_BINARY_DIR})
     3SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
     4SET(abs_top_builddir ${PROJECT_BINARY_DIR})
    55
    66CONFIGURE_FILE(
    7   ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
    8   ${CMAKE_BINARY_DIR}/doc/Doxyfile
    9   @ONLY)
     7  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
     8  ${PROJECT_BINARY_DIR}/doc/Doxyfile
     9  @ONLY
     10)
    1011
    1112IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     13  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
     14  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
     15  ADD_CUSTOM_TARGET(html
     16    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
     17    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
     18    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
     19    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
     20    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
     21    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
     22    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
     23    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
     24    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     25    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
     26    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
     27    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
     28    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
     29    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     30    COMMAND ${CMAKE_COMMAND} -E remove_directory html
     31    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     32    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     33  )
     34
     35  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
     36
    1237  IF(UNIX)
    13     ADD_CUSTOM_TARGET(html
    14       COMMAND rm -rf gen-images
    15       COMMAND mkdir gen-images
    16       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
    17       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
    18       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
    19       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
    20       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
    21       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
    22       COMMAND rm -rf html
    23       COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    24       WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
     38    INSTALL(
     39      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     40      DESTINATION share/doc/lemon/html
     41      COMPONENT html_documentation
     42    )
    2543  ELSEIF(WIN32)
    26     ADD_CUSTOM_TARGET(html
    27       COMMAND if exist gen-images rmdir /s /q gen-images
    28       COMMAND mkdir gen-images
    29       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
    30       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
    31       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
    32       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
    33       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
    34       COMMAND if exist html rmdir /s /q html
    35       COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    36       WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
    37   ENDIF(UNIX)
    38 ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     44    INSTALL(
     45      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     46      DESTINATION doc
     47      COMPONENT html_documentation
     48    )
     49  ENDIF()
    3950
    40 INSTALL(
    41   DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
    42   DESTINATION doc
    43   COMPONENT html_documentation)
     51ENDIF()
  • doc/Makefile.am

    r349 r720  
    99        doc/mainpage.dox \
    1010        doc/migration.dox \
     11        doc/min_cost_flow.dox \
    1112        doc/named-param.dox \
    1213        doc/namespaces.dox \
     
    2223        nodeshape_4.eps
    2324
     25DOC_EPS_IMAGES27 = \
     26        bipartite_matching.eps \
     27        bipartite_partitions.eps \
     28        connected_components.eps \
     29        edge_biconnected_components.eps \
     30        node_biconnected_components.eps \
     31        strongly_connected_components.eps
     32
    2433DOC_EPS_IMAGES = \
    25         $(DOC_EPS_IMAGES18)
     34        $(DOC_EPS_IMAGES18) \
     35        $(DOC_EPS_IMAGES27)
    2636
    2737DOC_PNG_IMAGES = \
     
    3949        if test ${gs_found} = yes; then \
    4050          $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \
     51        else \
     52          echo; \
     53          echo "Ghostscript not found."; \
     54          echo; \
     55          exit 1; \
     56        fi
     57
     58$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
     59        -mkdir doc/gen-images
     60        if test ${gs_found} = yes; then \
     61          $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \
    4162        else \
    4263          echo; \
     
    7192install-html-local: doc/html
    7293        @$(NORMAL_INSTALL)
    73         $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
     94        $(mkinstalldirs) $(DESTDIR)$(htmldir)/html
    7495        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    7596          f="`echo $$p | sed -e 's|^.*/||'`"; \
    76           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
    77           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
     97          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
     98          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
    7899        done
    79100
     
    82103        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    83104          f="`echo $$p | sed -e 's|^.*/||'`"; \
    84           echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
    85           rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
     105          echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
     106          rm -f $(DESTDIR)$(htmldir)/html/$$f; \
    86107        done
    87108
  • doc/groups.dox

    r478 r844  
    2121/**
    2222@defgroup datas Data Structures
    23 This group describes the several data structures implemented in LEMON.
     23This group contains the several data structures implemented in LEMON.
    2424*/
    2525
     
    139139
    140140/**
    141 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    142 @ingroup graphs
    143 \brief Graph types between real graphs and graph adaptors.
    144 
    145 This group describes some graph types between real graphs and graph adaptors.
    146 These classes wrap graphs to give new functionality as the adaptors do it.
    147 On the other hand they are not light-weight structures as the adaptors.
    148 */
    149 
    150 /**
    151141@defgroup maps Maps
    152142@ingroup datas
    153143\brief Map structures implemented in LEMON.
    154144
    155 This group describes the map structures implemented in LEMON.
     145This group contains the map structures implemented in LEMON.
    156146
    157147LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    166156\brief Special graph-related maps.
    167157
    168 This group describes maps that are specifically designed to assign
     158This group contains maps that are specifically designed to assign
    169159values to the nodes and arcs/edges of graphs.
    170160
     
    178168\brief Tools to create new maps from existing ones
    179169
    180 This group describes map adaptors that are used to create "implicit"
     170This group contains map adaptors that are used to create "implicit"
    181171maps from other maps.
    182172
     
    237227
    238228/**
    239 @defgroup matrices Matrices
    240 @ingroup datas
    241 \brief Two dimensional data storages implemented in LEMON.
    242 
    243 This group describes two dimensional data storages implemented in LEMON.
    244 */
    245 
    246 /**
    247229@defgroup paths Path Structures
    248230@ingroup datas
    249231\brief %Path structures implemented in LEMON.
    250232
    251 This group describes the path structures implemented in LEMON.
     233This group contains the path structures implemented in LEMON.
    252234
    253235LEMON provides flexible data structures to work with paths.
     
    265247\brief Auxiliary data structures implemented in LEMON.
    266248
    267 This group describes some data structures implemented in LEMON in
     249This group contains some data structures implemented in LEMON in
    268250order to make it easier to implement combinatorial algorithms.
    269251*/
     
    271253/**
    272254@defgroup algs Algorithms
    273 \brief This group describes the several algorithms
     255\brief This group contains the several algorithms
    274256implemented in LEMON.
    275257
    276 This group describes the several algorithms
     258This group contains the several algorithms
    277259implemented in LEMON.
    278260*/
     
    283265\brief Common graph search algorithms.
    284266
    285 This group describes the common graph search algorithms, namely
     267This group contains the common graph search algorithms, namely
    286268\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    287269*/
     
    292274\brief Algorithms for finding shortest paths.
    293275
    294 This group describes the algorithms for finding shortest paths in digraphs.
    295 
    296  - \ref Dijkstra algorithm for finding shortest paths from a source node
    297    when all arc lengths are non-negative.
    298  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
    299    from a source node when arc lenghts can be either positive or negative,
    300    but the digraph should not contain directed cycles with negative total
    301    length.
    302  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    303    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    304    lenghts can be either positive or negative, but the digraph should
    305    not contain directed cycles with negative total length.
     276This group contains the algorithms for finding shortest paths in digraphs.
     277
     278 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
     279   source node when all arc lengths are non-negative.
    306280 - \ref Suurballe A successive shortest path algorithm for finding
    307281   arc-disjoint paths between two nodes having minimum total length.
     
    313287\brief Algorithms for finding maximum flows.
    314288
    315 This group describes the algorithms for finding maximum flows and
     289This group contains the algorithms for finding maximum flows and
    316290feasible circulations.
    317291
    318292The \e maximum \e flow \e problem is to find a flow of maximum value between
    319293a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    320 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     294digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    321295\f$s, t \in V\f$ source and target nodes.
    322 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
     296A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
    323297following optimization problem.
    324298
    325 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
    326 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
    327     \qquad \forall v\in V\setminus\{s,t\} \f]
    328 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
    329 
    330 LEMON contains several algorithms for solving maximum flow problems:
    331 - \ref EdmondsKarp Edmonds-Karp algorithm.
    332 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    333 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    334 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    335 
    336 In most cases the \ref Preflow "Preflow" algorithm provides the
    337 fastest method for computing a maximum flow. All implementations
    338 provides functions to also query the minimum cut, which is the dual
    339 problem of the maximum flow.
    340 */
    341 
    342 /**
    343 @defgroup min_cost_flow Minimum Cost Flow Algorithms
     299\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     300\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     301    \quad \forall u\in V\setminus\{s,t\} \f]
     302\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
     303
     304\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
     305Tarjan for solving this problem. It also provides functions to query the
     306minimum cut, which is the dual problem of maximum flow.
     307
     308
     309\ref Circulation is a preflow push-relabel algorithm implemented directly
     310for finding feasible circulations, which is a somewhat different problem,
     311but it is strongly related to maximum flow.
     312For more information, see \ref Circulation.
     313*/
     314
     315/**
     316@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    344317@ingroup algs
    345318
    346319\brief Algorithms for finding minimum cost flows and circulations.
    347320
    348 This group describes the algorithms for finding minimum cost flows and
    349 circulations.
    350 
    351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    352 minimum total cost from a set of supply nodes to a set of demand nodes
    353 in a network with capacity constraints and arc costs.
    354 Formally, let \f$G=(V,A)\f$ be a digraph,
    355 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
    356 upper bounds for the flow values on the arcs,
    357 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
    358 on the arcs, and
    359 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
    360 of the nodes.
    361 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
    362 the following optimization problem.
    363 
    364 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
    365 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
    366     supply(v) \qquad \forall v\in V \f]
    367 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
    368 
    369 LEMON contains several algorithms for solving minimum cost flow problems:
    370  - \ref CycleCanceling Cycle-canceling algorithms.
    371  - \ref CapacityScaling Successive shortest path algorithm with optional
    372    capacity scaling.
    373  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
    374    cost scaling.
    375  - \ref NetworkSimplex Primal network simplex algorithm with various
    376    pivot strategies.
     321This group contains the algorithms for finding minimum cost flows and
     322circulations. For more information about this problem and its dual
     323solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     324
     325\ref NetworkSimplex is an efficient implementation of the primal Network
     326Simplex algorithm for finding minimum cost flows. It also provides dual
     327solution (node potentials), if an optimal flow is found.
    377328*/
    378329
     
    383334\brief Algorithms for finding minimum cut in graphs.
    384335
    385 This group describes the algorithms for finding minimum cut in graphs.
     336This group contains the algorithms for finding minimum cut in graphs.
    386337
    387338The \e minimum \e cut \e problem is to find a non-empty and non-complete
     
    398349- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    399350  in directed graphs.
    400 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    401   calculating minimum cut in undirected graphs.
    402 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
     351- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    403352  all-pairs minimum cut in undirected graphs.
    404353
     
    408357
    409358/**
    410 @defgroup graph_prop Connectivity and Other Graph Properties
     359@defgroup graph_properties Connectivity and Other Graph Properties
    411360@ingroup algs
    412361\brief Algorithms for discovering the graph properties
    413362
    414 This group describes the algorithms for discovering the graph properties
     363This group contains the algorithms for discovering the graph properties
    415364like connectivity, bipartiteness, euler property, simplicity etc.
    416365
     
    420369
    421370/**
    422 @defgroup planar Planarity Embedding and Drawing
    423 @ingroup algs
    424 \brief Algorithms for planarity checking, embedding and drawing
    425 
    426 This group describes the algorithms for planarity checking,
    427 embedding and drawing.
    428 
    429 \image html planar.png
    430 \image latex planar.eps "Plane graph" width=\textwidth
    431 */
    432 
    433 /**
    434371@defgroup matching Matching Algorithms
    435372@ingroup algs
    436373\brief Algorithms for finding matchings in graphs and bipartite graphs.
    437374
    438 This group contains algorithm objects and functions to calculate
    439 matchings in graphs and bipartite graphs. The general matching problem is
    440 finding a subset of the arcs which does not shares common endpoints.
     375This group contains the algorithms for calculating matchings in graphs.
     376The general matching problem is finding a subset of the edges for which
     377each node has at most one incident edge.
    441378
    442379There are several different algorithms for calculate matchings in
    443 graphs.  The matching problems in bipartite graphs are generally
    444 easier than in general graphs. The goal of the matching optimization
     380graphs. The goal of the matching optimization
    445381can be finding maximum cardinality, maximum weight or minimum cost
    446382matching. The search can be constrained to find perfect or
     
    448384
    449385The matching algorithms implemented in LEMON:
    450 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    451   for calculating maximum cardinality matching in bipartite graphs.
    452 - \ref PrBipartiteMatching Push-relabel algorithm
    453   for calculating maximum cardinality matching in bipartite graphs.
    454 - \ref MaxWeightedBipartiteMatching
    455   Successive shortest path algorithm for calculating maximum weighted
    456   matching and maximum weighted bipartite matching in bipartite graphs.
    457 - \ref MinCostMaxBipartiteMatching
    458   Successive shortest path algorithm for calculating minimum cost maximum
    459   matching in bipartite graphs.
    460386- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    461387  maximum cardinality matching in general graphs.
     
    473399@defgroup spantree Minimum Spanning Tree Algorithms
    474400@ingroup algs
    475 \brief Algorithms for finding a minimum cost spanning tree in a graph.
    476 
    477 This group describes the algorithms for finding a minimum cost spanning
    478 tree in a graph.
     401\brief Algorithms for finding minimum cost spanning trees and arborescences.
     402
     403This group contains the algorithms for finding minimum cost spanning
     404trees and arborescences.
    479405*/
    480406
     
    484410\brief Auxiliary algorithms implemented in LEMON.
    485411
    486 This group describes some algorithms implemented in LEMON
     412This group contains some algorithms implemented in LEMON
    487413in order to make it easier to implement complex algorithms.
    488414*/
    489415
    490416/**
    491 @defgroup approx Approximation Algorithms
    492 @ingroup algs
    493 \brief Approximation algorithms.
    494 
    495 This group describes the approximation and heuristic algorithms
     417@defgroup gen_opt_group General Optimization Tools
     418\brief This group contains some general optimization frameworks
    496419implemented in LEMON.
    497 */
    498 
    499 /**
    500 @defgroup gen_opt_group General Optimization Tools
    501 \brief This group describes some general optimization frameworks
    502 implemented in LEMON.
    503 
    504 This group describes some general optimization frameworks
     420
     421This group contains some general optimization frameworks
    505422implemented in LEMON.
    506423*/
     
    511428\brief Lp and Mip solver interfaces for LEMON.
    512429
    513 This group describes Lp and Mip solver interfaces for LEMON. The
     430This group contains Lp and Mip solver interfaces for LEMON. The
    514431various LP solvers could be used in the same manner with this
    515432interface.
    516 */
    517 
    518 /**
    519 @defgroup lp_utils Tools for Lp and Mip Solvers
    520 @ingroup lp_group
    521 \brief Helper tools to the Lp and Mip solvers.
    522 
    523 This group adds some helper tools to general optimization framework
    524 implemented in LEMON.
    525 */
    526 
    527 /**
    528 @defgroup metah Metaheuristics
    529 @ingroup gen_opt_group
    530 \brief Metaheuristics for LEMON library.
    531 
    532 This group describes some metaheuristic optimization tools.
    533433*/
    534434
     
    545445\brief Simple basic graph utilities.
    546446
    547 This group describes some simple basic graph utilities.
     447This group contains some simple basic graph utilities.
    548448*/
    549449
     
    553453\brief Tools for development, debugging and testing.
    554454
    555 This group describes several useful tools for development,
     455This group contains several useful tools for development,
    556456debugging and testing.
    557457*/
     
    562462\brief Simple tools for measuring the performance of algorithms.
    563463
    564 This group describes simple tools for measuring the performance
     464This group contains simple tools for measuring the performance
    565465of algorithms.
    566466*/
     
    571471\brief Exceptions defined in LEMON.
    572472
    573 This group describes the exceptions defined in LEMON.
     473This group contains the exceptions defined in LEMON.
    574474*/
    575475
     
    578478\brief Graph Input-Output methods
    579479
    580 This group describes the tools for importing and exporting graphs
     480This group contains the tools for importing and exporting graphs
    581481and graph related data. Now it supports the \ref lgf-format
    582482"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    589489\brief Reading and writing LEMON Graph Format.
    590490
    591 This group describes methods for reading and writing
     491This group contains methods for reading and writing
    592492\ref lgf-format "LEMON Graph Format".
    593493*/
     
    598498\brief General \c EPS drawer and graph exporter
    599499
    600 This group describes general \c EPS drawing methods and special
     500This group contains general \c EPS drawing methods and special
    601501graph exporting tools.
    602502*/
     
    622522\brief Skeleton classes and concept checking classes
    623523
    624 This group describes the data/algorithm skeletons and concept checking
     524This group contains the data/algorithm skeletons and concept checking
    625525classes implemented in LEMON.
    626526
     
    652552\brief Skeleton and concept checking classes for graph structures
    653553
    654 This group describes the skeletons and concept checking classes of LEMON's
     554This group contains the skeletons and concept checking classes of LEMON's
    655555graph structures and helper classes used to implement these.
    656556*/
     
    661561\brief Skeleton and concept checking classes for maps
    662562
    663 This group describes the skeletons and concept checking classes of maps.
     563This group contains the skeletons and concept checking classes of maps.
    664564*/
    665565
     
    672572the \c demo subdirectory of the source tree.
    673573
    674 It order to compile them, use <tt>--enable-demo</tt> configure option when
    675 build the library.
     574In order to compile them, use the <tt>make demo</tt> or the
     575<tt>make check</tt> commands.
    676576*/
    677577
  • doc/mainpage.dox

    r463 r705  
    2424\subsection whatis What is LEMON
    2525
    26 LEMON stands for
    27 <b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
     26LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
    2827and <b>O</b>ptimization in <b>N</b>etworks.
    2928It is a C++ template
     
    4241\subsection howtoread How to read the documentation
    4342
    44 If you want to get a quick start and see the most important features then
    45 take a look at our \ref quicktour
    46 "Quick Tour to LEMON" which will guide you along.
     43If you would like to get to know the library, see
     44<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    4745
    48 If you already feel like using our library, see the page that tells you
    49 \ref getstart "How to start using LEMON".
    50 
    51 If you
    52 want to see how LEMON works, see
    53 some \ref demoprograms "demo programs".
    54 
    55 If you know what you are looking for then try to find it under the
    56 <a class="el" href="modules.html">Modules</a>
    57 section.
     46If you know what you are looking for, then try to find it under the
     47<a class="el" href="modules.html">Modules</a> section.
    5848
    5949If you are a user of the old (0.x) series of LEMON, please check out the
  • lemon/CMakeLists.txt

    r482 r726  
    1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(
     2  ${PROJECT_SOURCE_DIR}
     3  ${PROJECT_BINARY_DIR}
     4)
    25
    3 ADD_LIBRARY(lemon
     6CONFIGURE_FILE(
     7  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
     8  ${CMAKE_CURRENT_BINARY_DIR}/config.h
     9)
     10
     11SET(LEMON_SOURCES
    412  arg_parser.cc
    513  base.cc
    614  color.cc
    7   random.cc)
     15  lp_base.cc
     16  lp_skeleton.cc
     17  random.cc
     18  bits/windows.cc
     19)
     20
     21IF(LEMON_HAVE_GLPK)
     22  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
     23  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
     24  IF(WIN32)
     25    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
     26    INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
     27    INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
     28  ENDIF()
     29ENDIF()
     30
     31IF(LEMON_HAVE_CPLEX)
     32  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
     33  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
     34ENDIF()
     35
     36IF(LEMON_HAVE_CLP)
     37  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
     38  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     39ENDIF()
     40
     41IF(LEMON_HAVE_CBC)
     42  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
     43  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     44ENDIF()
     45
     46ADD_LIBRARY(lemon ${LEMON_SOURCES})
     47IF(UNIX)
     48  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
     49ENDIF()
    850
    951INSTALL(
    1052  TARGETS lemon
    1153  ARCHIVE DESTINATION lib
    12   COMPONENT library)
     54  COMPONENT library
     55)
    1356
    1457INSTALL(
     
    1659  DESTINATION include/lemon
    1760  COMPONENT headers
    18   FILES_MATCHING PATTERN "*.h")
     61  FILES_MATCHING PATTERN "*.h"
     62)
     63
     64INSTALL(
     65  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
     66  DESTINATION include/lemon
     67  COMPONENT headers
     68)
  • lemon/Makefile.am

    r547 r850  
    11EXTRA_DIST += \
    22        lemon/lemon.pc.in \
    3         lemon/CMakeLists.txt
     3        lemon/CMakeLists.txt \
     4        lemon/config.h.cmake
    45
    56pkgconfig_DATA += lemon/lemon.pc
     
    1314        lemon/lp_base.cc \
    1415        lemon/lp_skeleton.cc \
    15         lemon/random.cc
     16        lemon/random.cc \
     17        lemon/bits/windows.cc
    1618
     19nodist_lemon_HEADERS = lemon/config.h   
    1720
    1821lemon_libemon_la_CXXFLAGS = \
     22        $(AM_CXXFLAGS) \
    1923        $(GLPK_CFLAGS) \
    2024        $(CPLEX_CFLAGS) \
    2125        $(SOPLEX_CXXFLAGS) \
    22         $(CLP_CXXFLAGS)
     26        $(CLP_CXXFLAGS) \
     27        $(CBC_CXXFLAGS)
    2328
    2429lemon_libemon_la_LDFLAGS = \
     
    2631        $(CPLEX_LIBS) \
    2732        $(SOPLEX_LIBS) \
    28         $(CLP_LIBS)
     33        $(CLP_LIBS) \
     34        $(CBC_LIBS)
    2935
    3036if HAVE_GLPK
    31 lemon_libemon_la_SOURCES += lemon/lp_glpk.cc
     37lemon_libemon_la_SOURCES += lemon/glpk.cc
    3238endif
    3339
    3440if HAVE_CPLEX
    35 lemon_libemon_la_SOURCES += lemon/lp_cplex.cc
     41lemon_libemon_la_SOURCES += lemon/cplex.cc
    3642endif
    3743
    3844if HAVE_SOPLEX
    39 lemon_libemon_la_SOURCES += lemon/lp_soplex.cc
     45lemon_libemon_la_SOURCES += lemon/soplex.cc
    4046endif
    4147
    4248if HAVE_CLP
    43 lemon_libemon_la_SOURCES += lemon/lp_clp.cc
     49lemon_libemon_la_SOURCES += lemon/clp.cc
     50endif
     51
     52if HAVE_CBC
     53lemon_libemon_la_SOURCES += lemon/cbc.cc
    4454endif
    4555
     
    5060        lemon/bfs.h \
    5161        lemon/bin_heap.h \
     62        lemon/cbc.h \
    5263        lemon/circulation.h \
     64        lemon/clp.h \
    5365        lemon/color.h \
    5466        lemon/concept_check.h \
     67        lemon/connectivity.h \
    5568        lemon/counter.h \
    5669        lemon/core.h \
     70        lemon/cplex.h \
    5771        lemon/dfs.h \
    5872        lemon/dijkstra.h \
    5973        lemon/dim2.h \
    6074        lemon/dimacs.h \
     75        lemon/edge_set.h \
    6176        lemon/elevator.h \
    6277        lemon/error.h \
     78        lemon/euler.h \
    6379        lemon/full_graph.h \
     80        lemon/glpk.h \
     81        lemon/gomory_hu.h \
    6482        lemon/graph_to_eps.h \
    6583        lemon/grid_graph.h \
     
    7290        lemon/lp.h \
    7391        lemon/lp_base.h \
    74         lemon/lp_clp.h \
    75         lemon/lp_cplex.h \
    76         lemon/lp_glpk.h \
    7792        lemon/lp_skeleton.h \
    78         lemon/lp_soplex.h \
    7993        lemon/maps.h \
     94        lemon/matching.h \
    8095        lemon/math.h \
    81         lemon/max_matching.h \
     96        lemon/min_cost_arborescence.h \
    8297        lemon/nauty_reader.h \
     98        lemon/network_simplex.h \
    8399        lemon/path.h \
    84100        lemon/preflow.h \
     
    86102        lemon/random.h \
    87103        lemon/smart_graph.h \
     104        lemon/soplex.h \
    88105        lemon/suurballe.h \
    89106        lemon/time_measure.h \
    90107        lemon/tolerance.h \
    91         lemon/unionfind.h
     108        lemon/unionfind.h \
     109        lemon/bits/windows.h
    92110
    93111bits_HEADERS += \
    94112        lemon/bits/alteration_notifier.h \
    95113        lemon/bits/array_map.h \
    96         lemon/bits/base_extender.h \
    97114        lemon/bits/bezier.h \
    98115        lemon/bits/default_map.h \
     116        lemon/bits/edge_set_extender.h \
    99117        lemon/bits/enable_if.h \
    100118        lemon/bits/graph_adaptor_extender.h \
  • lemon/adaptors.h

    r478 r703  
    3131
    3232#include <lemon/bits/graph_adaptor_extender.h>
     33#include <lemon/bits/map_extender.h>
    3334#include <lemon/tolerance.h>
    3435
     
    3738namespace lemon {
    3839
    39   template<typename _Digraph>
     40#ifdef _MSC_VER
     41#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED
     42#else
     43#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED
     44#endif
     45
     46  template<typename DGR>
    4047  class DigraphAdaptorBase {
    4148  public:
    42     typedef _Digraph Digraph;
     49    typedef DGR Digraph;
    4350    typedef DigraphAdaptorBase Adaptor;
    44     typedef Digraph ParentDigraph;
    4551
    4652  protected:
    47     Digraph* _digraph;
     53    DGR* _digraph;
    4854    DigraphAdaptorBase() : _digraph(0) { }
    49     void setDigraph(Digraph& digraph) { _digraph = &digraph; }
    50 
    51   public:
    52     DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
    53 
    54     typedef typename Digraph::Node Node;
    55     typedef typename Digraph::Arc Arc;
     55    void initialize(DGR& digraph) { _digraph = &digraph; }
     56
     57  public:
     58    DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }
     59
     60    typedef typename DGR::Node Node;
     61    typedef typename DGR::Arc Arc;
    5662
    5763    void first(Node& i) const { _digraph->first(i); }
     
    6874    Node target(const Arc& a) const { return _digraph->target(a); }
    6975
    70     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
     76    typedef NodeNumTagIndicator<DGR> NodeNumTag;
    7177    int nodeNum() const { return _digraph->nodeNum(); }
    7278
    73     typedef ArcNumTagIndicator<Digraph> ArcNumTag;
     79    typedef ArcNumTagIndicator<DGR> ArcNumTag;
    7480    int arcNum() const { return _digraph->arcNum(); }
    7581
    76     typedef FindArcTagIndicator<Digraph> FindArcTag;
     82    typedef FindArcTagIndicator<DGR> FindArcTag;
    7783    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
    7884      return _digraph->findArc(u, v, prev);
     
    96102    int maxArcId() const { return _digraph->maxArcId(); }
    97103
    98     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
     104    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
    99105    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
    100106
    101     typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
     107    typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
    102108    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
    103109
    104     template <typename _Value>
    105     class NodeMap : public Digraph::template NodeMap<_Value> {
     110    template <typename V>
     111    class NodeMap : public DGR::template NodeMap<V> {
     112      typedef typename DGR::template NodeMap<V> Parent;
     113
    106114    public:
    107 
    108       typedef typename Digraph::template NodeMap<_Value> Parent;
    109 
    110115      explicit NodeMap(const Adaptor& adaptor)
    111116        : Parent(*adaptor._digraph) {}
    112 
    113       NodeMap(const Adaptor& adaptor, const _Value& value)
     117      NodeMap(const Adaptor& adaptor, const V& value)
    114118        : Parent(*adaptor._digraph, value) { }
    115119
     
    127131    };
    128132
    129     template <typename _Value>
    130     class ArcMap : public Digraph::template ArcMap<_Value> {
     133    template <typename V>
     134    class ArcMap : public DGR::template ArcMap<V> {
     135      typedef typename DGR::template ArcMap<V> Parent;
     136
    131137    public:
    132 
    133       typedef typename Digraph::template ArcMap<_Value> Parent;
    134 
    135       explicit ArcMap(const Adaptor& adaptor)
     138      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
    136139        : Parent(*adaptor._digraph) {}
    137 
    138       ArcMap(const Adaptor& adaptor, const _Value& value)
     140      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
    139141        : Parent(*adaptor._digraph, value) {}
    140142
     
    154156  };
    155157
    156   template<typename _Graph>
     158  template<typename GR>
    157159  class GraphAdaptorBase {
    158160  public:
    159     typedef _Graph Graph;
    160     typedef Graph ParentGraph;
     161    typedef GR Graph;
    161162
    162163  protected:
    163     Graph* _graph;
     164    GR* _graph;
    164165
    165166    GraphAdaptorBase() : _graph(0) {}
    166167
    167     void setGraph(Graph& graph) { _graph = &graph; }
    168 
    169   public:
    170     GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
    171 
    172     typedef typename Graph::Node Node;
    173     typedef typename Graph::Arc Arc;
    174     typedef typename Graph::Edge Edge;
     168    void initialize(GR& graph) { _graph = &graph; }
     169
     170  public:
     171    GraphAdaptorBase(GR& graph) : _graph(&graph) {}
     172
     173    typedef typename GR::Node Node;
     174    typedef typename GR::Arc Arc;
     175    typedef typename GR::Edge Edge;
    175176
    176177    void first(Node& i) const { _graph->first(i); }
     
    240241    int maxEdgeId() const { return _graph->maxEdgeId(); }
    241242
    242     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     243    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
    243244    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
    244245
    245     typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
     246    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
    246247    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
    247248
    248     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
     249    typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
    249250    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
    250251
    251     template <typename _Value>
    252     class NodeMap : public Graph::template NodeMap<_Value> {
     252    template <typename V>
     253    class NodeMap : public GR::template NodeMap<V> {
     254      typedef typename GR::template NodeMap<V> Parent;
     255
    253256    public:
    254       typedef typename Graph::template NodeMap<_Value> Parent;
    255       explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
     257      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
    256258        : Parent(*adapter._graph) {}
    257       NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
     259      NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
    258260        : Parent(*adapter._graph, value) {}
    259261
     
    271273    };
    272274
    273     template <typename _Value>
    274     class ArcMap : public Graph::template ArcMap<_Value> {
     275    template <typename V>
     276    class ArcMap : public GR::template ArcMap<V> {
     277      typedef typename GR::template ArcMap<V> Parent;
     278
    275279    public:
    276       typedef typename Graph::template ArcMap<_Value> Parent;
    277       explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
     280      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
    278281        : Parent(*adapter._graph) {}
    279       ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
     282      ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
    280283        : Parent(*adapter._graph, value) {}
    281284
     
    292295    };
    293296
    294     template <typename _Value>
    295     class EdgeMap : public Graph::template EdgeMap<_Value> {
     297    template <typename V>
     298    class EdgeMap : public GR::template EdgeMap<V> {
     299      typedef typename GR::template EdgeMap<V> Parent;
     300
    296301    public:
    297       typedef typename Graph::template EdgeMap<_Value> Parent;
    298       explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
     302      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
    299303        : Parent(*adapter._graph) {}
    300       EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
     304      EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
    301305        : Parent(*adapter._graph, value) {}
    302306
     
    315319  };
    316320
    317   template <typename _Digraph>
    318   class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
    319   public:
    320     typedef _Digraph Digraph;
    321     typedef DigraphAdaptorBase<_Digraph> Parent;
     321  template <typename DGR>
     322  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
     323    typedef DigraphAdaptorBase<DGR> Parent;
     324  public:
     325    typedef DGR Digraph;
    322326  protected:
    323327    ReverseDigraphBase() : Parent() { }
     
    337341    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
    338342
    339     typedef FindArcTagIndicator<Digraph> FindArcTag;
     343    typedef FindArcTagIndicator<DGR> FindArcTag;
    340344    Arc findArc(const Node& u, const Node& v,
    341345                const Arc& prev = INVALID) const {
     
    357361  /// parameter is set to be \c const.
    358362  ///
    359   /// \tparam GR The type of the adapted digraph.
     363  /// \tparam DGR The type of the adapted digraph.
    360364  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    361365  /// It can also be specified to be \c const.
     
    363367  /// \note The \c Node and \c Arc types of this adaptor and the adapted
    364368  /// digraph are convertible to each other.
    365   template<typename GR>
     369  template<typename DGR>
    366370#ifdef DOXYGEN
    367371  class ReverseDigraph {
    368372#else
    369373  class ReverseDigraph :
    370     public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {
     374    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
    371375#endif
     376    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
    372377  public:
    373378    /// The type of the adapted digraph.
    374     typedef GR Digraph;
    375     typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;
     379    typedef DGR Digraph;
    376380  protected:
    377381    ReverseDigraph() { }
     
    381385    ///
    382386    /// Creates a reverse digraph adaptor for the given digraph.
    383     explicit ReverseDigraph(Digraph& digraph) {
    384       Parent::setDigraph(digraph);
     387    explicit ReverseDigraph(DGR& digraph) {
     388      Parent::initialize(digraph);
    385389    }
    386390  };
     
    391395  /// \ingroup graph_adaptors
    392396  /// \relates ReverseDigraph
    393   template<typename GR>
    394   ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {
    395     return ReverseDigraph<const GR>(digraph);
     397  template<typename DGR>
     398  ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
     399    return ReverseDigraph<const DGR>(digraph);
    396400  }
    397401
    398402
    399   template <typename _Digraph, typename _NodeFilterMap,
    400             typename _ArcFilterMap, bool _checked = true>
    401   class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
    402   public:
    403     typedef _Digraph Digraph;
    404     typedef _NodeFilterMap NodeFilterMap;
    405     typedef _ArcFilterMap ArcFilterMap;
     403  template <typename DGR, typename NF, typename AF, bool ch = true>
     404  class SubDigraphBase : public DigraphAdaptorBase<DGR> {
     405    typedef DigraphAdaptorBase<DGR> Parent;
     406  public:
     407    typedef DGR Digraph;
     408    typedef NF NodeFilterMap;
     409    typedef AF ArcFilterMap;
    406410
    407411    typedef SubDigraphBase Adaptor;
    408     typedef DigraphAdaptorBase<_Digraph> Parent;
    409412  protected:
    410     NodeFilterMap* _node_filter;
    411     ArcFilterMap* _arc_filter;
     413    NF* _node_filter;
     414    AF* _arc_filter;
    412415    SubDigraphBase()
    413416      : Parent(), _node_filter(0), _arc_filter(0) { }
    414417
    415     void setNodeFilterMap(NodeFilterMap& node_filter) {
     418    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
     419      Parent::initialize(digraph);
    416420      _node_filter = &node_filter;
    417     }
    418     void setArcFilterMap(ArcFilterMap& arc_filter) {
    419       _arc_filter = &arc_filter;
     421      _arc_filter = &arc_filter;     
    420422    }
    421423
     
    488490    typedef False ArcNumTag;
    489491
    490     typedef FindArcTagIndicator<Digraph> FindArcTag;
     492    typedef FindArcTagIndicator<DGR> FindArcTag;
    491493    Arc findArc(const Node& source, const Node& target,
    492494                const Arc& prev = INVALID) const {
     
    501503    }
    502504
    503     template <typename _Value>
    504     class NodeMap : public SubMapExtender<Adaptor,
    505       typename Parent::template NodeMap<_Value> > {
     505  public:
     506
     507    template <typename V>
     508    class NodeMap
     509      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     510              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     511      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     512        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     513
    506514    public:
    507       typedef _Value Value;
    508       typedef SubMapExtender<Adaptor, typename Parent::
    509                              template NodeMap<Value> > MapParent;
    510 
    511       NodeMap(const Adaptor& adaptor)
    512         : MapParent(adaptor) {}
    513       NodeMap(const Adaptor& adaptor, const Value& value)
    514         : MapParent(adaptor, value) {}
     515      typedef V Value;
     516
     517      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
     518        : Parent(adaptor) {}
     519      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
     520        : Parent(adaptor, value) {}
    515521
    516522    private:
     
    521527      template <typename CMap>
    522528      NodeMap& operator=(const CMap& cmap) {
    523         MapParent::operator=(cmap);
     529        Parent::operator=(cmap);
    524530        return *this;
    525531      }
    526532    };
    527533
    528     template <typename _Value>
    529     class ArcMap : public SubMapExtender<Adaptor,
    530       typename Parent::template ArcMap<_Value> > {
     534    template <typename V>
     535    class ArcMap
     536      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     537              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     538      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     539        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     540
    531541    public:
    532       typedef _Value Value;
    533       typedef SubMapExtender<Adaptor, typename Parent::
    534                              template ArcMap<Value> > MapParent;
    535 
    536       ArcMap(const Adaptor& adaptor)
    537         : MapParent(adaptor) {}
    538       ArcMap(const Adaptor& adaptor, const Value& value)
    539         : MapParent(adaptor, value) {}
     542      typedef V Value;
     543
     544      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
     545        : Parent(adaptor) {}
     546      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
     547        : Parent(adaptor, value) {}
    540548
    541549    private:
     
    546554      template <typename CMap>
    547555      ArcMap& operator=(const CMap& cmap) {
    548         MapParent::operator=(cmap);
     556        Parent::operator=(cmap);
    549557        return *this;
    550558      }
     
    553561  };
    554562
    555   template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
    556   class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
    557     : public DigraphAdaptorBase<_Digraph> {
    558   public:
    559     typedef _Digraph Digraph;
    560     typedef _NodeFilterMap NodeFilterMap;
    561     typedef _ArcFilterMap ArcFilterMap;
     563  template <typename DGR, typename NF, typename AF>
     564  class SubDigraphBase<DGR, NF, AF, false>
     565    : public DigraphAdaptorBase<DGR> {
     566    typedef DigraphAdaptorBase<DGR> Parent;
     567  public:
     568    typedef DGR Digraph;
     569    typedef NF NodeFilterMap;
     570    typedef AF ArcFilterMap;
    562571
    563572    typedef SubDigraphBase Adaptor;
    564     typedef DigraphAdaptorBase<Digraph> Parent;
    565573  protected:
    566     NodeFilterMap* _node_filter;
    567     ArcFilterMap* _arc_filter;
     574    NF* _node_filter;
     575    AF* _arc_filter;
    568576    SubDigraphBase()
    569577      : Parent(), _node_filter(0), _arc_filter(0) { }
    570578
    571     void setNodeFilterMap(NodeFilterMap& node_filter) {
     579    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
     580      Parent::initialize(digraph);
    572581      _node_filter = &node_filter;
    573     }
    574     void setArcFilterMap(ArcFilterMap& arc_filter) {
    575       _arc_filter = &arc_filter;
     582      _arc_filter = &arc_filter;     
    576583    }
    577584
     
    628635    typedef False ArcNumTag;
    629636
    630     typedef FindArcTagIndicator<Digraph> FindArcTag;
     637    typedef FindArcTagIndicator<DGR> FindArcTag;
    631638    Arc findArc(const Node& source, const Node& target,
    632639                const Arc& prev = INVALID) const {
     
    641648    }
    642649
    643     template <typename _Value>
    644     class NodeMap : public SubMapExtender<Adaptor,
    645       typename Parent::template NodeMap<_Value> > {
     650    template <typename V>
     651    class NodeMap
     652      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     653          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     654      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     655        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     656
    646657    public:
    647       typedef _Value Value;
    648       typedef SubMapExtender<Adaptor, typename Parent::
    649                              template NodeMap<Value> > MapParent;
    650 
    651       NodeMap(const Adaptor& adaptor)
    652         : MapParent(adaptor) {}
    653       NodeMap(const Adaptor& adaptor, const Value& value)
    654         : MapParent(adaptor, value) {}
     658      typedef V Value;
     659
     660      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
     661        : Parent(adaptor) {}
     662      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
     663        : Parent(adaptor, value) {}
    655664
    656665    private:
     
    661670      template <typename CMap>
    662671      NodeMap& operator=(const CMap& cmap) {
    663         MapParent::operator=(cmap);
     672        Parent::operator=(cmap);
    664673        return *this;
    665674      }
    666675    };
    667676
    668     template <typename _Value>
    669     class ArcMap : public SubMapExtender<Adaptor,
    670       typename Parent::template ArcMap<_Value> > {
     677    template <typename V>
     678    class ArcMap
     679      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     680          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     681      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     682        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     683
    671684    public:
    672       typedef _Value Value;
    673       typedef SubMapExtender<Adaptor, typename Parent::
    674                              template ArcMap<Value> > MapParent;
    675 
    676       ArcMap(const Adaptor& adaptor)
    677         : MapParent(adaptor) {}
    678       ArcMap(const Adaptor& adaptor, const Value& value)
    679         : MapParent(adaptor, value) {}
     685      typedef V Value;
     686
     687      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
     688        : Parent(adaptor) {}
     689      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
     690        : Parent(adaptor, value) {}
    680691
    681692    private:
     
    686697      template <typename CMap>
    687698      ArcMap& operator=(const CMap& cmap) {
    688         MapParent::operator=(cmap);
     699        Parent::operator=(cmap);
    689700        return *this;
    690701      }
     
    709720  /// parameter is set to be \c const.
    710721  ///
    711   /// \tparam GR The type of the adapted digraph.
     722  /// \tparam DGR The type of the adapted digraph.
    712723  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    713724  /// It can also be specified to be \c const.
     
    715726  /// It must be a \c bool (or convertible) node map of the
    716727  /// adapted digraph. The default type is
    717   /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>".
     728  /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".
    718729  /// \tparam AF The type of the arc filter map.
    719730  /// It must be \c bool (or convertible) arc map of the
    720731  /// adapted digraph. The default type is
    721   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
     732  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
    722733  ///
    723734  /// \note The \c Node and \c Arc types of this adaptor and the adapted
     
    727738  /// \see FilterArcs
    728739#ifdef DOXYGEN
    729   template<typename GR, typename NF, typename AF>
     740  template<typename DGR, typename NF, typename AF>
    730741  class SubDigraph {
    731742#else
    732   template<typename GR,
    733            typename NF = typename GR::template NodeMap<bool>,
    734            typename AF = typename GR::template ArcMap<bool> >
     743  template<typename DGR,
     744           typename NF = typename DGR::template NodeMap<bool>,
     745           typename AF = typename DGR::template ArcMap<bool> >
    735746  class SubDigraph :
    736     public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {
     747    public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {
    737748#endif
    738749  public:
    739750    /// The type of the adapted digraph.
    740     typedef GR Digraph;
     751    typedef DGR Digraph;
    741752    /// The type of the node filter map.
    742753    typedef NF NodeFilterMap;
     
    744755    typedef AF ArcFilterMap;
    745756
    746     typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> >
     757    typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >
    747758      Parent;
    748759
     
    758769    /// Creates a subdigraph for the given digraph with the
    759770    /// given node and arc filter maps.
    760     SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
    761                ArcFilterMap& arc_filter) {
    762       setDigraph(digraph);
    763       setNodeFilterMap(node_filter);
    764       setArcFilterMap(arc_filter);
     771    SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
     772      Parent::initialize(digraph, node_filter, arc_filter);
    765773    }
    766774
     
    824832  /// \ingroup graph_adaptors
    825833  /// \relates SubDigraph
    826   template<typename GR, typename NF, typename AF>
    827   SubDigraph<const GR, NF, AF>
    828   subDigraph(const GR& digraph,
    829              NF& node_filter_map, AF& arc_filter_map) {
    830     return SubDigraph<const GR, NF, AF>
    831       (digraph, node_filter_map, arc_filter_map);
     834  template<typename DGR, typename NF, typename AF>
     835  SubDigraph<const DGR, NF, AF>
     836  subDigraph(const DGR& digraph,
     837             NF& node_filter, AF& arc_filter) {
     838    return SubDigraph<const DGR, NF, AF>
     839      (digraph, node_filter, arc_filter);
    832840  }
    833841
    834   template<typename GR, typename NF, typename AF>
    835   SubDigraph<const GR, const NF, AF>
    836   subDigraph(const GR& digraph,
    837              const NF& node_filter_map, AF& arc_filter_map) {
    838     return SubDigraph<const GR, const NF, AF>
    839       (digraph, node_filter_map, arc_filter_map);
     842  template<typename DGR, typename NF, typename AF>
     843  SubDigraph<const DGR, const NF, AF>
     844  subDigraph(const DGR& digraph,
     845             const NF& node_filter, AF& arc_filter) {
     846    return SubDigraph<const DGR, const NF, AF>
     847      (digraph, node_filter, arc_filter);
    840848  }
    841849
    842   template<typename GR, typename NF, typename AF>
    843   SubDigraph<const GR, NF, const AF>
    844   subDigraph(const GR& digraph,
    845              NF& node_filter_map, const AF& arc_filter_map) {
    846     return SubDigraph<const GR, NF, const AF>
    847       (digraph, node_filter_map, arc_filter_map);
     850  template<typename DGR, typename NF, typename AF>
     851  SubDigraph<const DGR, NF, const AF>
     852  subDigraph(const DGR& digraph,
     853             NF& node_filter, const AF& arc_filter) {
     854    return SubDigraph<const DGR, NF, const AF>
     855      (digraph, node_filter, arc_filter);
    848856  }
    849857
    850   template<typename GR, typename NF, typename AF>
    851   SubDigraph<const GR, const NF, const AF>
    852   subDigraph(const GR& digraph,
    853              const NF& node_filter_map, const AF& arc_filter_map) {
    854     return SubDigraph<const GR, const NF, const AF>
    855       (digraph, node_filter_map, arc_filter_map);
     858  template<typename DGR, typename NF, typename AF>
     859  SubDigraph<const DGR, const NF, const AF>
     860  subDigraph(const DGR& digraph,
     861             const NF& node_filter, const AF& arc_filter) {
     862    return SubDigraph<const DGR, const NF, const AF>
     863      (digraph, node_filter, arc_filter);
    856864  }
    857865
    858866
    859   template <typename _Graph, typename _NodeFilterMap,
    860             typename _EdgeFilterMap, bool _checked = true>
    861   class SubGraphBase : public GraphAdaptorBase<_Graph> {
    862   public:
    863     typedef _Graph Graph;
    864     typedef _NodeFilterMap NodeFilterMap;
    865     typedef _EdgeFilterMap EdgeFilterMap;
     867  template <typename GR, typename NF, typename EF, bool ch = true>
     868  class SubGraphBase : public GraphAdaptorBase<GR> {
     869    typedef GraphAdaptorBase<GR> Parent;
     870  public:
     871    typedef GR Graph;
     872    typedef NF NodeFilterMap;
     873    typedef EF EdgeFilterMap;
    866874
    867875    typedef SubGraphBase Adaptor;
    868     typedef GraphAdaptorBase<_Graph> Parent;
    869876  protected:
    870877
    871     NodeFilterMap* _node_filter_map;
    872     EdgeFilterMap* _edge_filter_map;
     878    NF* _node_filter;
     879    EF* _edge_filter;
    873880
    874881    SubGraphBase()
    875       : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
    876 
    877     void setNodeFilterMap(NodeFilterMap& node_filter_map) {
    878       _node_filter_map=&node_filter_map;
    879     }
    880     void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
    881       _edge_filter_map=&edge_filter_map;
     882      : Parent(), _node_filter(0), _edge_filter(0) { }
     883
     884    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
     885      Parent::initialize(graph);
     886      _node_filter = &node_filter;
     887      _edge_filter = &edge_filter;
    882888    }
    883889
     
    890896    void first(Node& i) const {
    891897      Parent::first(i);
    892       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     898      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    893899    }
    894900
    895901    void first(Arc& i) const {
    896902      Parent::first(i);
    897       while (i!=INVALID && (!(*_edge_filter_map)[i]
    898                             || !(*_node_filter_map)[Parent::source(i)]
    899                             || !(*_node_filter_map)[Parent::target(i)]))
     903      while (i!=INVALID && (!(*_edge_filter)[i]
     904                            || !(*_node_filter)[Parent::source(i)]
     905                            || !(*_node_filter)[Parent::target(i)]))
    900906        Parent::next(i);
    901907    }
     
    903909    void first(Edge& i) const {
    904910      Parent::first(i);
    905       while (i!=INVALID && (!(*_edge_filter_map)[i]
    906                             || !(*_node_filter_map)[Parent::u(i)]
    907                             || !(*_node_filter_map)[Parent::v(i)]))
     911      while (i!=INVALID && (!(*_edge_filter)[i]
     912                            || !(*_node_filter)[Parent::u(i)]
     913                            || !(*_node_filter)[Parent::v(i)]))
    908914        Parent::next(i);
    909915    }
     
    911917    void firstIn(Arc& i, const Node& n) const {
    912918      Parent::firstIn(i, n);
    913       while (i!=INVALID && (!(*_edge_filter_map)[i]
    914                             || !(*_node_filter_map)[Parent::source(i)]))
     919      while (i!=INVALID && (!(*_edge_filter)[i]
     920                            || !(*_node_filter)[Parent::source(i)]))
    915921        Parent::nextIn(i);
    916922    }
     
    918924    void firstOut(Arc& i, const Node& n) const {
    919925      Parent::firstOut(i, n);
    920       while (i!=INVALID && (!(*_edge_filter_map)[i]
    921                             || !(*_node_filter_map)[Parent::target(i)]))
     926      while (i!=INVALID && (!(*_edge_filter)[i]
     927                            || !(*_node_filter)[Parent::target(i)]))
    922928        Parent::nextOut(i);
    923929    }
     
    925931    void firstInc(Edge& i, bool& d, const Node& n) const {
    926932      Parent::firstInc(i, d, n);
    927       while (i!=INVALID && (!(*_edge_filter_map)[i]
    928                             || !(*_node_filter_map)[Parent::u(i)]
    929                             || !(*_node_filter_map)[Parent::v(i)]))
     933      while (i!=INVALID && (!(*_edge_filter)[i]
     934                            || !(*_node_filter)[Parent::u(i)]
     935                            || !(*_node_filter)[Parent::v(i)]))
    930936        Parent::nextInc(i, d);
    931937    }
     
    933939    void next(Node& i) const {
    934940      Parent::next(i);
    935       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     941      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    936942    }
    937943
    938944    void next(Arc& i) const {
    939945      Parent::next(i);
    940       while (i!=INVALID && (!(*_edge_filter_map)[i]
    941                             || !(*_node_filter_map)[Parent::source(i)]
    942                             || !(*_node_filter_map)[Parent::target(i)]))
     946      while (i!=INVALID && (!(*_edge_filter)[i]
     947                            || !(*_node_filter)[Parent::source(i)]
     948                            || !(*_node_filter)[Parent::target(i)]))
    943949        Parent::next(i);
    944950    }
     
    946952    void next(Edge& i) const {
    947953      Parent::next(i);
    948       while (i!=INVALID && (!(*_edge_filter_map)[i]
    949                             || !(*_node_filter_map)[Parent::u(i)]
    950                             || !(*_node_filter_map)[Parent::v(i)]))
     954      while (i!=INVALID && (!(*_edge_filter)[i]
     955                            || !(*_node_filter)[Parent::u(i)]
     956                            || !(*_node_filter)[Parent::v(i)]))
    951957        Parent::next(i);
    952958    }
     
    954960    void nextIn(Arc& i) const {
    955961      Parent::nextIn(i);
    956       while (i!=INVALID && (!(*_edge_filter_map)[i]
    957                             || !(*_node_filter_map)[Parent::source(i)]))
     962      while (i!=INVALID && (!(*_edge_filter)[i]
     963                            || !(*_node_filter)[Parent::source(i)]))
    958964        Parent::nextIn(i);
    959965    }
     
    961967    void nextOut(Arc& i) const {
    962968      Parent::nextOut(i);
    963       while (i!=INVALID && (!(*_edge_filter_map)[i]
    964                             || !(*_node_filter_map)[Parent::target(i)]))
     969      while (i!=INVALID && (!(*_edge_filter)[i]
     970                            || !(*_node_filter)[Parent::target(i)]))
    965971        Parent::nextOut(i);
    966972    }
     
    968974    void nextInc(Edge& i, bool& d) const {
    969975      Parent::nextInc(i, d);
    970       while (i!=INVALID && (!(*_edge_filter_map)[i]
    971                             || !(*_node_filter_map)[Parent::u(i)]
    972                             || !(*_node_filter_map)[Parent::v(i)]))
     976      while (i!=INVALID && (!(*_edge_filter)[i]
     977                            || !(*_node_filter)[Parent::u(i)]
     978                            || !(*_node_filter)[Parent::v(i)]))
    973979        Parent::nextInc(i, d);
    974980    }
    975981
    976     void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
    977     void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
    978 
    979     bool status(const Node& n) const { return (*_node_filter_map)[n]; }
    980     bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
     982    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
     983    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
     984
     985    bool status(const Node& n) const { return (*_node_filter)[n]; }
     986    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
    981987
    982988    typedef False NodeNumTag;
     
    987993    Arc findArc(const Node& u, const Node& v,
    988994                const Arc& prev = INVALID) const {
    989       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
     995      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
    990996        return INVALID;
    991997      }
    992998      Arc arc = Parent::findArc(u, v, prev);
    993       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
     999      while (arc != INVALID && !(*_edge_filter)[arc]) {
    9941000        arc = Parent::findArc(u, v, arc);
    9951001      }
     
    10001006    Edge findEdge(const Node& u, const Node& v,
    10011007                  const Edge& prev = INVALID) const {
    1002       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
     1008      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
    10031009        return INVALID;
    10041010      }
    10051011      Edge edge = Parent::findEdge(u, v, prev);
    1006       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
     1012      while (edge != INVALID && !(*_edge_filter)[edge]) {
    10071013        edge = Parent::findEdge(u, v, edge);
    10081014      }
     
    10101016    }
    10111017
    1012     template <typename _Value>
    1013     class NodeMap : public SubMapExtender<Adaptor,
    1014       typename Parent::template NodeMap<_Value> > {
     1018    template <typename V>
     1019    class NodeMap
     1020      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1021          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
     1022      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1023        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
     1024
    10151025    public:
    1016       typedef _Value Value;
    1017       typedef SubMapExtender<Adaptor, typename Parent::
    1018                              template NodeMap<Value> > MapParent;
    1019 
    1020       NodeMap(const Adaptor& adaptor)
    1021         : MapParent(adaptor) {}
    1022       NodeMap(const Adaptor& adaptor, const Value& value)
    1023         : MapParent(adaptor, value) {}
     1026      typedef V Value;
     1027
     1028      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
     1029        : Parent(adaptor) {}
     1030      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
     1031        : Parent(adaptor, value) {}
    10241032
    10251033    private:
     
    10301038      template <typename CMap>
    10311039      NodeMap& operator=(const CMap& cmap) {
    1032         MapParent::operator=(cmap);
     1040        Parent::operator=(cmap);
    10331041        return *this;
    10341042      }
    10351043    };
    10361044
    1037     template <typename _Value>
    1038     class ArcMap : public SubMapExtender<Adaptor,
    1039       typename Parent::template ArcMap<_Value> > {
     1045    template <typename V>
     1046    class ArcMap
     1047      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1048          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
     1049      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1050        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
     1051
    10401052    public:
    1041       typedef _Value Value;
    1042       typedef SubMapExtender<Adaptor, typename Parent::
    1043                              template ArcMap<Value> > MapParent;
    1044 
    1045       ArcMap(const Adaptor& adaptor)
    1046         : MapParent(adaptor) {}
    1047       ArcMap(const Adaptor& adaptor, const Value& value)
    1048         : MapParent(adaptor, value) {}
     1053      typedef V Value;
     1054
     1055      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
     1056        : Parent(adaptor) {}
     1057      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
     1058        : Parent(adaptor, value) {}
    10491059
    10501060    private:
     
    10551065      template <typename CMap>
    10561066      ArcMap& operator=(const CMap& cmap) {
    1057         MapParent::operator=(cmap);
     1067        Parent::operator=(cmap);
    10581068        return *this;
    10591069      }
    10601070    };
    10611071
    1062     template <typename _Value>
    1063     class EdgeMap : public SubMapExtender<Adaptor,
    1064       typename Parent::template EdgeMap<_Value> > {
     1072    template <typename V>
     1073    class EdgeMap
     1074      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1075        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
     1076      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1077        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1078
    10651079    public:
    1066       typedef _Value Value;
    1067       typedef SubMapExtender<Adaptor, typename Parent::
    1068                              template EdgeMap<Value> > MapParent;
    1069 
    1070       EdgeMap(const Adaptor& adaptor)
    1071         : MapParent(adaptor) {}
    1072 
    1073       EdgeMap(const Adaptor& adaptor, const Value& value)
    1074         : MapParent(adaptor, value) {}
     1080      typedef V Value;
     1081
     1082      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
     1083        : Parent(adaptor) {}
     1084
     1085      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
     1086        : Parent(adaptor, value) {}
    10751087
    10761088    private:
     
    10811093      template <typename CMap>
    10821094      EdgeMap& operator=(const CMap& cmap) {
    1083         MapParent::operator=(cmap);
     1095        Parent::operator=(cmap);
    10841096        return *this;
    10851097      }
     
    10881100  };
    10891101
    1090   template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
    1091   class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
    1092     : public GraphAdaptorBase<_Graph> {
    1093   public:
    1094     typedef _Graph Graph;
    1095     typedef _NodeFilterMap NodeFilterMap;
    1096     typedef _EdgeFilterMap EdgeFilterMap;
     1102  template <typename GR, typename NF, typename EF>
     1103  class SubGraphBase<GR, NF, EF, false>
     1104    : public GraphAdaptorBase<GR> {
     1105    typedef GraphAdaptorBase<GR> Parent;
     1106  public:
     1107    typedef GR Graph;
     1108    typedef NF NodeFilterMap;
     1109    typedef EF EdgeFilterMap;
    10971110
    10981111    typedef SubGraphBase Adaptor;
    1099     typedef GraphAdaptorBase<_Graph> Parent;
    11001112  protected:
    1101     NodeFilterMap* _node_filter_map;
    1102     EdgeFilterMap* _edge_filter_map;
    1103     SubGraphBase() : Parent(),
    1104                      _node_filter_map(0), _edge_filter_map(0) { }
    1105 
    1106     void setNodeFilterMap(NodeFilterMap& node_filter_map) {
    1107       _node_filter_map=&node_filter_map;
    1108     }
    1109     void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
    1110       _edge_filter_map=&edge_filter_map;
     1113    NF* _node_filter;
     1114    EF* _edge_filter;
     1115    SubGraphBase()
     1116          : Parent(), _node_filter(0), _edge_filter(0) { }
     1117
     1118    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
     1119      Parent::initialize(graph);
     1120      _node_filter = &node_filter;
     1121      _edge_filter = &edge_filter;
    11111122    }
    11121123
     
    11191130    void first(Node& i) const {
    11201131      Parent::first(i);
    1121       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     1132      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    11221133    }
    11231134
    11241135    void first(Arc& i) const {
    11251136      Parent::first(i);
    1126       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1137      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    11271138    }
    11281139
    11291140    void first(Edge& i) const {
    11301141      Parent::first(i);
    1131       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1142      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    11321143    }
    11331144
    11341145    void firstIn(Arc& i, const Node& n) const {
    11351146      Parent::firstIn(i, n);
    1136       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
     1147      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
    11371148    }
    11381149
    11391150    void firstOut(Arc& i, const Node& n) const {
    11401151      Parent::firstOut(i, n);
    1141       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
     1152      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
    11421153    }
    11431154
    11441155    void firstInc(Edge& i, bool& d, const Node& n) const {
    11451156      Parent::firstInc(i, d, n);
    1146       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
     1157      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
    11471158    }
    11481159
    11491160    void next(Node& i) const {
    11501161      Parent::next(i);
    1151       while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
     1162      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
    11521163    }
    11531164    void next(Arc& i) const {
    11541165      Parent::next(i);
    1155       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1166      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    11561167    }
    11571168    void next(Edge& i) const {
    11581169      Parent::next(i);
    1159       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
     1170      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
    11601171    }
    11611172    void nextIn(Arc& i) const {
    11621173      Parent::nextIn(i);
    1163       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
     1174      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
    11641175    }
    11651176
    11661177    void nextOut(Arc& i) const {
    11671178      Parent::nextOut(i);
    1168       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
     1179      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
    11691180    }
    11701181    void nextInc(Edge& i, bool& d) const {
    11711182      Parent::nextInc(i, d);
    1172       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
    1173     }
    1174 
    1175     void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
    1176     void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
    1177 
    1178     bool status(const Node& n) const { return (*_node_filter_map)[n]; }
    1179     bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
     1183      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
     1184    }
     1185
     1186    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
     1187    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
     1188
     1189    bool status(const Node& n) const { return (*_node_filter)[n]; }
     1190    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
    11801191
    11811192    typedef False NodeNumTag;
     
    11871198                const Arc& prev = INVALID) const {
    11881199      Arc arc = Parent::findArc(u, v, prev);
    1189       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
     1200      while (arc != INVALID && !(*_edge_filter)[arc]) {
    11901201        arc = Parent::findArc(u, v, arc);
    11911202      }
     
    11971208                  const Edge& prev = INVALID) const {
    11981209      Edge edge = Parent::findEdge(u, v, prev);
    1199       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
     1210      while (edge != INVALID && !(*_edge_filter)[edge]) {
    12001211        edge = Parent::findEdge(u, v, edge);
    12011212      }
     
    12031214    }
    12041215
    1205     template <typename _Value>
    1206     class NodeMap : public SubMapExtender<Adaptor,
    1207       typename Parent::template NodeMap<_Value> > {
     1216    template <typename V>
     1217    class NodeMap
     1218      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1219          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
     1220      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1221        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
     1222
    12081223    public:
    1209       typedef _Value Value;
    1210       typedef SubMapExtender<Adaptor, typename Parent::
    1211                              template NodeMap<Value> > MapParent;
    1212 
    1213       NodeMap(const Adaptor& adaptor)
    1214         : MapParent(adaptor) {}
    1215       NodeMap(const Adaptor& adaptor, const Value& value)
    1216         : MapParent(adaptor, value) {}
     1224      typedef V Value;
     1225
     1226      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
     1227        : Parent(adaptor) {}
     1228      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
     1229        : Parent(adaptor, value) {}
    12171230
    12181231    private:
     
    12231236      template <typename CMap>
    12241237      NodeMap& operator=(const CMap& cmap) {
    1225         MapParent::operator=(cmap);
     1238        Parent::operator=(cmap);
    12261239        return *this;
    12271240      }
    12281241    };
    12291242
    1230     template <typename _Value>
    1231     class ArcMap : public SubMapExtender<Adaptor,
    1232       typename Parent::template ArcMap<_Value> > {
     1243    template <typename V>
     1244    class ArcMap
     1245      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1246          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
     1247      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1248        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
     1249
    12331250    public:
    1234       typedef _Value Value;
    1235       typedef SubMapExtender<Adaptor, typename Parent::
    1236                              template ArcMap<Value> > MapParent;
    1237 
    1238       ArcMap(const Adaptor& adaptor)
    1239         : MapParent(adaptor) {}
    1240       ArcMap(const Adaptor& adaptor, const Value& value)
    1241         : MapParent(adaptor, value) {}
     1251      typedef V Value;
     1252
     1253      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
     1254        : Parent(adaptor) {}
     1255      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
     1256        : Parent(adaptor, value) {}
    12421257
    12431258    private:
     
    12481263      template <typename CMap>
    12491264      ArcMap& operator=(const CMap& cmap) {
    1250         MapParent::operator=(cmap);
     1265        Parent::operator=(cmap);
    12511266        return *this;
    12521267      }
    12531268    };
    12541269
    1255     template <typename _Value>
    1256     class EdgeMap : public SubMapExtender<Adaptor,
    1257       typename Parent::template EdgeMap<_Value> > {
     1270    template <typename V>
     1271    class EdgeMap
     1272      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1273        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
     1274      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1275        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1276
    12581277    public:
    1259       typedef _Value Value;
    1260       typedef SubMapExtender<Adaptor, typename Parent::
    1261                              template EdgeMap<Value> > MapParent;
    1262 
    1263       EdgeMap(const Adaptor& adaptor)
    1264         : MapParent(adaptor) {}
    1265 
    1266       EdgeMap(const Adaptor& adaptor, const _Value& value)
    1267         : MapParent(adaptor, value) {}
     1278      typedef V Value;
     1279
     1280      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
     1281        : Parent(adaptor) {}
     1282
     1283      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
     1284        : Parent(adaptor, value) {}
    12681285
    12691286    private:
     
    12741291      template <typename CMap>
    12751292      EdgeMap& operator=(const CMap& cmap) {
    1276         MapParent::operator=(cmap);
     1293        Parent::operator=(cmap);
    12771294        return *this;
    12781295      }
     
    13331350    typedef EF EdgeFilterMap;
    13341351
    1335     typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> >
     1352    typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> >
    13361353      Parent;
    13371354
     
    13471364    /// Creates a subgraph for the given graph with the given node
    13481365    /// and edge filter maps.
    1349     SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
    1350              EdgeFilterMap& edge_filter_map) {
    1351       setGraph(graph);
    1352       setNodeFilterMap(node_filter_map);
    1353       setEdgeFilterMap(edge_filter_map);
     1366    SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
     1367      initialize(graph, node_filter, edge_filter);
    13541368    }
    13551369
     
    14151429  template<typename GR, typename NF, typename EF>
    14161430  SubGraph<const GR, NF, EF>
    1417   subGraph(const GR& graph,
    1418            NF& node_filter_map, EF& edge_filter_map) {
     1431  subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {
    14191432    return SubGraph<const GR, NF, EF>
    1420       (graph, node_filter_map, edge_filter_map);
     1433      (graph, node_filter, edge_filter);
    14211434  }
    14221435
    14231436  template<typename GR, typename NF, typename EF>
    14241437  SubGraph<const GR, const NF, EF>
    1425   subGraph(const GR& graph,
    1426            const NF& node_filter_map, EF& edge_filter_map) {
     1438  subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {
    14271439    return SubGraph<const GR, const NF, EF>
    1428       (graph, node_filter_map, edge_filter_map);
     1440      (graph, node_filter, edge_filter);
    14291441  }
    14301442
    14311443  template<typename GR, typename NF, typename EF>
    14321444  SubGraph<const GR, NF, const EF>
    1433   subGraph(const GR& graph,
    1434            NF& node_filter_map, const EF& edge_filter_map) {
     1445  subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {
    14351446    return SubGraph<const GR, NF, const EF>
    1436       (graph, node_filter_map, edge_filter_map);
     1447      (graph, node_filter, edge_filter);
    14371448  }
    14381449
    14391450  template<typename GR, typename NF, typename EF>
    14401451  SubGraph<const GR, const NF, const EF>
    1441   subGraph(const GR& graph,
    1442            const NF& node_filter_map, const EF& edge_filter_map) {
     1452  subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {
    14431453    return SubGraph<const GR, const NF, const EF>
    1444       (graph, node_filter_map, edge_filter_map);
     1454      (graph, node_filter, edge_filter);
    14451455  }
    14461456
     
    14821492  class FilterNodes :
    14831493    public DigraphAdaptorExtender<
    1484       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {
     1494      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
     1495                     true> > {
    14851496#endif
     1497    typedef DigraphAdaptorExtender<
     1498      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
     1499                     true> > Parent;
     1500
    14861501  public:
    14871502
     
    14891504    typedef NF NodeFilterMap;
    14901505
    1491     typedef DigraphAdaptorExtender<
    1492       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >
    1493       Parent;
    1494 
    14951506    typedef typename Parent::Node Node;
    14961507
    14971508  protected:
    1498     ConstMap<typename Digraph::Arc, bool> const_true_map;
    1499 
    1500     FilterNodes() : const_true_map(true) {
    1501       Parent::setArcFilterMap(const_true_map);
    1502     }
     1509    ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
     1510
     1511    FilterNodes() : const_true_map() {}
    15031512
    15041513  public:
     
    15081517    /// Creates a subgraph for the given digraph or graph with the
    15091518    /// given node filter map.
    1510     FilterNodes(GR& graph, NodeFilterMap& node_filter) :
    1511       Parent(), const_true_map(true)
     1519    FilterNodes(GR& graph, NF& node_filter)
     1520      : Parent(), const_true_map()
    15121521    {
    1513       Parent::setDigraph(graph);
    1514       Parent::setNodeFilterMap(node_filter);
    1515       Parent::setArcFilterMap(const_true_map);
     1522      Parent::initialize(graph, node_filter, const_true_map);
    15161523    }
    15171524
     
    15481555                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15491556    public GraphAdaptorExtender<
    1550       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {
    1551 
    1552   public:
     1557      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
     1558                   true> > {
     1559
     1560    typedef GraphAdaptorExtender<
     1561      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
     1562                   true> > Parent;
     1563
     1564  public:
     1565
    15531566    typedef GR Graph;
    15541567    typedef NF NodeFilterMap;
    1555     typedef GraphAdaptorExtender<
    1556       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >
    1557       Parent;
    15581568
    15591569    typedef typename Parent::Node Node;
     1570
    15601571  protected:
    1561     ConstMap<typename Graph::Edge, bool> const_true_map;
    1562 
    1563     FilterNodes() : const_true_map(true) {
    1564       Parent::setEdgeFilterMap(const_true_map);
    1565     }
    1566 
    1567   public:
    1568 
    1569     FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
    1570       Parent(), const_true_map(true) {
    1571       Parent::setGraph(_graph);
    1572       Parent::setNodeFilterMap(node_filter_map);
    1573       Parent::setEdgeFilterMap(const_true_map);
     1572    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
     1573
     1574    FilterNodes() : const_true_map() {}
     1575
     1576  public:
     1577
     1578    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
     1579      Parent(), const_true_map() {
     1580      Parent::initialize(graph, node_filter, const_true_map);
    15741581    }
    15751582
     
    15891596  template<typename GR, typename NF>
    15901597  FilterNodes<const GR, NF>
    1591   filterNodes(const GR& graph, NF& node_filter_map) {
    1592     return FilterNodes<const GR, NF>(graph, node_filter_map);
     1598  filterNodes(const GR& graph, NF& node_filter) {
     1599    return FilterNodes<const GR, NF>(graph, node_filter);
    15931600  }
    15941601
    15951602  template<typename GR, typename NF>
    15961603  FilterNodes<const GR, const NF>
    1597   filterNodes(const GR& graph, const NF& node_filter_map) {
    1598     return FilterNodes<const GR, const NF>(graph, node_filter_map);
     1604  filterNodes(const GR& graph, const NF& node_filter) {
     1605    return FilterNodes<const GR, const NF>(graph, node_filter);
    15991606  }
    16001607
     
    16131620  /// parameter is set to be \c const.
    16141621  ///
    1615   /// \tparam GR The type of the adapted digraph.
     1622  /// \tparam DGR The type of the adapted digraph.
    16161623  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    16171624  /// It can also be specified to be \c const.
     
    16191626  /// It must be a \c bool (or convertible) arc map of the
    16201627  /// adapted digraph. The default type is
    1621   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
     1628  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
    16221629  ///
    16231630  /// \note The \c Node and \c Arc types of this adaptor and the adapted
    16241631  /// digraph are convertible to each other.
    16251632#ifdef DOXYGEN
    1626   template<typename GR,
     1633  template<typename DGR,
    16271634           typename AF>
    16281635  class FilterArcs {
    16291636#else
    1630   template<typename GR,
    1631            typename AF = typename GR::template ArcMap<bool> >
     1637  template<typename DGR,
     1638           typename AF = typename DGR::template ArcMap<bool> >
    16321639  class FilterArcs :
    16331640    public DigraphAdaptorExtender<
    1634       SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > {
     1641      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
     1642                     AF, false> > {
    16351643#endif
    1636   public:
     1644    typedef DigraphAdaptorExtender<
     1645      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
     1646                     AF, false> > Parent;
     1647
     1648  public:
     1649
    16371650    /// The type of the adapted digraph.
    1638     typedef GR Digraph;
     1651    typedef DGR Digraph;
    16391652    /// The type of the arc filter map.
    16401653    typedef AF ArcFilterMap;
    16411654
    1642     typedef DigraphAdaptorExtender<
    1643       SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >
    1644       Parent;
    1645 
    16461655    typedef typename Parent::Arc Arc;
    16471656
    16481657  protected:
    1649     ConstMap<typename Digraph::Node, bool> const_true_map;
    1650 
    1651     FilterArcs() : const_true_map(true) {
    1652       Parent::setNodeFilterMap(const_true_map);
    1653     }
     1658    ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
     1659
     1660    FilterArcs() : const_true_map() {}
    16541661
    16551662  public:
     
    16591666    /// Creates a subdigraph for the given digraph with the given arc
    16601667    /// filter map.
    1661     FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
    1662       : Parent(), const_true_map(true) {
    1663       Parent::setDigraph(digraph);
    1664       Parent::setNodeFilterMap(const_true_map);
    1665       Parent::setArcFilterMap(arc_filter);
     1668    FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
     1669      : Parent(), const_true_map() {
     1670      Parent::initialize(digraph, const_true_map, arc_filter);
    16661671    }
    16671672
     
    16991704  /// \ingroup graph_adaptors
    17001705  /// \relates FilterArcs
    1701   template<typename GR, typename AF>
    1702   FilterArcs<const GR, AF>
    1703   filterArcs(const GR& digraph, AF& arc_filter_map) {
    1704     return FilterArcs<const GR, AF>(digraph, arc_filter_map);
     1706  template<typename DGR, typename AF>
     1707  FilterArcs<const DGR, AF>
     1708  filterArcs(const DGR& digraph, AF& arc_filter) {
     1709    return FilterArcs<const DGR, AF>(digraph, arc_filter);
    17051710  }
    17061711
    1707   template<typename GR, typename AF>
    1708   FilterArcs<const GR, const AF>
    1709   filterArcs(const GR& digraph, const AF& arc_filter_map) {
    1710     return FilterArcs<const GR, const AF>(digraph, arc_filter_map);
     1712  template<typename DGR, typename AF>
     1713  FilterArcs<const DGR, const AF>
     1714  filterArcs(const DGR& digraph, const AF& arc_filter) {
     1715    return FilterArcs<const DGR, const AF>(digraph, arc_filter);
    17111716  }
    17121717
     
    17441749  class FilterEdges :
    17451750    public GraphAdaptorExtender<
    1746       SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > {
     1751      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
     1752                   EF, false> > {
    17471753#endif
    1748   public:
     1754    typedef GraphAdaptorExtender<
     1755      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
     1756                   EF, false> > Parent;
     1757
     1758  public:
     1759
    17491760    /// The type of the adapted graph.
    17501761    typedef GR Graph;
     
    17521763    typedef EF EdgeFilterMap;
    17531764
    1754     typedef GraphAdaptorExtender<
    1755       SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> >
    1756       Parent;
    1757 
    17581765    typedef typename Parent::Edge Edge;
    17591766
    17601767  protected:
    1761     ConstMap<typename Graph::Node, bool> const_true_map;
     1768    ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
    17621769
    17631770    FilterEdges() : const_true_map(true) {
     
    17711778    /// Creates a subgraph for the given graph with the given edge
    17721779    /// filter map.
    1773     FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
    1774       Parent(), const_true_map(true) {
    1775       Parent::setGraph(graph);
    1776       Parent::setNodeFilterMap(const_true_map);
    1777       Parent::setEdgeFilterMap(edge_filter_map);
     1780    FilterEdges(GR& graph, EF& edge_filter)
     1781      : Parent(), const_true_map() {
     1782      Parent::initialize(graph, const_true_map, edge_filter);
    17781783    }
    17791784
     
    18131818  template<typename GR, typename EF>
    18141819  FilterEdges<const GR, EF>
    1815   filterEdges(const GR& graph, EF& edge_filter_map) {
    1816     return FilterEdges<const GR, EF>(graph, edge_filter_map);
     1820  filterEdges(const GR& graph, EF& edge_filter) {
     1821    return FilterEdges<const GR, EF>(graph, edge_filter);
    18171822  }
    18181823
    18191824  template<typename GR, typename EF>
    18201825  FilterEdges<const GR, const EF>
    1821   filterEdges(const GR& graph, const EF& edge_filter_map) {
    1822     return FilterEdges<const GR, const EF>(graph, edge_filter_map);
     1826  filterEdges(const GR& graph, const EF& edge_filter) {
     1827    return FilterEdges<const GR, const EF>(graph, edge_filter);
    18231828  }
    18241829
    18251830
    1826   template <typename _Digraph>
     1831  template <typename DGR>
    18271832  class UndirectorBase {
    18281833  public:
    1829     typedef _Digraph Digraph;
     1834    typedef DGR Digraph;
    18301835    typedef UndirectorBase Adaptor;
    18311836
     
    18351840    typedef typename Digraph::Node Node;
    18361841
    1837     class Arc : public Edge {
     1842    class Arc {
    18381843      friend class UndirectorBase;
    18391844    protected:
     1845      Edge _edge;
    18401846      bool _forward;
    18411847
    1842       Arc(const Edge& edge, bool forward) :
    1843         Edge(edge), _forward(forward) {}
     1848      Arc(const Edge& edge, bool forward)
     1849        : _edge(edge), _forward(forward) {}
    18441850
    18451851    public:
    18461852      Arc() {}
    18471853
    1848       Arc(Invalid) : Edge(INVALID), _forward(true) {}
     1854      Arc(Invalid) : _edge(INVALID), _forward(true) {}
     1855
     1856      operator const Edge&() const { return _edge; }
    18491857
    18501858      bool operator==(const Arc &other) const {
    1851         return _forward == other._forward &&
    1852           static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
     1859        return _forward == other._forward && _edge == other._edge;
    18531860      }
    18541861      bool operator!=(const Arc &other) const {
    1855         return _forward != other._forward ||
    1856           static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
     1862        return _forward != other._forward || _edge != other._edge;
    18571863      }
    18581864      bool operator<(const Arc &other) const {
    18591865        return _forward < other._forward ||
    1860           (_forward == other._forward &&
    1861            static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
     1866          (_forward == other._forward && _edge < other._edge);
    18621867      }
    18631868    };
     
    18721877
    18731878    void first(Arc& a) const {
    1874       _digraph->first(a);
     1879      _digraph->first(a._edge);
    18751880      a._forward = true;
    18761881    }
     
    18801885        a._forward = false;
    18811886      } else {
    1882         _digraph->next(a);
     1887        _digraph->next(a._edge);
    18831888        a._forward = true;
    18841889      }
     
    18941899
    18951900    void firstOut(Arc& a, const Node& n) const {
    1896       _digraph->firstIn(a, n);
    1897       if( static_cast<const Edge&>(a) != INVALID ) {
     1901      _digraph->firstIn(a._edge, n);
     1902      if (a._edge != INVALID ) {
    18981903        a._forward = false;
    18991904      } else {
    1900         _digraph->firstOut(a, n);
     1905        _digraph->firstOut(a._edge, n);
    19011906        a._forward = true;
    19021907      }
     
    19041909    void nextOut(Arc &a) const {
    19051910      if (!a._forward) {
    1906         Node n = _digraph->target(a);
    1907         _digraph->nextIn(a);
    1908         if (static_cast<const Edge&>(a) == INVALID ) {
    1909           _digraph->firstOut(a, n);
     1911        Node n = _digraph->target(a._edge);
     1912        _digraph->nextIn(a._edge);
     1913        if (a._edge == INVALID) {
     1914          _digraph->firstOut(a._edge, n);
    19101915          a._forward = true;
    19111916        }
    19121917      }
    19131918      else {
    1914         _digraph->nextOut(a);
     1919        _digraph->nextOut(a._edge);
    19151920      }
    19161921    }
    19171922
    19181923    void firstIn(Arc &a, const Node &n) const {
    1919       _digraph->firstOut(a, n);
    1920       if (static_cast<const Edge&>(a) != INVALID ) {
     1924      _digraph->firstOut(a._edge, n);
     1925      if (a._edge != INVALID ) {
    19211926        a._forward = false;
    19221927      } else {
    1923         _digraph->firstIn(a, n);
     1928        _digraph->firstIn(a._edge, n);
    19241929        a._forward = true;
    19251930      }
     
    19271932    void nextIn(Arc &a) const {
    19281933      if (!a._forward) {
    1929         Node n = _digraph->source(a);
    1930         _digraph->nextOut(a);
    1931         if( static_cast<const Edge&>(a) == INVALID ) {
    1932           _digraph->firstIn(a, n);
     1934        Node n = _digraph->source(a._edge);
     1935        _digraph->nextOut(a._edge);
     1936        if (a._edge == INVALID ) {
     1937          _digraph->firstIn(a._edge, n);
    19331938          a._forward = true;
    19341939        }
    19351940      }
    19361941      else {
    1937         _digraph->nextIn(a);
     1942        _digraph->nextIn(a._edge);
    19381943      }
    19391944    }
     
    19681973
    19691974    Node source(const Arc &a) const {
    1970       return a._forward ? _digraph->source(a) : _digraph->target(a);
     1975      return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
    19711976    }
    19721977
    19731978    Node target(const Arc &a) const {
    1974       return a._forward ? _digraph->target(a) : _digraph->source(a);
     1979      return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
    19751980    }
    19761981
    19771982    static Arc direct(const Edge &e, bool d) {
    19781983      return Arc(e, d);
    1979     }
    1980     Arc direct(const Edge &e, const Node& n) const {
    1981       return Arc(e, _digraph->source(e) == n);
    19821984    }
    19831985
     
    20632065  private:
    20642066
    2065     template <typename _Value>
     2067    template <typename V>
    20662068    class ArcMapBase {
    20672069    private:
    20682070
    2069       typedef typename Digraph::template ArcMap<_Value> MapImpl;
     2071      typedef typename DGR::template ArcMap<V> MapImpl;
    20702072
    20712073    public:
     
    20732075      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
    20742076
    2075       typedef _Value Value;
     2077      typedef V Value;
    20762078      typedef Arc Key;
    20772079      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
     
    20802082      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
    20812083
    2082       ArcMapBase(const Adaptor& adaptor) :
     2084      ArcMapBase(const UndirectorBase<DGR>& adaptor) :
    20832085        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
    20842086
    2085       ArcMapBase(const Adaptor& adaptor, const Value& v)
    2086         : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
    2087 
    2088       void set(const Arc& a, const Value& v) {
     2087      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
     2088        : _forward(*adaptor._digraph, value),
     2089          _backward(*adaptor._digraph, value) {}
     2090
     2091      void set(const Arc& a, const V& value) {
    20892092        if (direction(a)) {
    2090           _forward.set(a, v);
     2093          _forward.set(a, value);
    20912094        } else {
    2092           _backward.set(a, v);
     2095          _backward.set(a, value);
    20932096        }
    20942097      }
     
    21182121  public:
    21192122
    2120     template <typename _Value>
    2121     class NodeMap : public Digraph::template NodeMap<_Value> {
     2123    template <typename V>
     2124    class NodeMap : public DGR::template NodeMap<V> {
     2125      typedef typename DGR::template NodeMap<V> Parent;
     2126
    21222127    public:
    2123 
    2124       typedef _Value Value;
    2125       typedef typename Digraph::template NodeMap<Value> Parent;
    2126 
    2127       explicit NodeMap(const Adaptor& adaptor)
     2128      typedef V Value;
     2129
     2130      explicit NodeMap(const UndirectorBase<DGR>& adaptor)
    21282131        : Parent(*adaptor._digraph) {}
    21292132
    2130       NodeMap(const Adaptor& adaptor, const _Value& value)
     2133      NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
    21312134        : Parent(*adaptor._digraph, value) { }
    21322135
     
    21442147    };
    21452148
    2146     template <typename _Value>
     2149    template <typename V>
    21472150    class ArcMap
    2148       : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
    2149     {
     2151      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
     2152      typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
     2153
    21502154    public:
    2151       typedef _Value Value;
    2152       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    2153 
    2154       explicit ArcMap(const Adaptor& adaptor)
     2155      typedef V Value;
     2156
     2157      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
    21552158        : Parent(adaptor) {}
    21562159
    2157       ArcMap(const Adaptor& adaptor, const Value& value)
     2160      ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
    21582161        : Parent(adaptor, value) {}
    21592162
     
    21702173    };
    21712174
    2172     template <typename _Value>
    2173     class EdgeMap : public Digraph::template ArcMap<_Value> {
     2175    template <typename V>
     2176    class EdgeMap : public Digraph::template ArcMap<V> {
     2177      typedef typename Digraph::template ArcMap<V> Parent;
     2178
    21742179    public:
    2175 
    2176       typedef _Value Value;
    2177       typedef typename Digraph::template ArcMap<Value> Parent;
    2178 
    2179       explicit EdgeMap(const Adaptor& adaptor)
     2180      typedef V Value;
     2181
     2182      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
    21802183        : Parent(*adaptor._digraph) {}
    21812184
    2182       EdgeMap(const Adaptor& adaptor, const Value& value)
     2185      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
    21832186        : Parent(*adaptor._digraph, value) {}
    21842187
     
    21962199    };
    21972200
    2198     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
     2201    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
    21992202    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
    22002203
    2201     typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
     2204    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    22022205    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
     2206   
     2207    typedef EdgeNotifier ArcNotifier;
     2208    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
    22032209
    22042210  protected:
     
    22062212    UndirectorBase() : _digraph(0) {}
    22072213
    2208     Digraph* _digraph;
    2209 
    2210     void setDigraph(Digraph& digraph) {
     2214    DGR* _digraph;
     2215
     2216    void initialize(DGR& digraph) {
    22112217      _digraph = &digraph;
    22122218    }
     
    22272233  /// parameter is set to be \c const.
    22282234  ///
    2229   /// \tparam GR The type of the adapted digraph.
     2235  /// \tparam DGR The type of the adapted digraph.
    22302236  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    22312237  /// It can also be specified to be \c const.
     
    22372243  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
    22382244  /// of the adapted digraph.)
    2239   template<typename GR>
     2245  template<typename DGR>
    22402246#ifdef DOXYGEN
    22412247  class Undirector {
    22422248#else
    22432249  class Undirector :
    2244     public GraphAdaptorExtender<UndirectorBase<GR> > {
     2250    public GraphAdaptorExtender<UndirectorBase<DGR> > {
    22452251#endif
     2252    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
    22462253  public:
    22472254    /// The type of the adapted digraph.
    2248     typedef GR Digraph;
    2249     typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent;
     2255    typedef DGR Digraph;
    22502256  protected:
    22512257    Undirector() { }
     
    22552261    ///
    22562262    /// Creates an undirected graph from the given digraph.
    2257     Undirector(Digraph& digraph) {
    2258       setDigraph(digraph);
     2263    Undirector(DGR& digraph) {
     2264      initialize(digraph);
    22592265    }
    22602266
     
    22632269    /// This map adaptor class adapts two arc maps of the underlying
    22642270    /// digraph to get an arc map of the undirected graph.
    2265     /// Its value type is inherited from the first arc map type
    2266     /// (\c %ForwardMap).
    2267     template <typename ForwardMap, typename BackwardMap>
     2271    /// Its value type is inherited from the first arc map type (\c FW).
     2272    /// \tparam FW The type of the "foward" arc map.
     2273    /// \tparam BK The type of the "backward" arc map.
     2274    template <typename FW, typename BK>
    22682275    class CombinedArcMap {
    22692276    public:
     
    22722279      typedef typename Parent::Arc Key;
    22732280      /// The value type of the map
    2274       typedef typename ForwardMap::Value Value;
    2275 
    2276       typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
    2277 
    2278       typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
    2279       typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
    2280       typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
    2281       typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
     2281      typedef typename FW::Value Value;
     2282
     2283      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
     2284
     2285      typedef typename MapTraits<FW>::ReturnValue ReturnValue;
     2286      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
     2287      typedef typename MapTraits<FW>::ReturnValue Reference;
     2288      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
    22822289
    22832290      /// Constructor
    2284       CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
     2291      CombinedArcMap(FW& forward, BK& backward)
    22852292        : _forward(&forward), _backward(&backward) {}
    22862293
     
    23142321    protected:
    23152322
    2316       ForwardMap* _forward;
    2317       BackwardMap* _backward;
     2323      FW* _forward;
     2324      BK* _backward;
    23182325
    23192326    };
     
    23222329    ///
    23232330    /// This function just returns a combined arc map.
    2324     template <typename ForwardMap, typename BackwardMap>
    2325     static CombinedArcMap<ForwardMap, BackwardMap>
    2326     combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
    2327       return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
    2328     }
    2329 
    2330     template <typename ForwardMap, typename BackwardMap>
    2331     static CombinedArcMap<const ForwardMap, BackwardMap>
    2332     combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
    2333       return CombinedArcMap<const ForwardMap,
    2334         BackwardMap>(forward, backward);
    2335     }
    2336 
    2337     template <typename ForwardMap, typename BackwardMap>
    2338     static CombinedArcMap<ForwardMap, const BackwardMap>
    2339     combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
    2340       return CombinedArcMap<ForwardMap,
    2341         const BackwardMap>(forward, backward);
    2342     }
    2343 
    2344     template <typename ForwardMap, typename BackwardMap>
    2345     static CombinedArcMap<const ForwardMap, const BackwardMap>
    2346     combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
    2347       return CombinedArcMap<const ForwardMap,
    2348         const BackwardMap>(forward, backward);
     2331    template <typename FW, typename BK>
     2332    static CombinedArcMap<FW, BK>
     2333    combinedArcMap(FW& forward, BK& backward) {
     2334      return CombinedArcMap<FW, BK>(forward, backward);
     2335    }
     2336
     2337    template <typename FW, typename BK>
     2338    static CombinedArcMap<const FW, BK>
     2339    combinedArcMap(const FW& forward, BK& backward) {
     2340      return CombinedArcMap<const FW, BK>(forward, backward);
     2341    }
     2342
     2343    template <typename FW, typename BK>
     2344    static CombinedArcMap<FW, const BK>
     2345    combinedArcMap(FW& forward, const BK& backward) {
     2346      return CombinedArcMap<FW, const BK>(forward, backward);
     2347    }
     2348
     2349    template <typename FW, typename BK>
     2350    static CombinedArcMap<const FW, const BK>
     2351    combinedArcMap(const FW& forward, const BK& backward) {
     2352      return CombinedArcMap<const FW, const BK>(forward, backward);
    23492353    }
    23502354
     
    23562360  /// \ingroup graph_adaptors
    23572361  /// \relates Undirector
    2358   template<typename GR>
    2359   Undirector<const GR> undirector(const GR& digraph) {
    2360     return Undirector<const GR>(digraph);
     2362  template<typename DGR>
     2363  Undirector<const DGR> undirector(const DGR& digraph) {
     2364    return Undirector<const DGR>(digraph);
    23612365  }
    23622366
    23632367
    2364   template <typename _Graph, typename _DirectionMap>
     2368  template <typename GR, typename DM>
    23652369  class OrienterBase {
    23662370  public:
    23672371
    2368     typedef _Graph Graph;
    2369     typedef _DirectionMap DirectionMap;
    2370 
    2371     typedef typename Graph::Node Node;
    2372     typedef typename Graph::Edge Arc;
     2372    typedef GR Graph;
     2373    typedef DM DirectionMap;
     2374
     2375    typedef typename GR::Node Node;
     2376    typedef typename GR::Edge Arc;
    23732377
    23742378    void reverseArc(const Arc& arc) {
     
    24492453    int maxArcId() const { return _graph->maxEdgeId(); }
    24502454
    2451     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     2455    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
    24522456    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
    24532457
    2454     typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
     2458    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
    24552459    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
    24562460
    2457     template <typename _Value>
    2458     class NodeMap : public _Graph::template NodeMap<_Value> {
     2461    template <typename V>
     2462    class NodeMap : public GR::template NodeMap<V> {
     2463      typedef typename GR::template NodeMap<V> Parent;
     2464
    24592465    public:
    24602466
    2461       typedef typename _Graph::template NodeMap<_Value> Parent;
    2462 
    2463       explicit NodeMap(const OrienterBase& adapter)
     2467      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
    24642468        : Parent(*adapter._graph) {}
    24652469
    2466       NodeMap(const OrienterBase& adapter, const _Value& value)
     2470      NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
    24672471        : Parent(*adapter._graph, value) {}
    24682472
     
    24802484    };
    24812485
    2482     template <typename _Value>
    2483     class ArcMap : public _Graph::template EdgeMap<_Value> {
     2486    template <typename V>
     2487    class ArcMap : public GR::template EdgeMap<V> {
     2488      typedef typename Graph::template EdgeMap<V> Parent;
     2489
    24842490    public:
    24852491
    2486       typedef typename Graph::template EdgeMap<_Value> Parent;
    2487 
    2488       explicit ArcMap(const OrienterBase& adapter)
     2492      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
    24892493        : Parent(*adapter._graph) { }
    24902494
    2491       ArcMap(const OrienterBase& adapter, const _Value& value)
     2495      ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
    24922496        : Parent(*adapter._graph, value) { }
    24932497
     
    25082512  protected:
    25092513    Graph* _graph;
    2510     DirectionMap* _direction;
    2511 
    2512     void setDirectionMap(DirectionMap& direction) {
     2514    DM* _direction;
     2515
     2516    void initialize(GR& graph, DM& direction) {
     2517      _graph = &graph;
    25132518      _direction = &direction;
    2514     }
    2515 
    2516     void setGraph(Graph& graph) {
    2517       _graph = &graph;
    25182519    }
    25192520
     
    25572558    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
    25582559#endif
     2560    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
    25592561  public:
    25602562
     
    25642566    typedef DM DirectionMap;
    25652567
    2566     typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
    25672568    typedef typename Parent::Arc Arc;
     2569
    25682570  protected:
    25692571    Orienter() { }
     2572
    25702573  public:
    25712574
     
    25732576    ///
    25742577    /// Constructor of the adaptor.
    2575     Orienter(Graph& graph, DirectionMap& direction) {
    2576       setGraph(graph);
    2577       setDirectionMap(direction);
     2578    Orienter(GR& graph, DM& direction) {
     2579      Parent::initialize(graph, direction);
    25782580    }
    25792581
     
    25952597  template<typename GR, typename DM>
    25962598  Orienter<const GR, DM>
    2597   orienter(const GR& graph, DM& direction_map) {
    2598     return Orienter<const GR, DM>(graph, direction_map);
     2599  orienter(const GR& graph, DM& direction) {
     2600    return Orienter<const GR, DM>(graph, direction);
    25992601  }
    26002602
    26012603  template<typename GR, typename DM>
    26022604  Orienter<const GR, const DM>
    2603   orienter(const GR& graph, const DM& direction_map) {
    2604     return Orienter<const GR, const DM>(graph, direction_map);
     2605  orienter(const GR& graph, const DM& direction) {
     2606    return Orienter<const GR, const DM>(graph, direction);
    26052607  }
    26062608
    26072609  namespace _adaptor_bits {
    26082610
    2609     template<typename Digraph,
    2610              typename CapacityMap,
    2611              typename FlowMap,
    2612              typename Tolerance>
     2611    template <typename DGR, typename CM, typename FM, typename TL>
    26132612    class ResForwardFilter {
    26142613    public:
    26152614
    2616       typedef typename Digraph::Arc Key;
     2615      typedef typename DGR::Arc Key;
    26172616      typedef bool Value;
    26182617
    26192618    private:
    26202619
    2621       const CapacityMap* _capacity;
    2622       const FlowMap* _flow;
    2623       Tolerance _tolerance;
     2620      const CM* _capacity;
     2621      const FM* _flow;
     2622      TL _tolerance;
     2623
    26242624    public:
    26252625
    2626       ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
    2627                        const Tolerance& tolerance = Tolerance())
     2626      ResForwardFilter(const CM& capacity, const FM& flow,
     2627                       const TL& tolerance = TL())
    26282628        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
    26292629
    2630       bool operator[](const typename Digraph::Arc& a) const {
     2630      bool operator[](const typename DGR::Arc& a) const {
    26312631        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
    26322632      }
    26332633    };
    26342634
    2635     template<typename Digraph,
    2636              typename CapacityMap,
    2637              typename FlowMap,
    2638              typename Tolerance>
     2635    template<typename DGR,typename CM, typename FM, typename TL>
    26392636    class ResBackwardFilter {
    26402637    public:
    26412638
    2642       typedef typename Digraph::Arc Key;
     2639      typedef typename DGR::Arc Key;
    26432640      typedef bool Value;
    26442641
    26452642    private:
    26462643
    2647       const CapacityMap* _capacity;
    2648       const FlowMap* _flow;
    2649       Tolerance _tolerance;
     2644      const CM* _capacity;
     2645      const FM* _flow;
     2646      TL _tolerance;
    26502647
    26512648    public:
    26522649
    2653       ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
    2654                         const Tolerance& tolerance = Tolerance())
     2650      ResBackwardFilter(const CM& capacity, const FM& flow,
     2651                        const TL& tolerance = TL())
    26552652        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
    26562653
    2657       bool operator[](const typename Digraph::Arc& a) const {
     2654      bool operator[](const typename DGR::Arc& a) const {
    26582655        return _tolerance.positive((*_flow)[a]);
    26592656      }
     
    26672664  /// flow and circulation problems.
    26682665  ///
    2669   /// Residual can be used for composing the \e residual digraph for directed
    2670   /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
    2671   /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
    2672   /// functions on the arcs.
     2666  /// ResidualDigraph can be used for composing the \e residual digraph
     2667  /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
     2668  /// be a directed graph and let \f$ F \f$ be a number type.
     2669  /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
    26732670  /// This adaptor implements a digraph structure with node set \f$ V \f$
    26742671  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
     
    26822679  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    26832680  ///
    2684   /// \tparam GR The type of the adapted digraph.
     2681  /// \tparam DGR The type of the adapted digraph.
    26852682  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    26862683  /// It is implicitly \c const.
     
    27042701  /// is convertible to the \c Arc type of the adapted digraph.
    27052702#ifdef DOXYGEN
    2706   template<typename GR, typename CM, typename FM, typename TL>
    2707   class Residual
     2703  template<typename DGR, typename CM, typename FM, typename TL>
     2704  class ResidualDigraph
    27082705#else
    2709   template<typename GR,
    2710            typename CM = typename GR::template ArcMap<int>,
     2706  template<typename DGR,
     2707           typename CM = typename DGR::template ArcMap<int>,
    27112708           typename FM = CM,
    27122709           typename TL = Tolerance<typename CM::Value> >
    2713   class Residual :
    2714     public FilterArcs<
    2715       Undirector<const GR>,
    2716       typename Undirector<const GR>::template CombinedArcMap<
    2717         _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,
    2718         _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >
     2710  class ResidualDigraph
     2711    : public SubDigraph<
     2712        Undirector<const DGR>,
     2713        ConstMap<typename DGR::Node, Const<bool, true> >,
     2714        typename Undirector<const DGR>::template CombinedArcMap<
     2715          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
     2716          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
    27192717#endif
    27202718  {
     
    27222720
    27232721    /// The type of the underlying digraph.
    2724     typedef GR Digraph;
     2722    typedef DGR Digraph;
    27252723    /// The type of the capacity map.
    27262724    typedef CM CapacityMap;
     
    27312729
    27322730    typedef typename CapacityMap::Value Value;
    2733     typedef Residual Adaptor;
     2731    typedef ResidualDigraph Adaptor;
    27342732
    27352733  protected:
     
    27372735    typedef Undirector<const Digraph> Undirected;
    27382736
    2739     typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
    2740                                             FlowMap, Tolerance> ForwardFilter;
    2741 
    2742     typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
    2743                                              FlowMap, Tolerance> BackwardFilter;
     2737    typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
     2738
     2739    typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
     2740                                            FM, TL> ForwardFilter;
     2741
     2742    typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
     2743                                             FM, TL> BackwardFilter;
    27442744
    27452745    typedef typename Undirected::
    27462746      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
    27472747
    2748     typedef FilterArcs<Undirected, ArcFilter> Parent;
     2748    typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
    27492749
    27502750    const CapacityMap* _capacity;
     
    27522752
    27532753    Undirected _graph;
     2754    NodeFilter _node_filter;
    27542755    ForwardFilter _forward_filter;
    27552756    BackwardFilter _backward_filter;
     
    27622763    /// Constructor of the residual digraph adaptor. The parameters are the
    27632764    /// digraph, the capacity map, the flow map, and a tolerance object.
    2764     Residual(const Digraph& digraph, const CapacityMap& capacity,
    2765              FlowMap& flow, const Tolerance& tolerance = Tolerance())
    2766       : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
     2765    ResidualDigraph(const DGR& digraph, const CM& capacity,
     2766                    FM& flow, const TL& tolerance = Tolerance())
     2767      : Parent(), _capacity(&capacity), _flow(&flow),
     2768        _graph(digraph), _node_filter(),
    27672769        _forward_filter(capacity, flow, tolerance),
    27682770        _backward_filter(capacity, flow, tolerance),
    27692771        _arc_filter(_forward_filter, _backward_filter)
    27702772    {
    2771       Parent::setDigraph(_graph);
    2772       Parent::setArcFilterMap(_arc_filter);
     2773      Parent::initialize(_graph, _node_filter, _arc_filter);
    27732774    }
    27742775
     
    28462847
    28472848      /// Constructor
    2848       ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
     2849      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
     2850        : _adaptor(&adaptor) {}
    28492851
    28502852      /// Returns the value associated with the given residual arc
     
    28662868  /// \brief Returns a (read-only) Residual adaptor
    28672869  ///
    2868   /// This function just returns a (read-only) \ref Residual adaptor.
     2870  /// This function just returns a (read-only) \ref ResidualDigraph adaptor.
    28692871  /// \ingroup graph_adaptors
    2870   /// \relates Residual
    2871   template<typename GR, typename CM, typename FM>
    2872   Residual<GR, CM, FM> residual(const GR& digraph,
    2873                                 const CM& capacity_map,
    2874                                 FM& flow_map) {
    2875     return Residual<GR, CM, FM> (digraph, capacity_map, flow_map);
     2872  /// \relates ResidualDigraph
     2873    template<typename DGR, typename CM, typename FM>
     2874  ResidualDigraph<DGR, CM, FM>
     2875  residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
     2876    return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
    28762877  }
    28772878
    28782879
    2879   template <typename _Digraph>
     2880  template <typename DGR>
    28802881  class SplitNodesBase {
    2881   public:
    2882 
    2883     typedef _Digraph Digraph;
    2884     typedef DigraphAdaptorBase<const _Digraph> Parent;
     2882    typedef DigraphAdaptorBase<const DGR> Parent;
     2883
     2884  public:
     2885
     2886    typedef DGR Digraph;
    28852887    typedef SplitNodesBase Adaptor;
    28862888
    2887     typedef typename Digraph::Node DigraphNode;
    2888     typedef typename Digraph::Arc DigraphArc;
     2889    typedef typename DGR::Node DigraphNode;
     2890    typedef typename DGR::Arc DigraphArc;
    28892891
    28902892    class Node;
     
    31503152  private:
    31513153
    3152     template <typename _Value>
     3154    template <typename V>
    31533155    class NodeMapBase
    3154       : public MapTraits<typename Parent::template NodeMap<_Value> > {
    3155       typedef typename Parent::template NodeMap<_Value> NodeImpl;
     3156      : public MapTraits<typename Parent::template NodeMap<V> > {
     3157      typedef typename Parent::template NodeMap<V> NodeImpl;
    31563158    public:
    31573159      typedef Node Key;
    3158       typedef _Value Value;
     3160      typedef V Value;
    31593161      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
    31603162      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
     
    31633165      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
    31643166
    3165       NodeMapBase(const Adaptor& adaptor)
     3167      NodeMapBase(const SplitNodesBase<DGR>& adaptor)
    31663168        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
    3167       NodeMapBase(const Adaptor& adaptor, const Value& value)
     3169      NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
    31683170        : _in_map(*adaptor._digraph, value),
    31693171          _out_map(*adaptor._digraph, value) {}
    31703172
    3171       void set(const Node& key, const Value& val) {
    3172         if (Adaptor::inNode(key)) { _in_map.set(key, val); }
     3173      void set(const Node& key, const V& val) {
     3174        if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
    31733175        else {_out_map.set(key, val); }
    31743176      }
    31753177
    31763178      ReturnValue operator[](const Node& key) {
    3177         if (Adaptor::inNode(key)) { return _in_map[key]; }
     3179        if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
    31783180        else { return _out_map[key]; }
    31793181      }
     
    31883190    };
    31893191
    3190     template <typename _Value>
     3192    template <typename V>
    31913193    class ArcMapBase
    3192       : public MapTraits<typename Parent::template ArcMap<_Value> > {
    3193       typedef typename Parent::template ArcMap<_Value> ArcImpl;
    3194       typedef typename Parent::template NodeMap<_Value> NodeImpl;
     3194      : public MapTraits<typename Parent::template ArcMap<V> > {
     3195      typedef typename Parent::template ArcMap<V> ArcImpl;
     3196      typedef typename Parent::template NodeMap<V> NodeImpl;
    31953197    public:
    31963198      typedef Arc Key;
    3197       typedef _Value Value;
     3199      typedef V Value;
    31983200      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
    31993201      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
     
    32023204      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
    32033205
    3204       ArcMapBase(const Adaptor& adaptor)
     3206      ArcMapBase(const SplitNodesBase<DGR>& adaptor)
    32053207        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
    3206       ArcMapBase(const Adaptor& adaptor, const Value& value)
     3208      ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
    32073209        : _arc_map(*adaptor._digraph, value),
    32083210          _node_map(*adaptor._digraph, value) {}
    32093211
    3210       void set(const Arc& key, const Value& val) {
    3211         if (Adaptor::origArc(key)) {
    3212           _arc_map.set(key._item.first(), val);
     3212      void set(const Arc& key, const V& val) {
     3213        if (SplitNodesBase<DGR>::origArc(key)) {
     3214          _arc_map.set(static_cast<const DigraphArc&>(key), val);
    32133215        } else {
    3214           _node_map.set(key._item.second(), val);
     3216          _node_map.set(static_cast<const DigraphNode&>(key), val);
    32153217        }
    32163218      }
    32173219
    32183220      ReturnValue operator[](const Arc& key) {
    3219         if (Adaptor::origArc(key)) {
    3220           return _arc_map[key._item.first()];
     3221        if (SplitNodesBase<DGR>::origArc(key)) {
     3222          return _arc_map[static_cast<const DigraphArc&>(key)];
    32213223        } else {
    3222           return _node_map[key._item.second()];
     3224          return _node_map[static_cast<const DigraphNode&>(key)];
    32233225        }
    32243226      }
    32253227
    32263228      ConstReturnValue operator[](const Arc& key) const {
    3227         if (Adaptor::origArc(key)) {
    3228           return _arc_map[key._item.first()];
     3229        if (SplitNodesBase<DGR>::origArc(key)) {
     3230          return _arc_map[static_cast<const DigraphArc&>(key)];
    32293231        } else {
    3230           return _node_map[key._item.second()];
     3232          return _node_map[static_cast<const DigraphNode&>(key)];
    32313233        }
    32323234      }
     
    32393241  public:
    32403242
    3241     template <typename _Value>
     3243    template <typename V>
    32423244    class NodeMap
    3243       : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
    3244     {
     3245      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
     3246      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
     3247
    32453248    public:
    3246       typedef _Value Value;
    3247       typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
    3248 
    3249       NodeMap(const Adaptor& adaptor)
     3249      typedef V Value;
     3250
     3251      NodeMap(const SplitNodesBase<DGR>& adaptor)
    32503252        : Parent(adaptor) {}
    32513253
    3252       NodeMap(const Adaptor& adaptor, const Value& value)
     3254      NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
    32533255        : Parent(adaptor, value) {}
    32543256
     
    32653267    };
    32663268
    3267     template <typename _Value>
     3269    template <typename V>
    32683270    class ArcMap
    3269       : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
    3270     {
     3271      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
     3272      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
     3273
    32713274    public:
    3272       typedef _Value Value;
    3273       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    3274 
    3275       ArcMap(const Adaptor& adaptor)
     3275      typedef V Value;
     3276
     3277      ArcMap(const SplitNodesBase<DGR>& adaptor)
    32763278        : Parent(adaptor) {}
    32773279
    3278       ArcMap(const Adaptor& adaptor, const Value& value)
     3280      ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
    32793281        : Parent(adaptor, value) {}
    32803282
     
    32953297    SplitNodesBase() : _digraph(0) {}
    32963298
    3297     Digraph* _digraph;
    3298 
    3299     void setDigraph(Digraph& digraph) {
     3299    DGR* _digraph;
     3300
     3301    void initialize(Digraph& digraph) {
    33003302      _digraph = &digraph;
    33013303    }
     
    33243326  /// in the adaptor.
    33253327  ///
    3326   /// \tparam GR The type of the adapted digraph.
     3328  /// \tparam DGR The type of the adapted digraph.
    33273329  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    33283330  /// It is implicitly \c const.
     
    33303332  /// \note The \c Node type of this adaptor is converible to the \c Node
    33313333  /// type of the adapted digraph.
    3332   template <typename GR>
     3334  template <typename DGR>
    33333335#ifdef DOXYGEN
    33343336  class SplitNodes {
    33353337#else
    33363338  class SplitNodes
    3337     : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
     3339    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
    33383340#endif
    3339   public:
    3340     typedef GR Digraph;
    3341     typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
    3342 
    3343     typedef typename Digraph::Node DigraphNode;
    3344     typedef typename Digraph::Arc DigraphArc;
     3341    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
     3342
     3343  public:
     3344    typedef DGR Digraph;
     3345
     3346    typedef typename DGR::Node DigraphNode;
     3347    typedef typename DGR::Arc DigraphArc;
    33453348
    33463349    typedef typename Parent::Node Node;
     
    33503353    ///
    33513354    /// Constructor of the adaptor.
    3352     SplitNodes(const Digraph& g) {
    3353       Parent::setDigraph(g);
     3355    SplitNodes(const DGR& g) {
     3356      Parent::initialize(g);
    33543357    }
    33553358
     
    34203423    /// This map adaptor class adapts two node maps of the original digraph
    34213424    /// to get a node map of the split digraph.
    3422     /// Its value type is inherited from the first node map type
    3423     /// (\c InNodeMap).
    3424     template <typename InNodeMap, typename OutNodeMap>
     3425    /// Its value type is inherited from the first node map type (\c IN).
     3426    /// \tparam IN The type of the node map for the in-nodes.
     3427    /// \tparam OUT The type of the node map for the out-nodes.
     3428    template <typename IN, typename OUT>
    34253429    class CombinedNodeMap {
    34263430    public:
     
    34293433      typedef Node Key;
    34303434      /// The value type of the map
    3431       typedef typename InNodeMap::Value Value;
    3432 
    3433       typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
    3434       typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
    3435       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
    3436       typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
    3437       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
     3435      typedef typename IN::Value Value;
     3436
     3437      typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
     3438      typedef typename MapTraits<IN>::ReturnValue ReturnValue;
     3439      typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
     3440      typedef typename MapTraits<IN>::ReturnValue Reference;
     3441      typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
    34383442
    34393443      /// Constructor
    3440       CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
     3444      CombinedNodeMap(IN& in_map, OUT& out_map)
    34413445        : _in_map(in_map), _out_map(out_map) {}
    34423446
    34433447      /// Returns the value associated with the given key.
    34443448      Value operator[](const Key& key) const {
    3445         if (Parent::inNode(key)) {
     3449        if (SplitNodesBase<const DGR>::inNode(key)) {
    34463450          return _in_map[key];
    34473451        } else {
     
    34523456      /// Returns a reference to the value associated with the given key.
    34533457      Value& operator[](const Key& key) {
    3454         if (Parent::inNode(key)) {
     3458        if (SplitNodesBase<const DGR>::inNode(key)) {
    34553459          return _in_map[key];
    34563460        } else {
     
    34613465      /// Sets the value associated with the given key.
    34623466      void set(const Key& key, const Value& value) {
    3463         if (Parent::inNode(key)) {
     3467        if (SplitNodesBase<const DGR>::inNode(key)) {
    34643468          _in_map.set(key, value);
    34653469        } else {
     
    34703474    private:
    34713475
    3472       InNodeMap& _in_map;
    3473       OutNodeMap& _out_map;
     3476      IN& _in_map;
     3477      OUT& _out_map;
    34743478
    34753479    };
     
    34793483    ///
    34803484    /// This function just returns a combined node map.
    3481     template <typename InNodeMap, typename OutNodeMap>
    3482     static CombinedNodeMap<InNodeMap, OutNodeMap>
    3483     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
    3484       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
    3485     }
    3486 
    3487     template <typename InNodeMap, typename OutNodeMap>
    3488     static CombinedNodeMap<const InNodeMap, OutNodeMap>
    3489     combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
    3490       return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
    3491     }
    3492 
    3493     template <typename InNodeMap, typename OutNodeMap>
    3494     static CombinedNodeMap<InNodeMap, const OutNodeMap>
    3495     combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
    3496       return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
    3497     }
    3498 
    3499     template <typename InNodeMap, typename OutNodeMap>
    3500     static CombinedNodeMap<const InNodeMap, const OutNodeMap>
    3501     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
    3502       return CombinedNodeMap<const InNodeMap,
    3503         const OutNodeMap>(in_map, out_map);
     3485    template <typename IN, typename OUT>
     3486    static CombinedNodeMap<IN, OUT>
     3487    combinedNodeMap(IN& in_map, OUT& out_map) {
     3488      return CombinedNodeMap<IN, OUT>(in_map, out_map);
     3489    }
     3490
     3491    template <typename IN, typename OUT>
     3492    static CombinedNodeMap<const IN, OUT>
     3493    combinedNodeMap(const IN& in_map, OUT& out_map) {
     3494      return CombinedNodeMap<const IN, OUT>(in_map, out_map);
     3495    }
     3496
     3497    template <typename IN, typename OUT>
     3498    static CombinedNodeMap<IN, const OUT>
     3499    combinedNodeMap(IN& in_map, const OUT& out_map) {
     3500      return CombinedNodeMap<IN, const OUT>(in_map, out_map);
     3501    }
     3502
     3503    template <typename IN, typename OUT>
     3504    static CombinedNodeMap<const IN, const OUT>
     3505    combinedNodeMap(const IN& in_map, const OUT& out_map) {
     3506      return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
    35043507    }
    35053508
     
    35093512    /// This map adaptor class adapts an arc map and a node map of the
    35103513    /// original digraph to get an arc map of the split digraph.
    3511     /// Its value type is inherited from the original arc map type
    3512     /// (\c ArcMap).
    3513     template <typename ArcMap, typename NodeMap>
     3514    /// Its value type is inherited from the original arc map type (\c AM).
     3515    /// \tparam AM The type of the arc map.
     3516    /// \tparam NM the type of the node map.
     3517    template <typename AM, typename NM>
    35143518    class CombinedArcMap {
    35153519    public:
     
    35183522      typedef Arc Key;
    35193523      /// The value type of the map
    3520       typedef typename ArcMap::Value Value;
    3521 
    3522       typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
    3523       typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
    3524       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
    3525       typedef typename MapTraits<ArcMap>::ReturnValue Reference;
    3526       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
     3524      typedef typename AM::Value Value;
     3525
     3526      typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
     3527      typedef typename MapTraits<AM>::ReturnValue ReturnValue;
     3528      typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
     3529      typedef typename MapTraits<AM>::ReturnValue Reference;
     3530      typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
    35273531
    35283532      /// Constructor
    3529       CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
     3533      CombinedArcMap(AM& arc_map, NM& node_map)
    35303534        : _arc_map(arc_map), _node_map(node_map) {}
    35313535
    35323536      /// Returns the value associated with the given key.
    35333537      Value operator[](const Key& arc) const {
    3534         if (Parent::origArc(arc)) {
     3538        if (SplitNodesBase<const DGR>::origArc(arc)) {
    35353539          return _arc_map[arc];
    35363540        } else {
     
    35413545      /// Returns a reference to the value associated with the given key.
    35423546      Value& operator[](const Key& arc) {
    3543         if (Parent::origArc(arc)) {
     3547        if (SplitNodesBase<const DGR>::origArc(arc)) {
    35443548          return _arc_map[arc];
    35453549        } else {
     
    35503554      /// Sets the value associated with the given key.
    35513555      void set(const Arc& arc, const Value& val) {
    3552         if (Parent::origArc(arc)) {
     3556        if (SplitNodesBase<const DGR>::origArc(arc)) {
    35533557          _arc_map.set(arc, val);
    35543558        } else {
     
    35583562
    35593563    private:
    3560       ArcMap& _arc_map;
    3561       NodeMap& _node_map;
     3564
     3565      AM& _arc_map;
     3566      NM& _node_map;
     3567
    35623568    };
    35633569
     
    35963602  /// \ingroup graph_adaptors
    35973603  /// \relates SplitNodes
    3598   template<typename GR>
    3599   SplitNodes<GR>
    3600   splitNodes(const GR& digraph) {
    3601     return SplitNodes<GR>(digraph);
     3604  template<typename DGR>
     3605  SplitNodes<DGR>
     3606  splitNodes(const DGR& digraph) {
     3607    return SplitNodes<DGR>(digraph);
    36023608  }
    36033609
     3610#undef LEMON_SCOPE_FIX
     3611
    36043612} //namespace lemon
    36053613
  • lemon/base.cc

    r463 r554  
    2424namespace lemon {
    2525
    26   float Tolerance<float>::def_epsilon = 1e-4;
     26  float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
    2727  double Tolerance<double>::def_epsilon = 1e-10;
    2828  long double Tolerance<long double>::def_epsilon = 1e-14;
  • lemon/bfs.h

    r463 r525  
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a PredMap.
    53 
    54     ///This function instantiates a PredMap.
     52    ///Instantiates a \c PredMap.
     53
     54    ///This function instantiates a \ref PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///PredMap.
     56    ///\ref PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
     
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6666    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     67    ///Instantiates a \c ProcessedMap.
     68
     69    ///This function instantiates a \ref ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     71    ///we would like to define the \ref ProcessedMap
    7272#ifdef DOXYGEN
    7373    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8484    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8585    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     86    ///Instantiates a \c ReachedMap.
     87
     88    ///This function instantiates a \ref ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     90    ///we would like to define the \ref ReachedMap.
    9191    static ReachedMap *createReachedMap(const Digraph &g)
    9292    {
     
    9999    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100100    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     101    ///Instantiates a \c DistMap.
     102
     103    ///This function instantiates a \ref DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     105    ///\ref DistMap.
    106106    static DistMap *createDistMap(const Digraph &g)
    107107    {
     
    222222    };
    223223    ///\brief \ref named-templ-param "Named parameter" for setting
    224     ///PredMap type.
     224    ///\c PredMap type.
    225225    ///
    226226    ///\ref named-templ-param "Named parameter" for setting
    227     ///PredMap type.
     227    ///\c PredMap type.
    228228    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    229229    template <class T>
     
    242242    };
    243243    ///\brief \ref named-templ-param "Named parameter" for setting
    244     ///DistMap type.
     244    ///\c DistMap type.
    245245    ///
    246246    ///\ref named-templ-param "Named parameter" for setting
    247     ///DistMap type.
     247    ///\c DistMap type.
    248248    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    249249    template <class T>
     
    262262    };
    263263    ///\brief \ref named-templ-param "Named parameter" for setting
    264     ///ReachedMap type.
     264    ///\c ReachedMap type.
    265265    ///
    266266    ///\ref named-templ-param "Named parameter" for setting
    267     ///ReachedMap type.
     267    ///\c ReachedMap type.
    268268    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269269    template <class T>
     
    282282    };
    283283    ///\brief \ref named-templ-param "Named parameter" for setting
    284     ///ProcessedMap type.
     284    ///\c ProcessedMap type.
    285285    ///
    286286    ///\ref named-templ-param "Named parameter" for setting
    287     ///ProcessedMap type.
     287    ///\c ProcessedMap type.
    288288    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    289289    template <class T>
     
    301301    };
    302302    ///\brief \ref named-templ-param "Named parameter" for setting
    303     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     303    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    304304    ///
    305305    ///\ref named-templ-param "Named parameter" for setting
    306     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     306    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    307307    ///If you don't set it explicitly, it will be automatically allocated.
    308308    struct SetStandardProcessedMap :
     
    11951195  /// This class defines the interface of the BfsVisit events, and
    11961196  /// it could be the base of a real visitor class.
    1197   template <typename _Digraph>
     1197  template <typename GR>
    11981198  struct BfsVisitor {
    1199     typedef _Digraph Digraph;
     1199    typedef GR Digraph;
    12001200    typedef typename Digraph::Arc Arc;
    12011201    typedef typename Digraph::Node Node;
     
    12251225  };
    12261226#else
    1227   template <typename _Digraph>
     1227  template <typename GR>
    12281228  struct BfsVisitor {
    1229     typedef _Digraph Digraph;
     1229    typedef GR Digraph;
    12301230    typedef typename Digraph::Arc Arc;
    12311231    typedef typename Digraph::Node Node;
     
    12551255  ///
    12561256  /// Default traits class of BfsVisit class.
    1257   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1258   template<class _Digraph>
     1257  /// \tparam GR The type of the digraph the algorithm runs on.
     1258  template<class GR>
    12591259  struct BfsVisitDefaultTraits {
    12601260
    12611261    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef _Digraph Digraph;
     1262    typedef GR Digraph;
    12631263
    12641264    /// \brief The type of the map that indicates which nodes are reached.
     
    12811281  /// \ingroup search
    12821282  ///
    1283   /// \brief %BFS algorithm class with visitor interface.
     1283  /// \brief BFS algorithm class with visitor interface.
    12841284  ///
    1285   /// This class provides an efficient implementation of the %BFS algorithm
     1285  /// This class provides an efficient implementation of the BFS algorithm
    12861286  /// with visitor interface.
    12871287  ///
    1288   /// The %BfsVisit class provides an alternative interface to the Bfs
     1288  /// The BfsVisit class provides an alternative interface to the Bfs
    12891289  /// class. It works with callback mechanism, the BfsVisit object calls
    12901290  /// the member functions of the \c Visitor class on every BFS event.
     
    12951295  /// instead.
    12961296  ///
    1297   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1298   /// The default value is
    1299   /// \ref ListDigraph. The value of _Digraph is not used directly by
    1300   /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
    1301   /// \tparam _Visitor The Visitor type that is used by the algorithm.
    1302   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
     1297  /// \tparam GR The type of the digraph the algorithm runs on.
     1298  /// The default type is \ref ListDigraph.
     1299  /// The value of GR is not used directly by \ref BfsVisit,
     1300  /// it is only passed to \ref BfsVisitDefaultTraits.
     1301  /// \tparam VS The Visitor type that is used by the algorithm.
     1302  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
    13031303  /// does not observe the BFS events. If you want to observe the BFS
    13041304  /// events, you should implement your own visitor class.
    1305   /// \tparam _Traits Traits class to set various data types used by the
     1305  /// \tparam TR Traits class to set various data types used by the
    13061306  /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
     1307  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
    13081308  /// See \ref BfsVisitDefaultTraits for the documentation of
    13091309  /// a BFS visit traits class.
    13101310#ifdef DOXYGEN
    1311   template <typename _Digraph, typename _Visitor, typename _Traits>
     1311  template <typename GR, typename VS, typename TR>
    13121312#else
    1313   template <typename _Digraph = ListDigraph,
    1314             typename _Visitor = BfsVisitor<_Digraph>,
    1315             typename _Traits = BfsVisitDefaultTraits<_Digraph> >
     1313  template <typename GR = ListDigraph,
     1314            typename VS = BfsVisitor<GR>,
     1315            typename TR = BfsVisitDefaultTraits<GR> >
    13161316#endif
    13171317  class BfsVisit {
     
    13191319
    13201320    ///The traits class.
    1321     typedef _Traits Traits;
     1321    typedef TR Traits;
    13221322
    13231323    ///The type of the digraph the algorithm runs on.
     
    13251325
    13261326    ///The visitor type used by the algorithm.
    1327     typedef _Visitor Visitor;
     1327    typedef VS Visitor;
    13281328
    13291329    ///The type of the map that indicates which nodes are reached.
  • lemon/bin_heap.h

    r463 r631  
    3434  ///\brief A Binary Heap implementation.
    3535  ///
    36   ///This class implements the \e binary \e heap data structure. A \e heap
    37   ///is a data structure for storing items with specified values called \e
    38   ///priorities in such a way that finding the item with minimum priority is
    39   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    40   ///one can change the priority of an item, add or erase an item, etc.
     36  ///This class implements the \e binary \e heap data structure.
     37  ///
     38  ///A \e heap is a data structure for storing items with specified values
     39  ///called \e priorities in such a way that finding the item with minimum
     40  ///priority is efficient. \c Comp specifies the ordering of the priorities.
     41  ///In a heap one can change the priority of an item, add or erase an
     42  ///item, etc.
    4143  ///
    42   ///\tparam _Prio Type of the priority of the items.
    43   ///\tparam _ItemIntMap A read and writable Item int map, used internally
     44  ///\tparam PR Type of the priority of the items.
     45  ///\tparam IM A read and writable item map with int values, used internally
    4446  ///to handle the cross references.
    45   ///\tparam _Compare A class for the ordering of the priorities. The
    46   ///default is \c std::less<_Prio>.
     47  ///\tparam Comp A functor class for the ordering of the priorities.
     48  ///The default is \c std::less<PR>.
    4749  ///
    4850  ///\sa FibHeap
    4951  ///\sa Dijkstra
    50   template <typename _Prio, typename _ItemIntMap,
    51             typename _Compare = std::less<_Prio> >
     52  template <typename PR, typename IM, typename Comp = std::less<PR> >
    5253  class BinHeap {
    5354
    5455  public:
    5556    ///\e
    56     typedef _ItemIntMap ItemIntMap;
    57     ///\e
    58     typedef _Prio Prio;
     57    typedef IM ItemIntMap;
     58    ///\e
     59    typedef PR Prio;
    5960    ///\e
    6061    typedef typename ItemIntMap::Key Item;
     
    6263    typedef std::pair<Item,Prio> Pair;
    6364    ///\e
    64     typedef _Compare Compare;
     65    typedef Comp Compare;
    6566
    6667    /// \brief Type to represent the items states.
     
    7071    /// heap's point of view, but may be useful to the user.
    7172    ///
    72     /// The ItemIntMap \e should be initialized in such way that it maps
    73     /// PRE_HEAP (-1) to any element to be put in the heap...
     73    /// The item-int map must be initialized in such way that it assigns
     74    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    7475    enum State {
    75       IN_HEAP = 0,
    76       PRE_HEAP = -1,
    77       POST_HEAP = -2
     76      IN_HEAP = 0,    ///< = 0.
     77      PRE_HEAP = -1,  ///< = -1.
     78      POST_HEAP = -2  ///< = -2.
    7879    };
    7980
    8081  private:
    81     std::vector<Pair> data;
    82     Compare comp;
    83     ItemIntMap &iim;
     82    std::vector<Pair> _data;
     83    Compare _comp;
     84    ItemIntMap &_iim;
    8485
    8586  public:
     
    8788    ///
    8889    /// The constructor.
    89     /// \param _iim should be given to the constructor, since it is used
     90    /// \param map should be given to the constructor, since it is used
     91    /// internally to handle the cross references. The value of the map
     92    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
     93    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
     94
     95    /// \brief The constructor.
     96    ///
     97    /// The constructor.
     98    /// \param map should be given to the constructor, since it is used
    9099    /// internally to handle the cross references. The value of the map
    91100    /// should be PRE_HEAP (-1) for each element.
    92     explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    93 
    94     /// \brief The constructor.
    95     ///
    96     /// The constructor.
    97     /// \param _iim should be given to the constructor, since it is used
    98     /// internally to handle the cross references. The value of the map
    99     /// should be PRE_HEAP (-1) for each element.
    100     ///
    101     /// \param _comp The comparator function object.
    102     BinHeap(ItemIntMap &_iim, const Compare &_comp)
    103       : iim(_iim), comp(_comp) {}
     101    ///
     102    /// \param comp The comparator function object.
     103    BinHeap(ItemIntMap &map, const Compare &comp)
     104      : _iim(map), _comp(comp) {}
    104105
    105106
     
    107108    ///
    108109    /// \brief Returns the number of items stored in the heap.
    109     int size() const { return data.size(); }
     110    int size() const { return _data.size(); }
    110111
    111112    /// \brief Checks if the heap stores no items.
    112113    ///
    113114    /// Returns \c true if and only if the heap stores no items.
    114     bool empty() const { return data.empty(); }
     115    bool empty() const { return _data.empty(); }
    115116
    116117    /// \brief Make empty this heap.
     
    121122    /// each item to \c PRE_HEAP.
    122123    void clear() {
    123       data.clear();
     124      _data.clear();
    124125    }
    125126
     
    129130    static int second_child(int i) { return 2*i+2; }
    130131    bool less(const Pair &p1, const Pair &p2) const {
    131       return comp(p1.second, p2.second);
     132      return _comp(p1.second, p2.second);
    132133    }
    133134
    134135    int bubble_up(int hole, Pair p) {
    135136      int par = parent(hole);
    136       while( hole>0 && less(p,data[par]) ) {
    137         move(data[par],hole);
     137      while( hole>0 && less(p,_data[par]) ) {
     138        move(_data[par],hole);
    138139        hole = par;
    139140        par = parent(hole);
     
    146147      int child = second_child(hole);
    147148      while(child < length) {
    148         if( less(data[child-1], data[child]) ) {
     149        if( less(_data[child-1], _data[child]) ) {
    149150          --child;
    150151        }
    151         if( !less(data[child], p) )
     152        if( !less(_data[child], p) )
    152153          goto ok;
    153         move(data[child], hole);
     154        move(_data[child], hole);
    154155        hole = child;
    155156        child = second_child(hole);
    156157      }
    157158      child--;
    158       if( child<length && less(data[child], p) ) {
    159         move(data[child], hole);
     159      if( child<length && less(_data[child], p) ) {
     160        move(_data[child], hole);
    160161        hole=child;
    161162      }
     
    166167
    167168    void move(const Pair &p, int i) {
    168       data[i] = p;
    169       iim.set(p.first, i);
     169      _data[i] = p;
     170      _iim.set(p.first, i);
    170171    }
    171172
     
    176177    /// \param p The pair to insert.
    177178    void push(const Pair &p) {
    178       int n = data.size();
    179       data.resize(n+1);
     179      int n = _data.size();
     180      _data.resize(n+1);
    180181      bubble_up(n, p);
    181182    }
     
    194195    /// \pre The heap must be nonempty.
    195196    Item top() const {
    196       return data[0].first;
     197      return _data[0].first;
    197198    }
    198199
     
    202203    /// \pre The heap must be nonempty.
    203204    Prio prio() const {
    204       return data[0].second;
     205      return _data[0].second;
    205206    }
    206207
     
    211212    /// \pre The heap must be non-empty.
    212213    void pop() {
    213       int n = data.size()-1;
    214       iim.set(data[0].first, POST_HEAP);
     214      int n = _data.size()-1;
     215      _iim.set(_data[0].first, POST_HEAP);
    215216      if (n > 0) {
    216         bubble_down(0, data[n], n);
    217       }
    218       data.pop_back();
     217        bubble_down(0, _data[n], n);
     218      }
     219      _data.pop_back();
    219220    }
    220221
     
    225226    /// \pre The item should be in the heap.
    226227    void erase(const Item &i) {
    227       int h = iim[i];
    228       int n = data.size()-1;
    229       iim.set(data[h].first, POST_HEAP);
     228      int h = _iim[i];
     229      int n = _data.size()-1;
     230      _iim.set(_data[h].first, POST_HEAP);
    230231      if( h < n ) {
    231         if ( bubble_up(h, data[n]) == h) {
    232           bubble_down(h, data[n], n);
     232        if ( bubble_up(h, _data[n]) == h) {
     233          bubble_down(h, _data[n], n);
    233234        }
    234235      }
    235       data.pop_back();
     236      _data.pop_back();
    236237    }
    237238
     
    240241    ///
    241242    /// This function returns the priority of item \c i.
     243    /// \param i The item.
    242244    /// \pre \c i must be in the heap.
    243     /// \param i The item.
    244245    Prio operator[](const Item &i) const {
    245       int idx = iim[i];
    246       return data[idx].second;
     246      int idx = _iim[i];
     247      return _data[idx].second;
    247248    }
    248249
     
    255256    /// \param p The priority.
    256257    void set(const Item &i, const Prio &p) {
    257       int idx = iim[i];
     258      int idx = _iim[i];
    258259      if( idx < 0 ) {
    259260        push(i,p);
    260261      }
    261       else if( comp(p, data[idx].second) ) {
     262      else if( _comp(p, _data[idx].second) ) {
    262263        bubble_up(idx, Pair(i,p));
    263264      }
    264265      else {
    265         bubble_down(idx, Pair(i,p), data.size());
     266        bubble_down(idx, Pair(i,p), _data.size());
    266267      }
    267268    }
     
    270271    ///
    271272    /// This method decreases the priority of item \c i to \c p.
     273    /// \param i The item.
     274    /// \param p The priority.
    272275    /// \pre \c i must be stored in the heap with priority at least \c
    273276    /// p relative to \c Compare.
     277    void decrease(const Item &i, const Prio &p) {
     278      int idx = _iim[i];
     279      bubble_up(idx, Pair(i,p));
     280    }
     281
     282    /// \brief Increases the priority of \c i to \c p.
     283    ///
     284    /// This method sets the priority of item \c i to \c p.
    274285    /// \param i The item.
    275286    /// \param p The priority.
    276     void decrease(const Item &i, const Prio &p) {
    277       int idx = iim[i];
    278       bubble_up(idx, Pair(i,p));
    279     }
    280 
    281     /// \brief Increases the priority of \c i to \c p.
    282     ///
    283     /// This method sets the priority of item \c i to \c p.
    284287    /// \pre \c i must be stored in the heap with priority at most \c
    285288    /// p relative to \c Compare.
    286     /// \param i The item.
    287     /// \param p The priority.
    288289    void increase(const Item &i, const Prio &p) {
    289       int idx = iim[i];
    290       bubble_down(idx, Pair(i,p), data.size());
     290      int idx = _iim[i];
     291      bubble_down(idx, Pair(i,p), _data.size());
    291292    }
    292293
     
    300301    /// \param i The item.
    301302    State state(const Item &i) const {
    302       int s = iim[i];
     303      int s = _iim[i];
    303304      if( s>=0 )
    304305        s=0;
     
    320321          erase(i);
    321322        }
    322         iim[i] = st;
     323        _iim[i] = st;
    323324        break;
    324325      case IN_HEAP:
     
    334335    /// with the same prioriority as prevoiusly the \c i item.
    335336    void replace(const Item& i, const Item& j) {
    336       int idx = iim[i];
    337       iim.set(i, iim[j]);
    338       iim.set(j, idx);
    339       data[idx].first = j;
     337      int idx = _iim[i];
     338      _iim.set(i, _iim[j]);
     339      _iim.set(j, idx);
     340      _data[idx].first = j;
    340341    }
    341342
  • lemon/bits/array_map.h

    r463 r664  
    4848  public:
    4949    // The graph type.
    50     typedef _Graph Graph;
     50    typedef _Graph GraphType;
    5151    // The item type.
    5252    typedef _Item Item;
     
    6464    typedef _Value& Reference;
    6565
     66    // The map type.
     67    typedef ArrayMap Map;
     68
    6669    // The notifier type.
    6770    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    6871
     72  private:
     73 
    6974    // The MapBase of the Map which imlements the core regisitry function.
    7075    typedef typename Notifier::ObserverBase Parent;
    7176
    72   private:
    7377    typedef std::allocator<Value> Allocator;
    7478
     
    7882    //
    7983    // Graph initialized map constructor.
    80     explicit ArrayMap(const Graph& graph) {
     84    explicit ArrayMap(const GraphType& graph) {
    8185      Parent::attach(graph.notifier(Item()));
    8286      allocate_memory();
     
    9296    //
    9397    // It constructs a map and initialize all of the the map.
    94     ArrayMap(const Graph& graph, const Value& value) {
     98    ArrayMap(const GraphType& graph, const Value& value) {
    9599      Parent::attach(graph.notifier(Item()));
    96100      allocate_memory();
     
    136140    // \brief Template assign operator.
    137141    //
    138     // The given parameter should be conform to the ReadMap
     142    // The given parameter should conform to the ReadMap
    139143    // concecpt and could be indiced by the current item set of
    140144    // the NodeMap. In this case the value for each item
  • lemon/bits/default_map.h

    r463 r674  
    2020#define LEMON_BITS_DEFAULT_MAP_H
    2121
     22#include <lemon/config.h>
    2223#include <lemon/bits/array_map.h>
    2324#include <lemon/bits/vector_map.h>
     
    9798
    9899
    99 #if defined __GNUC__ && !defined __STRICT_ANSI__
     100#if defined LEMON_HAVE_LONG_LONG
    100101
    101102  // long long
     
    153154  class DefaultMap
    154155    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
     156    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     157
    155158  public:
    156     typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
    157159    typedef DefaultMap<_Graph, _Item, _Value> Map;
    158 
    159     typedef typename Parent::Graph Graph;
     160   
     161    typedef typename Parent::GraphType GraphType;
    160162    typedef typename Parent::Value Value;
    161163
    162     explicit DefaultMap(const Graph& graph) : Parent(graph) {}
    163     DefaultMap(const Graph& graph, const Value& value)
     164    explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
     165    DefaultMap(const GraphType& graph, const Value& value)
    164166      : Parent(graph, value) {}
    165167
  • lemon/bits/graph_adaptor_extender.h

    r478 r664  
    2323#include <lemon/error.h>
    2424
    25 #include <lemon/bits/default_map.h>
    26 
    2725namespace lemon {
    2826
    2927  template <typename _Digraph>
    3028  class DigraphAdaptorExtender : public _Digraph {
     29    typedef _Digraph Parent;
     30
    3131  public:
    3232
    33     typedef _Digraph Parent;
    3433    typedef _Digraph Digraph;
    3534    typedef DigraphAdaptorExtender Adaptor;
     
    176175  template <typename _Graph>
    177176  class GraphAdaptorExtender : public _Graph {
     177    typedef _Graph Parent;
     178
    178179  public:
    179180
    180     typedef _Graph Parent;
    181181    typedef _Graph Graph;
    182182    typedef GraphAdaptorExtender Adaptor;
  • lemon/bits/graph_extender.h

    r463 r664  
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
     40    typedef Base Parent;
     41
    4042  public:
    4143
    42     typedef Base Parent;
    4344    typedef DigraphExtender Digraph;
    4445
     
    219220    class NodeMap
    220221      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
    221     public:
    222       typedef DigraphExtender Digraph;
    223222      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    224223
     224    public:
    225225      explicit NodeMap(const Digraph& digraph)
    226226        : Parent(digraph) {}
     
    244244    class ArcMap
    245245      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    246     public:
    247       typedef DigraphExtender Digraph;
    248246      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    249247
     248    public:
    250249      explicit ArcMap(const Digraph& digraph)
    251250        : Parent(digraph) {}
     
    331330  template <typename Base>
    332331  class GraphExtender : public Base {
     332    typedef Base Parent;
     333
    333334  public:
    334335
    335     typedef Base Parent;
    336336    typedef GraphExtender Graph;
    337337
     
    602602    class NodeMap
    603603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    604     public:
    605       typedef GraphExtender Graph;
    606604      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    607605
     606    public:
    608607      NodeMap(const Graph& graph)
    609608        : Parent(graph) {}
     
    627626    class ArcMap
    628627      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    629     public:
    630       typedef GraphExtender Graph;
    631628      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    632629
     630    public:
    633631      ArcMap(const Graph& graph)
    634632        : Parent(graph) {}
     
    652650    class EdgeMap
    653651      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    654     public:
    655       typedef GraphExtender Graph;
    656652      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    657653
     654    public:
    658655      EdgeMap(const Graph& graph)
    659656        : Parent(graph) {}
  • lemon/bits/map_extender.h

    r463 r664  
    3737  template <typename _Map>
    3838  class MapExtender : public _Map {
    39   public:
    40 
    4139    typedef _Map Parent;
     40    typedef typename Parent::GraphType GraphType;
     41
     42  public:
     43
    4244    typedef MapExtender Map;
    43 
    44 
    45     typedef typename Parent::Graph Graph;
    4645    typedef typename Parent::Key Item;
    4746
    4847    typedef typename Parent::Key Key;
    4948    typedef typename Parent::Value Value;
     49    typedef typename Parent::Reference Reference;
     50    typedef typename Parent::ConstReference ConstReference;
    5051
    5152    class MapIt;
     
    5758  public:
    5859
    59     MapExtender(const Graph& graph)
     60    MapExtender(const GraphType& graph)
    6061      : Parent(graph) {}
    6162
    62     MapExtender(const Graph& graph, const Value& value)
     63    MapExtender(const GraphType& graph, const Value& value)
    6364      : Parent(graph, value) {}
    6465
     
    7677  public:
    7778    class MapIt : public Item {
    78     public:
    79 
    80       typedef Item Parent;
     79      typedef Item Parent;
     80
     81    public:
     82
    8183      typedef typename Map::Value Value;
    8284
     
    115117
    116118    class ConstMapIt : public Item {
    117     public:
    118 
    119       typedef Item Parent;
     119      typedef Item Parent;
     120
     121    public:
    120122
    121123      typedef typename Map::Value Value;
     
    146148
    147149    class ItemIt : public Item {
    148     public:
    149 
    150       typedef Item Parent;
     150      typedef Item Parent;
     151
     152    public:
    151153
    152154      ItemIt() {}
     
    177179  template <typename _Graph, typename _Map>
    178180  class SubMapExtender : public _Map {
    179   public:
    180 
    181181    typedef _Map Parent;
     182    typedef _Graph GraphType;
     183
     184  public:
     185
    182186    typedef SubMapExtender Map;
    183 
    184     typedef _Graph Graph;
    185 
    186187    typedef typename Parent::Key Item;
    187188
    188189    typedef typename Parent::Key Key;
    189190    typedef typename Parent::Value Value;
     191    typedef typename Parent::Reference Reference;
     192    typedef typename Parent::ConstReference ConstReference;
    190193
    191194    class MapIt;
     
    197200  public:
    198201
    199     SubMapExtender(const Graph& _graph)
     202    SubMapExtender(const GraphType& _graph)
    200203      : Parent(_graph), graph(_graph) {}
    201204
    202     SubMapExtender(const Graph& _graph, const Value& _value)
     205    SubMapExtender(const GraphType& _graph, const Value& _value)
    203206      : Parent(_graph, _value), graph(_graph) {}
    204207
     
    220223  public:
    221224    class MapIt : public Item {
    222     public:
    223 
    224       typedef Item Parent;
     225      typedef Item Parent;
     226
     227    public:
    225228      typedef typename Map::Value Value;
    226229
     
    259262
    260263    class ConstMapIt : public Item {
    261     public:
    262 
    263       typedef Item Parent;
     264      typedef Item Parent;
     265
     266    public:
    264267
    265268      typedef typename Map::Value Value;
     
    290293
    291294    class ItemIt : public Item {
    292     public:
    293 
    294       typedef Item Parent;
     295      typedef Item Parent;
     296
     297    public:
    295298
    296299      ItemIt() {}
     
    317320  private:
    318321
    319     const Graph& graph;
     322    const GraphType& graph;
    320323
    321324  };
  • lemon/bits/path_dump.h

    r463 r576  
    1717 */
    1818
    19 #ifndef LEMON_BITS_PRED_MAP_PATH_H
    20 #define LEMON_BITS_PRED_MAP_PATH_H
     19#ifndef LEMON_BITS_PATH_DUMP_H
     20#define LEMON_BITS_PATH_DUMP_H
     21
     22#include <lemon/core.h>
     23#include <lemon/concept_check.h>
    2124
    2225namespace lemon {
  • lemon/bits/solver_bits.h

    r482 r566  
    1919#ifndef LEMON_BITS_SOLVER_BITS_H
    2020#define LEMON_BITS_SOLVER_BITS_H
     21
     22#include <vector>
    2123
    2224namespace lemon {
  • lemon/bits/traits.h

    r463 r663  
    3030  struct InvalidType {};
    3131
    32   template <typename _Graph, typename _Item>
     32  template <typename GR, typename _Item>
    3333  class ItemSetTraits {};
    3434
    3535
    36   template <typename Graph, typename Enable = void>
     36  template <typename GR, typename Enable = void>
    3737  struct NodeNotifierIndicator {
    3838    typedef InvalidType Type;
    3939  };
    40   template <typename Graph>
     40  template <typename GR>
    4141  struct NodeNotifierIndicator<
    42     Graph,
    43     typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
    44   > {
    45     typedef typename Graph::NodeNotifier Type;
    46   };
    47 
    48   template <typename _Graph>
    49   class ItemSetTraits<_Graph, typename _Graph::Node> {
     42    GR,
     43    typename enable_if<typename GR::NodeNotifier::Notifier, void>::type
     44  > {
     45    typedef typename GR::NodeNotifier Type;
     46  };
     47
     48  template <typename GR>
     49  class ItemSetTraits<GR, typename GR::Node> {
    5050  public:
    5151
    52     typedef _Graph Graph;
    53 
    54     typedef typename Graph::Node Item;
    55     typedef typename Graph::NodeIt ItemIt;
    56 
    57     typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
    58 
    59     template <typename _Value>
    60     class Map : public Graph::template NodeMap<_Value> {
     52    typedef GR Graph;
     53    typedef GR Digraph;
     54
     55    typedef typename GR::Node Item;