COIN-OR::LEMON - Graph Library

Ignore:
Files:
14 added
3 deleted
87 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r564 r610  
    2323lemon/stamp-h2
    2424doc/Doxyfile
    25 cmake/cmake.version
     25cmake/version.cmake
    2626.dirstamp
    2727.libs/*
  • CMakeLists.txt

    r574 r599  
    1010PROJECT(${PROJECT_NAME})
    1111
    12 SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
     12SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
    1313
    1414INCLUDE(FindDoxygen)
     
    3939
    4040ADD_SUBDIRECTORY(lemon)
    41 ADD_SUBDIRECTORY(demo)
    42 ADD_SUBDIRECTORY(tools)
    43 ADD_SUBDIRECTORY(doc)
    44 ADD_SUBDIRECTORY(test)
     41IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     42  ADD_SUBDIRECTORY(demo)
     43  ADD_SUBDIRECTORY(tools)
     44  ADD_SUBDIRECTORY(doc)
     45  ADD_SUBDIRECTORY(test)
     46ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    4547
    46 IF(WIN32)
    47   SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    48   SET(CPACK_PACKAGE_VENDOR "EGRES")
    49   SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
    50     "LEMON - Library of Efficient Models and Optimization in Networks")
    51   SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
     48IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     49  IF(WIN32)
     50    SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
     51    SET(CPACK_PACKAGE_VENDOR "EGRES")
     52    SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
     53      "LEMON - Library of Efficient Models and Optimization in Networks")
     54    SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
    5255
    53   SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     56    SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
    5457
    55   SET(CPACK_PACKAGE_INSTALL_DIRECTORY
    56     "${PROJECT_NAME} ${PROJECT_VERSION}")
    57   SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
    58     "${PROJECT_NAME} ${PROJECT_VERSION}")
     58    SET(CPACK_PACKAGE_INSTALL_DIRECTORY
     59      "${PROJECT_NAME} ${PROJECT_VERSION}")
     60    SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
     61      "${PROJECT_NAME} ${PROJECT_VERSION}")
    5962
    60   SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
     63    SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
    6164
    62   SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    63   SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
    64   SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
    65   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
     65    SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
     66    SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     67    SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
     68    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    6669
    67   SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
    68     "C++ header files")
    69   SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    70     "DLL and import library")
    71   SET(CPACK_COMPONENT_BIN_DESCRIPTION
    72     "Command line utilities")
    73   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    74     "Doxygen generated documentation")
     70    SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
     71      "C++ header files")
     72    SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     73      "DLL and import library")
     74    SET(CPACK_COMPONENT_BIN_DESCRIPTION
     75      "Command line utilities")
     76    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     77      "Doxygen generated documentation")
    7578
    76   SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     79    SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
    7780
    78   SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
    79   SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
    80   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     81    SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     82    SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     83    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
    8184
    82   SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
    83     "Components needed to develop software using LEMON")
    84   SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
    85     "Documentation of LEMON")
     85    SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
     86      "Components needed to develop software using LEMON")
     87    SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
     88      "Documentation of LEMON")
    8689
    87   SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     90    SET(CPACK_ALL_INSTALL_TYPES Full Developer)
    8891
    89   SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
    90   SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
    91   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
     92    SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
     93    SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
     94    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
    9295
    93   SET(CPACK_GENERATOR "NSIS")
    94   SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
    95   SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
    96   #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
    97   SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    98   SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
    99   SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
    100   SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
    101   SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
    102   SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
    103     CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
    104     ")
    105   SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
    106     !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
    107     Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
    108     ")
     96    SET(CPACK_GENERATOR "NSIS")
     97    SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
     98    SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     99    #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
     100    SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
     101    SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     102    SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
     103    SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
     104    SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
     105    SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
     106      CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
     107      ")
     108    SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
     109      !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
     110      Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
     111      ")
    109112
    110   INCLUDE(CPack)
    111 ENDIF(WIN32)
     113    INCLUDE(CPack)
     114  ENDIF(WIN32)
     115ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
  • 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

    r555 r614  
    1212        m4/lx_check_glpk.m4 \
    1313        m4/lx_check_soplex.m4 \
     14        m4/lx_check_clp.m4 \
     15        m4/lx_check_cbc.m4 \
    1416        CMakeLists.txt \
    1517        cmake/FindGhostscript.cmake \
     
    4042include test/Makefile.am
    4143include doc/Makefile.am
    42 include demo/Makefile.am
    4344include tools/Makefile.am
     45
     46DIST_SUBDIRS = demo
     47
     48demo:
     49        $(MAKE) $(AM_MAKEFLAGS) -C demo
    4450
    4551MRPROPERFILES = \
     
    6975        bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
    7076
    71 .PHONY: mrproper dist-bz2 distcheck-bz2
     77.PHONY: demo mrproper dist-bz2 distcheck-bz2
  • NEWS

    r322 r534  
     12009-03-27 LEMON joins to the COIN-OR initiative
     2
     3        COIN-OR (Computational Infrastructure for Operations Research,
     4        http://www.coin-or.org) project is an initiative to spur the
     5        development of open-source software for the operations research
     6        community.
     7
    182008-10-13 Version 1.0 released
    29
  • configure.ac

    r564 r615  
    6060LX_CHECK_CPLEX
    6161LX_CHECK_SOPLEX
    62 LX_CHECK_CLP
     62LX_CHECK_COIN
    6363
    6464AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
    6565AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
    66 
    67 dnl Disable/enable building the demo programs.
    68 AC_ARG_ENABLE([demo],
    69 AS_HELP_STRING([--enable-demo], [build the demo programs])
    70 AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
    71               [], [enable_demo=no])
    72 AC_MSG_CHECKING([whether to build the demo programs])
    73 if test x"$enable_demo" != x"no"; then
    74   AC_MSG_RESULT([yes])
    75 else
    76   AC_MSG_RESULT([no])
    77 fi
    78 AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
    7966
    8067dnl Disable/enable building the binary tools.
     
    11198AC_CONFIG_FILES([
    11299Makefile
     100demo/Makefile
    113101cmake/version.cmake
    114102doc/Doxyfile
     
    132120echo SOPLEX support................ : $lx_soplex_found
    133121echo CLP support................... : $lx_clp_found
     122echo CBC support................... : $lx_cbc_found
    134123echo
    135 echo Build demo programs........... : $enable_demo
    136124echo Build additional tools........ : $enable_tools
    137125echo
  • demo/CMakeLists.txt

    r498 r596  
    11INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
    3   ${CMAKE_BINARY_DIR}
     2  ${PROJECT_SOURCE_DIR}
     3  ${PROJECT_BINARY_DIR}
    44)
    55
    6 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
     6LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
    77
    88SET(DEMOS
  • 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
  • doc/CMakeLists.txt

    r565 r633  
    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
     7  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
     8  ${PROJECT_BINARY_DIR}/doc/Doxyfile
    99  @ONLY)
    1010
     
    1515      COMMAND rm -rf gen-images
    1616      COMMAND mkdir gen-images
     17      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
     18      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
     19      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
     20      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
    1721      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
     22      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    1823      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
    1924      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
     
    2126      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
    2227      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
     28      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    2329      COMMAND rm -rf html
    2430      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     
    2834      COMMAND if exist gen-images rmdir /s /q gen-images
    2935      COMMAND mkdir gen-images
     36      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
     37      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
     38      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
     39      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
     40      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
     41      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    3042      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
    3143      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
     
    3345      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
    3446      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
     47      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    3548      COMMAND if exist html rmdir /s /q html
    3649      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
  • doc/Makefile.am

    r349 r634  
    2222        nodeshape_4.eps
    2323
     24DOC_EPS_IMAGES27 = \
     25        bipartite_matching.eps \
     26        bipartite_partitions.eps \
     27        connected_components.eps \
     28        edge_biconnected_components.eps \
     29        node_biconnected_components.eps \
     30        strongly_connected_components.eps
     31
    2432DOC_EPS_IMAGES = \
    25         $(DOC_EPS_IMAGES18)
     33        $(DOC_EPS_IMAGES18) \
     34        $(DOC_EPS_IMAGES27)
    2635
    2736DOC_PNG_IMAGES = \
     
    3948        if test ${gs_found} = yes; then \
    4049          $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \
     50        else \
     51          echo; \
     52          echo "Ghostscript not found."; \
     53          echo; \
     54          exit 1; \
     55        fi
     56
     57$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
     58        -mkdir doc/gen-images
     59        if test ${gs_found} = yes; then \
     60          $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \
    4161        else \
    4262          echo; \
  • doc/groups.dox

    r656 r658  
    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
     
    143143\brief Graph types between real graphs and graph adaptors.
    144144
    145 This group describes some graph types between real graphs and graph adaptors.
     145This group contains some graph types between real graphs and graph adaptors.
    146146These classes wrap graphs to give new functionality as the adaptors do it.
    147147On the other hand they are not light-weight structures as the adaptors.
     
    153153\brief Map structures implemented in LEMON.
    154154
    155 This group describes the map structures implemented in LEMON.
     155This group contains the map structures implemented in LEMON.
    156156
    157157LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    166166\brief Special graph-related maps.
    167167
    168 This group describes maps that are specifically designed to assign
     168This group contains maps that are specifically designed to assign
    169169values to the nodes and arcs/edges of graphs.
    170170
     
    178178\brief Tools to create new maps from existing ones
    179179
    180 This group describes map adaptors that are used to create "implicit"
     180This group contains map adaptors that are used to create "implicit"
    181181maps from other maps.
    182182
     
    241241\brief Two dimensional data storages implemented in LEMON.
    242242
    243 This group describes two dimensional data storages implemented in LEMON.
     243This group contains two dimensional data storages implemented in LEMON.
    244244*/
    245245
     
    249249\brief %Path structures implemented in LEMON.
    250250
    251 This group describes the path structures implemented in LEMON.
     251This group contains the path structures implemented in LEMON.
    252252
    253253LEMON provides flexible data structures to work with paths.
     
    265265\brief Auxiliary data structures implemented in LEMON.
    266266
    267 This group describes some data structures implemented in LEMON in
     267This group contains some data structures implemented in LEMON in
    268268order to make it easier to implement combinatorial algorithms.
    269269*/
     
    271271/**
    272272@defgroup algs Algorithms
    273 \brief This group describes the several algorithms
     273\brief This group contains the several algorithms
    274274implemented in LEMON.
    275275
    276 This group describes the several algorithms
     276This group contains the several algorithms
    277277implemented in LEMON.
    278278*/
     
    283283\brief Common graph search algorithms.
    284284
    285 This group describes the common graph search algorithms, namely
     285This group contains the common graph search algorithms, namely
    286286\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    287287*/
     
    292292\brief Algorithms for finding shortest paths.
    293293
    294 This group describes the algorithms for finding shortest paths in digraphs.
     294This group contains the algorithms for finding shortest paths in digraphs.
    295295
    296296 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    313313\brief Algorithms for finding maximum flows.
    314314
    315 This group describes the algorithms for finding maximum flows and
     315This group contains the algorithms for finding maximum flows and
    316316feasible circulations.
    317317
     
    451451\brief Algorithms for finding minimum cut in graphs.
    452452
    453 This group describes the algorithms for finding minimum cut in graphs.
     453This group contains the algorithms for finding minimum cut in graphs.
    454454
    455455The \e minimum \e cut \e problem is to find a non-empty and non-complete
     
    468468- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    469469  calculating minimum cut in undirected graphs.
    470 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
     470- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    471471  all-pairs minimum cut in undirected graphs.
    472472
     
    476476
    477477/**
    478 @defgroup graph_prop Connectivity and Other Graph Properties
     478@defgroup graph_properties Connectivity and Other Graph Properties
    479479@ingroup algs
    480480\brief Algorithms for discovering the graph properties
    481481
    482 This group describes the algorithms for discovering the graph properties
     482This group contains the algorithms for discovering the graph properties
    483483like connectivity, bipartiteness, euler property, simplicity etc.
    484484
     
    492492\brief Algorithms for planarity checking, embedding and drawing
    493493
    494 This group describes the algorithms for planarity checking,
     494This group contains the algorithms for planarity checking,
    495495embedding and drawing.
    496496
     
    504504\brief Algorithms for finding matchings in graphs and bipartite graphs.
    505505
    506 This group contains algorithm objects and functions to calculate
     506This group contains the algorithms for calculating
    507507matchings in graphs and bipartite graphs. The general matching problem is
    508 finding a subset of the arcs which does not shares common endpoints.
     508finding a subset of the edges for which each node has at most one incident
     509edge.
    509510
    510511There are several different algorithms for calculate matchings in
     
    543544\brief Algorithms for finding a minimum cost spanning tree in a graph.
    544545
    545 This group describes the algorithms for finding a minimum cost spanning
     546This group contains the algorithms for finding a minimum cost spanning
    546547tree in a graph.
    547548*/
     
    552553\brief Auxiliary algorithms implemented in LEMON.
    553554
    554 This group describes some algorithms implemented in LEMON
     555This group contains some algorithms implemented in LEMON
    555556in order to make it easier to implement complex algorithms.
    556557*/
     
    561562\brief Approximation algorithms.
    562563
    563 This group describes the approximation and heuristic algorithms
     564This group contains the approximation and heuristic algorithms
    564565implemented in LEMON.
    565566*/
     
    567568/**
    568569@defgroup gen_opt_group General Optimization Tools
    569 \brief This group describes some general optimization frameworks
     570\brief This group contains some general optimization frameworks
    570571implemented in LEMON.
    571572
    572 This group describes some general optimization frameworks
     573This group contains some general optimization frameworks
    573574implemented in LEMON.
    574575*/
     
    579580\brief Lp and Mip solver interfaces for LEMON.
    580581
    581 This group describes Lp and Mip solver interfaces for LEMON. The
     582This group contains Lp and Mip solver interfaces for LEMON. The
    582583various LP solvers could be used in the same manner with this
    583584interface.
     
    598599\brief Metaheuristics for LEMON library.
    599600
    600 This group describes some metaheuristic optimization tools.
     601This group contains some metaheuristic optimization tools.
    601602*/
    602603
     
    613614\brief Simple basic graph utilities.
    614615
    615 This group describes some simple basic graph utilities.
     616This group contains some simple basic graph utilities.
    616617*/
    617618
     
    621622\brief Tools for development, debugging and testing.
    622623
    623 This group describes several useful tools for development,
     624This group contains several useful tools for development,
    624625debugging and testing.
    625626*/
     
    630631\brief Simple tools for measuring the performance of algorithms.
    631632
    632 This group describes simple tools for measuring the performance
     633This group contains simple tools for measuring the performance
    633634of algorithms.
    634635*/
     
    639640\brief Exceptions defined in LEMON.
    640641
    641 This group describes the exceptions defined in LEMON.
     642This group contains the exceptions defined in LEMON.
    642643*/
    643644
     
    646647\brief Graph Input-Output methods
    647648
    648 This group describes the tools for importing and exporting graphs
     649This group contains the tools for importing and exporting graphs
    649650and graph related data. Now it supports the \ref lgf-format
    650651"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    657658\brief Reading and writing LEMON Graph Format.
    658659
    659 This group describes methods for reading and writing
     660This group contains methods for reading and writing
    660661\ref lgf-format "LEMON Graph Format".
    661662*/
     
    666667\brief General \c EPS drawer and graph exporter
    667668
    668 This group describes general \c EPS drawing methods and special
     669This group contains general \c EPS drawing methods and special
    669670graph exporting tools.
    670671*/
     
    690691\brief Skeleton classes and concept checking classes
    691692
    692 This group describes the data/algorithm skeletons and concept checking
     693This group contains the data/algorithm skeletons and concept checking
    693694classes implemented in LEMON.
    694695
     
    720721\brief Skeleton and concept checking classes for graph structures
    721722
    722 This group describes the skeletons and concept checking classes of LEMON's
     723This group contains the skeletons and concept checking classes of LEMON's
    723724graph structures and helper classes used to implement these.
    724725*/
     
    729730\brief Skeleton and concept checking classes for maps
    730731
    731 This group describes the skeletons and concept checking classes of maps.
     732This group contains the skeletons and concept checking classes of maps.
    732733*/
    733734
     
    740741the \c demo subdirectory of the source tree.
    741742
    742 It order to compile them, use <tt>--enable-demo</tt> configure option when
    743 build the library.
     743In order to compile them, use the <tt>make demo</tt> or the
     744<tt>make check</tt> commands.
    744745*/
    745746
  • doc/mainpage.dox

    r463 r606  
    4646"Quick Tour to LEMON" which will guide you along.
    4747
    48 If you already feel like using our library, see the page that tells you
    49 \ref getstart "How to start using LEMON".
    50 
    51 If you
    52 want to see how LEMON works, see
    53 some \ref demoprograms "demo programs".
     48If you already feel like using our library, see the
     49<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    5450
    5551If 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.
     52<a class="el" href="modules.html">Modules</a> section.
    5853
    5954If you are a user of the old (0.x) series of LEMON, please check out the
  • lemon/CMakeLists.txt

    r562 r596  
    11INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
    3   ${CMAKE_BINARY_DIR}
     2  ${PROJECT_SOURCE_DIR}
     3  ${PROJECT_BINARY_DIR}
    44)
    55
  • lemon/Makefile.am

    r648 r658  
    1313        lemon/lp_base.cc \
    1414        lemon/lp_skeleton.cc \
    15         lemon/random.cc \
     15        lemon/random.cc \
    1616        lemon/bits/windows.cc
    1717
    1818
    1919lemon_libemon_la_CXXFLAGS = \
     20        $(AM_CXXFLAGS) \
    2021        $(GLPK_CFLAGS) \
    2122        $(CPLEX_CFLAGS) \
    2223        $(SOPLEX_CXXFLAGS) \
    23         $(CLP_CXXFLAGS)
     24        $(CLP_CXXFLAGS) \
     25        $(CBC_CXXFLAGS)
    2426
    2527lemon_libemon_la_LDFLAGS = \
     
    2729        $(CPLEX_LIBS) \
    2830        $(SOPLEX_LIBS) \
    29         $(CLP_LIBS)
     31        $(CLP_LIBS) \
     32        $(CBC_LIBS)
    3033
    3134if HAVE_GLPK
     
    4346if HAVE_CLP
    4447lemon_libemon_la_SOURCES += lemon/clp.cc
     48endif
     49
     50if HAVE_CBC
     51lemon_libemon_la_SOURCES += lemon/cbc.cc
    4552endif
    4653
     
    6976        lemon/full_graph.h \
    7077        lemon/glpk.h \
     78        lemon/gomory_hu.h \
    7179        lemon/graph_to_eps.h \
    7280        lemon/grid_graph.h \
     
    8290        lemon/list_graph.h \
    8391        lemon/maps.h \
     92        lemon/matching.h \
    8493        lemon/math.h \
    85         lemon/max_matching.h \
    8694        lemon/min_cost_arborescence.h \
    8795        lemon/nauty_reader.h \
  • lemon/adaptors.h

    r566 r626  
    21932193    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    21942194    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
     2195   
     2196    typedef EdgeNotifier ArcNotifier;
     2197    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
    21952198
    21962199  protected:
     
    22552258    /// This map adaptor class adapts two arc maps of the underlying
    22562259    /// digraph to get an arc map of the undirected graph.
    2257     /// Its value type is inherited from the first arc map type
    2258     /// (\c %ForwardMap).
    2259     template <typename ForwardMap, typename BackwardMap>
     2260    /// Its value type is inherited from the first arc map type (\c FW).
     2261    /// \tparam FW The type of the "foward" arc map.
     2262    /// \tparam BK The type of the "backward" arc map.
     2263    template <typename FW, typename BK>
    22602264    class CombinedArcMap {
    22612265    public:
     
    22642268      typedef typename Parent::Arc Key;
    22652269      /// The value type of the map
    2266       typedef typename ForwardMap::Value Value;
    2267 
    2268       typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
    2269 
    2270       typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
    2271       typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
    2272       typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
    2273       typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
     2270      typedef typename FW::Value Value;
     2271
     2272      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
     2273
     2274      typedef typename MapTraits<FW>::ReturnValue ReturnValue;
     2275      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
     2276      typedef typename MapTraits<FW>::ReturnValue Reference;
     2277      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
    22742278
    22752279      /// Constructor
    2276       CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
     2280      CombinedArcMap(FW& forward, BK& backward)
    22772281        : _forward(&forward), _backward(&backward) {}
    22782282
     
    23062310    protected:
    23072311
    2308       ForwardMap* _forward;
    2309       BackwardMap* _backward;
     2312      FW* _forward;
     2313      BK* _backward;
    23102314
    23112315    };
     
    23142318    ///
    23152319    /// This function just returns a combined arc map.
    2316     template <typename ForwardMap, typename BackwardMap>
    2317     static CombinedArcMap<ForwardMap, BackwardMap>
    2318     combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
    2319       return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
    2320     }
    2321 
    2322     template <typename ForwardMap, typename BackwardMap>
    2323     static CombinedArcMap<const ForwardMap, BackwardMap>
    2324     combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
    2325       return CombinedArcMap<const ForwardMap,
    2326         BackwardMap>(forward, backward);
    2327     }
    2328 
    2329     template <typename ForwardMap, typename BackwardMap>
    2330     static CombinedArcMap<ForwardMap, const BackwardMap>
    2331     combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
    2332       return CombinedArcMap<ForwardMap,
    2333         const BackwardMap>(forward, backward);
    2334     }
    2335 
    2336     template <typename ForwardMap, typename BackwardMap>
    2337     static CombinedArcMap<const ForwardMap, const BackwardMap>
    2338     combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
    2339       return CombinedArcMap<const ForwardMap,
    2340         const BackwardMap>(forward, backward);
     2320    template <typename FW, typename BK>
     2321    static CombinedArcMap<FW, BK>
     2322    combinedArcMap(FW& forward, BK& backward) {
     2323      return CombinedArcMap<FW, BK>(forward, backward);
     2324    }
     2325
     2326    template <typename FW, typename BK>
     2327    static CombinedArcMap<const FW, BK>
     2328    combinedArcMap(const FW& forward, BK& backward) {
     2329      return CombinedArcMap<const FW, BK>(forward, backward);
     2330    }
     2331
     2332    template <typename FW, typename BK>
     2333    static CombinedArcMap<FW, const BK>
     2334    combinedArcMap(FW& forward, const BK& backward) {
     2335      return CombinedArcMap<FW, const BK>(forward, backward);
     2336    }
     2337
     2338    template <typename FW, typename BK>
     2339    static CombinedArcMap<const FW, const BK>
     2340    combinedArcMap(const FW& forward, const BK& backward) {
     2341      return CombinedArcMap<const FW, const BK>(forward, backward);
    23412342    }
    23422343
     
    34073408    /// This map adaptor class adapts two node maps of the original digraph
    34083409    /// to get a node map of the split digraph.
    3409     /// Its value type is inherited from the first node map type
    3410     /// (\c InNodeMap).
    3411     template <typename InNodeMap, typename OutNodeMap>
     3410    /// Its value type is inherited from the first node map type (\c IN).
     3411    /// \tparam IN The type of the node map for the in-nodes.
     3412    /// \tparam OUT The type of the node map for the out-nodes.
     3413    template <typename IN, typename OUT>
    34123414    class CombinedNodeMap {
    34133415    public:
     
    34163418      typedef Node Key;
    34173419      /// The value type of the map
    3418       typedef typename InNodeMap::Value Value;
    3419 
    3420       typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
    3421       typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
    3422       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
    3423       typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
    3424       typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
     3420      typedef typename IN::Value Value;
     3421
     3422      typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
     3423      typedef typename MapTraits<IN>::ReturnValue ReturnValue;
     3424      typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
     3425      typedef typename MapTraits<IN>::ReturnValue Reference;
     3426      typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
    34253427
    34263428      /// Constructor
    3427       CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
     3429      CombinedNodeMap(IN& in_map, OUT& out_map)
    34283430        : _in_map(in_map), _out_map(out_map) {}
    34293431
     
    34573459    private:
    34583460
    3459       InNodeMap& _in_map;
    3460       OutNodeMap& _out_map;
     3461      IN& _in_map;
     3462      OUT& _out_map;
    34613463
    34623464    };
     
    34663468    ///
    34673469    /// This function just returns a combined node map.
    3468     template <typename InNodeMap, typename OutNodeMap>
    3469     static CombinedNodeMap<InNodeMap, OutNodeMap>
    3470     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
    3471       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
    3472     }
    3473 
    3474     template <typename InNodeMap, typename OutNodeMap>
    3475     static CombinedNodeMap<const InNodeMap, OutNodeMap>
    3476     combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
    3477       return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
    3478     }
    3479 
    3480     template <typename InNodeMap, typename OutNodeMap>
    3481     static CombinedNodeMap<InNodeMap, const OutNodeMap>
    3482     combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
    3483       return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
    3484     }
    3485 
    3486     template <typename InNodeMap, typename OutNodeMap>
    3487     static CombinedNodeMap<const InNodeMap, const OutNodeMap>
    3488     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
    3489       return CombinedNodeMap<const InNodeMap,
    3490         const OutNodeMap>(in_map, out_map);
     3470    template <typename IN, typename OUT>
     3471    static CombinedNodeMap<IN, OUT>
     3472    combinedNodeMap(IN& in_map, OUT& out_map) {
     3473      return CombinedNodeMap<IN, OUT>(in_map, out_map);
     3474    }
     3475
     3476    template <typename IN, typename OUT>
     3477    static CombinedNodeMap<const IN, OUT>
     3478    combinedNodeMap(const IN& in_map, OUT& out_map) {
     3479      return CombinedNodeMap<const IN, OUT>(in_map, out_map);
     3480    }
     3481
     3482    template <typename IN, typename OUT>
     3483    static CombinedNodeMap<IN, const OUT>
     3484    combinedNodeMap(IN& in_map, const OUT& out_map) {
     3485      return CombinedNodeMap<IN, const OUT>(in_map, out_map);
     3486    }
     3487
     3488    template <typename IN, typename OUT>
     3489    static CombinedNodeMap<const IN, const OUT>
     3490    combinedNodeMap(const IN& in_map, const OUT& out_map) {
     3491      return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
    34913492    }
    34923493
     
    34963497    /// This map adaptor class adapts an arc map and a node map of the
    34973498    /// original digraph to get an arc map of the split digraph.
    3498     /// Its value type is inherited from the original arc map type
    3499     /// (\c ArcMap).
    3500     template <typename ArcMap, typename NodeMap>
     3499    /// Its value type is inherited from the original arc map type (\c AM).
     3500    /// \tparam AM The type of the arc map.
     3501    /// \tparam NM the type of the node map.
     3502    template <typename AM, typename NM>
    35013503    class CombinedArcMap {
    35023504    public:
     
    35053507      typedef Arc Key;
    35063508      /// The value type of the map
    3507       typedef typename ArcMap::Value Value;
    3508 
    3509       typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
    3510       typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
    3511       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
    3512       typedef typename MapTraits<ArcMap>::ReturnValue Reference;
    3513       typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
     3509      typedef typename AM::Value Value;
     3510
     3511      typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
     3512      typedef typename MapTraits<AM>::ReturnValue ReturnValue;
     3513      typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
     3514      typedef typename MapTraits<AM>::ReturnValue Reference;
     3515      typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
    35143516
    35153517      /// Constructor
    3516       CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
     3518      CombinedArcMap(AM& arc_map, NM& node_map)
    35173519        : _arc_map(arc_map), _node_map(node_map) {}
    35183520
     
    35453547
    35463548    private:
    3547       ArcMap& _arc_map;
    3548       NodeMap& _node_map;
     3549
     3550      AM& _arc_map;
     3551      NM& _node_map;
     3552
    35493553    };
    35503554
  • lemon/bin_heap.h

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

    r566 r606  
    2525#include <lemon/bits/map_extender.h>
    2626
    27 ///\ingroup digraphbits
    28 ///\file
    29 ///\brief Extenders for the arc set types
     27//\ingroup digraphbits
     28//\file
     29//\brief Extenders for the arc set types
    3030namespace lemon {
    3131
    32   /// \ingroup digraphbits
    33   ///
    34   /// \brief Extender for the ArcSets
     32  // \ingroup digraphbits
     33  //
     34  // \brief Extender for the ArcSets
    3535  template <typename Base>
    3636  class ArcSetExtender : public Base {
     
    7373    // Alteration notifier extensions
    7474
    75     /// The arc observer registry.
     75    // The arc observer registry.
    7676    typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
    7777
     
    8484    using Parent::notifier;
    8585
    86     /// \brief Gives back the arc alteration notifier.
    87     ///
    88     /// Gives back the arc alteration notifier.
     86    // Gives back the arc alteration notifier.
    8987    ArcNotifier& notifier(Arc) const {
    9088      return arc_notifier;
     
    186184    };
    187185
    188     /// \brief Base node of the iterator
    189     ///
    190     /// Returns the base node (ie. the source in this case) of the iterator
     186    // \brief Base node of the iterator
     187    //
     188    // Returns the base node (ie. the source in this case) of the iterator
    191189    Node baseNode(const OutArcIt &e) const {
    192190      return Parent::source(static_cast<const Arc&>(e));
    193191    }
    194     /// \brief Running node of the iterator
    195     ///
    196     /// Returns the running node (ie. the target in this case) of the
    197     /// iterator
     192    // \brief Running node of the iterator
     193    //
     194    // Returns the running node (ie. the target in this case) of the
     195    // iterator
    198196    Node runningNode(const OutArcIt &e) const {
    199197      return Parent::target(static_cast<const Arc&>(e));
    200198    }
    201199
    202     /// \brief Base node of the iterator
    203     ///
    204     /// Returns the base node (ie. the target in this case) of the iterator
     200    // \brief Base node of the iterator
     201    //
     202    // Returns the base node (ie. the target in this case) of the iterator
    205203    Node baseNode(const InArcIt &e) const {
    206204      return Parent::target(static_cast<const Arc&>(e));
    207205    }
    208     /// \brief Running node of the iterator
    209     ///
    210     /// Returns the running node (ie. the source in this case) of the
    211     /// iterator
     206    // \brief Running node of the iterator
     207    //
     208    // Returns the running node (ie. the source in this case) of the
     209    // iterator
    212210    Node runningNode(const InArcIt &e) const {
    213211      return Parent::source(static_cast<const Arc&>(e));
     
    272270
    273271
    274   /// \ingroup digraphbits
    275   ///
    276   /// \brief Extender for the EdgeSets
     272  // \ingroup digraphbits
     273  //
     274  // \brief Extender for the EdgeSets
    277275  template <typename Base>
    278276  class EdgeSetExtender : public Base {
     
    493491    };
    494492
    495     /// \brief Base node of the iterator
    496     ///
    497     /// Returns the base node (ie. the source in this case) of the iterator
     493    // \brief Base node of the iterator
     494    //
     495    // Returns the base node (ie. the source in this case) of the iterator
    498496    Node baseNode(const OutArcIt &e) const {
    499497      return Parent::source(static_cast<const Arc&>(e));
    500498    }
    501     /// \brief Running node of the iterator
    502     ///
    503     /// Returns the running node (ie. the target in this case) of the
    504     /// iterator
     499    // \brief Running node of the iterator
     500    //
     501    // Returns the running node (ie. the target in this case) of the
     502    // iterator
    505503    Node runningNode(const OutArcIt &e) const {
    506504      return Parent::target(static_cast<const Arc&>(e));
    507505    }
    508506
    509     /// \brief Base node of the iterator
    510     ///
    511     /// Returns the base node (ie. the target in this case) of the iterator
     507    // \brief Base node of the iterator
     508    //
     509    // Returns the base node (ie. the target in this case) of the iterator
    512510    Node baseNode(const InArcIt &e) const {
    513511      return Parent::target(static_cast<const Arc&>(e));
    514512    }
    515     /// \brief Running node of the iterator
    516     ///
    517     /// Returns the running node (ie. the source in this case) of the
    518     /// iterator
     513    // \brief Running node of the iterator
     514    //
     515    // Returns the running node (ie. the source in this case) of the
     516    // iterator
    519517    Node runningNode(const InArcIt &e) const {
    520518      return Parent::source(static_cast<const Arc&>(e));
    521519    }
    522520
    523     /// Base node of the iterator
    524     ///
    525     /// Returns the base node of the iterator
     521    // Base node of the iterator
     522    //
     523    // Returns the base node of the iterator
    526524    Node baseNode(const IncEdgeIt &e) const {
    527525      return e.direction ? u(e) : v(e);
    528526    }
    529     /// Running node of the iterator
    530     ///
    531     /// Returns the running node of the iterator
     527    // Running node of the iterator
     528    //
     529    // Returns the running node of the iterator
    532530    Node runningNode(const IncEdgeIt &e) const {
    533531      return e.direction ? v(e) : u(e);
  • lemon/bits/graph_adaptor_extender.h

    r478 r627  
    2222#include <lemon/core.h>
    2323#include <lemon/error.h>
    24 
    25 #include <lemon/bits/default_map.h>
    2624
    2725namespace lemon {
  • lemon/bits/map_extender.h

    r463 r627  
    4848    typedef typename Parent::Key Key;
    4949    typedef typename Parent::Value Value;
     50    typedef typename Parent::Reference Reference;
     51    typedef typename Parent::ConstReference ConstReference;
    5052
    5153    class MapIt;
     
    188190    typedef typename Parent::Key Key;
    189191    typedef typename Parent::Value Value;
     192    typedef typename Parent::Reference Reference;
     193    typedef typename Parent::ConstReference ConstReference;
    190194
    191195    class MapIt;
  • lemon/circulation.h

    r657 r658  
    231231    ///@{
    232232
    233     template <typename _FlowMap>
     233    template <typename T>
    234234    struct SetFlowMapTraits : public Traits {
    235       typedef _FlowMap FlowMap;
     235      typedef T FlowMap;
    236236      static FlowMap *createFlowMap(const Digraph&) {
    237237        LEMON_ASSERT(false, "FlowMap is not initialized");
     
    245245    /// \ref named-templ-param "Named parameter" for setting FlowMap
    246246    /// type.
    247     template <typename _FlowMap>
     247    template <typename T>
    248248    struct SetFlowMap
    249249      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    250                            SetFlowMapTraits<_FlowMap> > {
     250                           SetFlowMapTraits<T> > {
    251251      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    252                           SetFlowMapTraits<_FlowMap> > Create;
     252                          SetFlowMapTraits<T> > Create;
    253253    };
    254254
    255     template <typename _Elevator>
     255    template <typename T>
    256256    struct SetElevatorTraits : public Traits {
    257       typedef _Elevator Elevator;
     257      typedef T Elevator;
    258258      static Elevator *createElevator(const Digraph&, int) {
    259259        LEMON_ASSERT(false, "Elevator is not initialized");
     
    271271    /// \ref run() or \ref init().
    272272    /// \sa SetStandardElevator
    273     template <typename _Elevator>
     273    template <typename T>
    274274    struct SetElevator
    275275      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    276                            SetElevatorTraits<_Elevator> > {
     276                           SetElevatorTraits<T> > {
    277277      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    278                           SetElevatorTraits<_Elevator> > Create;
     278                          SetElevatorTraits<T> > Create;
    279279    };
    280280
    281     template <typename _Elevator>
     281    template <typename T>
    282282    struct SetStandardElevatorTraits : public Traits {
    283       typedef _Elevator Elevator;
     283      typedef T Elevator;
    284284      static Elevator *createElevator(const Digraph& digraph, int max_level) {
    285285        return new Elevator(digraph, max_level);
     
    299299    /// before calling \ref run() or \ref init().
    300300    /// \sa SetElevator
    301     template <typename _Elevator>
     301    template <typename T>
    302302    struct SetStandardElevator
    303303      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    304                        SetStandardElevatorTraits<_Elevator> > {
     304                       SetStandardElevatorTraits<T> > {
    305305      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    306                       SetStandardElevatorTraits<_Elevator> > Create;
     306                      SetStandardElevatorTraits<T> > Create;
    307307    };
    308308
     
    471471
    472472      for(NodeIt n(_g);n!=INVALID;++n) {
    473         _excess->set(n, (*_supply)[n]);
     473        (*_excess)[n] = (*_supply)[n];
    474474      }
    475475
    476476      for (ArcIt e(_g);e!=INVALID;++e) {
    477477        _flow->set(e, (*_lo)[e]);
    478         _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);
    479         _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);
     478        (*_excess)[_g.target(e)] += (*_flow)[e];
     479        (*_excess)[_g.source(e)] -= (*_flow)[e];
    480480      }
    481481
     
    500500
    501501      for(NodeIt n(_g);n!=INVALID;++n) {
    502         _excess->set(n, (*_supply)[n]);
     502        (*_excess)[n] = (*_supply)[n];
    503503      }
    504504
     
    506506        if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
    507507          _flow->set(e, (*_up)[e]);
    508           _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);
    509           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);
     508          (*_excess)[_g.target(e)] += (*_up)[e];
     509          (*_excess)[_g.source(e)] -= (*_up)[e];
    510510        } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
    511511          _flow->set(e, (*_lo)[e]);
    512           _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
    513           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
     512          (*_excess)[_g.target(e)] += (*_lo)[e];
     513          (*_excess)[_g.source(e)] -= (*_lo)[e];
    514514        } else {
    515515          Flow fc = -(*_excess)[_g.target(e)];
    516516          _flow->set(e, fc);
    517           _excess->set(_g.target(e), 0);
    518           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
     517          (*_excess)[_g.target(e)] = 0;
     518          (*_excess)[_g.source(e)] -= fc;
    519519        }
    520520      }
     
    555555            if(!_tol.less(fc, exc)) {
    556556              _flow->set(e, (*_flow)[e] + exc);
    557               _excess->set(v, (*_excess)[v] + exc);
     557              (*_excess)[v] += exc;
    558558              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    559559                _level->activate(v);
    560               _excess->set(act,0);
     560              (*_excess)[act] = 0;
    561561              _level->deactivate(act);
    562562              goto next_l;
     
    564564            else {
    565565              _flow->set(e, (*_up)[e]);
    566               _excess->set(v, (*_excess)[v] + fc);
     566              (*_excess)[v] += fc;
    567567              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    568568                _level->activate(v);
     
    579579            if(!_tol.less(fc, exc)) {
    580580              _flow->set(e, (*_flow)[e] - exc);
    581               _excess->set(v, (*_excess)[v] + exc);
     581              (*_excess)[v] += exc;
    582582              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    583583                _level->activate(v);
    584               _excess->set(act,0);
     584              (*_excess)[act] = 0;
    585585              _level->deactivate(act);
    586586              goto next_l;
     
    588588            else {
    589589              _flow->set(e, (*_lo)[e]);
    590               _excess->set(v, (*_excess)[v] + fc);
     590              (*_excess)[v] += fc;
    591591              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    592592                _level->activate(v);
     
    597597        }
    598598
    599         _excess->set(act, exc);
     599        (*_excess)[act] = exc;
    600600        if(!_tol.positive(exc)) _level->deactivate(act);
    601601        else if(mlevel==_node_num) {
     
    700700    ///
    701701    /// \note This function calls \ref barrier() for each node,
    702     /// so it runs in \f$O(n)\f$ time.
     702    /// so it runs in O(n) time.
    703703    ///
    704704    /// \pre Either \ref run() or \ref init() must be called before
  • lemon/clp.cc

    r485 r623  
    2525    _prob = new ClpSimplex();
    2626    _init_temporals();
    27     messageLevel(MESSAGE_NO_OUTPUT);
     27    messageLevel(MESSAGE_NOTHING);
    2828  }
    2929
     
    3333    cols = other.cols;
    3434    _init_temporals();
    35     messageLevel(MESSAGE_NO_OUTPUT);
     35    messageLevel(MESSAGE_NOTHING);
    3636  }
    3737
     
    5757  }
    5858
    59   ClpLp* ClpLp::_newSolver() const {
     59  ClpLp* ClpLp::newSolver() const {
    6060    ClpLp* newlp = new ClpLp;
    6161    return newlp;
    6262  }
    6363
    64   ClpLp* ClpLp::_cloneSolver() const {
     64  ClpLp* ClpLp::cloneSolver() const {
    6565    ClpLp* copylp = new ClpLp(*this);
    6666    return copylp;
     
    431431  }
    432432
    433   void ClpLp::messageLevel(MessageLevel m) {
    434     _prob->setLogLevel(static_cast<int>(m));
     433  void ClpLp::_messageLevel(MessageLevel level) {
     434    switch (level) {
     435    case MESSAGE_NOTHING:
     436      _prob->setLogLevel(0);
     437      break;
     438    case MESSAGE_ERROR:
     439      _prob->setLogLevel(1);
     440      break;
     441    case MESSAGE_WARNING:
     442      _prob->setLogLevel(2);
     443      break;
     444    case MESSAGE_NORMAL:
     445      _prob->setLogLevel(3);
     446      break;
     447    case MESSAGE_VERBOSE:
     448      _prob->setLogLevel(4);
     449      break;
     450    }
    435451  }
    436452
  • lemon/clp.h

    r485 r623  
    5757    ~ClpLp();
    5858
     59    /// \e
     60    virtual ClpLp* newSolver() const;
     61    /// \e
     62    virtual ClpLp* cloneSolver() const;
     63
    5964  protected:
    6065
     
    6671
    6772  protected:
    68 
    69     virtual ClpLp* _newSolver() const;
    70     virtual ClpLp* _cloneSolver() const;
    7173
    7274    virtual const char* _solverName() const;
     
    135137    virtual void _clear();
    136138
     139    virtual void _messageLevel(MessageLevel);
     140   
    137141  public:
    138142
     
    152156    int clpCol(Col c) const { return cols(id(c)); }
    153157
    154     ///Enum for \c messageLevel() parameter
    155     enum MessageLevel {
    156       /// no output (default value)
    157       MESSAGE_NO_OUTPUT = 0,
    158       /// print final solution
    159       MESSAGE_FINAL_SOLUTION = 1,
    160       /// print factorization
    161       MESSAGE_FACTORIZATION = 2,
    162       /// normal output
    163       MESSAGE_NORMAL_OUTPUT = 3,
    164       /// verbose output
    165       MESSAGE_VERBOSE_OUTPUT = 4
    166     };
    167     ///Set the verbosity of the messages
    168 
    169     ///Set the verbosity of the messages
    170     ///
    171     ///\param m is the level of the messages output by the solver routines.
    172     void messageLevel(MessageLevel m);
    173 
    174158  };
    175159
  • lemon/concepts/digraph.h

    r576 r627  
    422422      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
    423423
    424       /// \brief Read write map of the nodes to type \c T.
    425       ///
    426       /// ReadWrite map of the nodes to type \c T.
    427       /// \sa Reference
     424      /// \brief Reference map of the nodes to type \c T.
     425      ///
     426      /// Reference map of the nodes to type \c T.
    428427      template<class T>
    429       class NodeMap : public ReadWriteMap< Node, T > {
     428      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
    430429      public:
    431430
     
    437436      private:
    438437        ///Copy constructor
    439         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
     438        NodeMap(const NodeMap& nm) :
     439          ReferenceMap<Node, T, T&, const T&>(nm) { }
    440440        ///Assignment operator
    441441        template <typename CMap>
     
    446446      };
    447447
    448       /// \brief Read write map of the arcs to type \c T.
     448      /// \brief Reference map of the arcs to type \c T.
    449449      ///
    450450      /// Reference map of the arcs to type \c T.
    451       /// \sa Reference
    452451      template<class T>
    453       class ArcMap : public ReadWriteMap<Arc,T> {
     452      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
    454453      public:
    455454
     
    460459      private:
    461460        ///Copy constructor
    462         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
     461        ArcMap(const ArcMap& em) :
     462          ReferenceMap<Arc, T, T&, const T&>(em) { }
    463463        ///Assignment operator
    464464        template <typename CMap>
     
    472472      struct Constraints {
    473473        void constraints() {
     474          checkConcept<BaseDigraphComponent, _Digraph>();
    474475          checkConcept<IterableDigraphComponent<>, _Digraph>();
    475476          checkConcept<IDableDigraphComponent<>, _Digraph>();
  • lemon/concepts/graph.h

    r576 r627  
    498498      };
    499499
    500       /// \brief Read write map of the nodes to type \c T.
    501       ///
    502       /// ReadWrite map of the nodes to type \c T.
    503       /// \sa Reference
     500      /// \brief Reference map of the nodes to type \c T.
     501      ///
     502      /// Reference map of the nodes to type \c T.
    504503      template<class T>
    505       class NodeMap : public ReadWriteMap< Node, T >
     504      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
    506505      {
    507506      public:
     
    514513      private:
    515514        ///Copy constructor
    516         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
     515        NodeMap(const NodeMap& nm) :
     516          ReferenceMap<Node, T, T&, const T&>(nm) { }
    517517        ///Assignment operator
    518518        template <typename CMap>
     
    523523      };
    524524
    525       /// \brief Read write map of the directed arcs to type \c T.
    526       ///
    527       /// Reference map of the directed arcs to type \c T.
    528       /// \sa Reference
     525      /// \brief Reference map of the arcs to type \c T.
     526      ///
     527      /// Reference map of the arcs to type \c T.
    529528      template<class T>
    530       class ArcMap : public ReadWriteMap<Arc,T>
     529      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
    531530      {
    532531      public:
     
    538537      private:
    539538        ///Copy constructor
    540         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
     539        ArcMap(const ArcMap& em) :
     540          ReferenceMap<Arc, T, T&, const T&>(em) { }
    541541        ///Assignment operator
    542542        template <typename CMap>
     
    547547      };
    548548
    549       /// Read write map of the edges to type \c T.
    550 
    551       /// Reference map of the arcs to type \c T.
    552       /// \sa Reference
     549      /// Reference map of the edges to type \c T.
     550
     551      /// Reference map of the edges to type \c T.
    553552      template<class T>
    554       class EdgeMap : public ReadWriteMap<Edge,T>
     553      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
    555554      {
    556555      public:
     
    562561      private:
    563562        ///Copy constructor
    564         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
     563        EdgeMap(const EdgeMap& em) :
     564          ReferenceMap<Edge, T, T&, const T&>(em) {}
    565565        ///Assignment operator
    566566        template <typename CMap>
     
    602602      /// \brief Opposite node on an arc
    603603      ///
    604       /// \return the opposite of the given Node on the given Edge
     604      /// \return The opposite of the given node on the given edge.
    605605      Node oppositeNode(Node, Edge) const { return INVALID; }
    606606
    607607      /// \brief First node of the edge.
    608608      ///
    609       /// \return the first node of the given Edge.
     609      /// \return The first node of the given edge.
    610610      ///
    611611      /// Naturally edges don't have direction and thus
    612       /// don't have source and target node. But we use these two methods
    613       /// to query the two nodes of the arc. The direction of the arc
    614       /// which arises this way is called the inherent direction of the
     612      /// don't have source and target node. However we use \c u() and \c v()
     613      /// methods to query the two nodes of the arc. The direction of the
     614      /// arc which arises this way is called the inherent direction of the
    615615      /// edge, and is used to define the "default" direction
    616616      /// of the directed versions of the arcs.
    617       /// \sa direction
     617      /// \sa v()
     618      /// \sa direction()
    618619      Node u(Edge) const { return INVALID; }
    619620
    620621      /// \brief Second node of the edge.
     622      ///
     623      /// \return The second node of the given edge.
     624      ///
     625      /// Naturally edges don't have direction and thus
     626      /// don't have source and target node. However we use \c u() and \c v()
     627      /// methods to query the two nodes of the arc. The direction of the
     628      /// arc which arises this way is called the inherent direction of the
     629      /// edge, and is used to define the "default" direction
     630      /// of the directed versions of the arcs.
     631      /// \sa u()
     632      /// \sa direction()
    621633      Node v(Edge) const { return INVALID; }
    622634
     
    737749      struct Constraints {
    738750        void constraints() {
     751          checkConcept<BaseGraphComponent, _Graph>();
    739752          checkConcept<IterableGraphComponent<>, _Graph>();
    740753          checkConcept<IDableGraphComponent<>, _Graph>();
  • lemon/concepts/graph_components.h

    r581 r631  
    2121///\brief The concept of graph components.
    2222
    23 
    2423#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    2524#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     
    3332  namespace concepts {
    3433
    35     /// \brief Skeleton class for graph Node and Arc types
    36     ///
    37     /// This class describes the interface of Node and Arc (and Edge
    38     /// in undirected graphs) subtypes of graph types.
     34    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
     35    ///
     36    /// This class describes the concept of \c Node, \c Arc and \c Edge
     37    /// subtypes of digraph and graph types.
    3938    ///
    4039    /// \note This class is a template class so that we can use it to
    41     /// create graph skeleton classes. The reason for this is than Node
    42     /// and Arc types should \em not derive from the same base class.
    43     /// For Node you should instantiate it with character 'n' and for Arc
    44     /// with 'a'.
    45 
     40    /// create graph skeleton classes. The reason for this is that \c Node
     41    /// and \c Arc (or \c Edge) types should \e not derive from the same
     42    /// base class. For \c Node you should instantiate it with character
     43    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
    4644#ifndef DOXYGEN
    47     template <char _selector = '0'>
     45    template <char sel = '0'>
    4846#endif
    4947    class GraphItem {
     
    5149      /// \brief Default constructor.
    5250      ///
     51      /// Default constructor.
    5352      /// \warning The default constructor is not required to set
    5453      /// the item to some well-defined value. So you should consider it
    5554      /// as uninitialized.
    5655      GraphItem() {}
     56
    5757      /// \brief Copy constructor.
    5858      ///
    5959      /// Copy constructor.
    60       ///
    6160      GraphItem(const GraphItem &) {}
    62       /// \brief Invalid constructor \& conversion.
    63       ///
    64       /// This constructor initializes the item to be invalid.
     61
     62      /// \brief Constructor for conversion from \c INVALID.
     63      ///
     64      /// Constructor for conversion from \c INVALID.
     65      /// It initializes the item to be invalid.
    6566      /// \sa Invalid for more details.
    6667      GraphItem(Invalid) {}
    67       /// \brief Assign operator for nodes.
    68       ///
    69       /// The nodes are assignable.
    70       ///
    71       GraphItem& operator=(GraphItem const&) { return *this; }
     68
     69      /// \brief Assignment operator.
     70      ///
     71      /// Assignment operator for the item.
     72      GraphItem& operator=(const GraphItem&) { return *this; }
     73
    7274      /// \brief Equality operator.
    7375      ///
    74       /// Two iterators are equal if and only if they represents the
    75       /// same node in the graph or both are invalid.
    76       bool operator==(GraphItem) const { return false; }
     76      /// Equality operator.
     77      bool operator==(const GraphItem&) const { return false; }
     78
    7779      /// \brief Inequality operator.
    7880      ///
    79       /// \sa operator==(const Node& n)
    80       ///
    81       bool operator!=(GraphItem) const { return false; }
    82 
    83       /// \brief Artificial ordering operator.
    84       ///
    85       /// To allow the use of graph descriptors as key type in std::map or
    86       /// similar associative container we require this.
     81      /// Inequality operator.
     82      bool operator!=(const GraphItem&) const { return false; }
     83
     84      /// \brief Ordering operator.
     85      ///
     86      /// This operator defines an ordering of the items.
     87      /// It makes possible to use graph item types as key types in
     88      /// associative containers (e.g. \c std::map).
    8789      ///
    8890      /// \note This operator only have to define some strict ordering of
    8991      /// the items; this order has nothing to do with the iteration
    9092      /// ordering of the items.
    91       bool operator<(GraphItem) const { return false; }
     93      bool operator<(const GraphItem&) const { return false; }
    9294
    9395      template<typename _GraphItem>
     
    101103
    102104          bool b;
    103           //          b = (ia == ib) && (ia != ib) && (ia < ib);
    104105          b = (ia == ib) && (ia != ib);
    105106          b = (ia == INVALID) && (ib != INVALID);
     
    112113    };
    113114
    114     /// \brief An empty base directed graph class.
    115     ///
    116     /// This class provides the minimal set of features needed for a
    117     /// directed graph structure. All digraph concepts have to
    118     /// conform to this base directed graph. It just provides types
    119     /// for nodes and arcs and functions to get the source and the
    120     /// target of the arcs.
     115    /// \brief Base skeleton class for directed graphs.
     116    ///
     117    /// This class describes the base interface of directed graph types.
     118    /// All digraph %concepts have to conform to this class.
     119    /// It just provides types for nodes and arcs and functions
     120    /// to get the source and the target nodes of arcs.
    121121    class BaseDigraphComponent {
    122122    public:
     
    126126      /// \brief Node class of the digraph.
    127127      ///
    128       /// This class represents the Nodes of the digraph.
    129       ///
     128      /// This class represents the nodes of the digraph.
    130129      typedef GraphItem<'n'> Node;
    131130
    132131      /// \brief Arc class of the digraph.
    133132      ///
    134       /// This class represents the Arcs of the digraph.
    135       ///
    136       typedef GraphItem<'e'> Arc;
    137 
    138       /// \brief Gives back the target node of an arc.
    139       ///
    140       /// Gives back the target node of an arc.
    141       ///
    142       Node target(const Arc&) const { return INVALID;}
    143 
    144       /// \brief Gives back the source node of an arc.
    145       ///
    146       /// Gives back the source node of an arc.
    147       ///
    148       Node source(const Arc&) const { return INVALID;}
    149 
    150       /// \brief Gives back the opposite node on the given arc.
    151       ///
    152       /// Gives back the opposite node on the given arc.
     133      /// This class represents the arcs of the digraph.
     134      typedef GraphItem<'a'> Arc;
     135
     136      /// \brief Return the source node of an arc.
     137      ///
     138      /// This function returns the source node of an arc.
     139      Node source(const Arc&) const { return INVALID; }
     140
     141      /// \brief Return the target node of an arc.
     142      ///
     143      /// This function returns the target node of an arc.
     144      Node target(const Arc&) const { return INVALID; }
     145
     146      /// \brief Return the opposite node on the given arc.
     147      ///
     148      /// This function returns the opposite node on the given arc.
    153149      Node oppositeNode(const Node&, const Arc&) const {
    154150        return INVALID;
     
    176172    };
    177173
    178     /// \brief An empty base undirected graph class.
    179     ///
    180     /// This class provides the minimal set of features needed for an
    181     /// undirected graph structure. All undirected graph concepts have
    182     /// to conform to this base graph. It just provides types for
    183     /// nodes, arcs and edges and functions to get the
    184     /// source and the target of the arcs and edges,
    185     /// conversion from arcs to edges and function to get
    186     /// both direction of the edges.
     174    /// \brief Base skeleton class for undirected graphs.
     175    ///
     176    /// This class describes the base interface of undirected graph types.
     177    /// All graph %concepts have to conform to this class.
     178    /// It extends the interface of \ref BaseDigraphComponent with an
     179    /// \c Edge type and functions to get the end nodes of edges,
     180    /// to convert from arcs to edges and to get both direction of edges.
    187181    class BaseGraphComponent : public BaseDigraphComponent {
    188182    public:
    189183      typedef BaseDigraphComponent::Node Node;
    190184      typedef BaseDigraphComponent::Arc Arc;
    191       /// \brief Undirected arc class of the graph.
    192       ///
    193       /// This class represents the edges of the graph.
    194       /// The undirected graphs can be used as a directed graph which
    195       /// for each arc contains the opposite arc too so the graph is
    196       /// bidirected. The edge represents two opposite
    197       /// directed arcs.
    198       class Edge : public GraphItem<'u'> {
     185
     186      /// \brief Undirected edge class of the graph.
     187      ///
     188      /// This class represents the undirected edges of the graph.
     189      /// Undirected graphs can be used as directed graphs, each edge is
     190      /// represented by two opposite directed arcs.
     191      class Edge : public GraphItem<'e'> {
    199192      public:
    200         typedef GraphItem<'u'> Parent;
     193        typedef GraphItem<'e'> Parent;
     194
    201195        /// \brief Default constructor.
    202196        ///
     197        /// Default constructor.
    203198        /// \warning The default constructor is not required to set
    204199        /// the item to some well-defined value. So you should consider it
    205200        /// as uninitialized.
    206201        Edge() {}
     202
    207203        /// \brief Copy constructor.
    208204        ///
    209205        /// Copy constructor.
    210         ///
    211206        Edge(const Edge &) : Parent() {}
    212         /// \brief Invalid constructor \& conversion.
    213         ///
    214         /// This constructor initializes the item to be invalid.
     207
     208        /// \brief Constructor for conversion from \c INVALID.
     209        ///
     210        /// Constructor for conversion from \c INVALID.
     211        /// It initializes the item to be invalid.
    215212        /// \sa Invalid for more details.
    216213        Edge(Invalid) {}
    217         /// \brief Converter from arc to edge.
    218         ///
     214
     215        /// \brief Constructor for conversion from an arc.
     216        ///
     217        /// Constructor for conversion from an arc.
    219218        /// Besides the core graph item functionality each arc should
    220219        /// be convertible to the represented edge.
    221220        Edge(const Arc&) {}
    222         /// \brief Assign arc to edge.
    223         ///
     221
     222        /// \brief Assign an arc to an edge.
     223        ///
     224        /// This function assigns an arc to an edge.
    224225        /// Besides the core graph item functionality each arc should
    225226        /// be convertible to the represented edge.
     
    227228      };
    228229
    229       /// \brief Returns the direction of the arc.
     230      /// \brief Return one end node of an edge.
     231      ///
     232      /// This function returns one end node of an edge.
     233      Node u(const Edge&) const { return INVALID; }
     234
     235      /// \brief Return the other end node of an edge.
     236      ///
     237      /// This function returns the other end node of an edge.
     238      Node v(const Edge&) const { return INVALID; }
     239
     240      /// \brief Return a directed arc related to an edge.
     241      ///
     242      /// This function returns a directed arc from its direction and the
     243      /// represented edge.
     244      Arc direct(const Edge&, bool) const { return INVALID; }
     245
     246      /// \brief Return a directed arc related to an edge.
     247      ///
     248      /// This function returns a directed arc from its source node and the
     249      /// represented edge.
     250      Arc direct(const Edge&, const Node&) const { return INVALID; }
     251
     252      /// \brief Return the direction of the arc.
    230253      ///
    231254      /// Returns the direction of the arc. Each arc represents an
     
    234257      bool direction(const Arc&) const { return true; }
    235258
    236       /// \brief Returns the directed arc.
    237       ///
    238       /// Returns the directed arc from its direction and the
    239       /// represented edge.
    240       Arc direct(const Edge&, bool) const { return INVALID;}
    241 
    242       /// \brief Returns the directed arc.
    243       ///
    244       /// Returns the directed arc from its source and the
    245       /// represented edge.
    246       Arc direct(const Edge&, const Node&) const { return INVALID;}
    247 
    248       /// \brief Returns the opposite arc.
    249       ///
    250       /// Returns the opposite arc. It is the arc representing the
    251       /// same edge and has opposite direction.
    252       Arc oppositeArc(const Arc&) const { return INVALID;}
    253 
    254       /// \brief Gives back one ending of an edge.
    255       ///
    256       /// Gives back one ending of an edge.
    257       Node u(const Edge&) const { return INVALID;}
    258 
    259       /// \brief Gives back the other ending of an edge.
    260       ///
    261       /// Gives back the other ending of an edge.
    262       Node v(const Edge&) const { return INVALID;}
     259      /// \brief Return the opposite arc.
     260      ///
     261      /// This function returns the opposite arc, i.e. the arc representing
     262      /// the same edge and has opposite direction.
     263      Arc oppositeArc(const Arc&) const { return INVALID; }
    263264
    264265      template <typename _Graph>
     
    270271        void constraints() {
    271272          checkConcept<BaseDigraphComponent, _Graph>();
    272           checkConcept<GraphItem<'u'>, Edge>();
     273          checkConcept<GraphItem<'e'>, Edge>();
    273274          {
    274275            Node n;
     
    278279            n = graph.v(ue);
    279280            e = graph.direct(ue, true);
     281            e = graph.direct(ue, false);
    280282            e = graph.direct(ue, n);
    281283            e = graph.oppositeArc(e);
     
    291293    };
    292294
    293     /// \brief An empty idable base digraph class.
    294     ///
    295     /// This class provides beside the core digraph features
    296     /// core id functions for the digraph structure.
    297     /// The most of the base digraphs should conform to this concept.
    298     /// The id's are unique and immutable.
    299     template <typename _Base = BaseDigraphComponent>
    300     class IDableDigraphComponent : public _Base {
    301     public:
    302 
    303       typedef _Base Base;
     295    /// \brief Skeleton class for \e idable directed graphs.
     296    ///
     297    /// This class describes the interface of \e idable directed graphs.
     298    /// It extends \ref BaseDigraphComponent with the core ID functions.
     299    /// The ids of the items must be unique and immutable.
     300    /// This concept is part of the Digraph concept.
     301    template <typename BAS = BaseDigraphComponent>
     302    class IDableDigraphComponent : public BAS {
     303    public:
     304
     305      typedef BAS Base;
    304306      typedef typename Base::Node Node;
    305307      typedef typename Base::Arc Arc;
    306308
    307       /// \brief Gives back an unique integer id for the Node.
    308       ///
    309       /// Gives back an unique integer id for the Node.
    310       ///
    311       int id(const Node&) const { return -1;}
    312 
    313       /// \brief Gives back the node by the unique id.
    314       ///
    315       /// Gives back the node by the unique id.
    316       /// If the digraph does not contain node with the given id
    317       /// then the result of the function is undetermined.
    318       Node nodeFromId(int) const { return INVALID;}
    319 
    320       /// \brief Gives back an unique integer id for the Arc.
    321       ///
    322       /// Gives back an unique integer id for the Arc.
    323       ///
    324       int id(const Arc&) const { return -1;}
    325 
    326       /// \brief Gives back the arc by the unique id.
    327       ///
    328       /// Gives back the arc by the unique id.
    329       /// If the digraph does not contain arc with the given id
    330       /// then the result of the function is undetermined.
    331       Arc arcFromId(int) const { return INVALID;}
    332 
    333       /// \brief Gives back an integer greater or equal to the maximum
    334       /// Node id.
    335       ///
    336       /// Gives back an integer greater or equal to the maximum Node
    337       /// id.
    338       int maxNodeId() const { return -1;}
    339 
    340       /// \brief Gives back an integer greater or equal to the maximum
    341       /// Arc id.
    342       ///
    343       /// Gives back an integer greater or equal to the maximum Arc
    344       /// id.
    345       int maxArcId() const { return -1;}
     309      /// \brief Return a unique integer id for the given node.
     310      ///
     311      /// This function returns a unique integer id for the given node.
     312      int id(const Node&) const { return -1; }
     313
     314      /// \brief Return the node by its unique id.
     315      ///
     316      /// This function returns the node by its unique id.
     317      /// If the digraph does not contain a node with the given id,
     318      /// then the result of the function is undefined.
     319      Node nodeFromId(int) const { return INVALID; }
     320
     321      /// \brief Return a unique integer id for the given arc.
     322      ///
     323      /// This function returns a unique integer id for the given arc.
     324      int id(const Arc&) const { return -1; }
     325
     326      /// \brief Return the arc by its unique id.
     327      ///
     328      /// This function returns the arc by its unique id.
     329      /// If the digraph does not contain an arc with the given id,
     330      /// then the result of the function is undefined.
     331      Arc arcFromId(int) const { return INVALID; }
     332
     333      /// \brief Return an integer greater or equal to the maximum
     334      /// node id.
     335      ///
     336      /// This function returns an integer greater or equal to the
     337      /// maximum node id.
     338      int maxNodeId() const { return -1; }
     339
     340      /// \brief Return an integer greater or equal to the maximum
     341      /// arc id.
     342      ///
     343      /// This function returns an integer greater or equal to the
     344      /// maximum arc id.
     345      int maxArcId() const { return -1; }
    346346
    347347      template <typename _Digraph>
     
    369369    };
    370370
    371     /// \brief An empty idable base undirected graph class.
    372     ///
    373     /// This class provides beside the core undirected graph features
    374     /// core id functions for the undirected graph structure.  The
    375     /// most of the base undirected graphs should conform to this
    376     /// concept.  The id's are unique and immutable.
    377     template <typename _Base = BaseGraphComponent>
    378     class IDableGraphComponent : public IDableDigraphComponent<_Base> {
    379     public:
    380 
    381       typedef _Base Base;
     371    /// \brief Skeleton class for \e idable undirected graphs.
     372    ///
     373    /// This class describes the interface of \e idable undirected
     374    /// graphs. It extends \ref IDableDigraphComponent with the core ID
     375    /// functions of undirected graphs.
     376    /// The ids of the items must be unique and immutable.
     377    /// This concept is part of the Graph concept.
     378    template <typename BAS = BaseGraphComponent>
     379    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
     380    public:
     381
     382      typedef BAS Base;
    382383      typedef typename Base::Edge Edge;
    383384
    384       using IDableDigraphComponent<_Base>::id;
    385 
    386       /// \brief Gives back an unique integer id for the Edge.
    387       ///
    388       /// Gives back an unique integer id for the Edge.
    389       ///
    390       int id(const Edge&) const { return -1;}
    391 
    392       /// \brief Gives back the edge by the unique id.
    393       ///
    394       /// Gives back the edge by the unique id.  If the
    395       /// graph does not contain arc with the given id then the
    396       /// result of the function is undetermined.
    397       Edge edgeFromId(int) const { return INVALID;}
    398 
    399       /// \brief Gives back an integer greater or equal to the maximum
    400       /// Edge id.
    401       ///
    402       /// Gives back an integer greater or equal to the maximum Edge
    403       /// id.
    404       int maxEdgeId() const { return -1;}
     385      using IDableDigraphComponent<Base>::id;
     386
     387      /// \brief Return a unique integer id for the given edge.
     388      ///
     389      /// This function returns a unique integer id for the given edge.
     390      int id(const Edge&) const { return -1; }
     391
     392      /// \brief Return the edge by its unique id.
     393      ///
     394      /// This function returns the edge by its unique id.
     395      /// If the graph does not contain an edge with the given id,
     396      /// then the result of the function is undefined.
     397      Edge edgeFromId(int) const { return INVALID; }
     398
     399      /// \brief Return an integer greater or equal to the maximum
     400      /// edge id.
     401      ///
     402      /// This function returns an integer greater or equal to the
     403      /// maximum edge id.
     404      int maxEdgeId() const { return -1; }
    405405
    406406      template <typename _Graph>
     
    408408
    409409        void constraints() {
    410           checkConcept<Base, _Graph >();
    411410          checkConcept<IDableDigraphComponent<Base>, _Graph >();
    412411          typename _Graph::Edge edge;
     
    422421    };
    423422
    424     /// \brief Skeleton class for graph NodeIt and ArcIt
    425     ///
    426     /// Skeleton class for graph NodeIt and ArcIt.
    427     ///
    428     template <typename _Graph, typename _Item>
    429     class GraphItemIt : public _Item {
     423    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
     424    ///
     425    /// This class describes the concept of \c NodeIt, \c ArcIt and
     426    /// \c EdgeIt subtypes of digraph and graph types.
     427    template <typename GR, typename Item>
     428    class GraphItemIt : public Item {
    430429    public:
    431430      /// \brief Default constructor.
    432431      ///
    433       /// @warning The default constructor sets the iterator
    434       /// to an undefined value.
     432      /// Default constructor.
     433      /// \warning The default constructor is not required to set
     434      /// the iterator to some well-defined value. So you should consider it
     435      /// as uninitialized.
    435436      GraphItemIt() {}
     437
    436438      /// \brief Copy constructor.
    437439      ///
    438440      /// Copy constructor.
    439       ///
    440       GraphItemIt(const GraphItemIt& ) {}
    441       /// \brief Sets the iterator to the first item.
    442       ///
    443       /// Sets the iterator to the first item of \c the graph.
    444       ///
    445       explicit GraphItemIt(const _Graph&) {}
    446       /// \brief Invalid constructor \& conversion.
    447       ///
    448       /// This constructor initializes the item to be invalid.
     441      GraphItemIt(const GraphItemIt& it) : Item(it) {}
     442
     443      /// \brief Constructor that sets the iterator to the first item.
     444      ///
     445      /// Constructor that sets the iterator to the first item.
     446      explicit GraphItemIt(const GR&) {}
     447
     448      /// \brief Constructor for conversion from \c INVALID.
     449      ///
     450      /// Constructor for conversion from \c INVALID.
     451      /// It initializes the iterator to be invalid.
    449452      /// \sa Invalid for more details.
    450453      GraphItemIt(Invalid) {}
    451       /// \brief Assign operator for items.
    452       ///
    453       /// The items are assignable.
    454       ///
     454
     455      /// \brief Assignment operator.
     456      ///
     457      /// Assignment operator for the iterator.
    455458      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
    456       /// \brief Next item.
    457       ///
    458       /// Assign the iterator to the next item.
    459       ///
     459
     460      /// \brief Increment the iterator.
     461      ///
     462      /// This operator increments the iterator, i.e. assigns it to the
     463      /// next item.
    460464      GraphItemIt& operator++() { return *this; }
     465 
    461466      /// \brief Equality operator
    462467      ///
     468      /// Equality operator.
    463469      /// Two iterators are equal if and only if they point to the
    464470      /// same object or both are invalid.
    465471      bool operator==(const GraphItemIt&) const { return true;}
     472
    466473      /// \brief Inequality operator
    467474      ///
    468       /// \sa operator==(Node n)
    469       ///
     475      /// Inequality operator.
     476      /// Two iterators are equal if and only if they point to the
     477      /// same object or both are invalid.
    470478      bool operator!=(const GraphItemIt&) const { return true;}
    471479
     
    473481      struct Constraints {
    474482        void constraints() {
     483          checkConcept<GraphItem<>, _GraphItemIt>();
    475484          _GraphItemIt it1(g);
    476485          _GraphItemIt it2;
     486          _GraphItemIt it3 = it1;
     487          _GraphItemIt it4 = INVALID;
    477488
    478489          it2 = ++it1;
     
    480491          ++(++it1);
    481492
    482           _Item bi = it1;
     493          Item bi = it1;
    483494          bi = it2;
    484495        }
    485         _Graph& g;
    486       };
    487     };
    488 
    489     /// \brief Skeleton class for graph InArcIt and OutArcIt
    490     ///
    491     /// \note Because InArcIt and OutArcIt may not inherit from the same
    492     /// base class, the _selector is a additional template parameter. For
    493     /// InArcIt you should instantiate it with character 'i' and for
    494     /// OutArcIt with 'o'.
    495     template <typename _Graph,
    496               typename _Item = typename _Graph::Arc,
    497               typename _Base = typename _Graph::Node,
    498               char _selector = '0'>
    499     class GraphIncIt : public _Item {
     496        const GR& g;
     497      };
     498    };
     499
     500    /// \brief Concept class for \c InArcIt, \c OutArcIt and
     501    /// \c IncEdgeIt types.
     502    ///
     503    /// This class describes the concept of \c InArcIt, \c OutArcIt
     504    /// and \c IncEdgeIt subtypes of digraph and graph types.
     505    ///
     506    /// \note Since these iterator classes do not inherit from the same
     507    /// base class, there is an additional template parameter (selector)
     508    /// \c sel. For \c InArcIt you should instantiate it with character
     509    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
     510    template <typename GR,
     511              typename Item = typename GR::Arc,
     512              typename Base = typename GR::Node,
     513              char sel = '0'>
     514    class GraphIncIt : public Item {
    500515    public:
    501516      /// \brief Default constructor.
    502517      ///
    503       /// @warning The default constructor sets the iterator
    504       /// to an undefined value.
     518      /// Default constructor.
     519      /// \warning The default constructor is not required to set
     520      /// the iterator to some well-defined value. So you should consider it
     521      /// as uninitialized.
    505522      GraphIncIt() {}
     523
    506524      /// \brief Copy constructor.
    507525      ///
    508526      /// Copy constructor.
    509       ///
    510       GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
    511       /// \brief Sets the iterator to the first arc incoming into or outgoing
    512       /// from the node.
    513       ///
    514       /// Sets the iterator to the first arc incoming into or outgoing
    515       /// from the node.
    516       ///
    517       explicit GraphIncIt(const _Graph&, const _Base&) {}
    518       /// \brief Invalid constructor \& conversion.
    519       ///
    520       /// This constructor initializes the item to be invalid.
     527      GraphIncIt(const GraphIncIt& it) : Item(it) {}
     528
     529      /// \brief Constructor that sets the iterator to the first
     530      /// incoming or outgoing arc.
     531      ///
     532      /// Constructor that sets the iterator to the first arc
     533      /// incoming to or outgoing from the given node.
     534      explicit GraphIncIt(const GR&, const Base&) {}
     535
     536      /// \brief Constructor for conversion from \c INVALID.
     537      ///
     538      /// Constructor for conversion from \c INVALID.
     539      /// It initializes the iterator to be invalid.
    521540      /// \sa Invalid for more details.
    522541      GraphIncIt(Invalid) {}
    523       /// \brief Assign operator for iterators.
    524       ///
    525       /// The iterators are assignable.
    526       ///
    527       GraphIncIt& operator=(GraphIncIt const&) { return *this; }
    528       /// \brief Next item.
    529       ///
    530       /// Assign the iterator to the next item.
    531       ///
     542
     543      /// \brief Assignment operator.
     544      ///
     545      /// Assignment operator for the iterator.
     546      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
     547
     548      /// \brief Increment the iterator.
     549      ///
     550      /// This operator increments the iterator, i.e. assigns it to the
     551      /// next arc incoming to or outgoing from the given node.
    532552      GraphIncIt& operator++() { return *this; }
    533553
    534554      /// \brief Equality operator
    535555      ///
     556      /// Equality operator.
    536557      /// Two iterators are equal if and only if they point to the
    537558      /// same object or both are invalid.
     
    540561      /// \brief Inequality operator
    541562      ///
    542       /// \sa operator==(Node n)
    543       ///
     563      /// Inequality operator.
     564      /// Two iterators are equal if and only if they point to the
     565      /// same object or both are invalid.
    544566      bool operator!=(const GraphIncIt&) const { return true;}
    545567
     
    547569      struct Constraints {
    548570        void constraints() {
    549           checkConcept<GraphItem<_selector>, _GraphIncIt>();
     571          checkConcept<GraphItem<sel>, _GraphIncIt>();
    550572          _GraphIncIt it1(graph, node);
    551573          _GraphIncIt it2;
     574          _GraphIncIt it3 = it1;
     575          _GraphIncIt it4 = INVALID;
    552576
    553577          it2 = ++it1;
    554578          ++it2 = it1;
    555579          ++(++it1);
    556           _Item e = it1;
     580          Item e = it1;
    557581          e = it2;
    558 
    559         }
    560 
    561         _Item arc;
    562         _Base node;
    563         _Graph graph;
    564         _GraphIncIt it;
    565       };
    566     };
    567 
    568 
    569     /// \brief An empty iterable digraph class.
    570     ///
    571     /// This class provides beside the core digraph features
    572     /// iterator based iterable interface for the digraph structure.
     582        }
     583        const Base& node;
     584        const GR& graph;
     585      };
     586    };
     587
     588    /// \brief Skeleton class for iterable directed graphs.
     589    ///
     590    /// This class describes the interface of iterable directed
     591    /// graphs. It extends \ref BaseDigraphComponent with the core
     592    /// iterable interface.
    573593    /// This concept is part of the Digraph concept.
    574     template <typename _Base = BaseDigraphComponent>
    575     class IterableDigraphComponent : public _Base {
    576 
    577     public:
    578 
    579       typedef _Base Base;
     594    template <typename BAS = BaseDigraphComponent>
     595    class IterableDigraphComponent : public BAS {
     596
     597    public:
     598
     599      typedef BAS Base;
    580600      typedef typename Base::Node Node;
    581601      typedef typename Base::Arc Arc;
     
    583603      typedef IterableDigraphComponent Digraph;
    584604
    585       /// \name Base iteration
    586       ///
    587       /// This interface provides functions for iteration on digraph items
     605      /// \name Base Iteration
     606      ///
     607      /// This interface provides functions for iteration on digraph items.
    588608      ///
    589609      /// @{
    590610
    591       /// \brief Gives back the first node in the iterating order.
    592       ///
    593       /// Gives back the first node in the iterating order.
    594       ///
     611      /// \brief Return the first node.
     612      ///
     613      /// This function gives back the first node in the iteration order.
    595614      void first(Node&) const {}
    596615
    597       /// \brief Gives back the next node in the iterating order.
    598       ///
    599       /// Gives back the next node in the iterating order.
    600       ///
     616      /// \brief Return the next node.
     617      ///
     618      /// This function gives back the next node in the iteration order.
    601619      void next(Node&) const {}
    602620
    603       /// \brief Gives back the first arc in the iterating order.
    604       ///
    605       /// Gives back the first arc in the iterating order.
    606       ///
     621      /// \brief Return the first arc.
     622      ///
     623      /// This function gives back the first arc in the iteration order.
    607624      void first(Arc&) const {}
    608625
    609       /// \brief Gives back the next arc in the iterating order.
    610       ///
    611       /// Gives back the next arc in the iterating order.
    612       ///
     626      /// \brief Return the next arc.
     627      ///
     628      /// This function gives back the next arc in the iteration order.
    613629      void next(Arc&) const {}
    614630
    615 
    616       /// \brief Gives back the first of the arcs point to the given
    617       /// node.
    618       ///
    619       /// Gives back the first of the arcs point to the given node.
    620       ///
     631      /// \brief Return the first arc incomming to the given node.
     632      ///
     633      /// This function gives back the first arc incomming to the
     634      /// given node.
    621635      void firstIn(Arc&, const Node&) const {}
    622636
    623       /// \brief Gives back the next of the arcs points to the given
    624       /// node.
    625       ///
    626       /// Gives back the next of the arcs points to the given node.
    627       ///
     637      /// \brief Return the next arc incomming to the given node.
     638      ///
     639      /// This function gives back the next arc incomming to the
     640      /// given node.
    628641      void nextIn(Arc&) const {}
    629642
    630       /// \brief Gives back the first of the arcs start from the
     643      /// \brief Return the first arc outgoing form the given node.
     644      ///
     645      /// This function gives back the first arc outgoing form the
    631646      /// given node.
    632       ///
    633       /// Gives back the first of the arcs start from the given node.
    634       ///
    635647      void firstOut(Arc&, const Node&) const {}
    636648
    637       /// \brief Gives back the next of the arcs start from the given
    638       /// node.
    639       ///
    640       /// Gives back the next of the arcs start from the given node.
    641       ///
     649      /// \brief Return the next arc outgoing form the given node.
     650      ///
     651      /// This function gives back the next arc outgoing form the
     652      /// given node.
    642653      void nextOut(Arc&) const {}
    643654
    644655      /// @}
    645656
    646       /// \name Class based iteration
    647       ///
    648       /// This interface provides functions for iteration on digraph items
     657      /// \name Class Based Iteration
     658      ///
     659      /// This interface provides iterator classes for digraph items.
    649660      ///
    650661      /// @{
     
    656667      typedef GraphItemIt<Digraph, Node> NodeIt;
    657668
    658       /// \brief This iterator goes through each node.
    659       ///
    660       /// This iterator goes through each node.
     669      /// \brief This iterator goes through each arc.
     670      ///
     671      /// This iterator goes through each arc.
    661672      ///
    662673      typedef GraphItemIt<Digraph, Arc> ArcIt;
     
    664675      /// \brief This iterator goes trough the incoming arcs of a node.
    665676      ///
    666       /// This iterator goes trough the \e inccoming arcs of a certain node
     677      /// This iterator goes trough the \e incoming arcs of a certain node
    667678      /// of a digraph.
    668679      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
     
    676687      /// \brief The base node of the iterator.
    677688      ///
    678       /// Gives back the base node of the iterator.
    679       /// It is always the target of the pointed arc.
     689      /// This function gives back the base node of the iterator.
     690      /// It is always the target node of the pointed arc.
    680691      Node baseNode(const InArcIt&) const { return INVALID; }
    681692
    682693      /// \brief The running node of the iterator.
    683694      ///
    684       /// Gives back the running node of the iterator.
    685       /// It is always the source of the pointed arc.
     695      /// This function gives back the running node of the iterator.
     696      /// It is always the source node of the pointed arc.
    686697      Node runningNode(const InArcIt&) const { return INVALID; }
    687698
    688699      /// \brief The base node of the iterator.
    689700      ///
    690       /// Gives back the base node of the iterator.
    691       /// It is always the source of the pointed arc.
     701      /// This function gives back the base node of the iterator.
     702      /// It is always the source node of the pointed arc.
    692703      Node baseNode(const OutArcIt&) const { return INVALID; }
    693704
    694705      /// \brief The running node of the iterator.
    695706      ///
    696       /// Gives back the running node of the iterator.
    697       /// It is always the target of the pointed arc.
     707      /// This function gives back the running node of the iterator.
     708      /// It is always the target node of the pointed arc.
    698709      Node runningNode(const OutArcIt&) const { return INVALID; }
    699710
     
    737748
    738749            typename _Digraph::Node n;
    739             typename _Digraph::InArcIt ieit(INVALID);
    740             typename _Digraph::OutArcIt oeit(INVALID);
    741             n = digraph.baseNode(ieit);
    742             n = digraph.runningNode(ieit);
    743             n = digraph.baseNode(oeit);
    744             n = digraph.runningNode(oeit);
     750            const typename _Digraph::InArcIt iait(INVALID);
     751            const typename _Digraph::OutArcIt oait(INVALID);
     752            n = digraph.baseNode(iait);
     753            n = digraph.runningNode(iait);
     754            n = digraph.baseNode(oait);
     755            n = digraph.runningNode(oait);
    745756            ignore_unused_variable_warning(n);
    746757          }
     
    748759
    749760        const _Digraph& digraph;
    750 
    751       };
    752     };
    753 
    754     /// \brief An empty iterable undirected graph class.
    755     ///
    756     /// This class provides beside the core graph features iterator
    757     /// based iterable interface for the undirected graph structure.
     761      };
     762    };
     763
     764    /// \brief Skeleton class for iterable undirected graphs.
     765    ///
     766    /// This class describes the interface of iterable undirected
     767    /// graphs. It extends \ref IterableDigraphComponent with the core
     768    /// iterable interface of undirected graphs.
    758769    /// This concept is part of the Graph concept.
    759     template <typename _Base = BaseGraphComponent>
    760     class IterableGraphComponent : public IterableDigraphComponent<_Base> {
    761     public:
    762 
    763       typedef _Base Base;
     770    template <typename BAS = BaseGraphComponent>
     771    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
     772    public:
     773
     774      typedef BAS Base;
    764775      typedef typename Base::Node Node;
    765776      typedef typename Base::Arc Arc;
     
    769780      typedef IterableGraphComponent Graph;
    770781
    771       /// \name Base iteration
    772       ///
    773       /// This interface provides functions for iteration on graph items
     782      /// \name Base Iteration
     783      ///
     784      /// This interface provides functions for iteration on edges.
     785      ///
    774786      /// @{
    775787
    776       using IterableDigraphComponent<_Base>::first;
    777       using IterableDigraphComponent<_Base>::next;
    778 
    779       /// \brief Gives back the first edge in the iterating
    780       /// order.
    781       ///
    782       /// Gives back the first edge in the iterating order.
    783       ///
     788      using IterableDigraphComponent<Base>::first;
     789      using IterableDigraphComponent<Base>::next;
     790
     791      /// \brief Return the first edge.
     792      ///
     793      /// This function gives back the first edge in the iteration order.
    784794      void first(Edge&) const {}
    785795
    786       /// \brief Gives back the next edge in the iterating
    787       /// order.
    788       ///
    789       /// Gives back the next edge in the iterating order.
    790       ///
     796      /// \brief Return the next edge.
     797      ///
     798      /// This function gives back the next edge in the iteration order.
    791799      void next(Edge&) const {}
    792800
    793 
    794       /// \brief Gives back the first of the edges from the
     801      /// \brief Return the first edge incident to the given node.
     802      ///
     803      /// This function gives back the first edge incident to the given
     804      /// node. The bool parameter gives back the direction for which the
     805      /// source node of the directed arc representing the edge is the
    795806      /// given node.
    796       ///
    797       /// Gives back the first of the edges from the given
    798       /// node. The bool parameter gives back that direction which
    799       /// gives a good direction of the edge so the source of the
    800       /// directed arc is the given node.
    801807      void firstInc(Edge&, bool&, const Node&) const {}
    802808
     
    804810      /// given node.
    805811      ///
    806       /// Gives back the next of the edges from the given
    807       /// node. The bool parameter should be used as the \c firstInc()
    808       /// use it.
     812      /// This function gives back the next edge incident to the given
     813      /// node. The bool parameter should be used as \c firstInc() use it.
    809814      void nextInc(Edge&, bool&) const {}
    810815
    811       using IterableDigraphComponent<_Base>::baseNode;
    812       using IterableDigraphComponent<_Base>::runningNode;
     816      using IterableDigraphComponent<Base>::baseNode;
     817      using IterableDigraphComponent<Base>::runningNode;
    813818
    814819      /// @}
    815820
    816       /// \name Class based iteration
    817       ///
    818       /// This interface provides functions for iteration on graph items
     821      /// \name Class Based Iteration
     822      ///
     823      /// This interface provides iterator classes for edges.
    819824      ///
    820825      /// @{
    821826
    822       /// \brief This iterator goes through each node.
    823       ///
    824       /// This iterator goes through each node.
     827      /// \brief This iterator goes through each edge.
     828      ///
     829      /// This iterator goes through each edge.
    825830      typedef GraphItemIt<Graph, Edge> EdgeIt;
    826       /// \brief This iterator goes trough the incident arcs of a
     831
     832      /// \brief This iterator goes trough the incident edges of a
    827833      /// node.
    828834      ///
    829       /// This iterator goes trough the incident arcs of a certain
     835      /// This iterator goes trough the incident edges of a certain
    830836      /// node of a graph.
    831       typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt;
     837      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
     838
    832839      /// \brief The base node of the iterator.
    833840      ///
    834       /// Gives back the base node of the iterator.
     841      /// This function gives back the base node of the iterator.
    835842      Node baseNode(const IncEdgeIt&) const { return INVALID; }
    836843
    837844      /// \brief The running node of the iterator.
    838845      ///
    839       /// Gives back the running node of the iterator.
     846      /// This function gives back the running node of the iterator.
    840847      Node runningNode(const IncEdgeIt&) const { return INVALID; }
    841848
     
    866873              typename _Graph::EdgeIt >();
    867874            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
    868               typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
     875              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
    869876
    870877            typename _Graph::Node n;
    871             typename _Graph::IncEdgeIt ueit(INVALID);
    872             n = graph.baseNode(ueit);
    873             n = graph.runningNode(ueit);
     878            const typename _Graph::IncEdgeIt ieit(INVALID);
     879            n = graph.baseNode(ieit);
     880            n = graph.runningNode(ieit);
    874881          }
    875882        }
    876883
    877884        const _Graph& graph;
    878 
    879       };
    880     };
    881 
    882     /// \brief An empty alteration notifier digraph class.
    883     ///
    884     /// This class provides beside the core digraph features alteration
    885     /// notifier interface for the digraph structure.  This implements
     885      };
     886    };
     887
     888    /// \brief Skeleton class for alterable directed graphs.
     889    ///
     890    /// This class describes the interface of alterable directed
     891    /// graphs. It extends \ref BaseDigraphComponent with the alteration
     892    /// notifier interface. It implements
    886893    /// an observer-notifier pattern for each digraph item. More
    887894    /// obsevers can be registered into the notifier and whenever an
    888     /// alteration occured in the digraph all the observers will
     895    /// alteration occured in the digraph all the observers will be
    889896    /// notified about it.
    890     template <typename _Base = BaseDigraphComponent>
    891     class AlterableDigraphComponent : public _Base {
    892     public:
    893 
    894       typedef _Base Base;
     897    template <typename BAS = BaseDigraphComponent>
     898    class AlterableDigraphComponent : public BAS {
     899    public:
     900
     901      typedef BAS Base;
    895902      typedef typename Base::Node Node;
    896903      typedef typename Base::Arc Arc;
    897904
    898905
    899       /// The node observer registry.
     906      /// Node alteration notifier class.
    900907      typedef AlterationNotifier<AlterableDigraphComponent, Node>
    901908      NodeNotifier;
    902       /// The arc observer registry.
     909      /// Arc alteration notifier class.
    903910      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
    904911      ArcNotifier;
    905912
    906       /// \brief Gives back the node alteration notifier.
    907       ///
    908       /// Gives back the node alteration notifier.
     913      /// \brief Return the node alteration notifier.
     914      ///
     915      /// This function gives back the node alteration notifier.
    909916      NodeNotifier& notifier(Node) const {
    910         return NodeNotifier();
     917         return NodeNotifier();
    911918      }
    912919
    913       /// \brief Gives back the arc alteration notifier.
    914       ///
    915       /// Gives back the arc alteration notifier.
     920      /// \brief Return the arc alteration notifier.
     921      ///
     922      /// This function gives back the arc alteration notifier.
    916923      ArcNotifier& notifier(Arc) const {
    917924        return ArcNotifier();
     
    933940
    934941        const _Digraph& digraph;
    935 
    936       };
    937 
    938     };
    939 
    940     /// \brief An empty alteration notifier undirected graph class.
    941     ///
    942     /// This class provides beside the core graph features alteration
    943     /// notifier interface for the graph structure.  This implements
    944     /// an observer-notifier pattern for each graph item. More
     942      };
     943    };
     944
     945    /// \brief Skeleton class for alterable undirected graphs.
     946    ///
     947    /// This class describes the interface of alterable undirected
     948    /// graphs. It extends \ref AlterableDigraphComponent with the alteration
     949    /// notifier interface of undirected graphs. It implements
     950    /// an observer-notifier pattern for the edges. More
    945951    /// obsevers can be registered into the notifier and whenever an
    946     /// alteration occured in the graph all the observers will
     952    /// alteration occured in the graph all the observers will be
    947953    /// notified about it.
    948     template <typename _Base = BaseGraphComponent>
    949     class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
    950     public:
    951 
    952       typedef _Base Base;
     954    template <typename BAS = BaseGraphComponent>
     955    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
     956    public:
     957
     958      typedef BAS Base;
    953959      typedef typename Base::Edge Edge;
    954960
    955961
    956       /// The arc observer registry.
     962      /// Edge alteration notifier class.
    957963      typedef AlterationNotifier<AlterableGraphComponent, Edge>
    958964      EdgeNotifier;
    959965
    960       /// \brief Gives back the arc alteration notifier.
    961       ///
    962       /// Gives back the arc alteration notifier.
     966      /// \brief Return the edge alteration notifier.
     967      ///
     968      /// This function gives back the edge alteration notifier.
    963969      EdgeNotifier& notifier(Edge) const {
    964970        return EdgeNotifier();
     
    968974      struct Constraints {
    969975        void constraints() {
    970           checkConcept<AlterableGraphComponent<Base>, _Graph>();
     976          checkConcept<AlterableDigraphComponent<Base>, _Graph>();
    971977          typename _Graph::EdgeNotifier& uen
    972978            = graph.notifier(typename _Graph::Edge());
     
    975981
    976982        const _Graph& graph;
    977 
    978       };
    979 
    980     };
    981 
    982     /// \brief Class describing the concept of graph maps
    983     ///
    984     /// This class describes the common interface of the graph maps
    985     /// (NodeMap, ArcMap), that is maps that can be used to
    986     /// associate data to graph descriptors (nodes or arcs).
    987     template <typename _Graph, typename _Item, typename _Value>
    988     class GraphMap : public ReadWriteMap<_Item, _Value> {
    989     public:
    990 
    991       typedef ReadWriteMap<_Item, _Value> Parent;
     983      };
     984    };
     985
     986    /// \brief Concept class for standard graph maps.
     987    ///
     988    /// This class describes the concept of standard graph maps, i.e.
     989    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
     990    /// graph types, which can be used for associating data to graph items.
     991    /// The standard graph maps must conform to the ReferenceMap concept.
     992    template <typename GR, typename K, typename V>
     993    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
     994    public:
     995
     996      typedef ReadWriteMap<K, V> Parent;
    992997
    993998      /// The graph type of the map.
    994       typedef _Graph Graph;
     999      typedef GR Graph;
    9951000      /// The key type of the map.
    996       typedef _Item Key;
     1001      typedef K Key;
    9971002      /// The value type of the map.
    998       typedef _Value Value;
     1003      typedef V Value;
     1004      /// The reference type of the map.
     1005      typedef Value& Reference;
     1006      /// The const reference type of the map.
     1007      typedef const Value& ConstReference;
     1008
     1009      // The reference map tag.
     1010      typedef True ReferenceMapTag;
    9991011
    10001012      /// \brief Construct a new map.
     
    10041016      /// \brief Construct a new map with default value.
    10051017      ///
    1006       /// Construct a new map for the graph and initalise the values.
     1018      /// Construct a new map for the graph and initalize the values.
    10071019      GraphMap(const Graph&, const Value&) {}
    10081020
     
    10131025      GraphMap(const GraphMap&) : Parent() {}
    10141026
    1015       /// \brief Assign operator.
    1016       ///
    1017       /// Assign operator. It does not mofify the underlying graph,
     1027      /// \brief Assignment operator.
     1028      ///
     1029      /// Assignment operator. It does not mofify the underlying graph,
    10181030      /// it just iterates on the current item set and set the  map
    10191031      /// with the value returned by the assigned map.
     
    10281040      struct Constraints {
    10291041        void constraints() {
    1030           checkConcept<ReadWriteMap<Key, Value>, _Map >();
    1031           // Construction with a graph parameter
    1032           _Map a(g);
    1033           // Constructor with a graph and a default value parameter
    1034           _Map a2(g,t);
    1035           // Copy constructor.
    1036           // _Map b(c);
    1037 
     1042          checkConcept
     1043            <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
     1044          _Map m1(g);
     1045          _Map m2(g,t);
     1046         
     1047          // Copy constructor
     1048          // _Map m3(m);
     1049
     1050          // Assignment operator
    10381051          // ReadMap<Key, Value> cmap;
    1039           // b = cmap;
    1040 
    1041           ignore_unused_variable_warning(a);
    1042           ignore_unused_variable_warning(a2);
    1043           // ignore_unused_variable_warning(b);
    1044         }
    1045 
    1046         const _Map &c;
     1052          // m3 = cmap;
     1053
     1054          ignore_unused_variable_warning(m1);
     1055          ignore_unused_variable_warning(m2);
     1056          // ignore_unused_variable_warning(m3);
     1057        }
     1058
     1059        const _Map &m;
    10471060        const Graph &g;
    10481061        const typename GraphMap::Value &t;
     
    10511064    };
    10521065
    1053     /// \brief An empty mappable digraph class.
    1054     ///
    1055     /// This class provides beside the core digraph features
    1056     /// map interface for the digraph structure.
     1066    /// \brief Skeleton class for mappable directed graphs.
     1067    ///
     1068    /// This class describes the interface of mappable directed graphs.
     1069    /// It extends \ref BaseDigraphComponent with the standard digraph
     1070    /// map classes, namely \c NodeMap and \c ArcMap.
    10571071    /// This concept is part of the Digraph concept.
    1058     template <typename _Base = BaseDigraphComponent>
    1059     class MappableDigraphComponent : public _Base  {
    1060     public:
    1061 
    1062       typedef _Base Base;
     1072    template <typename BAS = BaseDigraphComponent>
     1073    class MappableDigraphComponent : public BAS  {
     1074    public:
     1075
     1076      typedef BAS Base;
    10631077      typedef typename Base::Node Node;
    10641078      typedef typename Base::Arc Arc;
     
    10661080      typedef MappableDigraphComponent Digraph;
    10671081
    1068       /// \brief ReadWrite map of the nodes.
    1069       ///
    1070       /// ReadWrite map of the nodes.
    1071       ///
    1072       template <typename _Value>
    1073       class NodeMap : public GraphMap<Digraph, Node, _Value> {
     1082      /// \brief Standard graph map for the nodes.
     1083      ///
     1084      /// Standard graph map for the nodes.
     1085      /// It conforms to the ReferenceMap concept.
     1086      template <typename V>
     1087      class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
    10741088      public:
    1075         typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;
     1089        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
    10761090
    10771091        /// \brief Construct a new map.
     
    10831097        /// \brief Construct a new map with default value.
    10841098        ///
    1085         /// Construct a new map for the digraph and initalise the values.
    1086         NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
     1099        /// Construct a new map for the digraph and initalize the values.
     1100        NodeMap(const MappableDigraphComponent& digraph, const V& value)
    10871101          : Parent(digraph, value) {}
    10881102
     
    10931107        NodeMap(const NodeMap& nm) : Parent(nm) {}
    10941108
    1095         /// \brief Assign operator.
    1096         ///
    1097         /// Assign operator.
     1109        /// \brief Assignment operator.
     1110        ///
     1111        /// Assignment operator.
    10981112        template <typename CMap>
    10991113        NodeMap& operator=(const CMap&) {
    1100           checkConcept<ReadMap<Node, _Value>, CMap>();
     1114          checkConcept<ReadMap<Node, V>, CMap>();
    11011115          return *this;
    11021116        }
     
    11041118      };
    11051119
    1106       /// \brief ReadWrite map of the arcs.
    1107       ///
    1108       /// ReadWrite map of the arcs.
    1109       ///
    1110       template <typename _Value>
    1111       class ArcMap : public GraphMap<Digraph, Arc, _Value> {
     1120      /// \brief Standard graph map for the arcs.
     1121      ///
     1122      /// Standard graph map for the arcs.
     1123      /// It conforms to the ReferenceMap concept.
     1124      template <typename V>
     1125      class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
    11121126      public:
    1113         typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;
     1127        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
    11141128
    11151129        /// \brief Construct a new map.
     
    11211135        /// \brief Construct a new map with default value.
    11221136        ///
    1123         /// Construct a new map for the digraph and initalise the values.
    1124         ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
     1137        /// Construct a new map for the digraph and initalize the values.
     1138        ArcMap(const MappableDigraphComponent& digraph, const V& value)
    11251139          : Parent(digraph, value) {}
    11261140
     
    11311145        ArcMap(const ArcMap& nm) : Parent(nm) {}
    11321146
    1133         /// \brief Assign operator.
    1134         ///
    1135         /// Assign operator.
     1147        /// \brief Assignment operator.
     1148        ///
     1149        /// Assignment operator.
    11361150        template <typename CMap>
    11371151        ArcMap& operator=(const CMap&) {
    1138           checkConcept<ReadMap<Arc, _Value>, CMap>();
     1152          checkConcept<ReadMap<Arc, V>, CMap>();
    11391153          return *this;
    11401154        }
     
    11831197        }
    11841198
    1185         _Digraph& digraph;
    1186       };
    1187     };
    1188 
    1189     /// \brief An empty mappable base bipartite graph class.
    1190     ///
    1191     /// This class provides beside the core graph features
    1192     /// map interface for the graph structure.
     1199        const _Digraph& digraph;
     1200      };
     1201    };
     1202
     1203    /// \brief Skeleton class for mappable undirected graphs.
     1204    ///
     1205    /// This class describes the interface of mappable undirected graphs.
     1206    /// It extends \ref MappableDigraphComponent with the standard graph
     1207    /// map class for edges (\c EdgeMap).
    11931208    /// This concept is part of the Graph concept.
    1194     template <typename _Base = BaseGraphComponent>
    1195     class MappableGraphComponent : public MappableDigraphComponent<_Base>  {
    1196     public:
    1197 
    1198       typedef _Base Base;
     1209    template <typename BAS = BaseGraphComponent>
     1210    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
     1211    public:
     1212
     1213      typedef BAS Base;
    11991214      typedef typename Base::Edge Edge;
    12001215
    12011216      typedef MappableGraphComponent Graph;
    12021217
    1203       /// \brief ReadWrite map of the edges.
    1204       ///
    1205       /// ReadWrite map of the edges.
    1206       ///
    1207       template <typename _Value>
    1208       class EdgeMap : public GraphMap<Graph, Edge, _Value> {
     1218      /// \brief Standard graph map for the edges.
     1219      ///
     1220      /// Standard graph map for the edges.
     1221      /// It conforms to the ReferenceMap concept.
     1222      template <typename V>
     1223      class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
    12091224      public:
    1210         typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;
     1225        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
    12111226
    12121227        /// \brief Construct a new map.
     
    12181233        /// \brief Construct a new map with default value.
    12191234        ///
    1220         /// Construct a new map for the graph and initalise the values.
    1221         EdgeMap(const MappableGraphComponent& graph, const _Value& value)
     1235        /// Construct a new map for the graph and initalize the values.
     1236        EdgeMap(const MappableGraphComponent& graph, const V& value)
    12221237          : Parent(graph, value) {}
    12231238
     
    12281243        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
    12291244
    1230         /// \brief Assign operator.
    1231         ///
    1232         /// Assign operator.
     1245        /// \brief Assignment operator.
     1246        ///
     1247        /// Assignment operator.
    12331248        template <typename CMap>
    12341249        EdgeMap& operator=(const CMap&) {
    1235           checkConcept<ReadMap<Edge, _Value>, CMap>();
     1250          checkConcept<ReadMap<Edge, V>, CMap>();
    12361251          return *this;
    12371252        }
     
    12501265
    12511266        void constraints() {
    1252           checkConcept<MappableGraphComponent<Base>, _Graph>();
     1267          checkConcept<MappableDigraphComponent<Base>, _Graph>();
    12531268
    12541269          { // int map test
     
    12671282        }
    12681283
    1269         _Graph& graph;
    1270       };
    1271     };
    1272 
    1273     /// \brief An empty extendable digraph class.
    1274     ///
    1275     /// This class provides beside the core digraph features digraph
    1276     /// extendable interface for the digraph structure.  The main
    1277     /// difference between the base and this interface is that the
    1278     /// digraph alterations should handled already on this level.
    1279     template <typename _Base = BaseDigraphComponent>
    1280     class ExtendableDigraphComponent : public _Base {
    1281     public:
    1282       typedef _Base Base;
    1283 
    1284       typedef typename _Base::Node Node;
    1285       typedef typename _Base::Arc Arc;
    1286 
    1287       /// \brief Adds a new node to the digraph.
    1288       ///
    1289       /// Adds a new node to the digraph.
    1290       ///
     1284        const _Graph& graph;
     1285      };
     1286    };
     1287
     1288    /// \brief Skeleton class for extendable directed graphs.
     1289    ///
     1290    /// This class describes the interface of extendable directed graphs.
     1291    /// It extends \ref BaseDigraphComponent with functions for adding
     1292    /// nodes and arcs to the digraph.
     1293    /// This concept requires \ref AlterableDigraphComponent.
     1294    template <typename BAS = BaseDigraphComponent>
     1295    class ExtendableDigraphComponent : public BAS {
     1296    public:
     1297      typedef BAS Base;
     1298
     1299      typedef typename Base::Node Node;
     1300      typedef typename Base::Arc Arc;
     1301
     1302      /// \brief Add a new node to the digraph.
     1303      ///
     1304      /// This function adds a new node to the digraph.
    12911305      Node addNode() {
    12921306        return INVALID;
    12931307      }
    12941308
    1295       /// \brief Adds a new arc connects the given two nodes.
    1296       ///
    1297       /// Adds a new arc connects the the given two nodes.
     1309      /// \brief Add a new arc connecting the given two nodes.
     1310      ///
     1311      /// This function adds a new arc connecting the given two nodes
     1312      /// of the digraph.
    12981313      Arc addArc(const Node&, const Node&) {
    12991314        return INVALID;
     
    13151330    };
    13161331
    1317     /// \brief An empty extendable base undirected graph class.
    1318     ///
    1319     /// This class provides beside the core undirected graph features
    1320     /// core undircted graph extend interface for the graph structure.
    1321     /// The main difference between the base and this interface is
    1322     /// that the graph alterations should handled already on this
    1323     /// level.
    1324     template <typename _Base = BaseGraphComponent>
    1325     class ExtendableGraphComponent : public _Base {
    1326     public:
    1327 
    1328       typedef _Base Base;
    1329       typedef typename _Base::Node Node;
    1330       typedef typename _Base::Edge Edge;
    1331 
    1332       /// \brief Adds a new node to the graph.
    1333       ///
    1334       /// Adds a new node to the graph.
    1335       ///
     1332    /// \brief Skeleton class for extendable undirected graphs.
     1333    ///
     1334    /// This class describes the interface of extendable undirected graphs.
     1335    /// It extends \ref BaseGraphComponent with functions for adding
     1336    /// nodes and edges to the graph.
     1337    /// This concept requires \ref AlterableGraphComponent.
     1338    template <typename BAS = BaseGraphComponent>
     1339    class ExtendableGraphComponent : public BAS {
     1340    public:
     1341
     1342      typedef BAS Base;
     1343      typedef typename Base::Node Node;
     1344      typedef typename Base::Edge Edge;
     1345
     1346      /// \brief Add a new node to the digraph.
     1347      ///
     1348      /// This function adds a new node to the digraph.
    13361349      Node addNode() {
    13371350        return INVALID;
    13381351      }
    13391352
    1340       /// \brief Adds a new arc connects the given two nodes.
    1341       ///
    1342       /// Adds a new arc connects the the given two nodes.
    1343       Edge addArc(const Node&, const Node&) {
     1353      /// \brief Add a new edge connecting the given two nodes.
     1354      ///
     1355      /// This function adds a new edge connecting the given two nodes
     1356      /// of the graph.
     1357      Edge addEdge(const Node&, const Node&) {
    13441358        return INVALID;
    13451359      }
     
    13601374    };
    13611375
    1362     /// \brief An empty erasable digraph class.
    1363     ///
    1364     /// This class provides beside the core digraph features core erase
    1365     /// functions for the digraph structure. The main difference between
    1366     /// the base and this interface is that the digraph alterations
    1367     /// should handled already on this level.
    1368     template <typename _Base = BaseDigraphComponent>
    1369     class ErasableDigraphComponent : public _Base {
    1370     public:
    1371 
    1372       typedef _Base Base;
     1376    /// \brief Skeleton class for erasable directed graphs.
     1377    ///
     1378    /// This class describes the interface of erasable directed graphs.
     1379    /// It extends \ref BaseDigraphComponent with functions for removing
     1380    /// nodes and arcs from the digraph.
     1381    /// This concept requires \ref AlterableDigraphComponent.
     1382    template <typename BAS = BaseDigraphComponent>
     1383    class ErasableDigraphComponent : public BAS {
     1384    public:
     1385
     1386      typedef BAS Base;
    13731387      typedef typename Base::Node Node;
    13741388      typedef typename Base::Arc Arc;
     
    13761390      /// \brief Erase a node from the digraph.
    13771391      ///
    1378       /// Erase a node from the digraph. This function should
    1379       /// erase all arcs connecting to the node.
     1392      /// This function erases the given node from the digraph and all arcs
     1393      /// connected to the node.
    13801394      void erase(const Node&) {}
    13811395
    13821396      /// \brief Erase an arc from the digraph.
    13831397      ///
    1384       /// Erase an arc from the digraph.
    1385       ///
     1398      /// This function erases the given arc from the digraph.
    13861399      void erase(const Arc&) {}
    13871400
     
    13901403        void constraints() {
    13911404          checkConcept<Base, _Digraph>();
    1392           typename _Digraph::Node node;
     1405          const typename _Digraph::Node node(INVALID);
    13931406          digraph.erase(node);
    1394           typename _Digraph::Arc arc;
     1407          const typename _Digraph::Arc arc(INVALID);
    13951408          digraph.erase(arc);
    13961409        }
     
    14001413    };
    14011414
    1402     /// \brief An empty erasable base undirected graph class.
    1403     ///
    1404     /// This class provides beside the core undirected graph features
    1405     /// core erase functions for the undirceted graph structure. The
    1406     /// main difference between the base and this interface is that
    1407     /// the graph alterations should handled already on this level.
    1408     template <typename _Base = BaseGraphComponent>
    1409     class ErasableGraphComponent : public _Base {
    1410     public:
    1411 
    1412       typedef _Base Base;
     1415    /// \brief Skeleton class for erasable undirected graphs.
     1416    ///
     1417    /// This class describes the interface of erasable undirected graphs.
     1418    /// It extends \ref BaseGraphComponent with functions for removing
     1419    /// nodes and edges from the graph.
     1420    /// This concept requires \ref AlterableGraphComponent.
     1421    template <typename BAS = BaseGraphComponent>
     1422    class ErasableGraphComponent : public BAS {
     1423    public:
     1424
     1425      typedef BAS Base;
    14131426      typedef typename Base::Node Node;
    14141427      typedef typename Base::Edge Edge;
     
    14161429      /// \brief Erase a node from the graph.
    14171430      ///
    1418       /// Erase a node from the graph. This function should erase
    1419       /// arcs connecting to the node.
     1431      /// This function erases the given node from the graph and all edges
     1432      /// connected to the node.
    14201433      void erase(const Node&) {}
    14211434
    1422       /// \brief Erase an arc from the graph.
    1423       ///
    1424       /// Erase an arc from the graph.
    1425       ///
     1435      /// \brief Erase an edge from the digraph.
     1436      ///
     1437      /// This function erases the given edge from the digraph.
    14261438      void erase(const Edge&) {}
    14271439
     
    14301442        void constraints() {
    14311443          checkConcept<Base, _Graph>();
    1432           typename _Graph::Node node;
     1444          const typename _Graph::Node node(INVALID);
    14331445          graph.erase(node);
    1434           typename _Graph::Edge edge;
     1446          const typename _Graph::Edge edge(INVALID);
    14351447          graph.erase(edge);
    14361448        }
     
    14401452    };
    14411453
    1442     /// \brief An empty clearable base digraph class.
    1443     ///
    1444     /// This class provides beside the core digraph features core clear
    1445     /// functions for the digraph structure. The main difference between
    1446     /// the base and this interface is that the digraph alterations
    1447     /// should handled already on this level.
    1448     template <typename _Base = BaseDigraphComponent>
    1449     class ClearableDigraphComponent : public _Base {
    1450     public:
    1451 
    1452       typedef _Base Base;
     1454    /// \brief Skeleton class for clearable directed graphs.
     1455    ///
     1456    /// This class describes the interface of clearable directed graphs.
     1457    /// It extends \ref BaseDigraphComponent with a function for clearing
     1458    /// the digraph.
     1459    /// This concept requires \ref AlterableDigraphComponent.
     1460    template <typename BAS = BaseDigraphComponent>
     1461    class ClearableDigraphComponent : public BAS {
     1462    public:
     1463
     1464      typedef BAS Base;
    14531465
    14541466      /// \brief Erase all nodes and arcs from the digraph.
    14551467      ///
    1456       /// Erase all nodes and arcs from the digraph.
    1457       ///
     1468      /// This function erases all nodes and arcs from the digraph.
    14581469      void clear() {}
    14591470
     
    14651476        }
    14661477
    1467         _Digraph digraph;
    1468       };
    1469     };
    1470 
    1471     /// \brief An empty clearable base undirected graph class.
    1472     ///
    1473     /// This class provides beside the core undirected graph features
    1474     /// core clear functions for the undirected graph structure. The
    1475     /// main difference between the base and this interface is that
    1476     /// the graph alterations should handled already on this level.
    1477     template <typename _Base = BaseGraphComponent>
    1478     class ClearableGraphComponent : public ClearableDigraphComponent<_Base> {
    1479     public:
    1480 
    1481       typedef _Base Base;
     1478        _Digraph& digraph;
     1479      };
     1480    };
     1481
     1482    /// \brief Skeleton class for clearable undirected graphs.
     1483    ///
     1484    /// This class describes the interface of clearable undirected graphs.
     1485    /// It extends \ref BaseGraphComponent with a function for clearing
     1486    /// the graph.
     1487    /// This concept requires \ref AlterableGraphComponent.
     1488    template <typename BAS = BaseGraphComponent>
     1489    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
     1490    public:
     1491
     1492      typedef BAS Base;
     1493
     1494      /// \brief Erase all nodes and edges from the graph.
     1495      ///
     1496      /// This function erases all nodes and edges from the graph.
     1497      void clear() {}
    14821498
    14831499      template <typename _Graph>
    14841500      struct Constraints {
    14851501        void constraints() {
    1486           checkConcept<ClearableGraphComponent<Base>, _Graph>();
    1487         }
    1488 
    1489         _Graph graph;
     1502          checkConcept<Base, _Graph>();
     1503          graph.clear();
     1504        }
     1505
     1506        _Graph& graph;
    14901507      };
    14911508    };
  • lemon/concepts/heap.h

    r576 r631  
    3636    /// \brief The heap concept.
    3737    ///
    38     /// Concept class describing the main interface of heaps.
    39     template <typename Priority, typename ItemIntMap>
     38    /// Concept class describing the main interface of heaps. A \e heap
     39    /// is a data structure for storing items with specified values called
     40    /// \e priorities in such a way that finding the item with minimum
     41    /// priority is efficient. In a heap one can change the priority of an
     42    /// item, add or erase an item, etc.
     43    ///
     44    /// \tparam PR Type of the priority of the items.
     45    /// \tparam IM A read and writable item map with int values, used
     46    /// internally to handle the cross references.
     47    /// \tparam Comp A functor class for the ordering of the priorities.
     48    /// The default is \c std::less<PR>.
     49#ifdef DOXYGEN
     50    template <typename PR, typename IM, typename Comp = std::less<PR> >
     51#else
     52    template <typename PR, typename IM>
     53#endif
    4054    class Heap {
    4155    public:
    4256
     57      /// Type of the item-int map.
     58      typedef IM ItemIntMap;
     59      /// Type of the priorities.
     60      typedef PR Prio;
    4361      /// Type of the items stored in the heap.
    4462      typedef typename ItemIntMap::Key Item;
    45 
    46       /// Type of the priorities.
    47       typedef Priority Prio;
    4863
    4964      /// \brief Type to represent the states of the items.
     
    5469      /// the user.
    5570      ///
    56       /// The \c ItemIntMap must be initialized in such a way, that it
    57       /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
     71      /// The item-int map must be initialized in such way that it assigns
     72      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    5873      enum State {
    59         IN_HEAP = 0,
    60         PRE_HEAP = -1,
    61         POST_HEAP = -2
     74        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
     75        PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
     76        POST_HEAP = -2  ///< = -2. The "post heap" state constant.
    6277      };
    6378
     
    120135      ///
    121136      /// Returns the priority of the given item.
     137      /// \param i The item.
    122138      /// \pre \c i must be in the heap.
    123       /// \param i The item.
    124139      Prio operator[](const Item &i) const {}
    125140
     
    138153      ///
    139154      /// Decreases the priority of an item to the given value.
     155      /// \param i The item.
     156      /// \param p The priority.
    140157      /// \pre \c i must be stored in the heap with priority at least \c p.
     158      void decrease(const Item &i, const Prio &p) {}
     159
     160      /// \brief Increases the priority of an item to the given value.
     161      ///
     162      /// Increases the priority of an item to the given value.
    141163      /// \param i The item.
    142164      /// \param p The priority.
    143       void decrease(const Item &i, const Prio &p) {}
    144 
    145       /// \brief Increases the priority of an item to the given value.
    146       ///
    147       /// Increases the priority of an item to the given value.
    148165      /// \pre \c i must be stored in the heap with priority at most \c p.
    149       /// \param i The item.
    150       /// \param p The priority.
    151166      void increase(const Item &i, const Prio &p) {}
    152167
  • lemon/concepts/path.h

    r576 r606  
    3939    /// A skeleton structure for representing directed paths in a
    4040    /// digraph.
    41     /// \tparam _Digraph The digraph type in which the path is.
     41    /// \tparam GR The digraph type in which the path is.
    4242    ///
    4343    /// In a sense, the path can be treated as a list of arcs. The
     
    4646    /// paths cannot store the source.
    4747    ///
    48     template <typename _Digraph>
     48    template <typename GR>
    4949    class Path {
    5050    public:
    5151
    5252      /// Type of the underlying digraph.
    53       typedef _Digraph Digraph;
     53      typedef GR Digraph;
    5454      /// Arc type of the underlying digraph.
    5555      typedef typename Digraph::Arc Arc;
     
    206206    /// assigned to a real path and the dumpers can be implemented as
    207207    /// an adaptor class to the predecessor map.
    208 
    209     /// \tparam _Digraph The digraph type in which the path is.
     208    ///
     209    /// \tparam GR The digraph type in which the path is.
    210210    ///
    211211    /// The paths can be constructed from any path type by a
    212212    /// template constructor or a template assignment operator.
    213     ///
    214     template <typename _Digraph>
     213    template <typename GR>
    215214    class PathDumper {
    216215    public:
    217216
    218217      /// Type of the underlying digraph.
    219       typedef _Digraph Digraph;
     218      typedef GR Digraph;
    220219      /// Arc type of the underlying digraph.
    221220      typedef typename Digraph::Arc Arc;
  • lemon/config.h.in

    r564 r614  
    1919/* Define to 1 if you have CLP */
    2020#undef HAVE_CLP
     21
     22/* Define to 1 if you have CBC */
     23#undef HAVE_CBC
  • lemon/connectivity.h

    r463 r633  
    3333#include <functional>
    3434
    35 /// \ingroup connectivity
     35/// \ingroup graph_properties
    3636/// \file
    3737/// \brief Connectivity algorithms
     
    4141namespace lemon {
    4242
    43   /// \ingroup connectivity
     43  /// \ingroup graph_properties
    4444  ///
    4545  /// \brief Check whether the given undirected graph is connected.
     
    4747  /// Check whether the given undirected graph is connected.
    4848  /// \param graph The undirected graph.
    49   /// \return %True when there is path between any two nodes in the graph.
     49  /// \return \c true when there is path between any two nodes in the graph.
    5050  /// \note By definition, the empty graph is connected.
    5151  template <typename Graph>
     
    6464  }
    6565
    66   /// \ingroup connectivity
     66  /// \ingroup graph_properties
    6767  ///
    6868  /// \brief Count the number of connected components of an undirected graph
     
    106106  }
    107107
    108   /// \ingroup connectivity
     108  /// \ingroup graph_properties
    109109  ///
    110110  /// \brief Find the connected components of an undirected graph
    111111  ///
    112112  /// Find the connected components of an undirected graph.
     113  ///
     114  /// \image html connected_components.png
     115  /// \image latex connected_components.eps "Connected components" width=\textwidth
    113116  ///
    114117  /// \param graph The graph. It must be undirected.
     
    118121  /// set continuously.
    119122  /// \return The number of components
    120   ///
    121123  template <class Graph, class NodeMap>
    122124  int connectedComponents(const Graph &graph, NodeMap &compMap) {
     
    228230
    229231
    230   /// \ingroup connectivity
     232  /// \ingroup graph_properties
    231233  ///
    232234  /// \brief Check whether the given directed graph is strongly connected.
     
    235237  /// graph is strongly connected when any two nodes of the graph are
    236238  /// connected with directed paths in both direction.
    237   /// \return %False when the graph is not strongly connected.
     239  /// \return \c false when the graph is not strongly connected.
    238240  /// \see connected
    239241  ///
     
    286288  }
    287289
    288   /// \ingroup connectivity
     290  /// \ingroup graph_properties
    289291  ///
    290292  /// \brief Count the strongly connected components of a directed graph
     
    350352  }
    351353
    352   /// \ingroup connectivity
     354  /// \ingroup graph_properties
    353355  ///
    354356  /// \brief Find the strongly connected components of a directed graph
     
    362364  /// a lower.
    363365  ///
     366  /// \image html strongly_connected_components.png
     367  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
     368  ///
    364369  /// \param digraph The digraph.
    365370  /// \retval compMap A writable node map. The values will be set from 0 to
     
    368373  /// will be set continuously.
    369374  /// \return The number of components
    370   ///
    371375  template <typename Digraph, typename NodeMap>
    372376  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
     
    417421  }
    418422
    419   /// \ingroup connectivity
     423  /// \ingroup graph_properties
    420424  ///
    421425  /// \brief Find the cut arcs of the strongly connected components.
     
    701705  int countBiNodeConnectedComponents(const Graph& graph);
    702706
    703   /// \ingroup connectivity
     707  /// \ingroup graph_properties
    704708  ///
    705709  /// \brief Checks the graph is bi-node-connected.
     
    710714  ///
    711715  /// \param graph The graph.
    712   /// \return %True when the graph bi-node-connected.
     716  /// \return \c true when the graph bi-node-connected.
    713717  template <typename Graph>
    714718  bool biNodeConnected(const Graph& graph) {
     
    716720  }
    717721
    718   /// \ingroup connectivity
     722  /// \ingroup graph_properties
    719723  ///
    720724  /// \brief Count the biconnected components.
     
    751755  }
    752756
    753   /// \ingroup connectivity
     757  /// \ingroup graph_properties
    754758  ///
    755759  /// \brief Find the bi-node-connected components.
     
    759763  /// relation on the undirected edges. Two undirected edge are in relationship
    760764  /// when they are on same circle.
     765  ///
     766  /// \image html node_biconnected_components.png
     767  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
    761768  ///
    762769  /// \param graph The graph.
     
    766773  /// will be set continuously.
    767774  /// \return The number of components.
    768   ///
    769775  template <typename Graph, typename EdgeMap>
    770776  int biNodeConnectedComponents(const Graph& graph,
     
    794800  }
    795801
    796   /// \ingroup connectivity
     802  /// \ingroup graph_properties
    797803  ///
    798804  /// \brief Find the bi-node-connected cut nodes.
     
    10241030  int countBiEdgeConnectedComponents(const Graph& graph);
    10251031
    1026   /// \ingroup connectivity
     1032  /// \ingroup graph_properties
    10271033  ///
    10281034  /// \brief Checks that the graph is bi-edge-connected.
     
    10391045  }
    10401046
    1041   /// \ingroup connectivity
     1047  /// \ingroup graph_properties
    10421048  ///
    10431049  /// \brief Count the bi-edge-connected components.
     
    10741080  }
    10751081
    1076   /// \ingroup connectivity
     1082  /// \ingroup graph_properties
    10771083  ///
    10781084  /// \brief Find the bi-edge-connected components.
     
    10821088  /// relation on the nodes. Two nodes are in relationship when they are
    10831089  /// connected at least two edge-disjoint paths.
     1090  ///
     1091  /// \image html edge_biconnected_components.png
     1092  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    10841093  ///
    10851094  /// \param graph The graph.
     
    10891098  /// will be set continuously.
    10901099  /// \return The number of components.
    1091   ///
    10921100  template <typename Graph, typename NodeMap>
    10931101  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
     
    11161124  }
    11171125
    1118   /// \ingroup connectivity
     1126  /// \ingroup graph_properties
    11191127  ///
    11201128  /// \brief Find the bi-edge-connected cut edges.
     
    11801188  }
    11811189
    1182   /// \ingroup connectivity
     1190  /// \ingroup graph_properties
    11831191  ///
    11841192  /// \brief Sort the nodes of a DAG into topolgical order.
     
    12191227  }
    12201228
    1221   /// \ingroup connectivity
     1229  /// \ingroup graph_properties
    12221230  ///
    12231231  /// \brief Sort the nodes of a DAG into topolgical order.
     
    12311239  /// of the map will be set exactly once, the values will be set descending
    12321240  /// order.
    1233   /// \return %False when the graph is not DAG.
     1241  /// \return \c false when the graph is not DAG.
    12341242  ///
    12351243  /// \see topologicalSort
     
    12741282  }
    12751283
    1276   /// \ingroup connectivity
     1284  /// \ingroup graph_properties
    12771285  ///
    12781286  /// \brief Check that the given directed graph is a DAG.
     
    12801288  /// Check that the given directed graph is a DAG. The DAG is
    12811289  /// an Directed Acyclic Digraph.
    1282   /// \return %False when the graph is not DAG.
     1290  /// \return \c false when the graph is not DAG.
    12831291  /// \see acyclic
    12841292  template <typename Digraph>
     
    13161324  }
    13171325
    1318   /// \ingroup connectivity
     1326  /// \ingroup graph_properties
    13191327  ///
    13201328  /// \brief Check that the given undirected graph is acyclic.
     
    13221330  /// Check that the given undirected graph acyclic.
    13231331  /// \param graph The undirected graph.
    1324   /// \return %True when there is no circle in the graph.
     1332  /// \return \c true when there is no circle in the graph.
    13251333  /// \see dag
    13261334  template <typename Graph>
     
    13501358  }
    13511359
    1352   /// \ingroup connectivity
     1360  /// \ingroup graph_properties
    13531361  ///
    13541362  /// \brief Check that the given undirected graph is tree.
     
    13561364  /// Check that the given undirected graph is tree.
    13571365  /// \param graph The undirected graph.
    1358   /// \return %True when the graph is acyclic and connected.
     1366  /// \return \c true when the graph is acyclic and connected.
    13591367  template <typename Graph>
    13601368  bool tree(const Graph& graph) {
     
    14421450  }
    14431451
    1444   /// \ingroup connectivity
     1452  /// \ingroup graph_properties
    14451453  ///
    14461454  /// \brief Check if the given undirected graph is bipartite or not
     
    14491457  /// or not. The \ref Bfs algorithm is used to calculate the result.
    14501458  /// \param graph The undirected graph.
    1451   /// \return %True if \c graph is bipartite, %false otherwise.
     1459  /// \return \c true if \c graph is bipartite, \c false otherwise.
    14521460  /// \sa bipartitePartitions
    14531461  template<typename Graph>
     
    14791487  }
    14801488
    1481   /// \ingroup connectivity
     1489  /// \ingroup graph_properties
    14821490  ///
    14831491  /// \brief Check if the given undirected graph is bipartite or not
     
    14871495  /// During the execution, the \c partMap will be set as the two
    14881496  /// partitions of the graph.
     1497  ///
     1498  /// \image html bipartite_partitions.png
     1499  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
     1500  ///
    14891501  /// \param graph The undirected graph.
    14901502  /// \retval partMap A writable bool map of nodes. It will be set as the
    14911503  /// two partitions of the graph.
    1492   /// \return %True if \c graph is bipartite, %false otherwise.
     1504  /// \return \c true if \c graph is bipartite, \c false otherwise.
    14931505  template<typename Graph, typename NodeMap>
    14941506  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
  • lemon/core.h

    r582 r628  
    10351035  ///\sa findArc()
    10361036  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    1037   template <typename _Graph>
    1038   class ConArcIt : public _Graph::Arc {
     1037  template <typename GR>
     1038  class ConArcIt : public GR::Arc {
    10391039  public:
    10401040
    1041     typedef _Graph Graph;
     1041    typedef GR Graph;
    10421042    typedef typename Graph::Arc Parent;
    10431043
     
    11581158  ///
    11591159  ///\sa findEdge()
    1160   template <typename _Graph>
    1161   class ConEdgeIt : public _Graph::Edge {
     1160  template <typename GR>
     1161  class ConEdgeIt : public GR::Edge {
    11621162  public:
    11631163
    1164     typedef _Graph Graph;
     1164    typedef GR Graph;
    11651165    typedef typename Graph::Edge Parent;
    11661166
     
    12121212  ///queries.
    12131213  ///
    1214   ///\tparam G The type of the underlying digraph.
     1214  ///\tparam GR The type of the underlying digraph.
    12151215  ///
    12161216  ///\sa ArcLookUp
    12171217  ///\sa AllArcLookUp
    1218   template<class G>
     1218  template <typename GR>
    12191219  class DynArcLookUp
    1220     : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
     1220    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
    12211221  {
    12221222  public:
    1223     typedef typename ItemSetTraits<G, typename G::Arc>
     1223    typedef typename ItemSetTraits<GR, typename GR::Arc>
    12241224    ::ItemNotifier::ObserverBase Parent;
    12251225
    1226     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1227     typedef G Digraph;
     1226    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1227    typedef GR Digraph;
    12281228
    12291229  protected:
    12301230
    1231     class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
     1231    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
    12321232    public:
    12331233
    1234       typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
    1235 
    1236       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
     1234      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
     1235
     1236      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
    12371237
    12381238      virtual void add(const Node& node) {
     
    13161316    virtual void clear() {
    13171317      for(NodeIt n(_g);n!=INVALID;++n) {
    1318         _head.set(n, INVALID);
     1318        _head[n] = INVALID;
    13191319      }
    13201320    }
     
    13231323      Node s = _g.source(arc);
    13241324      Node t = _g.target(arc);
    1325       _left.set(arc, INVALID);
    1326       _right.set(arc, INVALID);
     1325      _left[arc] = INVALID;
     1326      _right[arc] = INVALID;
    13271327
    13281328      Arc e = _head[s];
    13291329      if (e == INVALID) {
    1330         _head.set(s, arc);
    1331         _parent.set(arc, INVALID);
     1330        _head[s] = arc;
     1331        _parent[arc] = INVALID;
    13321332        return;
    13331333      }
     
    13351335        if (t < _g.target(e)) {
    13361336          if (_left[e] == INVALID) {
    1337             _left.set(e, arc);
    1338             _parent.set(arc, e);
     1337            _left[e] = arc;
     1338            _parent[arc] = e;
    13391339            splay(arc);
    13401340            return;
     
    13441344        } else {
    13451345          if (_right[e] == INVALID) {
    1346             _right.set(e, arc);
    1347             _parent.set(arc, e);
     1346            _right[e] = arc;
     1347            _parent[arc] = e;
    13481348            splay(arc);
    13491349            return;
     
    13581358      if (_left[arc] == INVALID) {
    13591359        if (_right[arc] != INVALID) {
    1360           _parent.set(_right[arc], _parent[arc]);
     1360          _parent[_right[arc]] = _parent[arc];
    13611361        }
    13621362        if (_parent[arc] != INVALID) {
    13631363          if (_left[_parent[arc]] == arc) {
    1364             _left.set(_parent[arc], _right[arc]);
     1364            _left[_parent[arc]] = _right[arc];
    13651365          } else {
    1366             _right.set(_parent[arc], _right[arc]);
     1366            _right[_parent[arc]] = _right[arc];
    13671367          }
    13681368        } else {
    1369           _head.set(_g.source(arc), _right[arc]);
     1369          _head[_g.source(arc)] = _right[arc];
    13701370        }
    13711371      } else if (_right[arc] == INVALID) {
    1372         _parent.set(_left[arc], _parent[arc]);
     1372        _parent[_left[arc]] = _parent[arc];
    13731373        if (_parent[arc] != INVALID) {
    13741374          if (_left[_parent[arc]] == arc) {
    1375             _left.set(_parent[arc], _left[arc]);
     1375            _left[_parent[arc]] = _left[arc];
    13761376          } else {
    1377             _right.set(_parent[arc], _left[arc]);
     1377            _right[_parent[arc]] = _left[arc];
    13781378          }
    13791379        } else {
    1380           _head.set(_g.source(arc), _left[arc]);
     1380          _head[_g.source(arc)] = _left[arc];
    13811381        }
    13821382      } else {
     
    13881388          }
    13891389          Arc s = _parent[e];
    1390           _right.set(_parent[e], _left[e]);
     1390          _right[_parent[e]] = _left[e];
    13911391          if (_left[e] != INVALID) {
    1392             _parent.set(_left[e], _parent[e]);
     1392            _parent[_left[e]] = _parent[e];
    13931393          }
    13941394
    1395           _left.set(e, _left[arc]);
    1396           _parent.set(_left[arc], e);
    1397           _right.set(e, _right[arc]);
    1398           _parent.set(_right[arc], e);
    1399 
    1400           _parent.set(e, _parent[arc]);
     1395          _left[e] = _left[arc];
     1396          _parent[_left[arc]] = e;
     1397          _right[e] = _right[arc];
     1398          _parent[_right[arc]] = e;
     1399
     1400          _parent[e] = _parent[arc];
    14011401          if (_parent[arc] != INVALID) {
    14021402            if (_left[_parent[arc]] == arc) {
    1403               _left.set(_parent[arc], e);
     1403              _left[_parent[arc]] = e;
    14041404            } else {
    1405               _right.set(_parent[arc], e);
     1405              _right[_parent[arc]] = e;
    14061406            }
    14071407          }
    14081408          splay(s);
    14091409        } else {
    1410           _right.set(e, _right[arc]);
    1411           _parent.set(_right[arc], e);
    1412           _parent.set(e, _parent[arc]);
     1410          _right[e] = _right[arc];
     1411          _parent[_right[arc]] = e;
     1412          _parent[e] = _parent[arc];
    14131413
    14141414          if (_parent[arc] != INVALID) {
    14151415            if (_left[_parent[arc]] == arc) {
    1416               _left.set(_parent[arc], e);
     1416              _left[_parent[arc]] = e;
    14171417            } else {
    1418               _right.set(_parent[arc], e);
     1418              _right[_parent[arc]] = e;
    14191419            }
    14201420          } else {
    1421             _head.set(_g.source(arc), e);
     1421            _head[_g.source(arc)] = e;
    14221422          }
    14231423        }
     
    14311431      if (a < m) {
    14321432        Arc left = refreshRec(v,a,m-1);
    1433         _left.set(me, left);
    1434         _parent.set(left, me);
     1433        _left[me] = left;
     1434        _parent[left] = me;
    14351435      } else {
    1436         _left.set(me, INVALID);
     1436        _left[me] = INVALID;
    14371437      }
    14381438      if (m < b) {
    14391439        Arc right = refreshRec(v,m+1,b);
    1440         _right.set(me, right);
    1441         _parent.set(right, me);
     1440        _right[me] = right;
     1441        _parent[right] = me;
    14421442      } else {
    1443         _right.set(me, INVALID);
     1443        _right[me] = INVALID;
    14441444      }
    14451445      return me;
     
    14531453          std::sort(v.begin(),v.end(),ArcLess(_g));
    14541454          Arc head = refreshRec(v,0,v.size()-1);
    1455           _head.set(n, head);
    1456           _parent.set(head, INVALID);
    1457         }
    1458         else _head.set(n, INVALID);
     1455          _head[n] = head;
     1456          _parent[head] = INVALID;
     1457        }
     1458        else _head[n] = INVALID;
    14591459      }
    14601460    }
     
    14621462    void zig(Arc v) {
    14631463      Arc w = _parent[v];
    1464       _parent.set(v, _parent[w]);
    1465       _parent.set(w, v);
    1466       _left.set(w, _right[v]);
    1467       _right.set(v, w);
     1464      _parent[v] = _parent[w];
     1465      _parent[w] = v;
     1466      _left[w] = _right[v];
     1467      _right[v] = w;
    14681468      if (_parent[v] != INVALID) {
    14691469        if (_right[_parent[v]] == w) {
    1470           _right.set(_parent[v], v);
     1470          _right[_parent[v]] = v;
    14711471        } else {
    1472           _left.set(_parent[v], v);
     1472          _left[_parent[v]] = v;
    14731473        }
    14741474      }
    14751475      if (_left[w] != INVALID){
    1476         _parent.set(_left[w], w);
     1476        _parent[_left[w]] = w;
    14771477      }
    14781478    }
     
    14801480    void zag(Arc v) {
    14811481      Arc w = _parent[v];
    1482       _parent.set(v, _parent[w]);
    1483       _parent.set(w, v);
    1484       _right.set(w, _left[v]);
    1485       _left.set(v, w);
     1482      _parent[v] = _parent[w];
     1483      _parent[w] = v;
     1484      _right[w] = _left[v];
     1485      _left[v] = w;
    14861486      if (_parent[v] != INVALID){
    14871487        if (_left[_parent[v]] == w) {
    1488           _left.set(_parent[v], v);
     1488          _left[_parent[v]] = v;
    14891489        } else {
    1490           _right.set(_parent[v], v);
     1490          _right[_parent[v]] = v;
    14911491        }
    14921492      }
    14931493      if (_right[w] != INVALID){
    1494         _parent.set(_right[w], w);
     1494        _parent[_right[w]] = w;
    14951495      }
    14961496    }
     
    16241624  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    16251625  ///
    1626   ///\tparam G The type of the underlying digraph.
     1626  ///\tparam GR The type of the underlying digraph.
    16271627  ///
    16281628  ///\sa DynArcLookUp
    16291629  ///\sa AllArcLookUp
    1630   template<class G>
     1630  template<class GR>
    16311631  class ArcLookUp
    16321632  {
    16331633  public:
    1634     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1635     typedef G Digraph;
     1634    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1635    typedef GR Digraph;
    16361636
    16371637  protected:
     
    17341734  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    17351735  ///
    1736   ///\tparam G The type of the underlying digraph.
     1736  ///\tparam GR The type of the underlying digraph.
    17371737  ///
    17381738  ///\sa DynArcLookUp
    17391739  ///\sa ArcLookUp
    1740   template<class G>
    1741   class AllArcLookUp : public ArcLookUp<G>
     1740  template<class GR>
     1741  class AllArcLookUp : public ArcLookUp<GR>
    17421742  {
    1743     using ArcLookUp<G>::_g;
    1744     using ArcLookUp<G>::_right;
    1745     using ArcLookUp<G>::_left;
    1746     using ArcLookUp<G>::_head;
    1747 
    1748     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1749     typedef G Digraph;
     1743    using ArcLookUp<GR>::_g;
     1744    using ArcLookUp<GR>::_right;
     1745    using ArcLookUp<GR>::_left;
     1746    using ArcLookUp<GR>::_head;
     1747
     1748    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1749    typedef GR Digraph;
    17501750
    17511751    typename Digraph::template ArcMap<Arc> _next;
     
    17741774    ///It builds up the search database, which remains valid until the digraph
    17751775    ///changes.
    1776     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
     1776    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
    17771777
    17781778    ///Refresh the data structure at a node.
     
    17841784    void refresh(Node n)
    17851785    {
    1786       ArcLookUp<G>::refresh(n);
     1786      ArcLookUp<GR>::refresh(n);
    17871787      refreshNext(_head[n]);
    17881788    }
     
    18311831    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
    18321832#else
    1833     using ArcLookUp<G>::operator() ;
     1833    using ArcLookUp<GR>::operator() ;
    18341834    Arc operator()(Node s, Node t, Arc prev) const
    18351835    {
  • lemon/cplex.cc

    r485 r623  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7373    int status;
    7474    _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
     75    messageLevel(MESSAGE_NOTHING);
    7576  }
    7677
     
    7980    int status;
    8081    _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
     82    messageLevel(MESSAGE_NOTHING);
    8183  }
    8284
     
    8789    rows = cplex.rows;
    8890    cols = cplex.cols;
     91    messageLevel(MESSAGE_NOTHING);
    8992  }
    9093
     
    439442  }
    440443
     444  void CplexBase::_messageLevel(MessageLevel level) {
     445    switch (level) {
     446    case MESSAGE_NOTHING:
     447      _message_enabled = false;
     448      break;
     449    case MESSAGE_ERROR:
     450    case MESSAGE_WARNING:
     451    case MESSAGE_NORMAL:
     452    case MESSAGE_VERBOSE:
     453      _message_enabled = true;
     454      break;
     455    }
     456  }
     457
     458  void CplexBase::_applyMessageLevel() {
     459    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
     460                   _message_enabled ? CPX_ON : CPX_OFF);
     461  }
     462
    441463  // CplexLp members
    442464
    443465  CplexLp::CplexLp()
    444     : LpBase(), CplexBase(), LpSolver() {}
     466    : LpBase(), LpSolver(), CplexBase() {}
    445467
    446468  CplexLp::CplexLp(const CplexEnv& env)
    447     : LpBase(), CplexBase(env), LpSolver() {}
     469    : LpBase(), LpSolver(), CplexBase(env) {}
    448470
    449471  CplexLp::CplexLp(const CplexLp& other)
    450     : LpBase(), CplexBase(other), LpSolver() {}
     472    : LpBase(), LpSolver(), CplexBase(other) {}
    451473
    452474  CplexLp::~CplexLp() {}
    453475
    454   CplexLp* CplexLp::_newSolver() const { return new CplexLp; }
    455   CplexLp* CplexLp::_cloneSolver() const {return new CplexLp(*this); }
     476  CplexLp* CplexLp::newSolver() const { return new CplexLp; }
     477  CplexLp* CplexLp::cloneSolver() const {return new CplexLp(*this); }
    456478
    457479  const char* CplexLp::_solverName() const { return "CplexLp"; }
     
    508530  CplexLp::SolveExitStatus CplexLp::_solve() {
    509531    _clear_temporals();
     532    _applyMessageLevel();
    510533    return convertStatus(CPXlpopt(cplexEnv(), _prob));
    511534  }
     
    513536  CplexLp::SolveExitStatus CplexLp::solvePrimal() {
    514537    _clear_temporals();
     538    _applyMessageLevel();
    515539    return convertStatus(CPXprimopt(cplexEnv(), _prob));
    516540  }
     
    518542  CplexLp::SolveExitStatus CplexLp::solveDual() {
    519543    _clear_temporals();
     544    _applyMessageLevel();
    520545    return convertStatus(CPXdualopt(cplexEnv(), _prob));
    521546  }
     
    523548  CplexLp::SolveExitStatus CplexLp::solveBarrier() {
    524549    _clear_temporals();
     550    _applyMessageLevel();
    525551    return convertStatus(CPXbaropt(cplexEnv(), _prob));
    526552  }
     
    601627  }
    602628
    603   //7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!)
     629  // Cplex 7.0 status values
    604630  // This table lists the statuses, returned by the CPXgetstat()
    605631  // routine, for solutions to LP problems or mixed integer problems. If
     
    648674  //       User pivot used
    649675  //
    650   //     Ezeket hova tegyem:
     676  // Pending return values
    651677  // ??case CPX_ABORT_DUAL_INFEAS
    652678  // ??case CPX_ABORT_CROSSOVER
     
    719745    statusSwitch(cplexEnv(),stat);
    720746    //CPXgetstat(cplexEnv(), _prob);
    721     //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
    722747    switch (stat) {
    723748    case 0:
     
    752777  }
    753778
    754   //9.0-as cplex verzio statusai
     779  // Cplex 9.0 status values
    755780  // CPX_STAT_ABORT_DUAL_OBJ_LIM
    756781  // CPX_STAT_ABORT_IT_LIM
     
    799824
    800825  CplexMip::CplexMip()
    801     : LpBase(), CplexBase(), MipSolver() {
     826    : LpBase(), MipSolver(), CplexBase() {
    802827
    803828#if CPX_VERSION < 800
     
    809834
    810835  CplexMip::CplexMip(const CplexEnv& env)
    811     : LpBase(), CplexBase(env), MipSolver() {
     836    : LpBase(), MipSolver(), CplexBase(env) {
    812837
    813838#if CPX_VERSION < 800
     
    820845
    821846  CplexMip::CplexMip(const CplexMip& other)
    822     : LpBase(), CplexBase(other), MipSolver() {}
     847    : LpBase(), MipSolver(), CplexBase(other) {}
    823848
    824849  CplexMip::~CplexMip() {}
    825850
    826   CplexMip* CplexMip::_newSolver() const { return new CplexMip; }
    827   CplexMip* CplexMip::_cloneSolver() const {return new CplexMip(*this); }
     851  CplexMip* CplexMip::newSolver() const { return new CplexMip; }
     852  CplexMip* CplexMip::cloneSolver() const {return new CplexMip(*this); }
    828853
    829854  const char* CplexMip::_solverName() const { return "CplexMip"; }
     
    865890  CplexMip::SolveExitStatus CplexMip::_solve() {
    866891    int status;
     892    _applyMessageLevel();
    867893    status = CPXmipopt (cplexEnv(), _prob);
    868894    if (status==0)
  • lemon/cplex.h

    r485 r623  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7979  ///
    8080  /// This class implements the common interface of the CPLEX LP and
    81   /// MIP solvers. 
     81  /// MIP solvers.
    8282  /// \ingroup lp_group
    8383  class CplexBase : virtual public LpBase {
     
    145145    virtual void _clear();
    146146
     147    virtual void _messageLevel(MessageLevel level);
     148    void _applyMessageLevel();
     149
     150    bool _message_enabled;
     151
    147152  public:
    148153
    149154    /// Returns the used \c CplexEnv instance
    150155    const CplexEnv& env() const { return _env; }
     156
     157    /// \brief Returns the const cpxenv pointer
    151158    ///
     159    /// \note The cpxenv might be destructed with the solver.
    152160    const cpxenv* cplexEnv() const { return _env.cplexEnv(); }
    153161
     162    /// \brief Returns the const cpxenv pointer
     163    ///
     164    /// \note The cpxenv might be destructed with the solver.
     165    cpxenv* cplexEnv() { return _env.cplexEnv(); }
     166
     167    /// Returns the cplex problem object
    154168    cpxlp* cplexLp() { return _prob; }
     169    /// Returns the cplex problem object
    155170    const cpxlp* cplexLp() const { return _prob; }
    156171
     
    161176  /// This class implements an interface for the CPLEX LP solver.
    162177  ///\ingroup lp_group
    163   class CplexLp : public CplexBase, public LpSolver {
     178  class CplexLp : public LpSolver, public CplexBase {
    164179  public:
    165180    /// \e
     
    171186    /// \e
    172187    virtual ~CplexLp();
     188
     189    /// \e
     190    virtual CplexLp* cloneSolver() const;
     191    /// \e
     192    virtual CplexLp* newSolver() const;
    173193
    174194  private:
     
    186206
    187207  protected:
    188 
    189     virtual CplexLp* _cloneSolver() const;
    190     virtual CplexLp* _newSolver() const;
    191208
    192209    virtual const char* _solverName() const;
     
    223240  /// This class implements an interface for the CPLEX MIP solver.
    224241  ///\ingroup lp_group
    225   class CplexMip : public CplexBase, public MipSolver {
     242  class CplexMip : public MipSolver, public CplexBase {
    226243  public:
    227244    /// \e
     
    234251    virtual ~CplexMip();
    235252
    236   protected:
    237 
    238     virtual CplexMip* _cloneSolver() const;
    239     virtual CplexMip* _newSolver() const;
     253    /// \e
     254    virtual CplexMip* cloneSolver() const;
     255    /// \e
     256    virtual CplexMip* newSolver() const;
     257
     258  protected:
     259
    240260
    241261    virtual const char* _solverName() const;
  • lemon/dfs.h

    r525 r631  
    207207    typedef Dfs Create;
    208208
    209     ///\name Named template parameters
     209    ///\name Named Template Parameters
    210210
    211211    ///@{
  • lemon/dijkstra.h

    r525 r631  
    3939  /// This operation traits class defines all computational operations and
    4040  /// constants which are used in the Dijkstra algorithm.
    41   template <typename Value>
     41  template <typename V>
    4242  struct DijkstraDefaultOperationTraits {
     43    /// \e
     44    typedef V Value;
    4345    /// \brief Gives back the zero value of the type.
    4446    static Value zero() {
     
    5961  ///Default traits class of Dijkstra class.
    6062  ///\tparam GR The type of the digraph.
    61   ///\tparam LM The type of the length map.
    62   template<class GR, class LM>
     63  ///\tparam LEN The type of the length map.
     64  template<typename GR, typename LEN>
    6365  struct DijkstraDefaultTraits
    6466  {
     
    7072    ///The type of the map that stores the arc lengths.
    7173    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    72     typedef LM LengthMap;
     74    typedef LEN LengthMap;
    7375    ///The type of the length of the arcs.
    74     typedef typename LM::Value Value;
     76    typedef typename LEN::Value Value;
    7577
    7678    /// Operation traits for %Dijkstra algorithm.
     
    101103    ///\sa BinHeap
    102104    ///\sa Dijkstra
    103     typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
     105    typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap;
    104106    ///Instantiates a \c Heap.
    105107
     
    151153    ///The type of the map that stores the distances of the nodes.
    152154    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    153     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
     155    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    154156    ///Instantiates a \c DistMap.
    155157
     
    181183  ///\tparam GR The type of the digraph the algorithm runs on.
    182184  ///The default type is \ref ListDigraph.
    183   ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
     185  ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
    184186  ///the lengths of the arcs.
    185187  ///It is read once for each arc, so the map may involve in
     
    188190  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
    189191#ifdef DOXYGEN
    190   template <typename GR, typename LM, typename TR>
     192  template <typename GR, typename LEN, typename TR>
    191193#else
    192194  template <typename GR=ListDigraph,
    193             typename LM=typename GR::template ArcMap<int>,
    194             typename TR=DijkstraDefaultTraits<GR,LM> >
     195            typename LEN=typename GR::template ArcMap<int>,
     196            typename TR=DijkstraDefaultTraits<GR,LEN> >
    195197#endif
    196198  class Dijkstra {
     
    285287    typedef Dijkstra Create;
    286288
    287     ///\name Named template parameters
     289    ///\name Named Template Parameters
    288290
    289291    ///@{
     
    914916  ///Default traits class of dijkstra() function.
    915917  ///\tparam GR The type of the digraph.
    916   ///\tparam LM The type of the length map.
    917   template<class GR, class LM>
     918  ///\tparam LEN The type of the length map.
     919  template<class GR, class LEN>
    918920  struct DijkstraWizardDefaultTraits
    919921  {
     
    924926    ///The type of the map that stores the arc lengths.
    925927    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    926     typedef LM LengthMap;
     928    typedef LEN LengthMap;
    927929    ///The type of the length of the arcs.
    928     typedef typename LM::Value Value;
     930    typedef typename LEN::Value Value;
    929931
    930932    /// Operation traits for Dijkstra algorithm.
     
    10081010    ///The type of the map that stores the distances of the nodes.
    10091011    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1010     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
     1012    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    10111013    ///Instantiates a DistMap.
    10121014
     
    10341036  /// The \ref DijkstraWizardBase is a class to be the default traits of the
    10351037  /// \ref DijkstraWizard class.
    1036   template<class GR,class LM>
    1037   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
     1038  template<typename GR, typename LEN>
     1039  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
    10381040  {
    1039     typedef DijkstraWizardDefaultTraits<GR,LM> Base;
     1041    typedef DijkstraWizardDefaultTraits<GR,LEN> Base;
    10401042  protected:
    10411043    //The type of the nodes in the digraph.
     
    10711073    /// \param g The digraph the algorithm runs on.
    10721074    /// \param l The length map.
    1073     DijkstraWizardBase(const GR &g,const LM &l) :
     1075    DijkstraWizardBase(const GR &g,const LEN &l) :
    10741076      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    1075       _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
     1077      _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))),
    10761078      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
    10771079
     
    12821284  ///\sa DijkstraWizard
    12831285  ///\sa Dijkstra
    1284   template<class GR, class LM>
    1285   DijkstraWizard<DijkstraWizardBase<GR,LM> >
    1286   dijkstra(const GR &digraph, const LM &length)
     1286  template<typename GR, typename LEN>
     1287  DijkstraWizard<DijkstraWizardBase<GR,LEN> >
     1288  dijkstra(const GR &digraph, const LEN &length)
    12871289  {
    1288     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
     1290    return DijkstraWizard<DijkstraWizardBase<GR,LEN> >(digraph,length);
    12891291  }
    12901292
  • lemon/dimacs.h

    r572 r631  
    2323#include <string>
    2424#include <vector>
     25#include <limits>
    2526#include <lemon/maps.h>
    2627#include <lemon/error.h>
    27 
    2828/// \ingroup dimacs_group
    2929/// \file
     
    3838  struct DimacsDescriptor
    3939  {
    40     ///File type enum
    41     enum Type
    42       {
    43         NONE, MIN, MAX, SP, MAT
    44       };
     40    ///\brief DIMACS file type enum
     41    ///
     42    ///DIMACS file type enum.
     43    enum Type {
     44      NONE,  ///< Undefined type.
     45      MIN,   ///< DIMACS file type for minimum cost flow problems.
     46      MAX,   ///< DIMACS file type for maximum flow problems.
     47      SP,    ///< DIMACS file type for shostest path problems.
     48      MAT    ///< DIMACS file type for plain graphs and matching problems.
     49    };
    4550    ///The file type
    4651    Type type;
     
    5055    int edgeNum;
    5156    int lineShift;
    52     /// Constructor. Sets the type to NONE.
     57    ///Constructor. It sets the type to \c NONE.
    5358    DimacsDescriptor() : type(NONE) {}
    5459  };
     
    5661  ///Discover the type of a DIMACS file
    5762
    58   ///It starts seeking the begining of the file for the problem type
    59   ///and size info. The found data is returned in a special struct
    60   ///that can be evaluated and passed to the appropriate reader
    61   ///function.
     63  ///This function starts seeking the beginning of the given file for the
     64  ///problem type and size info.
     65  ///The found data is returned in a special struct that can be evaluated
     66  ///and passed to the appropriate reader function.
    6267  DimacsDescriptor dimacsType(std::istream& is)
    6368  {
     
    97102
    98103
    99 
    100   /// DIMACS minimum cost flow reader function.
     104  /// \brief DIMACS minimum cost flow reader function.
    101105  ///
    102106  /// This function reads a minimum cost flow instance from DIMACS format,
     
    106110  /// \endcode
    107111  /// At the beginning, \c g is cleared by \c g.clear(). The supply
    108   /// amount of the nodes are written to \c supply (signed). The
    109   /// lower bounds, capacities and costs of the arcs are written to
    110   /// \c lower, \c capacity and \c cost.
     112  /// amount of the nodes are written to the \c supply node map
     113  /// (they are signed values). The lower bounds, capacities and costs
     114  /// of the arcs are written to the \c lower, \c capacity and \c cost
     115  /// arc maps.
     116  ///
     117  /// If the capacity of an arc is less than the lower bound, it will
     118  /// be set to "infinite" instead. The actual value of "infinite" is
     119  /// contolled by the \c infty parameter. If it is 0 (the default value),
     120  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,
     121  /// \c std::n