COIN-OR::LEMON - Graph Library

Ignore:
Files:
50 added
4 deleted
113 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 r791  
    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})
     37
     38INCLUDE(FindPythonInterp)
    1239
    1340ENABLE_TESTING()
    1441
    1542ADD_SUBDIRECTORY(lemon)
    16 ADD_SUBDIRECTORY(demo)
    17 ADD_SUBDIRECTORY(doc)
    18 ADD_SUBDIRECTORY(test)
     43IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     44  ADD_SUBDIRECTORY(demo)
     45  ADD_SUBDIRECTORY(tools)
     46  ADD_SUBDIRECTORY(doc)
     47  ADD_SUBDIRECTORY(test)
     48ENDIF()
    1949
    20 IF(WIN32)
    21   INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico
    22     DESTINATION bin)
    23 ENDIF(WIN32)
     50CONFIGURE_FILE(
     51  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
     52  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     53  @ONLY
     54)
     55IF(UNIX)
     56  INSTALL(
     57    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     58    DESTINATION share/lemon/cmake
     59  )
     60ELSEIF(WIN32)
     61  INSTALL(
     62    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     63    DESTINATION cmake
     64  )
     65ENDIF()
    2466
    25 IF(WIN32)
     67IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
    2668  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    27   SET(CPACK_PACKAGE_VENDOR
    28     "EGRES - Egervary Research Group on Combinatorial Optimization")
     69  SET(CPACK_PACKAGE_VENDOR "EGRES")
    2970  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")
     71    "LEMON - Library for Efficient Modeling and Optimization in Networks")
     72  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
    3273
    3374  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     
    3879    "${PROJECT_NAME} ${PROJECT_VERSION}")
    3980
    40   # Variables to generate a component-based installer.
    41   #SET(CPACK_COMPONENTS_ALL headers library html_documentation)
     81  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
    4282
    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")
     83  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
     84  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     85  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
     86  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    4687
    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")
     88  SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
     89    "C++ header files")
     90  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     91    "DLL and import library")
     92  SET(CPACK_COMPONENT_BIN_DESCRIPTION
     93    "Command line utilities")
     94  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     95    "Doxygen generated documentation")
    5396
    54   #SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     97  SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
    5598
    56   #SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
    57   #SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
    58   #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     99  SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     100  SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     101  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
    59102
    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")
     103  SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
     104    "Components needed to develop software using LEMON")
     105  SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
     106    "Documentation of LEMON")
    64107
    65   #SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     108  SET(CPACK_ALL_INSTALL_TYPES Full Developer)
    66109
    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)
     110  SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
     111  SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
     112  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
    70113
    71114  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")
     115  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
     116  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     117  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
    75118  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    76119  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     
    79122  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
    80123  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
    81     CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\"
     124    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
    82125    ")
    83126  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
     
    87130
    88131  INCLUDE(CPack)
    89 ENDIF(WIN32)
     132ENDIF()
  • 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 r799  
    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/LEMONConfig.cmake.in \
     21        cmake/version.cmake.in \
     22        cmake/version.cmake \
     23        cmake/nsis/lemon.ico \
     24        cmake/nsis/uninstall.ico
    1625
    1726pkgconfigdir = $(libdir)/pkgconfig
     
    3544include test/Makefile.am
    3645include doc/Makefile.am
    37 include demo/Makefile.am
    3846include tools/Makefile.am
     47
     48DIST_SUBDIRS = demo
     49
     50demo:
     51        $(MAKE) $(AM_MAKEFLAGS) -C demo
    3952
    4053MRPROPERFILES = \
     
    6477        bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
    6578
    66 .PHONY: mrproper dist-bz2 distcheck-bz2
     79.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 r791  
    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.
     
    3142
    3243AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
     44AC_CHECK_PROG([python_found],[python],[yes],[no])
    3345AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    3446
     
    5466LX_CHECK_CPLEX
    5567LX_CHECK_SOPLEX
    56 LX_CHECK_CLP
     68LX_CHECK_COIN
    5769
    5870AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
    5971AM_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"])
    7372
    7473dnl Disable/enable building the binary tools.
     
    101100dnl Add dependencies on files generated by configure.
    102101AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
    103   ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in'])
     102  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
    104103
    105104AC_CONFIG_FILES([
    106105Makefile
     106demo/Makefile
     107cmake/version.cmake
    107108doc/Doxyfile
    108109lemon/lemon.pc
     
    119120echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    120121echo
     122echo Compiler supports long long... : $long_long_found
     123echo
    121124echo GLPK support.................. : $lx_glpk_found
    122125echo CPLEX support................. : $lx_cplex_found
    123126echo SOPLEX support................ : $lx_soplex_found
    124127echo CLP support................... : $lx_clp_found
     128echo CBC support................... : $lx_cbc_found
    125129echo
    126 echo Build demo programs........... : $enable_demo
    127130echo Build additional tools........ : $enable_tools
    128131echo
  • 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 r791  
    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
    11 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     12IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND 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 ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
     32    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     33    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     34  )
     35
     36  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
     37
    1238  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})
     39    INSTALL(
     40      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     41      DESTINATION share/doc/lemon/html
     42      COMPONENT html_documentation
     43    )
    2544  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)
     45    INSTALL(
     46      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     47      DESTINATION doc
     48      COMPONENT html_documentation
     49    )
     50  ENDIF()
    3951
    40 INSTALL(
    41   DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
    42   DESTINATION doc
    43   COMPONENT html_documentation)
     52ENDIF()
  • doc/Doxyfile.in

    r379 r803  
    1 # Doxyfile 1.5.7.1
     1# Doxyfile 1.5.9
    22
    33#---------------------------------------------------------------------------
     
    2222QT_AUTOBRIEF           = NO
    2323MULTILINE_CPP_IS_BRIEF = NO
    24 DETAILS_AT_TOP         = YES
    2524INHERIT_DOCS           = NO
    2625SEPARATE_MEMBER_PAGES  = NO
     
    9291                         "@abs_top_srcdir@/demo" \
    9392                         "@abs_top_srcdir@/tools" \
    94                          "@abs_top_srcdir@/test/test_tools.h"
     93                         "@abs_top_srcdir@/test/test_tools.h" \
     94                         "@abs_top_builddir@/doc/references.dox"
    9595INPUT_ENCODING         = UTF-8
    9696FILE_PATTERNS          = *.h \
     
    224224SKIP_FUNCTION_MACROS   = YES
    225225#---------------------------------------------------------------------------
    226 # Configuration::additions related to external references   
     226# Options related to the search engine   
    227227#---------------------------------------------------------------------------
    228228TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
  • doc/Makefile.am

    r349 r791  
    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 = \
     
    4656        fi
    4757
    48 html-local: $(DOC_PNG_IMAGES)
     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=$@ $<; \
     62        else \
     63          echo; \
     64          echo "Ghostscript not found."; \
     65          echo; \
     66          exit 1; \
     67        fi
     68
     69references.dox: doc/references.bib
     70        if test ${python_found} = yes; then \
     71          cd doc; \
     72          python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
     73          cd ..; \
     74        else \
     75          echo; \
     76          echo "Python not found."; \
     77          echo; \
     78          exit 1; \
     79        fi
     80
     81html-local: $(DOC_PNG_IMAGES) references.dox
    4982        if test ${doxygen_found} = yes; then \
    5083          cd doc; \
     
    71104install-html-local: doc/html
    72105        @$(NORMAL_INSTALL)
    73         $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
     106        $(mkinstalldirs) $(DESTDIR)$(htmldir)/html
    74107        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    75108          f="`echo $$p | sed -e 's|^.*/||'`"; \
    76           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
    77           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
     109          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
     110          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
    78111        done
    79112
     
    82115        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    83116          f="`echo $$p | sed -e 's|^.*/||'`"; \
    84           echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
    85           rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
     117          echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
     118          rm -f $(DESTDIR)$(htmldir)/html/$$f; \
    86119        done
    87120
  • doc/groups.dox

    r478 r818  
    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.
     
    257239any kind of path structure.
    258240
    259 \sa lemon::concepts::Path
     241\sa \ref concepts::Path "Path concept"
     242*/
     243
     244/**
     245@defgroup heaps Heap Structures
     246@ingroup datas
     247\brief %Heap structures implemented in LEMON.
     248
     249This group contains the heap structures implemented in LEMON.
     250
     251LEMON provides several heap classes. They are efficient implementations
     252of the abstract data type \e priority \e queue. They store items with
     253specified values called \e priorities in such a way that finding and
     254removing the item with minimum priority are efficient.
     255The basic operations are adding and erasing items, changing the priority
     256of an item, etc.
     257
     258Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     259The heap implementations have the same interface, thus any of them can be
     260used easily in such algorithms.
     261
     262\sa \ref concepts::Heap "Heap concept"
     263*/
     264
     265/**
     266@defgroup matrices Matrices
     267@ingroup datas
     268\brief Two dimensional data storages implemented in LEMON.
     269
     270This group contains two dimensional data storages implemented in LEMON.
    260271*/
    261272
     
    265276\brief Auxiliary data structures implemented in LEMON.
    266277
    267 This group describes some data structures implemented in LEMON in
     278This group contains some data structures implemented in LEMON in
    268279order to make it easier to implement combinatorial algorithms.
    269280*/
    270281
    271282/**
     283@defgroup geomdat Geometric Data Structures
     284@ingroup auxdat
     285\brief Geometric data structures implemented in LEMON.
     286
     287This group contains geometric data structures implemented in LEMON.
     288
     289 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
     290   vector with the usual operations.
     291 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
     292   rectangular bounding box of a set of \ref lemon::dim2::Point
     293   "dim2::Point"'s.
     294*/
     295
     296/**
     297@defgroup matrices Matrices
     298@ingroup auxdat
     299\brief Two dimensional data storages implemented in LEMON.
     300
     301This group contains two dimensional data storages implemented in LEMON.
     302*/
     303
     304/**
    272305@defgroup algs Algorithms
    273 \brief This group describes the several algorithms
     306\brief This group contains the several algorithms
    274307implemented in LEMON.
    275308
    276 This group describes the several algorithms
     309This group contains the several algorithms
    277310implemented in LEMON.
    278311*/
     
    283316\brief Common graph search algorithms.
    284317
    285 This group describes the common graph search algorithms, namely
    286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     318This group contains the common graph search algorithms, namely
     319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     320\ref clrs01algorithms.
    287321*/
    288322
     
    292326\brief Algorithms for finding shortest paths.
    293327
    294 This group describes the algorithms for finding shortest paths in digraphs.
     328This group contains the algorithms for finding shortest paths in digraphs
     329\ref clrs01algorithms.
    295330
    296331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    309344
    310345/**
     346@defgroup spantree Minimum Spanning Tree Algorithms
     347@ingroup algs
     348\brief Algorithms for finding minimum cost spanning trees and arborescences.
     349
     350This group contains the algorithms for finding minimum cost spanning
     351trees and arborescences \ref clrs01algorithms.
     352*/
     353
     354/**
    311355@defgroup max_flow Maximum Flow Algorithms
    312356@ingroup algs
    313357\brief Algorithms for finding maximum flows.
    314358
    315 This group describes the algorithms for finding maximum flows and
    316 feasible circulations.
     359This group contains the algorithms for finding maximum flows and
     360feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    317361
    318362The \e maximum \e flow \e problem is to find a flow of maximum value between
    319363a 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
     364digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    321365\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
     366A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
    323367following optimization problem.
    324368
    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]
     369\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     370\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     371    \quad \forall u\in V\setminus\{s,t\} \f]
     372\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    329373
    330374LEMON 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
     375- \ref EdmondsKarp Edmonds-Karp algorithm
     376  \ref edmondskarp72theoretical.
     377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
     378  \ref goldberg88newapproach.
     379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
     380  \ref dinic70algorithm, \ref sleator83dynamic.
     381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
     382  \ref goldberg88newapproach, \ref sleator83dynamic.
     383
     384In most cases the \ref Preflow algorithm provides the
    337385fastest 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
     386also provide functions to query the minimum cut, which is the dual
     387problem of maximum flow.
     388
     389\ref Circulation is a preflow push-relabel algorithm implemented directly
     390for finding feasible circulations, which is a somewhat different problem,
     391but it is strongly related to maximum flow.
     392For more information, see \ref Circulation.
     393*/
     394
     395/**
     396@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    344397@ingroup algs
    345398
    346399\brief Algorithms for finding minimum cost flows and circulations.
    347400
    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.
     401This group contains the algorithms for finding minimum cost flows and
     402circulations \ref amo93networkflows. For more information about this
     403problem and its dual solution, see \ref min_cost_flow
     404"Minimum Cost Flow Problem".
     405
     406LEMON contains several algorithms for this problem.
     407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
     408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
     410   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     411   \ref bunnagel98efficient.
     412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
     413   capacity scaling \ref edmondskarp72theoretical.
     414 - \ref CancelAndTighten The Cancel and Tighten algorithm
     415   \ref goldberg89cyclecanceling.
     416 - \ref CycleCanceling Cycle-Canceling algorithms
     417   \ref klein67primal, \ref goldberg89cyclecanceling.
     418
     419In general NetworkSimplex is the most efficient implementation,
     420but in special cases other algorithms could be faster.
     421For example, if the total supply and/or capacities are rather small,
     422CapacityScaling is usually the fastest algorithm (without effective scaling).
    377423*/
    378424
     
    383429\brief Algorithms for finding minimum cut in graphs.
    384430
    385 This group describes the algorithms for finding minimum cut in graphs.
     431This group contains the algorithms for finding minimum cut in graphs.
    386432
    387433The \e minimum \e cut \e problem is to find a non-empty and non-complete
     
    392438
    393439\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    394     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     440    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    395441
    396442LEMON contains several algorithms related to minimum cut problems:
     
    400446- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    401447  calculating minimum cut in undirected graphs.
    402 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
     448- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    403449  all-pairs minimum cut in undirected graphs.
    404450
     
    408454
    409455/**
    410 @defgroup graph_prop Connectivity and Other Graph Properties
    411 @ingroup algs
    412 \brief Algorithms for discovering the graph properties
    413 
    414 This group describes the algorithms for discovering the graph properties
    415 like connectivity, bipartiteness, euler property, simplicity etc.
    416 
    417 \image html edge_biconnected_components.png
    418 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    419 */
    420 
    421 /**
    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
     456@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     457@ingroup algs
     458\brief Algorithms for finding minimum mean cycles.
     459
     460This group contains the algorithms for finding minimum mean cycles
     461\ref clrs01algorithms, \ref amo93networkflows.
     462
     463The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     464of minimum mean length (cost) in a digraph.
     465The mean length of a cycle is the average length of its arcs, i.e. the
     466ratio between the total length of the cycle and the number of arcs on it.
     467
     468This problem has an important connection to \e conservative \e length
     469\e functions, too. A length function on the arcs of a digraph is called
     470conservative if and only if there is no directed cycle of negative total
     471length. For an arbitrary length function, the negative of the minimum
     472cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     473arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     474function.
     475
     476LEMON contains three algorithms for solving the minimum mean cycle problem:
     477- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
     478  \ref dasdan98minmeancycle.
     479- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     480  version of Karp's algorithm \ref dasdan98minmeancycle.
     481- \ref Howard "Howard"'s policy iteration algorithm
     482  \ref dasdan98minmeancycle.
     483
     484In practice, the Howard algorithm proved to be by far the most efficient
     485one, though the best known theoretical bound on its running time is
     486exponential.
     487Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
     488O(n<sup>2</sup>+e), but the latter one is typically faster due to the
     489applied early termination scheme.
    431490*/
    432491
     
    436495\brief Algorithms for finding matchings in graphs and bipartite graphs.
    437496
    438 This group contains algorithm objects and functions to calculate
     497This group contains the algorithms for calculating
    439498matchings in graphs and bipartite graphs. The general matching problem is
    440 finding a subset of the arcs which does not shares common endpoints.
     499finding a subset of the edges for which each node has at most one incident
     500edge.
    441501
    442502There are several different algorithms for calculate matchings in
     
    471531
    472532/**
    473 @defgroup spantree Minimum Spanning Tree Algorithms
    474 @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.
     533@defgroup graph_properties Connectivity and Other Graph Properties
     534@ingroup algs
     535\brief Algorithms for discovering the graph properties
     536
     537This group contains the algorithms for discovering the graph properties
     538like connectivity, bipartiteness, euler property, simplicity etc.
     539
     540\image html connected_components.png
     541\image latex connected_components.eps "Connected components" width=\textwidth
     542*/
     543
     544/**
     545@defgroup planar Planarity Embedding and Drawing
     546@ingroup algs
     547\brief Algorithms for planarity checking, embedding and drawing
     548
     549This group contains the algorithms for planarity checking,
     550embedding and drawing.
     551
     552\image html planar.png
     553\image latex planar.eps "Plane graph" width=\textwidth
     554*/
     555
     556/**
     557@defgroup approx Approximation Algorithms
     558@ingroup algs
     559\brief Approximation algorithms.
     560
     561This group contains the approximation and heuristic algorithms
     562implemented in LEMON.
    479563*/
    480564
     
    484568\brief Auxiliary algorithms implemented in LEMON.
    485569
    486 This group describes some algorithms implemented in LEMON
     570This group contains some algorithms implemented in LEMON
    487571in order to make it easier to implement complex algorithms.
    488572*/
    489573
    490574/**
    491 @defgroup approx Approximation Algorithms
    492 @ingroup algs
    493 \brief Approximation algorithms.
    494 
    495 This group describes the approximation and heuristic algorithms
     575@defgroup gen_opt_group General Optimization Tools
     576\brief This group contains some general optimization frameworks
    496577implemented in LEMON.
    497 */
    498 
    499 /**
    500 @defgroup gen_opt_group General Optimization Tools
    501 \brief This group describes some general optimization frameworks
     578
     579This group contains some general optimization frameworks
    502580implemented in LEMON.
    503 
    504 This group describes some general optimization frameworks
    505 implemented in LEMON.
    506 */
    507 
    508 /**
    509 @defgroup lp_group Lp and Mip Solvers
     581*/
     582
     583/**
     584@defgroup lp_group LP and MIP Solvers
    510585@ingroup gen_opt_group
    511 \brief Lp and Mip solver interfaces for LEMON.
    512 
    513 This group describes Lp and Mip solver interfaces for LEMON. The
    514 various LP solvers could be used in the same manner with this
    515 interface.
     586\brief LP and MIP solver interfaces for LEMON.
     587
     588This group contains LP and MIP solver interfaces for LEMON.
     589Various LP solvers could be used in the same manner with this
     590high-level interface.
     591
     592The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     593\ref cplex, \ref soplex.
    516594*/
    517595
     
    530608\brief Metaheuristics for LEMON library.
    531609
    532 This group describes some metaheuristic optimization tools.
     610This group contains some metaheuristic optimization tools.
    533611*/
    534612
     
    545623\brief Simple basic graph utilities.
    546624
    547 This group describes some simple basic graph utilities.
     625This group contains some simple basic graph utilities.
    548626*/
    549627
     
    553631\brief Tools for development, debugging and testing.
    554632
    555 This group describes several useful tools for development,
     633This group contains several useful tools for development,
    556634debugging and testing.
    557635*/
     
    562640\brief Simple tools for measuring the performance of algorithms.
    563641
    564 This group describes simple tools for measuring the performance
     642This group contains simple tools for measuring the performance
    565643of algorithms.
    566644*/
     
    571649\brief Exceptions defined in LEMON.
    572650
    573 This group describes the exceptions defined in LEMON.
     651This group contains the exceptions defined in LEMON.
    574652*/
    575653
     
    578656\brief Graph Input-Output methods
    579657
    580 This group describes the tools for importing and exporting graphs
     658This group contains the tools for importing and exporting graphs
    581659and graph related data. Now it supports the \ref lgf-format
    582660"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    589667\brief Reading and writing LEMON Graph Format.
    590668
    591 This group describes methods for reading and writing
     669This group contains methods for reading and writing
    592670\ref lgf-format "LEMON Graph Format".
    593671*/
     
    598676\brief General \c EPS drawer and graph exporter
    599677
    600 This group describes general \c EPS drawing methods and special
     678This group contains general \c EPS drawing methods and special
    601679graph exporting tools.
    602680*/
    603681
    604682/**
    605 @defgroup dimacs_group DIMACS format
     683@defgroup dimacs_group DIMACS Format
    606684@ingroup io_group
    607685\brief Read and write files in DIMACS format
     
    622700\brief Skeleton classes and concept checking classes
    623701
    624 This group describes the data/algorithm skeletons and concept checking
     702This group contains the data/algorithm skeletons and concept checking
    625703classes implemented in LEMON.
    626704
     
    652730\brief Skeleton and concept checking classes for graph structures
    653731
    654 This group describes the skeletons and concept checking classes of LEMON's
    655 graph structures and helper classes used to implement these.
     732This group contains the skeletons and concept checking classes of
     733graph structures.
    656734*/
    657735
     
    661739\brief Skeleton and concept checking classes for maps
    662740
    663 This group describes the skeletons and concept checking classes of maps.
     741This group contains the skeletons and concept checking classes of maps.
     742*/
     743
     744/**
     745@defgroup tools Standalone Utility Applications
     746
     747Some utility applications are listed here.
     748
     749The standard compilation procedure (<tt>./configure;make</tt>) will compile
     750them, as well.
    664751*/
    665752
     
    672759the \c demo subdirectory of the source tree.
    673760
    674 It order to compile them, use <tt>--enable-demo</tt> configure option when
    675 build the library.
    676 */
    677 
    678 /**
    679 @defgroup tools Standalone Utility Applications
    680 
    681 Some utility applications are listed here.
    682 
    683 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    684 them, as well.
     761In order to compile them, use the <tt>make demo</tt> or the
     762<tt>make check</tt> commands.
    685763*/
    686764
  • doc/mainpage.dox

    r463 r802  
    2222\section intro Introduction
    2323
    24 \subsection whatis What is LEMON
    25 
    26 LEMON stands for
    27 <b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
    28 and <b>O</b>ptimization in <b>N</b>etworks.
    29 It is a C++ template
    30 library aimed at combinatorial optimization tasks which
    31 often involve in working
    32 with graphs.
     24<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
     25and <b>O</b>ptimization in <b>N</b>etworks</i>.
     26It is a C++ template library providing efficient implementation of common
     27data structures and algorithms with focus on combinatorial optimization
     28problems in graphs and networks.
    3329
    3430<b>
     
    4036</b>
    4137
    42 \subsection howtoread How to read the documentation
     38The project is maintained by the
     39<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
     40Combinatorial Optimization</a> \ref egres
     41at the Operations Research Department of the
     42<a href="http://www.elte.hu/">E&ouml;tv&ouml;s Lor&aacute;nd University,
     43Budapest</a>, Hungary.
     44LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
     45initiative \ref coinor.
    4346
    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.
     47\section howtoread How to Read the Documentation
    4748
    48 If you already feel like using our library, see the page that tells you
    49 \ref getstart "How to start using LEMON".
     49If you would like to get to know the library, see
     50<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    5051
    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.
     52If you know what you are looking for, then try to find it under the
     53<a class="el" href="modules.html">Modules</a> section.
    5854
    5955If 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

    r492 r827  
    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
     
    4450endif
    4551
     52if HAVE_CBC
     53lemon_libemon_la_SOURCES += lemon/cbc.cc
     54endif
     55
    4656lemon_HEADERS += \
    4757        lemon/adaptors.h \
    4858        lemon/arg_parser.h \
    4959        lemon/assert.h \
     60        lemon/bellman_ford.h \
    5061        lemon/bfs.h \
    5162        lemon/bin_heap.h \
     63        lemon/binom_heap.h \
     64        lemon/bucket_heap.h \
     65        lemon/cbc.h \
    5266        lemon/circulation.h \
    5367        lemon/clp.h \
    5468        lemon/color.h \
    5569        lemon/concept_check.h \
     70        lemon/connectivity.h \
    5671        lemon/counter.h \
    5772        lemon/core.h \
     
    6479        lemon/elevator.h \
    6580        lemon/error.h \
     81        lemon/euler.h \
     82        lemon/fib_heap.h \
     83        lemon/fourary_heap.h \
    6684        lemon/full_graph.h \
    6785        lemon/glpk.h \
     86        lemon/gomory_hu.h \
    6887        lemon/graph_to_eps.h \
    6988        lemon/grid_graph.h \
     89        lemon/hartmann_orlin.h \
     90        lemon/howard.h \
    7091        lemon/hypercube_graph.h \
     92        lemon/karp.h \
     93        lemon/kary_heap.h \
    7194        lemon/kruskal.h \
    7295        lemon/hao_orlin.h \
     
    77100        lemon/lp_base.h \
    78101        lemon/lp_skeleton.h \
    79         lemon/list_graph.h \
    80102        lemon/maps.h \
     103        lemon/matching.h \
    81104        lemon/math.h \
    82         lemon/max_matching.h \
     105        lemon/min_cost_arborescence.h \
    83106        lemon/nauty_reader.h \
     107        lemon/network_simplex.h \
     108        lemon/pairing_heap.h \
    84109        lemon/path.h \
    85110        lemon/preflow.h \
     111        lemon/radix_heap.h \
    86112        lemon/radix_sort.h \
    87113        lemon/random.h \
    88114        lemon/smart_graph.h \
    89115        lemon/soplex.h \
     116        lemon/static_graph.h \
    90117        lemon/suurballe.h \
    91118        lemon/time_measure.h \
    92119        lemon/tolerance.h \
    93         lemon/unionfind.h
     120        lemon/unionfind.h \
     121        lemon/bits/windows.h
    94122
    95123bits_HEADERS += \
    96124        lemon/bits/alteration_notifier.h \
    97125        lemon/bits/array_map.h \
    98         lemon/bits/base_extender.h \
    99126        lemon/bits/bezier.h \
    100127        lemon/bits/default_map.h \
  • lemon/adaptors.h

    r487 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      }
     
    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>
     2703  template<typename DGR, typename CM, typename FM, typename TL>
    27072704  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 ResidualDigraph :
    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;
     
    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     ResidualDigraph(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   ResidualDigraph<GR, CM, FM>
    2873   residualDigraph(const GR& digraph, const CM& capacity_map, FM& flow_map) {
    2874     return ResidualDigraph<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);
    28752877  }
    28762878
    28772879
    2878   template <typename _Digraph>
     2880  template <typename DGR>
    28792881  class SplitNodesBase {
    2880   public:
    2881 
    2882     typedef _Digraph Digraph;
    2883     typedef DigraphAdaptorBase<const _Digraph> Parent;
     2882    typedef DigraphAdaptorBase<const DGR> Parent;
     2883
     2884  public:
     2885
     2886    typedef DGR Digraph;
    28842887    typedef SplitNodesBase Adaptor;
    28852888
    2886     typedef typename Digraph::Node DigraphNode;
    2887     typedef typename Digraph::Arc DigraphArc;
     2889    typedef typename DGR::Node DigraphNode;
     2890    typedef typename DGR::Arc DigraphArc;
    28882891
    28892892    class Node;
     
    31493152  private:
    31503153
    3151     template <typename _Value>
     3154    template <typename V>
    31523155    class NodeMapBase
    3153       : public MapTraits<typename Parent::template NodeMap<_Value> > {
    3154       typedef typename Parent::template NodeMap<_Value> NodeImpl;
     3156      : public MapTraits<typename Parent::template NodeMap<V> > {
     3157      typedef typename Parent::template NodeMap<V> NodeImpl;
    31553158    public:
    31563159      typedef Node Key;
    3157       typedef _Value Value;
     3160      typedef V Value;
    31583161      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
    31593162      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
     
    31623165      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
    31633166
    3164       NodeMapBase(const Adaptor& adaptor)
     3167      NodeMapBase(const SplitNodesBase<DGR>& adaptor)
    31653168        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
    3166       NodeMapBase(const Adaptor& adaptor, const Value& value)
     3169      NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
    31673170        : _in_map(*adaptor._digraph, value),
    31683171          _out_map(*adaptor._digraph, value) {}
    31693172
    3170       void set(const Node& key, const Value& val) {
    3171         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); }
    31723175        else {_out_map.set(key, val); }
    31733176      }
    31743177
    31753178      ReturnValue operator[](const Node& key) {
    3176         if (Adaptor::inNode(key)) { return _in_map[key]; }
     3179        if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
    31773180        else { return _out_map[key]; }
    31783181      }
     
    31873190    };
    31883191
    3189     template <typename _Value>
     3192    template <typename V>
    31903193    class ArcMapBase
    3191       : public MapTraits<typename Parent::template ArcMap<_Value> > {
    3192       typedef typename Parent::template ArcMap<_Value> ArcImpl;
    3193       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;
    31943197    public:
    31953198      typedef Arc Key;
    3196       typedef _Value Value;
     3199      typedef V Value;
    31973200      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
    31983201      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
     
    32013204      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
    32023205
    3203       ArcMapBase(const Adaptor& adaptor)
     3206      ArcMapBase(const SplitNodesBase<DGR>& adaptor)
    32043207        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
    3205       ArcMapBase(const Adaptor& adaptor, const Value& value)
     3208      ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
    32063209        : _arc_map(*adaptor._digraph, value),
    32073210          _node_map(*adaptor._digraph, value) {}
    32083211
    3209       void set(const Arc& key, const Value& val) {
    3210         if (Adaptor::origArc(key)) {
    3211           _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);
    32123215        } else {
    3213           _node_map.set(key._item.second(), val);
     3216          _node_map.set(static_cast<const DigraphNode&>(key), val);
    32143217        }
    32153218      }
    32163219
    32173220      ReturnValue operator[](const Arc& key) {
    3218         if (Adaptor::origArc(key)) {
    3219           return _arc_map[key._item.first()];
     3221        if (SplitNodesBase<DGR>::origArc(key)) {
     3222          return _arc_map[static_cast<const DigraphArc&>(key)];
    32203223        } else {
    3221           return _node_map[key._item.second()];
     3224          return _node_map[static_cast<const DigraphNode&>(key)];
    32223225        }
    32233226      }
    32243227
    32253228      ConstReturnValue operator[](const Arc& key) const {
    3226         if (Adaptor::origArc(key)) {
    3227           return _arc_map[key._item.first()];
     3229        if (SplitNodesBase<DGR>::origArc(key)) {
     3230          return _arc_map[static_cast<const DigraphArc&>(key)];
    32283231        } else {
    3229           return _node_map[key._item.second()];
     3232          return _node_map[static_cast<const DigraphNode&>(key)];
    32303233        }
    32313234      }
     
    32383241  public:
    32393242
    3240     template <typename _Value>
     3243    template <typename V>
    32413244    class NodeMap
    3242       : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
    3243     {
     3245      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
     3246      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
     3247
    32443248    public:
    3245       typedef _Value Value;
    3246       typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
    3247 
    3248       NodeMap(const Adaptor& adaptor)
     3249      typedef V Value;
     3250
     3251      NodeMap(const SplitNodesBase<DGR>& adaptor)
    32493252        : Parent(adaptor) {}
    32503253
    3251       NodeMap(const Adaptor& adaptor, const Value& value)
     3254      NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
    32523255        : Parent(adaptor, value) {}
    32533256
     
    32643267    };
    32653268
    3266     template <typename _Value>
     3269    template <typename V>
    32673270    class ArcMap
    3268       : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
    3269     {
     3271      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
     3272      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
     3273
    32703274    public:
    3271       typedef _Value Value;
    3272       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    3273 
    3274       ArcMap(const Adaptor& adaptor)
     3275      typedef V Value;
     3276
     3277      ArcMap(const SplitNodesBase<DGR>& adaptor)
    32753278        : Parent(adaptor) {}
    32763279
    3277       ArcMap(const Adaptor& adaptor, const Value& value)
     3280      ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
    32783281        : Parent(adaptor, value) {}
    32793282
     
    32943297    SplitNodesBase() : _digraph(0) {}
    32953298
    3296     Digraph* _digraph;
    3297 
    3298     void setDigraph(Digraph& digraph) {
     3299    DGR* _digraph;
     3300
     3301    void initialize(Digraph& digraph) {
    32993302      _digraph = &digraph;
    33003303    }
     
    33233326  /// in the adaptor.
    33243327  ///
    3325   /// \tparam GR The type of the adapted digraph.
     3328  /// \tparam DGR The type of the adapted digraph.
    33263329  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
    33273330  /// It is implicitly \c const.
     
    33293332  /// \note The \c Node type of this adaptor is converible to the \c Node
    33303333  /// type of the adapted digraph.
    3331   template <typename GR>
     3334  template <typename DGR>
    33323335#ifdef DOXYGEN
    33333336  class SplitNodes {
    33343337#else
    33353338  class SplitNodes
    3336     : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
     3339    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
    33373340#endif
    3338   public:
    3339     typedef GR Digraph;
    3340     typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
    3341 
    3342     typedef typename Digraph::Node DigraphNode;
    3343     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;
    33443348
    33453349    typedef typename Parent::Node Node;
     
    33493353    ///
    33503354    /// Constructor of the adaptor.
    3351     SplitNodes(const Digraph& g) {
    3352       Parent::setDigraph(g);
     3355    SplitNodes(const DGR& g) {
     3356      Parent::initialize(g);
    33533357    }
    33543358
     
    34193423    /// This map adaptor class adapts two node maps of the original digraph
    34203424    /// to get a node map of the split digraph.
    3421     /// Its value type is inherited from the first node map type
    3422     /// (\c InNodeMap).
    3423     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>
    34243429    class CombinedNodeMap {
    34253430    public:
     
    34283433      typedef Node Key;
    34293434      /// The value type of the map
    3430       typedef typename InNodeMap::Value Value;
    3431 
    3432       typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
    3433       typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
    3434       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
    3435       typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
    3436       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;
    34373442
    34383443      /// Constructor
    3439       CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
     3444      CombinedNodeMap(IN& in_map, OUT& out_map)
    34403445        : _in_map(in_map), _out_map(out_map) {}
    34413446
    34423447      /// Returns the value associated with the given key.
    34433448      Value operator[](const Key& key) const {
    3444         if (Parent::inNode(key)) {
     3449        if (SplitNodesBase<const DGR>::inNode(key)) {
    34453450          return _in_map[key];
    34463451        } else {
     
    34513456      /// Returns a reference to the value associated with the given key.
    34523457      Value& operator[](const Key& key) {
    3453         if (Parent::inNode(key)) {
     3458        if (SplitNodesBase<const DGR>::inNode(key)) {
    34543459          return _in_map[key];
    34553460        } else {
     
    34603465      /// Sets the value associated with the given key.
    34613466      void set(const Key& key, const Value& value) {
    3462         if (Parent::inNode(key)) {
     3467        if (SplitNodesBase<const DGR>::inNode(key)) {
    34633468          _in_map.set(key, value);
    34643469        } else {
     
    34693474    private:
    34703475
    3471       InNodeMap& _in_map;
    3472       OutNodeMap& _out_map;
     3476      IN& _in_map;
     3477      OUT& _out_map;
    34733478
    34743479    };
     
    34783483    ///
    34793484    /// This function just returns a combined node map.
    3480     template <typename InNodeMap, typename OutNodeMap>
    3481     static CombinedNodeMap<InNodeMap, OutNodeMap>
    3482     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
    3483       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
    3484     }
    3485 
    3486     template <typename InNodeMap, typename OutNodeMap>
    3487     static CombinedNodeMap<const InNodeMap, OutNodeMap>
    3488     combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
    3489       return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
    3490     }
    3491 
    3492     template <typename InNodeMap, typename OutNodeMap>
    3493     static CombinedNodeMap<InNodeMap, const OutNodeMap>
    3494     combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
    3495       return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
    3496     }
    3497 
    3498     template <typename InNodeMap, typename OutNodeMap>
    3499     static CombinedNodeMap<const InNodeMap, const OutNodeMap>
    3500     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
    3501       return CombinedNodeMap<const InNodeMap,
    3502         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);
    35033507    }
    35043508
     
    35083512    /// This map adaptor class adapts an arc map and a node map of the
    35093513    /// original digraph to get an arc map of the split digraph.
    3510     /// Its value type is inherited from the original arc map type
    3511     /// (\c ArcMap).
    3512     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>
    35133518    class CombinedArcMap {
    35143519    public:
     
    35173522      typedef Arc Key;
    35183523      /// The value type of the map
    3519       typedef typename ArcMap::Value Value;
    3520 
    3521       typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
    3522       typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
    3523       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
    3524       typedef typename MapTraits<ArcMap>::ReturnValue Reference;
    3525       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;
    35263531
    35273532      /// Constructor
    3528       CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
     3533      CombinedArcMap(AM& arc_map, NM& node_map)
    35293534        : _arc_map(arc_map), _node_map(node_map) {}
    35303535
    35313536      /// Returns the value associated with the given key.
    35323537      Value operator[](const Key& arc) const {
    3533         if (Parent::origArc(arc)) {
     3538        if (SplitNodesBase<const DGR>::origArc(arc)) {
    35343539          return _arc_map[arc];
    35353540        } else {
     
    35403545      /// Returns a reference to the value associated with the given key.
    35413546      Value& operator[](const Key& arc) {
    3542         if (Parent::origArc(arc)) {
     3547        if (SplitNodesBase<const DGR>::origArc(arc)) {
    35433548          return _arc_map[arc];
    35443549        } else {
     
    35493554      /// Sets the value associated with the given key.
    35503555      void set(const Arc& arc, const Value& val) {
    3551         if (Parent::origArc(arc)) {
     3556        if (SplitNodesBase<const DGR>::origArc(arc)) {
    35523557          _arc_map.set(arc, val);
    35533558        } else {
     
    35573562
    35583563    private:
    3559       ArcMap& _arc_map;
    3560       NodeMap& _node_map;
     3564
     3565      AM& _arc_map;
     3566      NM& _node_map;
     3567
    35613568    };
    35623569
     
    35953602  /// \ingroup graph_adaptors
    35963603  /// \relates SplitNodes
    3597   template<typename GR>
    3598   SplitNodes<GR>
    3599   splitNodes(const GR& digraph) {
    3600     return SplitNodes<GR>(digraph);
     3604  template<typename DGR>
     3605  SplitNodes<DGR>
     3606  splitNodes(const DGR& digraph) {
     3607    return SplitNodes<DGR>(digraph);
    36013608  }
    36023609
     3610#undef LEMON_SCOPE_FIX
     3611
    36033612} //namespace lemon
    36043613
  • 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 r764  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the shortest paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to 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    {
     
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     68    ///Instantiates a \c ProcessedMap.
     69
     70    ///This function instantiates a \ref ProcessedMap.
    7071    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     72    ///we would like to define the \ref ProcessedMap
    7273#ifdef DOXYGEN
    7374    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8586    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     87    ///Instantiates a \c ReachedMap.
     88
     89    ///This function instantiates a \ref ReachedMap.
    8990    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     91    ///we would like to define the \ref ReachedMap.
    9192    static ReachedMap *createReachedMap(const Digraph &g)
    9293    {
     
    9798
    9899    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     100    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100101    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     102    ///Instantiates a \c DistMap.
     103
     104    ///This function instantiates a \ref DistMap.
    104105    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     106    ///\ref DistMap.
    106107    static DistMap *createDistMap(const Digraph &g)
    107108    {
     
    222223    };
    223224    ///\brief \ref named-templ-param "Named parameter" for setting
    224     ///PredMap type.
     225    ///\c PredMap type.
    225226    ///
    226227    ///\ref named-templ-param "Named parameter" for setting
    227     ///PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     228    ///\c PredMap type.
     229    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    229230    template <class T>
    230231    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    242243    };
    243244    ///\brief \ref named-templ-param "Named parameter" for setting
    244     ///DistMap type.
     245    ///\c DistMap type.
    245246    ///
    246247    ///\ref named-templ-param "Named parameter" for setting
    247     ///DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     248    ///\c DistMap type.
     249    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    249250    template <class T>
    250251    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    262263    };
    263264    ///\brief \ref named-templ-param "Named parameter" for setting
    264     ///ReachedMap type.
     265    ///\c ReachedMap type.
    265266    ///
    266267    ///\ref named-templ-param "Named parameter" for setting
    267     ///ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     268    ///\c ReachedMap type.
     269    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269270    template <class T>
    270271    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    282283    };
    283284    ///\brief \ref named-templ-param "Named parameter" for setting
    284     ///ProcessedMap type.
     285    ///\c ProcessedMap type.
    285286    ///
    286287    ///\ref named-templ-param "Named parameter" for setting
    287     ///ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     288    ///\c ProcessedMap type.
     289    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    289290    template <class T>
    290291    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    301302    };
    302303    ///\brief \ref named-templ-param "Named parameter" for setting
    303     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     304    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    304305    ///
    305306    ///\ref named-templ-param "Named parameter" for setting
    306     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     307    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    307308    ///If you don't set it explicitly, it will be automatically allocated.
    308309    struct SetStandardProcessedMap :
     
    414415    ///The simplest way to execute the BFS algorithm is to use one of the
    415416    ///member functions called \ref run(Node) "run()".\n
    416     ///If you need more control on the execution, first you have to call
    417     ///\ref init(), then you can add several source nodes with
     417    ///If you need better control on the execution, you have to call
     418    ///\ref init() first, then you can add several source nodes with
    418419    ///\ref addSource(). Finally the actual path computation can be
    419420    ///performed with one of the \ref start() functions.
     
    738739    ///@{
    739740
    740     ///The shortest path to a node.
    741 
    742     ///Returns the shortest path to a node.
     741    ///The shortest path to the given node.
     742
     743    ///Returns the shortest path to the given node from the root(s).
    743744    ///
    744745    ///\warning \c t should be reached from the root(s).
     
    748749    Path path(Node t) const { return Path(*G, *_pred, t); }
    749750
    750     ///The distance of a node from the root(s).
    751 
    752     ///Returns the distance of a node from the root(s).
     751    ///The distance of the given node from the root(s).
     752
     753    ///Returns the distance of the given node from the root(s).
    753754    ///
    754755    ///\warning If node \c v is not reached from the root(s), then
     
    759760    int dist(Node v) const { return (*_dist)[v]; }
    760761
    761     ///Returns the 'previous arc' of the shortest path tree for a node.
    762 
     762    ///\brief Returns the 'previous arc' of the shortest path tree for
     763    ///the given node.
     764    ///
    763765    ///This function returns the 'previous arc' of the shortest path
    764766    ///tree for the node \c v, i.e. it returns the last arc of a
     
    767769    ///
    768770    ///The shortest path tree used here is equal to the shortest path
    769     ///tree used in \ref predNode().
     771    ///tree used in \ref predNode() and \ref predMap().
    770772    ///
    771773    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    773775    Arc predArc(Node v) const { return (*_pred)[v];}
    774776
    775     ///Returns the 'previous node' of the shortest path tree for a node.
    776 
     777    ///\brief Returns the 'previous node' of the shortest path tree for
     778    ///the given node.
     779    ///
    777780    ///This function returns the 'previous node' of the shortest path
    778781    ///tree for the node \c v, i.e. it returns the last but one node
    779     ///from a shortest path from a root to \c v. It is \c INVALID
     782    ///of a shortest path from a root to \c v. It is \c INVALID
    780783    ///if \c v is not reached from the root(s) or if \c v is a root.
    781784    ///
    782785    ///The shortest path tree used here is equal to the shortest path
    783     ///tree used in \ref predArc().
     786    ///tree used in \ref predArc() and \ref predMap().
    784787    ///
    785788    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    802805    ///
    803806    ///Returns a const reference to the node map that stores the predecessor
    804     ///arcs, which form the shortest path tree.
     807    ///arcs, which form the shortest path tree (forest).
    805808    ///
    806809    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    808811    const PredMap &predMap() const { return *_pred;}
    809812
    810     ///Checks if a node is reached from the root(s).
     813    ///Checks if the given node is reached from the root(s).
    811814
    812815    ///Returns \c true if \c v is reached from the root(s).
     
    834837    ///The type of the map that stores the predecessor
    835838    ///arcs of the shortest paths.
    836     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     839    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    837840    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    838841    ///Instantiates a PredMap.
     
    849852
    850853    ///The type of the map that indicates which nodes are processed.
    851     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     854    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    852855    ///By default it is a NullMap.
    853856    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    869872
    870873    ///The type of the map that indicates which nodes are reached.
    871     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     874    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    872875    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    873876    ///Instantiates a ReachedMap.
     
    884887
    885888    ///The type of the map that stores the distances of the nodes.
    886     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     889    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    887890    typedef typename Digraph::template NodeMap<int> DistMap;
    888891    ///Instantiates a DistMap.
     
    899902
    900903    ///The type of the shortest paths.
    901     ///It must meet the \ref concepts::Path "Path" concept.
     904    ///It must conform to the \ref concepts::Path "Path" concept.
    902905    typedef lemon::Path<Digraph> Path;
    903906  };
     
    905908  /// Default traits class used by BfsWizard
    906909
    907   /// To make it easier to use Bfs algorithm
    908   /// we have created a wizard class.
    909   /// This \ref BfsWizard class needs default traits,
    910   /// as well as the \ref Bfs class.
    911   /// The \ref BfsWizardBase is a class to be the default traits of the
    912   /// \ref BfsWizard class.
     910  /// Default traits class used by BfsWizard.
     911  /// \tparam GR The type of the digraph.
    913912  template<class GR>
    914913  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
     
    938937    /// Constructor.
    939938
    940     /// This constructor does not require parameters, therefore it initiates
     939    /// This constructor does not require parameters, it initiates
    941940    /// all of the attributes to \c 0.
    942941    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    968967    typedef TR Base;
    969968
    970     ///The type of the digraph the algorithm runs on.
    971969    typedef typename TR::Digraph Digraph;
    972970
     
    976974    typedef typename Digraph::OutArcIt OutArcIt;
    977975
    978     ///\brief The type of the map that stores the predecessor
    979     ///arcs of the shortest paths.
    980976    typedef typename TR::PredMap PredMap;
    981     ///\brief The type of the map that stores the distances of the nodes.
    982977    typedef typename TR::DistMap DistMap;
    983     ///\brief The type of the map that indicates which nodes are reached.
    984978    typedef typename TR::ReachedMap ReachedMap;
    985     ///\brief The type of the map that indicates which nodes are processed.
    986979    typedef typename TR::ProcessedMap ProcessedMap;
    987     ///The type of the shortest paths
    988980    typedef typename TR::Path Path;
    989981
     
    10681060      SetPredMapBase(const TR &b) : TR(b) {}
    10691061    };
    1070     ///\brief \ref named-func-param "Named parameter"
    1071     ///for setting PredMap object.
    1072     ///
    1073     ///\ref named-func-param "Named parameter"
    1074     ///for setting PredMap object.
     1062
     1063    ///\brief \ref named-templ-param "Named parameter" for setting
     1064    ///the predecessor map.
     1065    ///
     1066    ///\ref named-templ-param "Named parameter" function for setting
     1067    ///the map that stores the predecessor arcs of the nodes.
    10751068    template<class T>
    10761069    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10861079      SetReachedMapBase(const TR &b) : TR(b) {}
    10871080    };
    1088     ///\brief \ref named-func-param "Named parameter"
    1089     ///for setting ReachedMap object.
    1090     ///
    1091     /// \ref named-func-param "Named parameter"
    1092     ///for setting ReachedMap object.
     1081
     1082    ///\brief \ref named-templ-param "Named parameter" for setting
     1083    ///the reached map.
     1084    ///
     1085    ///\ref named-templ-param "Named parameter" function for setting
     1086    ///the map that indicates which nodes are reached.
    10931087    template<class T>
    10941088    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    11041098      SetDistMapBase(const TR &b) : TR(b) {}
    11051099    };
    1106     ///\brief \ref named-func-param "Named parameter"
    1107     ///for setting DistMap object.
    1108     ///
    1109     /// \ref named-func-param "Named parameter"
    1110     ///for setting DistMap object.
     1100
     1101    ///\brief \ref named-templ-param "Named parameter" for setting
     1102    ///the distance map.
     1103    ///
     1104    ///\ref named-templ-param "Named parameter" function for setting
     1105    ///the map that stores the distances of the nodes calculated
     1106    ///by the algorithm.
    11111107    template<class T>
    11121108    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    11221118      SetProcessedMapBase(const TR &b) : TR(b) {}
    11231119    };
    1124     ///\brief \ref named-func-param "Named parameter"
    1125     ///for setting ProcessedMap object.
    1126     ///
    1127     /// \ref named-func-param "Named parameter"
    1128     ///for setting ProcessedMap object.
     1120
     1121    ///\brief \ref named-func-param "Named parameter" for setting
     1122    ///the processed map.
     1123    ///
     1124    ///\ref named-templ-param "Named parameter" function for setting
     1125    ///the map that indicates which nodes are processed.
    11291126    template<class T>
    11301127    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    11951192  /// This class defines the interface of the BfsVisit events, and
    11961193  /// it could be the base of a real visitor class.
    1197   template <typename _Digraph>
     1194  template <typename GR>
    11981195  struct BfsVisitor {
    1199     typedef _Digraph Digraph;
     1196    typedef GR Digraph;
    12001197    typedef typename Digraph::Arc Arc;
    12011198    typedef typename Digraph::Node Node;
     
    12251222  };
    12261223#else
    1227   template <typename _Digraph>
     1224  template <typename GR>
    12281225  struct BfsVisitor {
    1229     typedef _Digraph Digraph;
     1226    typedef GR Digraph;
    12301227    typedef typename Digraph::Arc Arc;
    12311228    typedef typename Digraph::Node Node;
     
    12551252  ///
    12561253  /// Default traits class of BfsVisit class.
    1257   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1258   template<class _Digraph>
     1254  /// \tparam GR The type of the digraph the algorithm runs on.
     1255  template<class GR>
    12591256  struct BfsVisitDefaultTraits {
    12601257
    12611258    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef _Digraph Digraph;
     1259    typedef GR Digraph;
    12631260
    12641261    /// \brief The type of the map that indicates which nodes are reached.
    12651262    ///
    12661263    /// The type of the map that indicates which nodes are reached.
    1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1264    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12681265    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12691266
     
    12811278  /// \ingroup search
    12821279  ///
    1283   /// \brief %BFS algorithm class with visitor interface.
     1280  /// \brief BFS algorithm class with visitor interface.
    12841281  ///
    1285   /// This class provides an efficient implementation of the %BFS algorithm
     1282  /// This class provides an efficient implementation of the BFS algorithm
    12861283  /// with visitor interface.
    12871284  ///
    1288   /// The %BfsVisit class provides an alternative interface to the Bfs
     1285  /// The BfsVisit class provides an alternative interface to the Bfs
    12891286  /// class. It works with callback mechanism, the BfsVisit object calls
    12901287  /// the member functions of the \c Visitor class on every BFS event.
     
    12951292  /// instead.
    12961293  ///
    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
     1294  /// \tparam GR The type of the digraph the algorithm runs on.
     1295  /// The default type is \ref ListDigraph.
     1296  /// The value of GR is not used directly by \ref BfsVisit,
     1297  /// it is only passed to \ref BfsVisitDefaultTraits.
     1298  /// \tparam VS The Visitor type that is used by the algorithm.
     1299  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
    13031300  /// does not observe the BFS events. If you want to observe the BFS
    13041301  /// events, you should implement your own visitor class.
    1305   /// \tparam _Traits Traits class to set various data types used by the
     1302  /// \tparam TR Traits class to set various data types used by the
    13061303  /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
     1304  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
    13081305  /// See \ref BfsVisitDefaultTraits for the documentation of
    13091306  /// a BFS visit traits class.
    13101307#ifdef DOXYGEN
    1311   template <typename _Digraph, typename _Visitor, typename _Traits>
     1308  template <typename GR, typename VS, typename TR>
    13121309#else
    1313   template <typename _Digraph = ListDigraph,
    1314             typename _Visitor = BfsVisitor<_Digraph>,
    1315             typename _Traits = BfsVisitDefaultTraits<_Digraph> >
     1310  template <typename GR = ListDigraph,
     1311            typename VS = BfsVisitor<GR>,
     1312            typename TR = BfsVisitDefaultTraits<GR> >
    13161313#endif
    13171314  class BfsVisit {
     
    13191316
    13201317    ///The traits class.
    1321     typedef _Traits Traits;
     1318    typedef TR Traits;
    13221319
    13231320    ///The type of the digraph the algorithm runs on.
     
    13251322
    13261323    ///The visitor type used by the algorithm.
    1327     typedef _Visitor Visitor;
     1324    typedef VS Visitor;
    13281325
    13291326    ///The type of the map that indicates which nodes are reached.
     
    14261423    /// The simplest way to execute the BFS algorithm is to use one of the
    14271424    /// member functions called \ref run(Node) "run()".\n
    1428     /// If you need more control on the execution, first you have to call
    1429     /// \ref init(), then you can add several source nodes with
     1425    /// If you need better control on the execution, you have to call
     1426    /// \ref init() first, then you can add several source nodes with
    14301427    /// \ref addSource(). Finally the actual path computation can be
    14311428    /// performed with one of the \ref start() functions.
     
    17361733    ///@{
    17371734
    1738     /// \brief Checks if a node is reached from the root(s).
     1735    /// \brief Checks if the given node is reached from the root(s).
    17391736    ///
    17401737    /// Returns \c true if \c v is reached from the root(s).
  • lemon/bin_heap.h

    r463 r758  
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief Binary Heap implementation.
     24///\brief Binary heap implementation.
    2525
    2626#include <vector>
     
    3030namespace lemon {
    3131
    32   ///\ingroup auxdat
     32  /// \ingroup heaps
    3333  ///
    34   ///\brief A Binary Heap implementation.
     34  /// \brief Binary heap data structure.
    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  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4138  ///
    42   ///\tparam _Prio Type of the priority of the items.
    43   ///\tparam _ItemIntMap A read and writable Item int map, used internally
    44   ///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   ///
    48   ///\sa FibHeap
    49   ///\sa Dijkstra
    50   template <typename _Prio, typename _ItemIntMap,
    51             typename _Compare = std::less<_Prio> >
     39  /// \tparam PR Type of the priorities of the items.
     40  /// \tparam IM A read-writable item map with \c int values, used
     41  /// internally to handle the cross references.
     42  /// \tparam CMP A functor class for comparing the priorities.
     43  /// The default is \c std::less<PR>.
     44#ifdef DOXYGEN
     45  template <typename PR, typename IM, typename CMP>
     46#else
     47  template <typename PR, typename IM, typename CMP = std::less<PR> >
     48#endif
    5249  class BinHeap {
    53 
    5450  public:
    55     ///\e
    56     typedef _ItemIntMap ItemIntMap;
    57     ///\e
    58     typedef _Prio Prio;
    59     ///\e
     51
     52    /// Type of the item-int map.
     53    typedef IM ItemIntMap;
     54    /// Type of the priorities.
     55    typedef PR Prio;
     56    /// Type of the items stored in the heap.
    6057    typedef typename ItemIntMap::Key Item;
    61     ///\e
     58    /// Type of the item-priority pairs.
    6259    typedef std::pair<Item,Prio> Pair;
    63     ///\e
    64     typedef _Compare Compare;
    65 
    66     /// \brief Type to represent the items states.
    67     ///
    68     /// Each Item element have a state associated to it. It may be "in heap",
    69     /// "pre heap" or "post heap". The latter two are indifferent from the
     60    /// Functor type for comparing the priorities.
     61    typedef CMP Compare;
     62
     63    /// \brief Type to represent the states of the items.
     64    ///
     65    /// Each item has a state associated to it. It can be "in heap",
     66    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    7067    /// heap's point of view, but may be useful to the user.
    7168    ///
    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...
     69    /// The item-int map must be initialized in such way that it assigns
     70    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    7471    enum State {
    75       IN_HEAP = 0,
    76       PRE_HEAP = -1,
    77       POST_HEAP = -2
     72      IN_HEAP = 0,    ///< = 0.
     73      PRE_HEAP = -1,  ///< = -1.
     74      POST_HEAP = -2  ///< = -2.
    7875    };
    7976
    8077  private:
    81     std::vector<Pair> data;
    82     Compare comp;
    83     ItemIntMap &iim;
     78    std::vector<Pair> _data;
     79    Compare _comp;
     80    ItemIntMap &_iim;
    8481
    8582  public:
    86     /// \brief The constructor.
    87     ///
    88     /// The constructor.
    89     /// \param _iim should be given to the constructor, since it is used
    90     /// internally to handle the cross references. The value of the map
    91     /// 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) {}
    104 
    105 
    106     /// The number of items stored in the heap.
    107     ///
    108     /// \brief Returns the number of items stored in the heap.
    109     int size() const { return data.size(); }
    110 
    111     /// \brief Checks if the heap stores no items.
    112     ///
    113     /// Returns \c true if and only if the heap stores no items.
    114     bool empty() const { return data.empty(); }
    115 
    116     /// \brief Make empty this heap.
    117     ///
    118     /// Make empty this heap. It does not change the cross reference map.
    119     /// If you want to reuse what is not surely empty you should first clear
    120     /// the heap and after that you should set the cross reference map for
    121     /// each item to \c PRE_HEAP.
     83
     84    /// \brief Constructor.
     85    ///
     86    /// Constructor.
     87    /// \param map A map that assigns \c int values to the items.
     88    /// It is used internally to handle the cross references.
     89    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     90    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
     91
     92    /// \brief Constructor.
     93    ///
     94    /// Constructor.
     95    /// \param map A map that assigns \c int values to the items.
     96    /// It is used internally to handle the cross references.
     97    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     98    /// \param comp The function object used for comparing the priorities.
     99    BinHeap(ItemIntMap &map, const Compare &comp)
     100      : _iim(map), _comp(comp) {}
     101
     102
     103    /// \brief The number of items stored in the heap.
     104    ///
     105    /// This function returns the number of items stored in the heap.
     106    int size() const { return _data.size(); }
     107
     108    /// \brief Check if the heap is empty.
     109    ///
     110    /// This function returns \c true if the heap is empty.
     111    bool empty() const { return _data.empty(); }
     112
     113    /// \brief Make the heap empty.
     114    ///
     115    /// This functon makes the heap empty.
     116    /// It does not change the cross reference map. If you want to reuse
     117    /// a heap that is not surely empty, you should first clear it and
     118    /// then you should set the cross reference map to \c PRE_HEAP
     119    /// for each item.
    122120    void clear() {
    123       data.clear();
     121      _data.clear();
    124122    }
    125123
     
    127125    static int parent(int i) { return (i-1)/2; }
    128126
    129     static int second_child(int i) { return 2*i+2; }
     127    static int secondChild(int i) { return 2*i+2; }
    130128    bool less(const Pair &p1, const Pair &p2) const {
    131       return comp(p1.second, p2.second);
    132     }
    133 
    134     int bubble_up(int hole, Pair p) {
     129      return _comp(p1.second, p2.second);
     130    }
     131
     132    int bubbleUp(int hole, Pair p) {
    135133      int par = parent(hole);
    136       while( hole>0 && less(p,data[par]) ) {
    137         move(data[par],hole);
     134      while( hole>0 && less(p,_data[par]) ) {
     135        move(_data[par],hole);
    138136        hole = par;
    139137        par = parent(hole);
     
    143141    }
    144142
    145     int bubble_down(int hole, Pair p, int length) {
    146       int child = second_child(hole);
     143    int bubbleDown(int hole, Pair p, int length) {
     144      int child = secondChild(hole);
    147145      while(child < length) {
    148         if( less(data[child-1], data[child]) ) {
     146        if( less(_data[child-1], _data[child]) ) {
    149147          --child;
    150148        }
    151         if( !less(data[child], p) )
     149        if( !less(_data[child], p) )
    152150          goto ok;
    153         move(data[child], hole);
     151        move(_data[child], hole);
    154152        hole = child;
    155         child = second_child(hole);
     153        child = secondChild(hole);
    156154      }
    157155      child--;
    158       if( child<length && less(data[child], p) ) {
    159         move(data[child], hole);
     156      if( child<length && less(_data[child], p) ) {
     157        move(_data[child], hole);
    160158        hole=child;
    161159      }
     
    166164
    167165    void move(const Pair &p, int i) {
    168       data[i] = p;
    169       iim.set(p.first, i);
     166      _data[i] = p;
     167      _iim.set(p.first, i);
    170168    }
    171169
    172170  public:
     171
    173172    /// \brief Insert a pair of item and priority into the heap.
    174173    ///
    175     /// Adds \c p.first to the heap with priority \c p.second.
     174    /// This function inserts \c p.first to the heap with priority
     175    /// \c p.second.
    176176    /// \param p The pair to insert.
     177    /// \pre \c p.first must not be stored in the heap.
    177178    void push(const Pair &p) {
    178       int n = data.size();
    179       data.resize(n+1);
    180       bubble_up(n, p);
    181     }
    182 
    183     /// \brief Insert an item into the heap with the given heap.
    184     ///
    185     /// Adds \c i to the heap with priority \c p.
     179      int n = _data.size();
     180      _data.resize(n+1);
     181      bubbleUp(n, p);
     182    }
     183
     184    /// \brief Insert an item into the heap with the given priority.
     185    ///
     186    /// This function inserts the given item into the heap with the
     187    /// given priority.
    186188    /// \param i The item to insert.
    187189    /// \param p The priority of the item.
     190    /// \pre \e i must not be stored in the heap.
    188191    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    189192
    190     /// \brief Returns the item with minimum priority relative to \c Compare.
    191     ///
    192     /// This method returns the item with minimum priority relative to \c
    193     /// Compare.
    194     /// \pre The heap must be nonempty.
     193    /// \brief Return the item having minimum priority.
     194    ///
     195    /// This function returns the item having minimum priority.
     196    /// \pre The heap must be non-empty.
    195197    Item top() const {
    196       return data[0].first;
    197     }
    198 
    199