COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
67 added
106 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r514 r610  
    2323lemon/stamp-h2
    2424doc/Doxyfile
    25 cmake/cmake.version
     25cmake/version.cmake
    2626.dirstamp
    2727.libs/*
    2828.deps/*
    2929demo/*.eps
     30m4/libtool.m4
     31m4/ltoptions.m4
     32m4/ltsugar.m4
     33m4/ltversion.m4
     34m4/lt~obsolete.m4
    3035
    3136syntax: regexp
    … …  
    3641^autom4te.cache/.*
    3742^build-aux/.*
    38 ^objs.*/.*
     43^.*objs.*/.*
    3944^test/[a-z_]*$
     45^tools/[a-z-_]*$
    4046^demo/.*_demo$
    41 ^build/.*
     47^.*build.*/.*
    4248^doc/gen-images/.*
    4349CMakeFiles

  • CMakeLists.txt

    r520 r674  
    1010PROJECT(${PROJECT_NAME})
    1111
    12 SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
     12SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
    1313
    1414INCLUDE(FindDoxygen)
    1515INCLUDE(FindGhostscript)
     16FIND_PACKAGE(GLPK 4.33)
     17FIND_PACKAGE(CPLEX)
     18FIND_PACKAGE(COIN)
     19
     20ADD_DEFINITIONS(-DHAVE_CONFIG_H)
     21
     22IF(MSVC)
     23  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
     24# Suppressed warnings:
     25# C4250: 'class1' : inherits 'class2::member' via dominance
     26# C4355: 'this' : used in base member initializer list
     27# C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
     28# C4996: 'function': was declared deprecated
     29ENDIF(MSVC)
     30
     31ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    1632
    1733INCLUDE(CheckTypeSize)
    18 CHECK_TYPE_SIZE("long long" LONG_LONG)
     34CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
    1935
    2036ENABLE_TESTING()
    2137
    2238ADD_SUBDIRECTORY(lemon)
    23 ADD_SUBDIRECTORY(demo)
    24 ADD_SUBDIRECTORY(doc)
    25 ADD_SUBDIRECTORY(test)
     39IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     40  ADD_SUBDIRECTORY(demo)
     41  ADD_SUBDIRECTORY(tools)
     42  ADD_SUBDIRECTORY(doc)
     43  ADD_SUBDIRECTORY(test)
     44ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    2645
    27 IF(WIN32)
    28   SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    29   SET(CPACK_PACKAGE_VENDOR "EGRES")
    30   SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
    31     "LEMON - Library of Efficient Models and Optimization in Networks")
    32   SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
     46IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     47  IF(WIN32)
     48    SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
     49    SET(CPACK_PACKAGE_VENDOR "EGRES")
     50    SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
     51      "LEMON - Library of Efficient Models and Optimization in Networks")
     52    SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
    3353
    34   SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     54    SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
    3555
    36   SET(CPACK_PACKAGE_INSTALL_DIRECTORY
    37     "${PROJECT_NAME} ${PROJECT_VERSION}")
    38   SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
    39     "${PROJECT_NAME} ${PROJECT_VERSION}")
     56    SET(CPACK_PACKAGE_INSTALL_DIRECTORY
     57      "${PROJECT_NAME} ${PROJECT_VERSION}")
     58    SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
     59      "${PROJECT_NAME} ${PROJECT_VERSION}")
    4060
    41   SET(CPACK_COMPONENTS_ALL headers library html_documentation)
     61    SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
    4262
    43   SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    44   SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
    45   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
     63    SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
     64    SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     65    SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
     66    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    4667
    47   SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
    48     "C++ header files")
    49   SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    50     "DLL and import library")
    51   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    52     "Doxygen generated documentation")
     68    SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
     69      "C++ header files")
     70    SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     71      "DLL and import library")
     72    SET(CPACK_COMPONENT_BIN_DESCRIPTION
     73      "Command line utilities")
     74    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     75      "Doxygen generated documentation")
    5376
    54   SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     77    SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
    5578
    56   SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
    57   SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
    58   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     79    SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     80    SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     81    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
    5982
    60   SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
    61     "Components needed to develop software using LEMON")
    62   SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
    63     "Documentation of LEMON")
     83    SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
     84      "Components needed to develop software using LEMON")
     85    SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
     86      "Documentation of LEMON")
    6487
    65   SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     88    SET(CPACK_ALL_INSTALL_TYPES Full Developer)
    6689
    67   SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
    68   SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
    69   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
     90    SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
     91    SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
     92    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
    7093
    71   SET(CPACK_GENERATOR "NSIS")
    72   SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
    73   SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
    74   #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
    75   SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    76   SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
    77   SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
    78   SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
    79   SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
    80   SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
    81     CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
    82     ")
    83   SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
    84     !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
    85     Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
    86     ")
     94    SET(CPACK_GENERATOR "NSIS")
     95    SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
     96    SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     97    #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
     98    SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
     99    SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     100    SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
     101    SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
     102    SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
     103    SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
     104      CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
     105      ")
     106    SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
     107      !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
     108      Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
     109      ")
    87110
    88   INCLUDE(CPack)
    89 ENDIF(WIN32)
     111    INCLUDE(CPack)
     112  ENDIF(WIN32)
     113ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})

  • INSTALL

    r526 r615  
    2828
    2929      This command compiles the non-template part of LEMON into libemon.a
    30       file. It also compiles the programs in the tools and demo subdirectories
    31       when enabled.
     30      file. It also compiles the programs in the tools subdirectory by
     31      default.
    3232
    3333   4. `make check'
    … …  
    7575
    7676  Set the installation prefix to PREFIX. By default it is /usr/local.
    77 
    78 --enable-demo
    79 
    80    Build the examples in the demo subdirectory.
    81 
    82 --disable-demo
    83 
    84    Do not build the examples in the demo subdirectory (default).
    8577
    8678--enable-tools
    … …  
    159151
    160152   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

    r530 r600  
    22copyright/license.
    33
    4 Copyright (C) 2003-2008 Egervary Jeno Kombinatorikus Optimalizalasi
     4Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
    55Kutatocsoport (Egervary Combinatorial Optimization Research Group,
    66EGRES).

  • Makefile.am

    r503 r614  
    11ACLOCAL_AMFLAGS = -I m4
     2
     3AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    24
    35AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
    … …  
    1012        m4/lx_check_glpk.m4 \
    1113        m4/lx_check_soplex.m4 \
     14        m4/lx_check_clp.m4 \
     15        m4/lx_check_cbc.m4 \
    1216        CMakeLists.txt \
    1317        cmake/FindGhostscript.cmake \
     18        cmake/FindGLPK.cmake \
    1419        cmake/version.cmake.in \
    1520        cmake/version.cmake \
    … …  
    3742include test/Makefile.am
    3843include doc/Makefile.am
    39 include demo/Makefile.am
    4044include tools/Makefile.am
     45
     46DIST_SUBDIRS = demo
     47
     48demo:
     49        $(MAKE) $(AM_MAKEFLAGS) -C demo
    4150
    4251MRPROPERFILES = \
    … …  
    6675        bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
    6776
    68 .PHONY: mrproper dist-bz2 distcheck-bz2
     77.PHONY: demo mrproper dist-bz2 distcheck-bz2

  • configure.ac

    r515 r674  
    2020AC_CONFIG_HEADERS([config.h lemon/config.h])
    2121
    22 lx_cmdline_cxxflags_set=${CXXFLAGS+set}
    23 
    2422dnl Do compilation tests using the C++ compiler.
    2523AC_LANG([C++])
    … …  
    2826AC_CHECK_TYPE(long long, [long_long_found=yes], [long_long_found=no])
    2927if test x"$long_long_found" = x"yes"; then
    30   AC_DEFINE([HAVE_LONG_LONG], [1], [Define to 1 if you have long long.])
     28  AC_DEFINE([LEMON_HAVE_LONG_LONG], [1], [Define to 1 if you have long long.])
    3129fi
    3230
    … …  
    5351
    5452dnl Set custom compiler flags when using g++.
    55 if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
    56   CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
     53if test "$GXX" = yes -a "$ICC" = no; then
     54  WARNINGCXXFLAGS="-Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
    5755fi
     56AC_SUBST([WARNINGCXXFLAGS])
    5857
    5958dnl Checks for libraries.
    60 #LX_CHECK_GLPK
    61 #LX_CHECK_CPLEX
    62 #LX_CHECK_SOPLEX
     59LX_CHECK_GLPK
     60LX_CHECK_CPLEX
     61LX_CHECK_SOPLEX
     62LX_CHECK_COIN
    6363
    64 dnl Disable/enable building the demo programs.
    65 AC_ARG_ENABLE([demo],
    66 AS_HELP_STRING([--enable-demo], [build the demo programs])
    67 AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
    68               [], [enable_demo=no])
    69 AC_MSG_CHECKING([whether to build the demo programs])
    70 if test x"$enable_demo" != x"no"; then
    71   AC_MSG_RESULT([yes])
    72 else
    73   AC_MSG_RESULT([no])
    74 fi
    75 AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
     64AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
     65AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
    7666
    7767dnl Disable/enable building the binary tools.
    … …  
    10898AC_CONFIG_FILES([
    10999Makefile
     100demo/Makefile
    110101cmake/version.cmake
    111102doc/Doxyfile
    … …  
    121112echo
    122113echo C++ compiler.................. : $CXX
    123 echo C++ compiles flags............ : $CXXFLAGS
     114echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    124115echo
    125116echo Compiler supports long long... : $long_long_found
    126117echo
    127 #echo GLPK support.................. : $lx_glpk_found
    128 #echo CPLEX support................. : $lx_cplex_found
    129 #echo SOPLEX support................ : $lx_soplex_found
    130 #echo
    131 echo Build demo programs........... : $enable_demo
     118echo GLPK support.................. : $lx_glpk_found
     119echo CPLEX support................. : $lx_cplex_found
     120echo SOPLEX support................ : $lx_soplex_found
     121echo CLP support................... : $lx_clp_found
     122echo CBC support................... : $lx_cbc_found
     123echo
    132124echo Build additional tools........ : $enable_tools
    133125echo

  • demo/CMakeLists.txt

    r225 r674  
    1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(
     2  ${PROJECT_SOURCE_DIR}
     3  ${PROJECT_BINARY_DIR}
     4)
    25
    3 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
     6LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
    47
    58SET(DEMOS

  • demo/Makefile.am

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

  • demo/arg_parser_demo.cc

    r311 r463  
    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).

  • demo/graph_to_eps_demo.cc

    r313 r659  
    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).
    … …  
    8686    coords(coords).
    8787    title("Sample .eps figure").
    88     copyright("(C) 2003-2008 LEMON Project").
     88    copyright("(C) 2003-2009 LEMON Project").
    8989    run();
    9090
    … …  
    9393    coords(coords).
    9494    title("Sample .eps figure").
    95     copyright("(C) 2003-2008 LEMON Project").
     95    copyright("(C) 2003-2009 LEMON Project").
    9696    absoluteNodeSizes().absoluteArcWidths().
    9797    nodeScale(2).nodeSizes(sizes).
    … …  
    106106  graphToEps(g,"graph_to_eps_demo_out_3_arr.eps").
    107107    title("Sample .eps figure (with arrowheads)").
    108     copyright("(C) 2003-2008 LEMON Project").
     108    copyright("(C) 2003-2009 LEMON Project").
    109109    absoluteNodeSizes().absoluteArcWidths().
    110110    nodeColors(composeMap(palette,colors)).
    … …  
    133133  graphToEps(g,"graph_to_eps_demo_out_4_par.eps").
    134134    title("Sample .eps figure (parallel arcs)").
    135     copyright("(C) 2003-2008 LEMON Project").
     135    copyright("(C) 2003-2009 LEMON Project").
    136136    absoluteNodeSizes().absoluteArcWidths().
    137137    nodeShapes(shapes).
    … …  
    148148  graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps").
    149149    title("Sample .eps figure (parallel arcs and arrowheads)").
    150     copyright("(C) 2003-2008 LEMON Project").
     150    copyright("(C) 2003-2009 LEMON Project").
    151151    absoluteNodeSizes().absoluteArcWidths().
    152152    nodeScale(2).nodeSizes(sizes).
    … …  
    164164  graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps").
    165165    title("Sample .eps figure (fits to A4)").
    166     copyright("(C) 2003-2008 LEMON Project").
     166    copyright("(C) 2003-2009 LEMON Project").
    167167    scaleToA4().
    168168    absoluteNodeSizes().absoluteArcWidths().
    … …  
    183183  ListDigraph::NodeMap<Point> hcoords(h);
    184184
    185   int cols=int(sqrt(double(palette.size())));
     185  int cols=int(std::sqrt(double(palette.size())));
    186186  for(int i=0;i<int(paletteW.size());i++) {
    187187    Node n=h.addNode();
    … …  
    194194    scale(60).
    195195    title("Sample .eps figure (Palette demo)").
    196     copyright("(C) 2003-2008 LEMON Project").
     196    copyright("(C) 2003-2009 LEMON Project").
    197197    coords(hcoords).
    198198    absoluteNodeSizes().absoluteArcWidths().

  • demo/lgf_demo.cc

    r294 r463  
    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).

  • doc/CMakeLists.txt

    r520 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
     21      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
    1723      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
    1824      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
    … …  
    2026      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
    2127      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
    2229      COMMAND rm -rf html
    2330      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    … …  
    2734      COMMAND if exist gen-images rmdir /s /q gen-images
    2835      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
    2942      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
    3043      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
    … …  
    3245      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
    3346      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
    3448      COMMAND if exist html rmdir /s /q html
    3549      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile

  • doc/Doxyfile.in

    r316 r379  
    6767ENABLED_SECTIONS       =
    6868MAX_INITIALIZER_LINES  = 5
    69 SHOW_USED_FILES        = YES
     69SHOW_USED_FILES        = NO
    7070SHOW_DIRECTORIES       = YES
    7171SHOW_FILES             = YES

  • doc/Makefile.am

    r317 r634  
    1515
    1616DOC_EPS_IMAGES18 = \
     17        grid_graph.eps \
    1718        nodeshape_0.eps \
    1819        nodeshape_1.eps \
    … …  
    2122        nodeshape_4.eps
    2223
     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
    2332DOC_EPS_IMAGES = \
    24         $(DOC_EPS_IMAGES18)
     33        $(DOC_EPS_IMAGES18) \
     34        $(DOC_EPS_IMAGES27)
    2535
    2636DOC_PNG_IMAGES = \
    … …  
    3848        if test ${gs_found} = yes; then \
    3949          $(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=$@ $<; \
    4061        else \
    4162          echo; \

  • doc/coding_style.dox

    r210 r463  
    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).

  • doc/dirs.dox

    r318 r463  
    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).
    … …  
    7272\brief Auxiliary tools for implementation.
    7373
    74 This directory contains some auxiliary classes for implementing graphs, 
     74This directory contains some auxiliary classes for implementing graphs,
    7575maps and some other classes.
    7676As a user you typically don't have to deal with these files.

  • doc/groups.dox

    r318 r658  
    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).
    … …  
    1717 */
    1818
     19namespace lemon {
     20
    1921/**
    2022@defgroup datas Data Structures
    21 This group describes the several data structures implemented in LEMON.
     23This group contains the several data structures implemented in LEMON.
    2224*/
    2325
    … …  
    6163
    6264/**
     65@defgroup graph_adaptors Adaptor Classes for Graphs
     66@ingroup graphs
     67\brief Adaptor classes for digraphs and graphs
     68
     69This group contains several useful adaptor classes for digraphs and graphs.
     70
     71The main parts of LEMON are the different graph structures, generic
     72graph algorithms, graph concepts, which couple them, and graph
     73adaptors. While the previous notions are more or less clear, the
     74latter one needs further explanation. Graph adaptors are graph classes
     75which serve for considering graph structures in different ways.
     76
     77A short example makes this much clearer.  Suppose that we have an
     78instance \c g of a directed graph type, say ListDigraph and an algorithm
     79\code
     80template <typename Digraph>
     81int algorithm(const Digraph&);
     82\endcode
     83is needed to run on the reverse oriented graph.  It may be expensive
     84(in time or in memory usage) to copy \c g with the reversed
     85arcs.  In this case, an adaptor class is used, which (according
     86to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
     87The adaptor uses the original digraph structure and digraph operations when
     88methods of the reversed oriented graph are called.  This means that the adaptor
     89have minor memory usage, and do not perform sophisticated algorithmic
     90actions.  The purpose of it is to give a tool for the cases when a
     91graph have to be used in a specific alteration.  If this alteration is
     92obtained by a usual construction like filtering the node or the arc set or
     93considering a new orientation, then an adaptor is worthwhile to use.
     94To come back to the reverse oriented graph, in this situation
     95\code
     96template<typename Digraph> class ReverseDigraph;
     97\endcode
     98template class can be used. The code looks as follows
     99\code
     100ListDigraph g;
     101ReverseDigraph<ListDigraph> rg(g);
     102int result = algorithm(rg);
     103\endcode
     104During running the algorithm, the original digraph \c g is untouched.
     105This techniques give rise to an elegant code, and based on stable
     106graph adaptors, complex algorithms can be implemented easily.
     107
     108In flow, circulation and matching problems, the residual
     109graph is of particular importance. Combining an adaptor implementing
     110this with shortest path algorithms or minimum mean cycle algorithms,
     111a range of weighted and cardinality optimization algorithms can be
     112obtained. For other examples, the interested user is referred to the
     113detailed documentation of particular adaptors.
     114
     115The behavior of graph adaptors can be very different. Some of them keep
     116capabilities of the original graph while in other cases this would be
     117meaningless. This means that the concepts that they meet depend
     118on the graph adaptor, and the wrapped graph.
     119For example, if an arc of a reversed digraph is deleted, this is carried
     120out by deleting the corresponding arc of the original digraph, thus the
     121adaptor modifies the original digraph.
     122However in case of a residual digraph, this operation has no sense.
     123
     124Let us stand one more example here to simplify your work.
     125ReverseDigraph has constructor
     126\code
     127ReverseDigraph(Digraph& digraph);
     128\endcode
     129This means that in a situation, when a <tt>const %ListDigraph&</tt>
     130reference to a graph is given, then it have to be instantiated with
     131<tt>Digraph=const %ListDigraph</tt>.
     132\code
     133int algorithm1(const ListDigraph& g) {
     134  ReverseDigraph<const ListDigraph> rg(g);
     135  return algorithm2(rg);
     136}
     137\endcode
     138*/
     139
     140/**
    63141@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    64142@ingroup graphs
    65143\brief Graph types between real graphs and graph adaptors.
    66144
    67 This group describes some graph types between real graphs and graph adaptors.
     145This group contains some graph types between real graphs and graph adaptors.
    68146These classes wrap graphs to give new functionality as the adaptors do it.
    69147On the other hand they are not light-weight structures as the adaptors.
    … …  
    75153\brief Map structures implemented in LEMON.
    76154
    77 This group describes the map structures implemented in LEMON.
     155This group contains the map structures implemented in LEMON.
    78156
    79157LEMON provides several special purpose maps and map adaptors that e.g. combine
    … …  
    88166\brief Special graph-related maps.
    89167
    90 This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
     168This group contains maps that are specifically designed to assign
     169values to the nodes and arcs/edges of graphs.
     170
     171If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     172\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    92173*/
    93174
    … …  
    97178\brief Tools to create new maps from existing ones
    98179
    99 This group describes map adaptors that are used to create "implicit"
     180This group contains map adaptors that are used to create "implicit"
    100181maps from other maps.
    101182
    102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     183Most of them are \ref concepts::ReadMap "read-only maps".
    103184They can make arithmetic and logical operations between one or two maps
    104185(negation, shifting, addition, multiplication, logical 'and', 'or',
    … …  
    160241\brief Two dimensional data storages implemented in LEMON.
    161242
    162 This group describes two dimensional data storages implemented in LEMON.
     243This group contains two dimensional data storages implemented in LEMON.
    163244*/
    164245
    … …  
    168249\brief %Path structures implemented in LEMON.
    169250
    170 This group describes the path structures implemented in LEMON.
     251This group contains the path structures implemented in LEMON.
    171252
    172253LEMON provides flexible data structures to work with paths.
    … …  
    184265\brief Auxiliary data structures implemented in LEMON.
    185266
    186 This group describes some data structures implemented in LEMON in
     267This group contains some data structures implemented in LEMON in
    187268order to make it easier to implement combinatorial algorithms.
    188269*/
    … …  
    190271/**
    191272@defgroup algs Algorithms
    192 \brief This group describes the several algorithms
     273\brief This group contains the several algorithms
    193274implemented in LEMON.
    194275
    195 This group describes the several algorithms
     276This group contains the several algorithms
    196277implemented in LEMON.
    197278*/
    … …  
    202283\brief Common graph search algorithms.
    203284
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     285This group contains the common graph search algorithms, namely
     286\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    206287*/
    207288
    … …  
    211292\brief Algorithms for finding shortest paths.
    212293
    213 This group describes the algorithms for finding shortest paths in graphs.
     294This group contains the algorithms for finding shortest paths in digraphs.
     295
     296 - \ref Dijkstra algorithm for finding shortest paths from a source node
     297   when all arc lengths are non-negative.
     298 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
     299   from a source node when arc lenghts can be either positive or negative,
     300   but the digraph should not contain directed cycles with negative total
     301   length.
     302 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
     303   for solving the \e all-pairs \e shortest \e paths \e problem when arc
     304   lenghts can be either positive or negative, but the digraph should
     305   not contain directed cycles with negative total length.
     306 - \ref Suurballe A successive shortest path algorithm for finding
     307   arc-disjoint paths between two nodes having minimum total length.
    214308*/
    215309
    … …  
    219313\brief Algorithms for finding maximum flows.
    220314
    221 This group describes the algorithms for finding maximum flows and
     315This group contains the algorithms for finding maximum flows and
    222316feasible circulations.
    223317
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
    229 
    230 \f[ 0 \le f_a \le c_a \f]
    231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
    232 \qquad \forall u \in V \setminus \{s,t\}\f]
    233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
     318The \e maximum \e flow \e problem is to find a flow of maximum value between
     319a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     320digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     321\f$s, t \in V\f$ source and target nodes.
     322A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
     323following optimization problem.
     324
     325\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     326\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     327    \quad \forall u\in V\setminus\{s,t\} \f]
     328\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    234329
    235330LEMON contains several algorithms for solving maximum flow problems:
    236 - \ref lemon::EdmondsKarp "Edmonds-Karp"
    237 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
    238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
    240 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming problem of the maximum flow.
     331- \ref EdmondsKarp Edmonds-Karp algorithm.
     332- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
     333- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
     334- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
     335
     336In most cases the \ref Preflow "Preflow" algorithm provides the
     337fastest method for computing a maximum flow. All implementations
     338provides functions to also query the minimum cut, which is the dual
     339problem of the maximum flow.
    245340*/
    246341
    … …  
    251346\brief Algorithms for finding minimum cost flows and circulations.
    252347
    253 This group describes the algorithms for finding minimum cost flows and
     348This group contains the algorithms for finding minimum cost flows and
    254349circulations.
     350
     351The \e minimum \e cost \e flow \e problem is to find a feasible flow of
     352minimum total cost from a set of supply nodes to a set of demand nodes
     353in a network with capacity constraints (lower and upper bounds)
     354and arc costs.
     355Formally, let \f$G=(V,A)\f$ be a digraph,
     356\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
     357upper bounds for the flow values on the arcs, for which
     358\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
     359\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
     360on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
     361signed supply values of the nodes.
     362If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
     363supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
     364\f$-sup(u)\f$ demand.
     365A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
     366of the following optimization problem.
     367
     368\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
     369\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
     370    sup(u) \quad \forall u\in V \f]
     371\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
     372
     373The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
     374zero or negative in order to have a feasible solution (since the sum
     375of the expressions on the left-hand side of the inequalities is zero).
     376It means that the total demand must be greater or equal to the total
     377supply and all the supplies have to be carried out from the supply nodes,
     378but there could be demands that are not satisfied.
     379If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
     380constraints have to be satisfied with equality, i.e. all demands
     381have to be satisfied and all supplies have to be used.
     382
     383If you need the opposite inequalities in the supply/demand constraints
     384(i.e. the total demand is less than the total supply and all the demands
     385have to be satisfied while there could be supplies that are not used),
     386then you could easily transform the problem to the above form by reversing
     387the direction of the arcs and taking the negative of the supply values
     388(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
     389However \ref NetworkSimplex algorithm also supports this form directly
     390for the sake of convenience.
     391
     392A feasible solution for this problem can be found using \ref Circulation.
     393
     394Note that the above formulation is actually more general than the usual
     395definition of the minimum cost flow problem, in which strict equalities
     396are required in the supply/demand contraints, i.e.
     397
     398\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
     399    sup(u) \quad \forall u\in V. \f]
     400
     401However if the sum of the supply values is zero, then these two problems
     402are equivalent. So if you need the equality form, you have to ensure this
     403additional contraint for the algorithms.
     404
     405The dual solution of the minimum cost flow problem is represented by node
     406potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
     407An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
     408is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
     409node potentials the following \e complementary \e slackness optimality
     410conditions hold.
     411
     412 - For all \f$uv\in A\f$ arcs:
     413   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
     414   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
     415   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
     416 - For all \f$u\in V\f$:
     417   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
     418     then \f$\pi(u)=0\f$.
     419 
     420Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
     421\f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
     422\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
     423
     424All algorithms provide dual solution (node potentials) as well
     425if an optimal flow is found.
     426
     427LEMON contains several algorithms for solving minimum cost flow problems.
     428 - \ref NetworkSimplex Primal Network Simplex algorithm with various
     429   pivot strategies.
     430 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
     431   cost scaling.
     432 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
     433   capacity scaling.
     434 - \ref CancelAndTighten The Cancel and Tighten algorithm.
     435 - \ref CycleCanceling Cycle-Canceling algorithms.
     436
     437Most of these implementations support the general inequality form of the
     438minimum cost flow problem, but CancelAndTighten and CycleCanceling
     439only support the equality form due to the primal method they use.
     440
     441In general NetworkSimplex is the most efficient implementation,
     442but in special cases other algorithms could be faster.
     443For example, if the total supply and/or capacities are rather small,
     444CapacityScaling is usually the fastest algorithm (without effective scaling).
    255445*/
    256446
    … …  
    261451\brief Algorithms for finding minimum cut in graphs.
    262452
    263 This group describes the algorithms for finding minimum cut in graphs.
    264 
    265 The minimum cut problem is to find a non-empty and non-complete
    266 \f$X\f$ subset of the vertices with minimum overall capacity on
    267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
    268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     453This group contains the algorithms for finding minimum cut in graphs.
     454
     455The \e minimum \e cut \e problem is to find a non-empty and non-complete
     456\f$X\f$ subset of the nodes with minimum overall capacity on
     457outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     458\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269459cut is the \f$X\f$ solution of the next optimization problem:
    270460
    271461\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     462    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    273463
    274464LEMON contains several algorithms related to minimum cut problems:
    275465
    276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
    277   in directed graphs
    278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
    279   calculate minimum cut in undirected graphs
    280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
    281   pairs minimum cut in undirected graphs
     466- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     467  in directed graphs.
     468- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     469  calculating minimum cut in undirected graphs.
     470- \ref GomoryHu "Gomory-Hu tree computation" for calculating
     471  all-pairs minimum cut in undirected graphs.
    282472
    283473If you want to find minimum cut just between two distinict nodes,
    284 please see the \ref max_flow "Maximum Flow page".
    285 */
    286 
    287 /**
    288 @defgroup graph_prop Connectivity and Other Graph Properties
     474see the \ref max_flow "maximum flow problem".
     475*/
     476
     477/**
     478@defgroup graph_properties Connectivity and Other Graph Properties
    289479@ingroup algs
    290480\brief Algorithms for discovering the graph properties
    291481
    292 This group describes the algorithms for discovering the graph properties
     482This group contains the algorithms for discovering the graph properties
    293483like connectivity, bipartiteness, euler property, simplicity etc.
    294484
    … …  
    302492\brief Algorithms for planarity checking, embedding and drawing
    303493
    304 This group describes the algorithms for planarity checking,
     494This group contains the algorithms for planarity checking,
    305495embedding and drawing.
    306496
    … …  
    314504\brief Algorithms for finding matchings in graphs and bipartite graphs.
    315505
    316 This group contains algorithm objects and functions to calculate
     506This group contains the algorithms for calculating
    317507matchings in graphs and bipartite graphs. The general matching problem is
    318 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.
    319510
    320511There are several different algorithms for calculate matchings in
    321512graphs.  The matching problems in bipartite graphs are generally
    322513easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     514can be finding maximum cardinality, maximum weight or minimum cost
    324515matching. The search can be constrained to find perfect or
    325516maximum cardinality matching.
    326517
    327 LEMON contains the next algorithms:
    328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
    329   augmenting path algorithm for calculate maximum cardinality matching in
    330   bipartite graphs
    331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
    332   algorithm for calculate maximum cardinality matching in bipartite graphs
    333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
    334   Successive shortest path algorithm for calculate maximum weighted matching
    335   and maximum weighted bipartite matching in bipartite graph
    336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
    337   Successive shortest path algorithm for calculate minimum cost maximum
    338   matching in bipartite graph
    339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
    340   for calculate maximum cardinality matching in general graph
    341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
    342   shrinking algorithm for calculate maximum weighted matching in general
    343   graph
    344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
    345   Edmond's blossom shrinking algorithm for calculate maximum weighted
    346   perfect matching in general graph
     518The matching algorithms implemented in LEMON:
     519- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
     520  for calculating maximum cardinality matching in bipartite graphs.
     521- \ref PrBipartiteMatching Push-relabel algorithm
     522  for calculating maximum cardinality matching in bipartite graphs.
     523- \ref MaxWeightedBipartiteMatching
     524  Successive shortest path algorithm for calculating maximum weighted
     525  matching and maximum weighted bipartite matching in bipartite graphs.
     526- \ref MinCostMaxBipartiteMatching
     527  Successive shortest path algorithm for calculating minimum cost maximum
     528  matching in bipartite graphs.
     529- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     530  maximum cardinality matching in general graphs.
     531- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     532  maximum weighted matching in general graphs.
     533- \ref MaxWeightedPerfectMatching
     534  Edmond's blossom shrinking algorithm for calculating maximum weighted
     535  perfect matching in general graphs.
    347536
    348537\image html bipartite_matching.png
    … …  
    355544\brief Algorithms for finding a minimum cost spanning tree in a graph.
    356545
    357 This group describes the algorithms for finding a minimum cost spanning
    358 tree in a graph
     546This group contains the algorithms for finding a minimum cost spanning
     547tree in a graph.
    359548*/
    360549
    … …  
    364553\brief Auxiliary algorithms implemented in LEMON.
    365554
    366 This group describes some algorithms implemented in LEMON
     555This group contains some algorithms implemented in LEMON
    367556in order to make it easier to implement complex algorithms.
    368557*/
    … …  
    373562\brief Approximation algorithms.
    374563
    375 This group describes the approximation and heuristic algorithms
     564This group contains the approximation and heuristic algorithms
    376565implemented in LEMON.
    377566*/
    … …  
    379568/**
    380569@defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
     570\brief This group contains some general optimization frameworks
    382571implemented in LEMON.
    383572
    384 This group describes some general optimization frameworks
     573This group contains some general optimization frameworks
    385574implemented in LEMON.
    386575*/
    … …  
    391580\brief Lp and Mip solver interfaces for LEMON.
    392581
    393 This group describes Lp and Mip solver interfaces for LEMON. The
     582This group contains Lp and Mip solver interfaces for LEMON. The
    394583various LP solvers could be used in the same manner with this
    395584interface.
    … …  
    410599\brief Metaheuristics for LEMON library.
    411600
    412 This group describes some metaheuristic optimization tools.
     601This group contains some metaheuristic optimization tools.
    413602*/
    414603
    … …  
    425614\brief Simple basic graph utilities.
    426615
    427 This group describes some simple basic graph utilities.
     616This group contains some simple basic graph utilities.
    428617*/
    429618
    … …  
    433622\brief Tools for development, debugging and testing.
    434623
    435 This group describes several useful tools for development,
     624This group contains several useful tools for development,
    436625debugging and testing.
    437626*/
    … …  
    442631\brief Simple tools for measuring the performance of algorithms.
    443632
    444 This group describes simple tools for measuring the performance
     633This group contains simple tools for measuring the performance
    445634of algorithms.
    446635*/
    … …  
    451640\brief Exceptions defined in LEMON.
    452641
    453 This group describes the exceptions defined in LEMON.
     642This group contains the exceptions defined in LEMON.
    454643*/
    455644
    … …  
    458647\brief Graph Input-Output methods
    459648
    460 This group describes the tools for importing and exporting graphs
     649This group contains the tools for importing and exporting graphs
    461650and graph related data. Now it supports the \ref lgf-format
    462651"LEMON Graph Format", the \c DIMACS format and the encapsulated
    … …  
    465654
    466655/**
    467 @defgroup lemon_io LEMON Input-Output
     656@defgroup lemon_io LEMON Graph Format
    468657@ingroup io_group
    469658\brief Reading and writing LEMON Graph Format.
    470659
    471 This group describes methods for reading and writing
     660This group contains methods for reading and writing
    472661\ref lgf-format "LEMON Graph Format".
    473662*/
    … …  
    478667\brief General \c EPS drawer and graph exporter
    479668
    480 This group describes general \c EPS drawing methods and special
     669This group contains general \c EPS drawing methods and special
    481670graph exporting tools.
     671*/
     672
     673/**
     674@defgroup dimacs_group DIMACS format
     675@ingroup io_group
     676\brief Read and write files in DIMACS format
     677
     678Tools to read a digraph from or write it to a file in DIMACS format data.
     679*/
     680
     681/**
     682@defgroup nauty_group NAUTY Format
     683@ingroup io_group
     684\brief Read \e Nauty format
     685
     686Tool to read graphs from \e Nauty format data.
    482687*/
    483688
    … …  
    486691\brief Skeleton classes and concept checking classes
    487692
    488 This group describes the data/algorithm skeletons and concept checking
     693This group contains the data/algorithm skeletons and concept checking
    489694classes implemented in LEMON.
    490695
    … …  
    516721\brief Skeleton and concept checking classes for graph structures
    517722
    518 This group describes the skeletons and concept checking classes of LEMON's
     723This group contains the skeletons and concept checking classes of LEMON's
    519724graph structures and helper classes used to implement these.
    520725*/
    … …  
    525730\brief Skeleton and concept checking classes for maps
    526731
    527 This group describes the skeletons and concept checking classes of maps.
     732This group contains the skeletons and concept checking classes of maps.
    528733*/
    529734
    … …  
    531736\anchor demoprograms
    532737
    533 @defgroup demos Demo programs
     738@defgroup demos Demo Programs
    534739
    535740Some demo programs are listed here. Their full source codes can be found in
    536741the \c demo subdirectory of the source tree.
    537742
    538 It order to compile them, use <tt>--enable-demo</tt> configure option when
    539 build the library.
    540 */
    541 
    542 /**
    543 @defgroup tools Standalone utility applications
     743In order to compile them, use the <tt>make demo</tt> or the
     744<tt>make check</tt> commands.
     745*/
     746
     747/**
     748@defgroup tools Standalone Utility Applications
    544749
    545750Some utility applications are listed here.
    … …  
    549754*/
    550755
     756}

  • doc/lgf.dox

    r313 r463  
    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).

  • doc/license.dox

    r209 r463  
    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).

  • doc/mainpage.dox

    r314 r606  
    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).
    … …  
    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

  • doc/migration.dox

    r314 r463  
    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).
    … …  
    2626
    2727Many of these changes adjusted automatically by the
    28 <tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
     28<tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
    2929update are typeset <b>boldface</b>.
    3030
    … …  
    5454
    5555\warning
    56 <b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
    57 the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
    58 in strings, comments etc. as well as in all identifiers.</b>
     56<b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph,
     57\c ugraph, \c edge and \c uedge in your own identifiers and in
     58strings, comments etc. as well as in all LEMON specific identifiers.
     59So use the script carefully and make a backup copy of your source files
     60before applying the script to them.</b>
    5961
    6062\section migration-lgf LGF tools

  • doc/named-param.dox

    r269 r463  
    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).

  • doc/namespaces.dox

    r209 r463  
    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).

  • doc/template.h

    r209 r463  
    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).

  • lemon/CMakeLists.txt

    r511 r674  
    1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(
     2  ${PROJECT_SOURCE_DIR}
     3  ${PROJECT_BINARY_DIR}
     4)
    25
    3 ADD_LIBRARY(lemon
     6CONFIGURE_FILE(
     7  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
     8  ${CMAKE_CURRENT_BINARY_DIR}/config.h
     9)
     10
     11SET(LEMON_SOURCES
    412  arg_parser.cc
    513  base.cc
    614  color.cc
     15  lp_base.cc
     16  lp_skeleton.cc
    717  random.cc
    818  bits/windows.cc
    919)
     20
     21IF(LEMON_HAVE_GLPK)
     22  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
     23  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
     24  IF(WIN32)
     25    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
     26    INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
     27    INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
     28  ENDIF(WIN32)
     29ENDIF(LEMON_HAVE_GLPK)
     30
     31IF(LEMON_HAVE_CPLEX)
     32  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
     33  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
     34ENDIF(LEMON_HAVE_CPLEX)
     35
     36IF(LEMON_HAVE_CLP)
     37  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
     38  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     39ENDIF(LEMON_HAVE_CLP)
     40
     41IF(LEMON_HAVE_CBC)
     42  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
     43  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     44ENDIF(LEMON_HAVE_CBC)
     45
     46ADD_LIBRARY(lemon ${LEMON_SOURCES})
    1047
    1148INSTALL(
    … …  
    1956  COMPONENT headers
    2057  FILES_MATCHING PATTERN "*.h")
     58
     59INSTALL(
     60  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
     61  DESTINATION include/lemon
     62  COMPONENT headers)

  • lemon/Makefile.am

    r511 r674  
    88
    99lemon_libemon_la_SOURCES = \
    10         lemon/arg_parser.cc \
    11         lemon/base.cc \
    12         lemon/color.cc \
    13         lemon/random.cc \
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
     13        lemon/lp_base.cc \
     14        lemon/lp_skeleton.cc \
     15        lemon/random.cc \
    1416        lemon/bits/windows.cc
    1517
    16 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    17 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     18
     19lemon_libemon_la_CXXFLAGS = \
     20        $(AM_CXXFLAGS) \
     21        $(GLPK_CFLAGS) \
     22        $(CPLEX_CFLAGS) \
     23        $(SOPLEX_CXXFLAGS) \
     24        $(CLP_CXXFLAGS) \
     25        $(CBC_CXXFLAGS)
     26
     27lemon_libemon_la_LDFLAGS = \
     28        $(GLPK_LIBS) \
     29        $(CPLEX_LIBS) \
     30        $(SOPLEX_LIBS) \
     31        $(CLP_LIBS) \
     32        $(CBC_LIBS)
     33
     34if HAVE_GLPK
     35lemon_libemon_la_SOURCES += lemon/glpk.cc
     36endif
     37
     38if HAVE_CPLEX
     39lemon_libemon_la_SOURCES += lemon/cplex.cc
     40endif
     41
     42if HAVE_SOPLEX
     43lemon_libemon_la_SOURCES += lemon/soplex.cc
     44endif
     45
     46if HAVE_CLP
     47lemon_libemon_la_SOURCES += lemon/clp.cc
     48endif
     49
     50if HAVE_CBC
     51lemon_libemon_la_SOURCES += lemon/cbc.cc
     52endif
    1853
    1954lemon_HEADERS += \
    20         lemon/arg_parser.h \
     55        lemon/adaptors.h \
     56        lemon/arg_parser.h \
    2157        lemon/assert.h \
    22         lemon/bfs.h \
    23         lemon/bin_heap.h \
    24         lemon/color.h \
     58        lemon/bfs.h \
     59        lemon/bin_heap.h \
     60        lemon/circulation.h \
     61        lemon/clp.h \
     62        lemon/color.h \
    2563        lemon/concept_check.h \
    26         lemon/counter.h \
     64        lemon/config.h \
     65        lemon/connectivity.h \
     66        lemon/counter.h \
    2767        lemon/core.h \
    28         lemon/dfs.h \
    29         lemon/dijkstra.h \
    30         lemon/dim2.h \
     68        lemon/cplex.h \
     69        lemon/dfs.h \
     70        lemon/dijkstra.h \
     71        lemon/dim2.h \
     72        lemon/dimacs.h \
     73        lemon/edge_set.h \
     74        lemon/elevator.h \
    3175        lemon/error.h \
    32         lemon/graph_to_eps.h \
     76        lemon/euler.h \
     77        lemon/full_graph.h \
     78        lemon/glpk.h \
     79        lemon/gomory_hu.h \
     80        lemon/graph_to_eps.h \
     81        lemon/grid_graph.h \
     82        lemon/hypercube_graph.h \
    3383        lemon/kruskal.h \
     84        lemon/hao_orlin.h \
    3485        lemon/lgf_reader.h \
    3586        lemon/lgf_writer.h \
    3687        lemon/list_graph.h \
     88        lemon/lp.h \
     89        lemon/lp_base.h \
     90        lemon/lp_skeleton.h \
     91        lemon/list_graph.h \
    3792        lemon/maps.h \
     93        lemon/matching.h \
    3894        lemon/math.h \
     95        lemon/min_cost_arborescence.h \
     96        lemon/nauty_reader.h \
     97        lemon/network_simplex.h \
    3998        lemon/path.h \
    40         lemon/random.h \
     99        lemon/preflow.h \
     100        lemon/radix_sort.h \
     101        lemon/random.h \
    41102        lemon/smart_graph.h \
    42         lemon/time_measure.h \
    43         lemon/tolerance.h \
     103        lemon/soplex.h \
     104        lemon/suurballe.h \
     105        lemon/time_measure.h \
     106        lemon/tolerance.h \
    44107        lemon/unionfind.h \
    45108        lemon/bits/windows.h
    … …  
    49112        lemon/bits/array_map.h \
    50113        lemon/bits/base_extender.h \
    51         lemon/bits/bezier.h \
     114        lemon/bits/bezier.h \
    52115        lemon/bits/default_map.h \
    53         lemon/bits/enable_if.h \
     116        lemon/bits/edge_set_extender.h \
     117        lemon/bits/enable_if.h \
     118        lemon/bits/graph_adaptor_extender.h \
    54119        lemon/bits/graph_extender.h \
    55120        lemon/bits/map_extender.h \
    56121        lemon/bits/path_dump.h \
     122        lemon/bits/solver_bits.h \
    57123        lemon/bits/traits.h \
     124        lemon/bits/variant.h \
    58125        lemon/bits/vector_map.h
    59126

  • lemon/arg_parser.cc

    r311 r463  
    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).

  • lemon/arg_parser.h

    r311 r463  
    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).

  • lemon/assert.h

    r290 r463  
    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).

  • lemon/base.cc

    r220 r554  
    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).
    … …  
    2424namespace lemon {
    2525
    26   float Tolerance<float>::def_epsilon = 1e-4;
     26  float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
    2727  double Tolerance<double>::def_epsilon = 1e-10;
    2828  long double Tolerance<long double>::def_epsilon = 1e-14;

  • lemon/bfs.h

    r301 r525  
    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).
    … …  
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a PredMap.
    53 
    54     ///This function instantiates a PredMap.
     52    ///Instantiates a \c PredMap.
     53
     54    ///This function instantiates a \ref PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///PredMap.
     56    ///\ref PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
    … …  
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6666    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     67    ///Instantiates a \c ProcessedMap.
     68
     69    ///This function instantiates a \ref ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     71    ///we would like to define the \ref ProcessedMap
    7272#ifdef DOXYGEN
    7373    static ProcessedMap *createProcessedMap(const Digraph &g)
    … …  
    8484    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8585    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     86    ///Instantiates a \c ReachedMap.
     87
     88    ///This function instantiates a \ref ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     90    ///we would like to define the \ref ReachedMap.
    9191    static ReachedMap *createReachedMap(const Digraph &g)
    9292    {
    … …  
    9999    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100100    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     101    ///Instantiates a \c DistMap.
     102
     103    ///This function instantiates a \ref DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     105    ///\ref DistMap.
    106106    static DistMap *createDistMap(const Digraph &g)
    107107    {
    … …  
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default value is \ref ListDigraph. The value of GR is not used
    123   ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
    124   ///\tparam TR Traits class to set various data types used by the algorithm.
    125   ///The default traits class is
    126   ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
    127   ///See \ref BfsDefaultTraits for the documentation of
    128   ///a Bfs traits class.
     122  ///The default type is \ref ListDigraph.
    129123#ifdef DOXYGEN
    130124  template <typename GR,
    … …  
    152146    typedef PredMapPath<Digraph, PredMap> Path;
    153147
    154     ///The traits class.
     148    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    155149    typedef TR Traits;
    156150
    … …  
    214208    typedef Bfs Create;
    215209
    216     ///\name Named template parameters
     210    ///\name Named Template Parameters
    217211
    218212    ///@{
    … …  
    228222    };
    229223    ///\brief \ref named-templ-param "Named parameter" for setting
    230     ///PredMap type.
     224    ///\c PredMap type.
    231225    ///
    232226    ///\ref named-templ-param "Named parameter" for setting
    233     ///PredMap type.
     227    ///\c PredMap type.
     228    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    234229    template <class T>
    235230    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    … …  
    247242    };
    248243    ///\brief \ref named-templ-param "Named parameter" for setting
    249     ///DistMap type.
     244    ///\c DistMap type.
    250245    ///
    251246    ///\ref named-templ-param "Named parameter" for setting
    252     ///DistMap type.
     247    ///\c DistMap type.
     248    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    253249    template <class T>
    254250    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    … …  
    266262    };
    267263    ///\brief \ref named-templ-param "Named parameter" for setting
    268     ///ReachedMap type.
     264    ///\c ReachedMap type.
    269265    ///
    270266    ///\ref named-templ-param "Named parameter" for setting
    271     ///ReachedMap type.
     267    ///\c ReachedMap type.
     268    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    272269    template <class T>
    273270    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    285282    };
    286283    ///\brief \ref named-templ-param "Named parameter" for setting
    287     ///ProcessedMap type.
     284    ///\c ProcessedMap type.
    288285    ///
    289286    ///\ref named-templ-param "Named parameter" for setting
    290     ///ProcessedMap type.
     287    ///\c ProcessedMap type.
     288    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    291289    template <class T>
    292290    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    303301    };
    304302    ///\brief \ref named-templ-param "Named parameter" for setting
    305     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     303    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    306304    ///
    307305    ///\ref named-templ-param "Named parameter" for setting
    308     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     306    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    309307    ///If you don't set it explicitly, it will be automatically allocated.
    310308    struct SetStandardProcessedMap :
    … …  
    341339
    342340    ///Sets the map that stores the predecessor arcs.
    343     ///If you don't use this function before calling \ref run(),
    344     ///it will allocate one. The destructor deallocates this
    345     ///automatically allocated map, of course.
     341    ///If you don't use this function before calling \ref run(Node) "run()"
     342    ///or \ref init(), an instance will be allocated automatically.
     343    ///The destructor deallocates this automatically allocated map,
     344    ///of course.
    346345    ///\return <tt> (*this) </tt>
    347346    Bfs &predMap(PredMap &m)
    … …  
    358357
    359358    ///Sets the map that indicates which nodes are reached.
    360     ///If you don't use this function before calling \ref run(),
    361     ///it will allocate one. The destructor deallocates this
    362     ///automatically allocated map, of course.
     359    ///If you don't use this function before calling \ref run(Node) "run()"
     360    ///or \ref init(), an instance will be allocated automatically.
     361    ///The destructor deallocates this automatically allocated map,
     362    ///of course.
    363363    ///\return <tt> (*this) </tt>
    364364    Bfs &reachedMap(ReachedMap &m)
    … …  
    375375
    376376    ///Sets the map that indicates which nodes are processed.
    377     ///If you don't use this function before calling \ref run(),
    378     ///it will allocate one. The destructor deallocates this
    379     ///automatically allocated map, of course.
     377    ///If you don't use this function before calling \ref run(Node) "run()"
     378    ///or \ref init(), an instance will be allocated automatically.
     379    ///The destructor deallocates this automatically allocated map,
     380    ///of course.
    380381    ///\return <tt> (*this) </tt>
    381382    Bfs &processedMap(ProcessedMap &m)
    … …  
    393394    ///Sets the map that stores the distances of the nodes calculated by
    394395    ///the algorithm.
    395     ///If you don't use this function before calling \ref run(),
    396     ///it will allocate one. The destructor deallocates this
    397     ///automatically allocated map, of course.
     396    ///If you don't use this function before calling \ref run(Node) "run()"
     397    ///or \ref init(), an instance will be allocated automatically.
     398    ///The destructor deallocates this automatically allocated map,
     399    ///of course.
    398400    ///\return <tt> (*this) </tt>
    399401    Bfs &distMap(DistMap &m)
    … …  
    409411  public:
    410412
    411     ///\name Execution control
    412     ///The simplest way to execute the algorithm is to use
    413     ///one of the member functions called \ref lemon::Bfs::run() "run()".
    414     ///\n
    415     ///If you need more control on the execution, first you must call
    416     ///\ref lemon::Bfs::init() "init()", then you can add several source
    417     ///nodes with \ref lemon::Bfs::addSource() "addSource()".
    418     ///Finally \ref lemon::Bfs::start() "start()" will perform the
    419     ///actual path computation.
     413    ///\name Execution Control
     414    ///The simplest way to execute the BFS algorithm is to use one of the
     415    ///member functions called \ref run(Node) "run()".\n
     416    ///If you need more control on the execution, first you have to call
     417    ///\ref init(), then you can add several source nodes with
     418    ///\ref addSource(). Finally the actual path computation can be
     419    ///performed with one of the \ref start() functions.
    420420
    421421    ///@{
    422422
     423    ///\brief Initializes the internal data structures.
     424    ///
    423425    ///Initializes the internal data structures.
    424 
    425     ///Initializes the internal data structures.
    426     ///
    427426    void init()
    428427    {
    … …  
    558557    }
    559558
    560     ///\brief Returns \c false if there are nodes
    561     ///to be processed.
    562     ///
    563     ///Returns \c false if there are nodes
    564     ///to be processed in the queue.
     559    ///Returns \c false if there are nodes to be processed.
     560
     561    ///Returns \c false if there are nodes to be processed
     562    ///in the queue.
    565563    bool emptyQueue() const { return _queue_tail==_queue_head; }
    566564
    567565    ///Returns the number of the nodes to be processed.
    568566
    569     ///Returns the number of the nodes to be processed in the queue.
     567    ///Returns the number of the nodes to be processed
     568    ///in the queue.
    570569    int queueSize() const { return _queue_head-_queue_tail; }
    571570
    … …  
    732731
    733732    ///\name Query Functions
    734     ///The result of the %BFS algorithm can be obtained using these
     733    ///The results of the BFS algorithm can be obtained using these
    735734    ///functions.\n
    736     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
    737     ///"start()" must be called before using them.
     735    ///Either \ref run(Node) "run()" or \ref start() should be called
     736    ///before using them.
    738737
    739738    ///@{
    … …  
    743742    ///Returns the shortest path to a node.
    744743    ///
    745     ///\warning \c t should be reachable from the root(s).
    746     ///
    747     ///\pre Either \ref run() or \ref start() must be called before
    748     ///using this function.
     744    ///\warning \c t should be reached from the root(s).
     745    ///
     746    ///\pre Either \ref run(Node) "run()" or \ref init()
     747    ///must be called before using this function.
    749748    Path path(Node t) const { return Path(*G, *_pred, t); }
    750749
    … …  
    753752    ///Returns the distance of a node from the root(s).
    754753    ///
    755     ///\warning If node \c v is not reachable from the root(s), then
     754    ///\warning If node \c v is not reached from the root(s), then
    756755    ///the return value of this function is undefined.
    757756    ///
    758     ///\pre Either \ref run() or \ref start() must be called before
    759     ///using this function.
     757    ///\pre Either \ref run(Node) "run()" or \ref init()
     758    ///must be called before using this function.
    760759    int dist(Node v) const { return (*_dist)[v]; }
    761760
    … …  
    764763    ///This function returns the 'previous arc' of the shortest path
    765764    ///tree for the node \c v, i.e. it returns the last arc of a
    766     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    767     ///is not reachable from the root(s) or if \c v is a root.
     765    ///shortest path from a root to \c v. It is \c INVALID if \c v
     766    ///is not reached from the root(s) or if \c v is a root.
    768767    ///
    769768    ///The shortest path tree used here is equal to the shortest path
    770769    ///tree used in \ref predNode().
    771770    ///
    772     ///\pre Either \ref run() or \ref start() must be called before
    773     ///using this function.
     771    ///\pre Either \ref run(Node) "run()" or \ref init()
     772    ///must be called before using this function.
    774773    Arc predArc(Node v) const { return (*_pred)[v];}
    775774
    … …  
    778777    ///This function returns the 'previous node' of the shortest path
    779778    ///tree for the node \c v, i.e. it returns the last but one node
    780     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    781     ///if \c v is not reachable from the root(s) or if \c v is a root.
     779    ///from a shortest path from a root to \c v. It is \c INVALID
     780    ///if \c v is not reached from the root(s) or if \c v is a root.
    782781    ///
    783782    ///The shortest path tree used here is equal to the shortest path
    784783    ///tree used in \ref predArc().
    785784    ///
    786     ///\pre Either \ref run() or \ref start() must be called before
    787     ///using this function.
     785    ///\pre Either \ref run(Node) "run()" or \ref init()
     786    ///must be called before using this function.
    788787    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    789788                                  G->source((*_pred)[v]); }
    … …  
    795794    ///of the nodes calculated by the algorithm.
    796795    ///
    797     ///\pre Either \ref run() or \ref init()
     796    ///\pre Either \ref run(Node) "run()" or \ref init()
    798797    ///must be called before using this function.
    799798    const DistMap &distMap() const { return *_dist;}
    … …  
    805804    ///arcs, which form the shortest path tree.
    806805    ///
    807     ///\pre Either \ref run() or \ref init()
     806    ///\pre Either \ref run(Node) "run()" or \ref init()
    808807    ///must be called before using this function.
    809808    const PredMap &predMap() const { return *_pred;}
    810809
    811     ///Checks if a node is reachable from the root(s).
    812 
    813     ///Returns \c true if \c v is reachable from the root(s).
    814     ///\pre Either \ref run() or \ref start()
     810    ///Checks if a node is reached from the root(s).
     811
     812    ///Returns \c true if \c v is reached from the root(s).
     813    ///
     814    ///\pre Either \ref run(Node) "run()" or \ref init()
    815815    ///must be called before using this function.
    816816    bool reached(Node v) const { return (*_reached)[v]; }
    … …  
    958958  /// This auxiliary class is created to implement the
    959959  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
    960   /// It does not have own \ref run() method, it uses the functions
    961   /// and features of the plain \ref Bfs.
     960  /// It does not have own \ref run(Node) "run()" method, it uses the
     961  /// functions and features of the plain \ref Bfs.
    962962  ///
    963963  /// This class should only be used through the \ref bfs() function,
    … …  
    11791179  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11801180  ///\endcode
    1181   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     1181  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
    11821182  ///to the end of the parameter list.
    11831183  ///\sa BfsWizard
    … …  
    11951195  /// This class defines the interface of the BfsVisit events, and
    11961196  /// it could be the base of a real visitor class.
    1197   template <typename _Digraph>
     1197  template <typename GR>
    11981198  struct BfsVisitor {
    1199     typedef _Digraph Digraph;
     1199    typedef GR Digraph;
    12001200    typedef typename Digraph::Arc Arc;
    12011201    typedef typename Digraph::Node Node;
    … …  
    12251225  };
    12261226#else
    1227   template <typename _Digraph>
     1227  template <typename GR>
    12281228  struct BfsVisitor {
    1229     typedef _Digraph Digraph;
     1229    typedef GR Digraph;
    12301230    typedef typename Digraph::Arc Arc;
    12311231    typedef typename Digraph::Node Node;
    … …  
    12551255  ///
    12561256  /// Default traits class of BfsVisit class.
    1257   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1258   template<class _Digraph>
     1257  /// \tparam GR The type of the digraph the algorithm runs on.
     1258  template<class GR>
    12591259  struct BfsVisitDefaultTraits {
    12601260
    12611261    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef _Digraph Digraph;
     1262    typedef GR Digraph;
    12631263
    12641264    /// \brief The type of the map that indicates which nodes are reached.
    … …  
    12811281  /// \ingroup search
    12821282  ///
    1283   /// \brief %BFS algorithm class with visitor interface.
     1283  /// \brief BFS algorithm class with visitor interface.
    12841284  ///
    1285   /// This class provides an efficient implementation of the %BFS algorithm
     1285  /// This class provides an efficient implementation of the BFS algorithm
    12861286  /// with visitor interface.
    12871287  ///
    1288   /// The %BfsVisit class provides an alternative interface to the Bfs
     1288  /// The BfsVisit class provides an alternative interface to the Bfs
    12891289  /// class. It works with callback mechanism, the BfsVisit object calls
    12901290  /// the member functions of the \c Visitor class on every BFS event.
    … …  
    12951295  /// instead.
    12961296  ///
    1297   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1298   /// The default value is
    1299   /// \ref ListDigraph. The value of _Digraph is not used directly by
    1300   /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
    1301   /// \tparam _Visitor The Visitor type that is used by the algorithm.
    1302   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
     1297  /// \tparam GR The type of the digraph the algorithm runs on.
     1298  /// The default type is \ref ListDigraph.
     1299  /// The value of GR is not used directly by \ref BfsVisit,
     1300  /// it is only passed to \ref BfsVisitDefaultTraits.
     1301  /// \tparam VS The Visitor type that is used by the algorithm.
     1302  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
    13031303  /// does not observe the BFS events. If you want to observe the BFS
    13041304  /// events, you should implement your own visitor class.
    1305   /// \tparam _Traits Traits class to set various data types used by the
     1305  /// \tparam TR Traits class to set various data types used by the
    13061306  /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
     1307  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
    13081308  /// See \ref BfsVisitDefaultTraits for the documentation of
    13091309  /// a BFS visit traits class.
    13101310#ifdef DOXYGEN
    1311   template <typename _Digraph, typename _Visitor, typename _Traits>
     1311  template <typename GR, typename VS, typename TR>
    13121312#else
    1313   template <typename _Digraph = ListDigraph,
    1314             typename _Visitor = BfsVisitor<_Digraph>,
    1315             typename _Traits = BfsVisitDefaultTraits<_Digraph> >
     1313  template <typename GR = ListDigraph,
     1314            typename VS = BfsVisitor<GR>,
     1315            typename TR = BfsVisitDefaultTraits<GR> >
    13161316#endif
    13171317  class BfsVisit {
    … …  
    13191319
    13201320    ///The traits class.
    1321     typedef _Traits Traits;
     1321    typedef TR Traits;
    13221322
    13231323    ///The type of the digraph the algorithm runs on.
    … …  
    13251325
    13261326    ///The visitor type used by the algorithm.
    1327     typedef _Visitor Visitor;
     1327    typedef VS Visitor;
    13281328
    13291329    ///The type of the map that indicates which nodes are reached.
    … …  
    13651365    typedef BfsVisit Create;
    13661366
    1367     /// \name Named template parameters
     1367    /// \name Named Template Parameters
    13681368
    13691369    ///@{
    … …  
    14071407    ///
    14081408    /// Sets the map that indicates which nodes are reached.
    1409     /// If you don't use this function before calling \ref run(),
    1410     /// it will allocate one. The destructor deallocates this
    1411     /// automatically allocated map, of course.
     1409    /// If you don't use this function before calling \ref run(Node) "run()"
     1410    /// or \ref init(), an instance will be allocated automatically.
     1411    /// The destructor deallocates this automatically allocated map,
     1412    /// of course.
    14121413    /// \return <tt> (*this) </tt>
    14131414    BfsVisit &reachedMap(ReachedMap &m) {
    … …  
    14221423  public:
    14231424
    1424     /// \name Execution control
    1425     /// The simplest way to execute the algorithm is to use
    1426     /// one of the member functions called \ref lemon::BfsVisit::run()
    1427     /// "run()".
    1428     /// \n
    1429     /// If you need more control on the execution, first you must call
    1430     /// \ref lemon::BfsVisit::init() "init()", then you can add several
    1431     /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
    1432     /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
    1433     /// actual path computation.
     1425    /// \name Execution Control
     1426    /// The simplest way to execute the BFS algorithm is to use one of the
     1427    /// member functions called \ref run(Node) "run()".\n
     1428    /// If you need more control on the execution, first you have to call
     1429    /// \ref init(), then you can add several source nodes with
     1430    /// \ref addSource(). Finally the actual path computation can be
     1431    /// performed with one of the \ref start() functions.
    14341432
    14351433    /// @{
    … …  
    17311729
    17321730    /// \name Query Functions
    1733     /// The result of the %BFS algorithm can be obtained using these
     1731    /// The results of the BFS algorithm can be obtained using these
    17341732    /// functions.\n
    1735     /// Either \ref lemon::BfsVisit::run() "run()" or
    1736     /// \ref lemon::BfsVisit::start() "start()" must be called before
    1737     /// using them.
     1733    /// Either \ref run(Node) "run()" or \ref start() should be called
     1734    /// before using them.
     1735
    17381736    ///@{
    17391737
    1740     /// \brief Checks if a node is reachable from the root(s).
    1741     ///
    1742     /// Returns \c true if \c v is reachable from the root(s).
    1743     /// \pre Either \ref run() or \ref start()
     1738    /// \brief Checks if a node is reached from the root(s).
     1739    ///
     1740    /// Returns \c true if \c v is reached from the root(s).
     1741    ///
     1742    /// \pre Either \ref run(Node) "run()" or \ref init()
    17441743    /// must be called before using this function.
    1745     bool reached(Node v) { return (*_reached)[v]; }
     1744    bool reached(Node v) const { return (*_reached)[v]; }
    17461745
    17471746    ///@}

  • lemon/bin_heap.h

    r209 r631  
    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).
    … …  
    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/alteration_notifier.h

    r314 r463  
    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).
    … …  
    3636  // a container.
    3737  //
    38   // The simple graph's can be refered as two containers, one node container
    39   // and one edge container. But they are not standard containers they
    40   // does not store values directly they are just key continars for more
    41   // value containers which are the node and edge maps.
    42   //
    43   // The graph's node and edge sets can be changed as we add or erase
     38  // The simple graphs can be refered as two containers: a node container
     39  // and an edge container. But they do not store values directly, they
     40  // are just key continars for more value containers, which are the
     41  // node and edge maps.
     42  //
     43  // The node and edge sets of the graphs can be changed as we add or erase
    4444  // nodes and edges in the graph. LEMON would like to handle easily
    4545  // that the node and edge maps should contain values for all nodes or
    4646  // edges. If we want to check on every indicing if the map contains
    4747  // the current indicing key that cause a drawback in the performance
    48   // in the library. We use another solution we notify all maps about
     48  // in the library. We use another solution: we notify all maps about
    4949  // an alteration in the graph, which cause only drawback on the
    5050  // alteration of the graph.
    5151  //
    52   // This class provides an interface to the container. The \e first() and \e
    53   // next() member functions make possible to iterate on the keys of the
    54   // container. The \e id() function returns an integer id for each key.
    55   // The \e maxId() function gives back an upper bound of the ids.
     52  // This class provides an interface to a node or edge container.
     53  // The first() and next() member functions make possible
     54  // to iterate on the keys of the container.
     55  // The id() function returns an integer id for each key.
     56  // The maxId() function gives back an upper bound of the ids.
    5657  //
    5758  // For the proper functonality of this class, we should notify it
    58   // about each alteration in the container. The alterations have four type
    59   // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
    60   // \e erase() signals that only one or few items added or erased to or
    61   // from the graph. If all items are erased from the graph or from an empty
    62   // graph a new graph is builded then it can be signaled with the
     59  // about each alteration in the container. The alterations have four type:
     60  // add(), erase(), build() and clear(). The add() and
     61  // erase() signal that only one or few items added or erased to or
     62  // from the graph. If all items are erased from the graph or if a new graph
     63  // is built from an empty graph, then it can be signaled with the
    6364  // clear() and build() members. Important rule that if we erase items
    64   // from graph we should first signal the alteration and after that erase
     65  // from graphs we should first signal the alteration and after that erase
    6566  // them from the container, on the other way on item addition we should
    6667  // first extend the container and just after that signal the alteration.
    6768  //
    6869  // The alteration can be observed with a class inherited from the
    69   // \e ObserverBase nested class. The signals can be handled with
     70  // ObserverBase nested class. The signals can be handled with
    7071  // overriding the virtual functions defined in the base class.  The
    7172  // observer base can be attached to the notifier with the
    72   // \e attach() member and can be detached with detach() function. The
     73  // attach() member and can be detached with detach() function. The
    7374  // alteration handlers should not call any function which signals
    7475  // an other alteration in the same notifier and should not
    7576  // detach any observer from the notifier.
    7677  //
    77   // Alteration observers try to be exception safe. If an \e add() or
    78   // a \e clear() function throws an exception then the remaining
     78  // Alteration observers try to be exception safe. If an add() or
     79  // a clear() function throws an exception then the remaining
    7980  // observeres will not be notified and the fulfilled additions will
    80   // be rolled back by calling the \e erase() or \e clear()
    81   // functions. Thence the \e erase() and \e clear() should not throw
    82   // exception. Actullay, it can be throw only \ref ImmediateDetach
    83   // exception which detach the observer from the notifier.
    84   //
    85   // There are some place when the alteration observing is not completly
     81  // be rolled back by calling the erase() or clear() functions.
     82  // Hence erase() and clear() should not throw exception.
     83  // Actullay, they can throw only \ref ImmediateDetach exception,
     84  // which detach the observer from the notifier.
     85  //
     86  // There are some cases, when the alteration observing is not completly
    8687  // reliable. If we want to carry out the node degree in the graph
    87   // as in the \ref InDegMap and we use the reverseEdge that cause
     88  // as in the \ref InDegMap and we use the reverseArc(), then it cause
    8889  // unreliable functionality. Because the alteration observing signals
    89   // only erasing and adding but not the reversing it will stores bad
    90   // degrees. The sub graph adaptors cannot signal the alterations because
    91   // just a setting in the filter map can modify the graph and this cannot
    92   // be watched in any way.
     90  // only erasing and adding but not the reversing, it will stores bad
     91  // degrees. Apart form that the subgraph adaptors cannot even signal
     92  // the alterations because just a setting in the filter map can modify
     93  // the graph and this cannot be watched in any way.
    9394  //
    9495  // \param _Container The container which is observed.
    … …  
    104105    typedef _Item Item;
    105106
    106     // \brief Exception which can be called from \e clear() and
    107     // \e erase().
    108     //
    109     // From the \e clear() and \e erase() function only this
     107    // \brief Exception which can be called from clear() and
     108    // erase().
     109    //
     110    // From the clear() and erase() function only this
    110111    // exception is allowed to throw. The exception immediatly
    111112    // detaches the current observer from the notifier. Because the
    112     // \e clear() and \e erase() should not throw other exceptions
     113    // clear() and erase() should not throw other exceptions
    113114    // it can be used to invalidate the observer.
    114115    struct ImmediateDetach {};
    … …  
    122123    // The observer interface contains some pure virtual functions
    123124    // to override. The add() and erase() functions are
    124     // to notify the oberver when one item is added or
    125     // erased.
     125    // to notify the oberver when one item is added or erased.
    126126    //
    127127    // The build() and clear() members are to notify the observer

  • lemon/bits/array_map.h

    r314 r664  
    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).
    … …  
    3737  // \brief Graph map based on the array storage.
    3838  //
    39   // The ArrayMap template class is graph map structure what
    40   // automatically updates the map when a key is added to or erased from
    41   // the map. This map uses the allocators to implement
    42   // the container functionality.
     39  // The ArrayMap template class is graph map structure that automatically
     40  // updates the map when a key is added to or erased from the graph.
     41  // This map uses the allocators to implement the container functionality.
    4342  //
    44   // The template parameters are the Graph the current Item type and
     43  // The template parameters are the Graph, the current Item type and
    4544  // the Value type of the map.
    4645  template <typename _Graph, typename _Item, typename _Value>
    … …  
    4847    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4948  public:
    50     // The graph type of the maps.
    51     typedef _Graph Graph;
    52     // The item type of the map.
     49    // The graph type.
     50    typedef _Graph GraphType;
     51    // The item type.
    5352    typedef _Item Item;
    5453    // The reference map tag.
    5554    typedef True ReferenceMapTag;
    5655
    57     // The key type of the maps.
     56    // The key type of the map.
    5857    typedef _Item Key;
    5958    // The value type of the map.
    … …  
    6564    typedef _Value& Reference;
    6665
     66    // The map type.
     67    typedef ArrayMap Map;
     68
    6769    // The notifier type.
    6870    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    6971
     72  private:
     73 
    7074    // The MapBase of the Map which imlements the core regisitry function.
    7175    typedef typename Notifier::ObserverBase Parent;
    7276
    73   private:
    7477    typedef std::allocator<Value> Allocator;
    7578
    … …  
    7982    //
    8083    // Graph initialized map constructor.
    81     explicit ArrayMap(const Graph& graph) {
     84    explicit ArrayMap(const GraphType& graph) {
    8285      Parent::attach(graph.notifier(Item()));
    8386      allocate_memory();
    … …  
    9396    //
    9497    // It constructs a map and initialize all of the the map.
    95     ArrayMap(const Graph& graph, const Value& value) {
     98    ArrayMap(const GraphType& graph, const Value& value) {
    9699      Parent::attach(graph.notifier(Item()));
    97100      allocate_memory();
    … …  
    137140    // \brief Template assign operator.
    138141    //
    139     // The given parameter should be conform to the ReadMap
     142    // The given parameter should conform to the ReadMap
    140143    // concecpt and could be indiced by the current item set of
    141144    // the NodeMap. In this case the value for each item
    … …  
    201204    // \brief Adds a new key to the map.
    202205    //
    203     // It adds a new key to the map. It called by the observer notifier
     206    // It adds a new key to the map. It is called by the observer notifier
    204207    // and it overrides the add() member function of the observer base.
    205208    virtual void add(const Key& key) {
    … …  
    229232    // \brief Adds more new keys to the map.
    230233    //
    231     // It adds more new keys to the map. It called by the observer notifier
     234    // It adds more new keys to the map. It is called by the observer notifier
    232235    // and it overrides the add() member function of the observer base.
    233236    virtual void add(const std::vector<Key>& keys) {
    … …  
    273276    // \brief Erase a key from the map.
    274277    //
    275     // Erase a key from the map. It called by the observer notifier
     278    // Erase a key from the map. It is called by the observer notifier
    276279    // and it overrides the erase() member function of the observer base.
    277280    virtual void erase(const Key& key) {
    … …  
    282285    // \brief Erase more keys from the map.
    283286    //
    284     // Erase more keys from the map. It called by the observer notifier
     287    // Erase more keys from the map. It is called by the observer notifier
    285288    // and it overrides the erase() member function of the observer base.
    286289    virtual void erase(const std::vector<Key>& keys) {
    … …  
    291294    }
    292295
    293     // \brief Buildes the map.
    294     //
    295     // It buildes the map. It called by the observer notifier
     296    // \brief Builds the map.
     297    //
     298    // It builds the map. It is called by the observer notifier
    296299    // and it overrides the build() member function of the observer base.
    297300    virtual void build() {
    … …  
    307310    // \brief Clear the map.
    308311    //
    309     // It erase all items from the map. It called by the observer notifier
     312    // It erase all items from the map. It is called by the observer notifier
    310313    // and it overrides the clear() member function of the observer base.
    311314    virtual void clear() {

  • lemon/bits/base_extender.h

    r314 r664  
    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).
    … …  
    3131//\ingroup digraphbits
    3232//\file
    33 //\brief Extenders for the digraph types
     33//\brief Extenders for the graph types
    3434namespace lemon {
    3535
    … …  
    3939  template <typename Base>
    4040  class UndirDigraphExtender : public Base {
     41    typedef Base Parent;
    4142
    4243  public:
    4344
    44     typedef Base Parent;
    4545    typedef typename Parent::Arc Edge;
    4646    typedef typename Parent::Node Node;
    … …  
    281281  template <typename Base>
    282282  class BidirBpGraphExtender : public Base {
     283    typedef Base Parent;
     284
    283285  public:
    284     typedef Base Parent;
    285286    typedef BidirBpGraphExtender Digraph;
    286287

  • lemon/bits/bezier.h

    r314 r463  
    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).

  • lemon/bits/default_map.h

    r523 r674  
    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).
    … …  
    9898
    9999
    100 #if defined HAVE_LONG_LONG
     100#if defined LEMON_HAVE_LONG_LONG
    101101
    102102  // long long
    … …  
    154154  class DefaultMap
    155155    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
     156    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     157
    156158  public:
    157     typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
    158159    typedef DefaultMap<_Graph, _Item, _Value> Map;
    159 
    160     typedef typename Parent::Graph Graph;
     160   
     161    typedef typename Parent::GraphType GraphType;
    161162    typedef typename Parent::Value Value;
    162163
    163     explicit DefaultMap(const Graph& graph) : Parent(graph) {}
    164     DefaultMap(const Graph& graph, const Value& value)
     164    explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
     165    DefaultMap(const GraphType& graph, const Value& value)
    165166      : Parent(graph, value) {}
    166167

  • lemon/bits/enable_if.h

    r314 r463  
    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).

  • lemon/bits/graph_extender.h

    r314 r664  
    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).
    … …  
    3030//\ingroup graphbits
    3131//\file
    32 //\brief Extenders for the digraph types
     32//\brief Extenders for the graph types
    3333namespace lemon {
    3434
    3535  // \ingroup graphbits
    3636  //
    37   // \brief Extender for the Digraphs
     37  // \brief Extender for the digraph implementations
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
     40    typedef Base Parent;
     41
    4042  public:
    4143
    42     typedef Base Parent;
    4344    typedef DigraphExtender Digraph;
    4445
    … …  
    219220    class NodeMap
    220221      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
    221     public:
    222       typedef DigraphExtender Digraph;
    223222      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    224223
     224    public:
    225225      explicit NodeMap(const Digraph& digraph)
    226226        : Parent(digraph) {}
    … …  
    244244    class ArcMap
    245245      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    246     public:
    247       typedef DigraphExtender Digraph;
    248246      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    249247
     248    public:
    250249      explicit ArcMap(const Digraph& digraph)
    251250        : Parent(digraph) {}
    … …  
    331330  template <typename Base>
    332331  class GraphExtender : public Base {
     332    typedef Base Parent;
     333
    333334  public:
    334335
    335     typedef Base Parent;
    336336    typedef GraphExtender Graph;
    337337
    … …  
    602602    class NodeMap
    603603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    604     public:
    605       typedef GraphExtender Graph;
    606604      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    607605
     606    public:
    608607      NodeMap(const Graph& graph)
    609608        : Parent(graph) {}
    … …  
    627626    class ArcMap
    628627      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    629     public:
    630       typedef GraphExtender Graph;
    631628      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    632629
     630    public:
    633631      ArcMap(const Graph& graph)
    634632        : Parent(graph) {}
    … …  
    652650    class EdgeMap
    653651      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    654     public:
    655       typedef GraphExtender Graph;
    656652      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    657653
     654    public:
    658655      EdgeMap(const Graph& graph)
    659656        : Parent(graph) {}

  • lemon/bits/map_extender.h

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

  • lemon/bits/path_dump.h

    r209 r576  
    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).
    … …  
    1717 */
    1818
    19 #ifndef LEMON_BITS_PRED_MAP_PATH_H
    20 #define LEMON_BITS_PRED_MAP_PATH_H
     19#ifndef LEMON_BITS_PATH_DUMP_H
     20#define LEMON_BITS_PATH_DUMP_H
     21
     22#include <lemon/core.h>
     23#include <lemon/concept_check.h>
    2124
    2225namespace lemon {

  • lemon/bits/traits.h

    r314 r663  
    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).
    … …  
    3030  struct InvalidType {};
    3131
    32   template <typename _Graph, typename _Item>
     32  template <typename GR, typename _Item>
    3333  class ItemSetTraits {};
    3434
    3535
    36   template <typename Graph, typename Enable = void>
     36  template <typename GR, typename Enable = void>
    3737  struct NodeNotifierIndicator {
    3838    typedef InvalidType Type;
    3939  };
    40   template <typename Graph>
     40  template <typename GR>
    4141  struct NodeNotifierIndicator<
    42     Graph,
    43     typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
    44   > {
    45     typedef typename Graph::NodeNotifier Type;
    46   };
    47 
    48   template <typename _Graph>
    49   class ItemSetTraits<_Graph, typename _Graph::Node> {
     42    GR,
     43    typename enable_if<typename GR::NodeNotifier::Notifier, void>::type
     44  > {
     45    typedef typename GR::NodeNotifier Type;
     46  };
     47
     48  template <typename GR>
     49  class ItemSetTraits<GR, typename GR::Node> {
    5050  public:
    5151
    52     typedef _Graph Graph;
    53 
    54     typedef typename Graph::Node Item;
    55     typedef typename Graph::NodeIt ItemIt;
    56 
    57     typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
    58 
    59     template <typename _Value>
    60     class Map : public Graph::template NodeMap<_Value> {
     52    typedef GR Graph;
     53    typedef GR Digraph;
     54
     55    typedef typename GR::Node Item;
     56    typedef typename GR::NodeIt ItemIt;
     57
     58    typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier;
     59
     60    template <typename V>
     61    class Map : public GR::template NodeMap<V> {
     62      typedef typename GR::template NodeMap<V> Parent;
     63
    6164    public:
    62       typedef typename Graph::template NodeMap<_Value> Parent;
    63       typedef typename Graph::template NodeMap<_Value> Type;
     65      typedef typename GR::template NodeMap<V> Type;
    6466      typedef typename Parent::Value Value;
    6567
    66       Map(const Graph& _digraph) : Parent(_digraph) {}
    67       Map(const Graph& _digraph, const Value& _value)
     68      Map(const GR& _digraph) : Parent(_digraph) {}
     69      Map(const GR& _digraph, const Value& _value)
    6870        : Parent(_digraph, _value) {}
    6971
    … …  
    7274  };
    7375
    74   template <typename Graph, typename Enable = void>
     76  template <typename GR, typename Enable = void>
    7577  struct ArcNotifierIndicator {
    7678    typedef InvalidType Type;
    7779  };
    78   template <typename Graph>
     80  template <typename GR>
    7981  struct ArcNotifierIndicator<
    80     Graph,
    81     typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type
    82   > {
    83     typedef typename Graph::ArcNotifier Type;
    84   };
    85 
    86   template <typename _Graph>
    87   class ItemSetTraits<_Graph, typename _Graph::Arc> {
     82    GR,
     83    typename enable_if<typename GR::ArcNotifier::Notifier, void>::type
     84  > {
     85    typedef typename GR::ArcNotifier Type;
     86  };
     87
     88  template <typename GR>
     89  class ItemSetTraits<GR, typename GR::Arc> {
    8890  public:
    8991
    90     typedef _Graph Graph;
    91 
    92     typedef typename Graph::Arc Item;
    93     typedef typename Graph::ArcIt ItemIt;
    94 
    95     typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;
    96 
    97     template <typename _Value>
    98     class Map : public Graph::template ArcMap<_Value> {
     92    typedef GR Graph;
     93    typedef GR Digraph;
     94
     95    typedef typename GR::Arc Item;
     96    typedef typename GR::ArcIt ItemIt;
     97
     98    typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier;
     99
     100    template <typename V>
     101    class Map : public GR::template ArcMap<V> {
     102      typedef typename GR::template ArcMap<V> Parent;
     103
    99104    public:
    100       typedef typename Graph::template ArcMap<_Value> Parent;
    101       typedef typename Graph::template ArcMap<_Value> Type;
     105      typedef typename GR::template ArcMap<V> Type;
    102106      typedef typename Parent::Value Value;
    103107
    104       Map(const Graph& _digraph) : Parent(_digraph) {}
    105       Map(const Graph& _digraph, const Value& _value)
     108      Map(const GR& _digraph) : Parent(_digraph) {}
     109      Map(const GR& _digraph, const Value& _value)
    106110        : Parent(_digraph, _value) {}
    107111    };
    … …  
    109113  };
    110114
    111   template <typename Graph, typename Enable = void>
     115  template <typename GR, typename Enable = void>
    112116  struct EdgeNotifierIndicator {
    113117    typedef InvalidType Type;
    114118  };
    115   template <typename Graph>
     119  template <typename GR>
    116120  struct EdgeNotifierIndicator<
    117     Graph,
    118     typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type
    119   > {
    120     typedef typename Graph::EdgeNotifier Type;
    121   };
    122 
    123   template <typename _Graph>
    124   class ItemSetTraits<_Graph, typename _Graph::Edge> {
     121    GR,
     122    typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type
     123  > {
     124    typedef typename GR::EdgeNotifier Type;
     125  };
     126
     127  template <typename GR>
     128  class ItemSetTraits<GR, typename GR::Edge> {
    125129  public:
    126130
    127     typedef _Graph Graph;
    128 
    129     typedef typename Graph::Edge Item;
    130     typedef typename Graph::EdgeIt ItemIt;
    131 
    132     typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;
    133 
    134     template <typename _Value>
    135     class Map : public Graph::template EdgeMap<_Value> {
     131    typedef GR Graph;
     132    typedef GR Digraph;
     133
     134    typedef typename GR::Edge Item;
     135    typedef typename GR::EdgeIt ItemIt;
     136
     137    typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier;
     138
     139    template <typename V>
     140    class Map : public GR::template EdgeMap<V> {
     141      typedef typename GR::template EdgeMap<V> Parent;
     142
    136143    public:
    137       typedef typename Graph::template EdgeMap<_Value> Parent;
    138       typedef typename Graph::template EdgeMap<_Value> Type;
     144      typedef typename GR::template EdgeMap<V> Type;
    139145      typedef typename Parent::Value Value;
    140146
    141       Map(const Graph& _digraph) : Parent(_digraph) {}
    142       Map(const Graph& _digraph, const Value& _value)
     147      Map(const GR& _digraph) : Parent(_digraph) {}
     148      Map(const GR& _digraph, const Value& _value)
    143149        : Parent(_digraph, _value) {}
    144150    };
    … …  
    205211  // Indicators for the tags
    206212
    207   template <typename Graph, typename Enable = void>
     213  template <typename GR, typename Enable = void>
    208214  struct NodeNumTagIndicator {
    209215    static const bool value = false;
    210216  };
    211217
    212   template <typename Graph>
     218  template <typename GR>
    213219  struct NodeNumTagIndicator<
    214     Graph,
    215     typename enable_if<typename Graph::NodeNumTag, void>::type
    216   > {
    217     static const bool value = true;
    218   };
    219 
    220   template <typename Graph, typename Enable = void>
     220    GR,
     221    typename enable_if<typename GR::NodeNumTag, void>::type
     222  > {
     223    static const bool value = true;
     224  };
     225
     226  template <typename GR, typename Enable = void>
     227  struct ArcNumTagIndicator {
     228    static const bool value = false;
     229  };
     230
     231  template <typename GR>
     232  struct ArcNumTagIndicator<
     233    GR,
     234    typename enable_if<typename GR::ArcNumTag, void>::type
     235  > {
     236    static const bool value = true;
     237  };
     238
     239  template <typename GR, typename Enable = void>
    221240  struct EdgeNumTagIndicator {
    222241    static const bool value = false;
    223242  };
    224243
    225   template <typename Graph>
     244  template <typename GR>
    226245  struct EdgeNumTagIndicator<
    227     Graph,
    228     typename enable_if<typename Graph::EdgeNumTag, void>::type
    229   > {
    230     static const bool value = true;
    231   };
    232 
    233   template <typename Graph, typename Enable = void>
     246    GR,
     247    typename enable_if<typename GR::EdgeNumTag, void>::type
     248  > {
     249    static const bool value = true;
     250  };
     251
     252  template <typename GR, typename Enable = void>
     253  struct FindArcTagIndicator {
     254    static const bool value = false;
     255  };
     256
     257  template <typename GR>
     258  struct FindArcTagIndicator<
     259    GR,
     260    typename enable_if<typename GR::FindArcTag, void>::type
     261  > {
     262    static const bool value = true;
     263  };
     264
     265  template <typename GR, typename Enable = void>
    234266  struct FindEdgeTagIndicator {
    235267    static const bool value = false;
    236268  };
    237269
    238   template <typename Graph>
     270  template <typename GR>
    239271  struct FindEdgeTagIndicator<
    240     Graph,
    241     typename enable_if<typename Graph::FindEdgeTag, void>::type
    242   > {
    243     static const bool value = true;
    244   };
    245 
    246   template <typename Graph, typename Enable = void>
     272    GR,
     273    typename enable_if<typename GR::FindEdgeTag, void>::type
     274  > {
     275    static const bool value = true;
     276  };
     277
     278  template <typename GR, typename Enable = void>
    247279  struct UndirectedTagIndicator {
    248280    static const bool value = false;
    249281  };
    250282
    251   template <typename Graph>
     283  template <typename GR>
    252284  struct UndirectedTagIndicator<
    253     Graph,
    254     typename enable_if<typename Graph::UndirectedTag, void>::type
    255   > {
    256     static const bool value = true;
    257   };
    258 
    259   template <typename Graph, typename Enable = void>
     285    GR,
     286    typename enable_if<typename GR::UndirectedTag, void>::type
     287  > {
     288    static const bool value = true;
     289  };
     290
     291  template <typename GR, typename Enable = void>
    260292  struct BuildTagIndicator {
    261293    static const bool value = false;
    262294  };
    263295
    264   template <typename Graph>
     296  template <typename GR>
    265297  struct BuildTagIndicator<
    266     Graph,
    267     typename enable_if<typename Graph::BuildTag, void>::type
     298    GR,
     299    typename enable_if<typename GR::BuildTag, void>::type
    268300  > {
    269301    static const bool value = true;

  • lemon/bits/vector_map.h

    r314 r664  
    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).
    … …  
    3939  // \brief Graph map based on the std::vector storage.
    4040  //
    41   // The VectorMap template class is graph map structure what
    42   // automatically updates the map when a key is added to or erased from
    43   // the map. This map type uses the std::vector to store the values.
     41  // The VectorMap template class is graph map structure that automatically
     42  // updates the map when a key is added to or erased from the graph.
     43  // This map type uses std::vector to store the values.
    4444  //
    4545  // \tparam _Graph The graph this map is attached to.
    … …  
    5757
    5858    // The graph type of the map.
    59     typedef _Graph Graph;
     59    typedef _Graph GraphType;
    6060    // The item type of the map.
    6161    typedef _Item Item;
    … …  
    7373    // The map type.
    7474    typedef VectorMap Map;
    75     // The base class of the map.
    76     typedef typename Notifier::ObserverBase Parent;
    7775
    7876    // The reference type of the map;
    … …  
    8179    typedef typename Container::const_reference ConstReference;
    8280
     81  private:
     82
     83    // The base class of the map.
     84    typedef typename Notifier::ObserverBase Parent;
     85
     86  public:
    8387
    8488    // \brief Constructor to attach the new map into the notifier.
    … …  
    8690    // It constructs a map and attachs it into the notifier.
    8791    // It adds all the items of the graph to the map.
    88     VectorMap(const Graph& graph) {
     92    VectorMap(const GraphType& graph) {
    8993      Parent::attach(graph.notifier(Item()));
    9094      container.resize(Parent::notifier()->maxId() + 1);
    … …  
    9599    // It constructs a map uses a given value to initialize the map.
    96100    // It adds all the items of the graph to the map.
    97     VectorMap(const Graph& graph, const Value& value) {
     101    VectorMap(const GraphType& graph, const Value& value) {
    98102      Parent::attach(graph.notifier(Item()));
    99103      container.resize(Parent::notifier()->maxId() + 1, value);
    … …  
    125129    // \brief Template assign operator.
    126130    //
    127     // The given parameter should be conform to the ReadMap
     131    // The given parameter should conform to the ReadMap
    128132    // concecpt and could be indiced by the current item set of
    129133    // the NodeMap. In this case the value for each item
    … …  
    170174    // \brief Adds a new key to the map.
    171175    //
    172     // It adds a new key to the map. It called by the observer notifier
     176    // It adds a new key to the map. It is called by the observer notifier
    173177    // and it overrides the add() member function of the observer base.
    174178    virtual void add(const Key& key) {
    … …  
    181185    // \brief Adds more new keys to the map.
    182186    //
    183     // It adds more new keys to the map. It called by the observer notifier
     187    // It adds more new keys to the map. It is called by the observer notifier
    184188    // and it overrides the add() member function of the observer base.
    185189    virtual void add(const std::vector<Key>& keys) {
    … …  
    196200    // \brief Erase a key from the map.
    197201    //
    198     // Erase a key from the map. It called by the observer notifier
     202    // Erase a key from the map. It is called by the observer notifier
    199203    // and it overrides the erase() member function of the observer base.
    200204    virtual void erase(const Key& key) {
    … …  
    204208    // \brief Erase more keys from the map.
    205209    //
    206     // Erase more keys from the map. It called by the observer notifier
     210    // It erases more keys from the map. It is called by the observer notifier
    207211    // and it overrides the erase() member function of the observer base.
    208212    virtual void erase(const std::vector<Key>& keys) {
    … …  
    212216    }
    213217
    214     // \brief Buildes the map.
    215     //
    216     // It buildes the map. It called by the observer notifier
     218    // \brief Build the map.
     219    //
     220    // It builds the map. It is called by the observer notifier
    217221    // and it overrides the build() member function of the observer base.
    218222    virtual void build() {
    … …  
    224228    // \brief Clear the map.
    225229    //
    226     // It erase all items from the map. It called by the observer notifier
     230    // It erases all items from the map. It is called by the observer notifier
    227231    // and it overrides the clear() member function of the observer base.
    228232    virtual void clear() {

  • lemon/bits/windows.h

    r511 r576  
    1717 */
    1818
    19 #ifndef LEMON_WINDOWS_H
    20 #define LEMON_WINDOWS_H
     19#ifndef LEMON_BITS_WINDOWS_H
     20#define LEMON_BITS_WINDOWS_H
    2121
    2222#include <string>

  • lemon/color.cc

    r209 r463  
    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).

  • lemon/color.h

    r313 r463  
    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).

  • lemon/concept_check.h

    r285 r463  
    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).

  • lemon/concepts/digraph.h

    r263 r627  
    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).
    … …  
    1717 */
    1818
    19 #ifndef LEMON_CONCEPT_DIGRAPH_H
    20 #define LEMON_CONCEPT_DIGRAPH_H
     19#ifndef LEMON_CONCEPTS_DIGRAPH_H
     20#define LEMON_CONCEPTS_DIGRAPH_H
    2121
    2222///\ingroup graph_concepts
    … …  
    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>();
    … …  
    485486
    486487
    487 #endif // LEMON_CONCEPT_DIGRAPH_H
     488#endif

  • lemon/concepts/graph.h

    r263 r627  
    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).
    … …  
    2121///\brief The concept of Undirected Graphs.
    2222
    23 #ifndef LEMON_CONCEPT_GRAPH_H
    24 #define LEMON_CONCEPT_GRAPH_H
     23#ifndef LEMON_CONCEPTS_GRAPH_H
     24#define LEMON_CONCEPTS_GRAPH_H
    2525
    2626#include <lemon/concepts/graph_components.h>
    27 #include <lemon/concepts/graph.h>
    2827#include <lemon/core.h>
    2928
    … …  
    499498      };
    500499
    501       /// \brief Read write map of the nodes to type \c T.
    502       ///
    503       /// ReadWrite map of the nodes to type \c T.
    504       /// \sa Reference
     500      /// \brief Reference map of the nodes to type \c T.
     501      ///
     502      /// Reference map of the nodes to type \c T.
    505503      template<class T>
    506       class NodeMap : public ReadWriteMap< Node, T >
     504      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
    507505      {
    508506      public:
    … …  
    515513      private:
    516514        ///Copy constructor
    517         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
     515        NodeMap(const NodeMap& nm) :
     516          ReferenceMap<Node, T, T&, const T&>(nm) { }
    518517        ///Assignment operator
    519518        template <typename CMap>
    … …  
    524523      };
    525524
    526       /// \brief Read write map of the directed arcs to type \c T.
    527       ///
    528       /// Reference map of the directed arcs to type \c T.
    529       /// \sa Reference
     525      /// \brief Reference map of the arcs to type \c T.
     526      ///
     527      /// Reference map of the arcs to type \c T.
    530528      template<class T>
    531       class ArcMap : public ReadWriteMap<Arc,T>
     529      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
    532530      {
    533531      public:
    … …  
    539537      private:
    540538        ///Copy constructor
    541         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
     539        ArcMap(const ArcMap& em) :
     540          ReferenceMap<Arc, T, T&, const T&>(em) { }
    542541        ///Assignment operator
    543542        template <typename CMap>
    … …  
    548547      };
    549548
    550       /// Read write map of the edges to type \c T.
    551 
    552       /// Reference map of the arcs to type \c T.
    553       /// \sa Reference
     549      /// Reference map of the edges to type \c T.
     550
     551      /// Reference map of the edges to type \c T.
    554552      template<class T>
    555       class EdgeMap : public ReadWriteMap<Edge,T>
     553      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
    556554      {
    557555      public:
    … …  
    563561      private:
    564562        ///Copy constructor
    565         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
     563        EdgeMap(const EdgeMap& em) :
     564          ReferenceMap<Edge, T, T&, const T&>(em) {}
    566565        ///Assignment operator
    567566        template <typename CMap>
    … …  
    603602      /// \brief Opposite node on an arc
    604603      ///
    605       /// \return the opposite of the given Node on the given Edge
     604      /// \return The opposite of the given node on the given edge.
    606605      Node oppositeNode(Node, Edge) const { return INVALID; }
    607606
    608607      /// \brief First node of the edge.
    609608      ///
    610       /// \return the first node of the given Edge.
     609      /// \return The first node of the given edge.
    611610      ///
    612611      /// Naturally edges don't have direction and thus
    613       /// don't have source and target node. But we use these two methods
    614       /// to query the two nodes of the arc. The direction of the arc
    615       /// 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
    616615      /// edge, and is used to define the "default" direction
    617616      /// of the directed versions of the arcs.
    618       /// \sa direction
     617      /// \sa v()
     618      /// \sa direction()
    619619      Node u(Edge) const { return INVALID; }
    620620
    621621      /// \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()
    622633      Node v(Edge) const { return INVALID; }
    623634
    … …  
    738749      struct Constraints {
    739750        void constraints() {
     751          checkConcept<BaseGraphComponent, _Graph>();
    740752          checkConcept<IterableGraphComponent<>, _Graph>();
    741753          checkConcept<IDableGraphComponent<>, _Graph>();

  • lemon/concepts/graph_components.h

    r313 r664  
    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).
    … …  
    2121///\brief The concept of graph components.
    2222
    23 
    24 #ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
    25 #define LEMON_CONCEPT_GRAPH_COMPONENTS_H
     23#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     24#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    2625
    2726#include <lemon/core.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 be
    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 be 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:
     183
     184      typedef BaseGraphComponent Graph;
     185
    189186      typedef BaseDigraphComponent::Node Node;
    190187      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'> {
     188
     189      /// \brief Undirected edge class of the graph.
     190      ///
     191      /// This class represents the undirected edges of the graph.
     192      /// Undirected graphs can be used as directed graphs, each edge is
     193      /// represented by two opposite directed arcs.
     194      class Edge : public GraphItem<'e'> {
     195        typedef GraphItem<'e'> Parent;
     196
    199197      public:
    200         typedef GraphItem<'u'> Parent;
    201198        /// \brief Default constructor.
    202199        ///
     200        /// Default constructor.
    203201        /// \warning The default constructor is not required to set
    204202        /// the item to some well-defined value. So you should consider it
    205203        /// as uninitialized.
    206204        Edge() {}
     205
    207206        /// \brief Copy constructor.
    208207        ///
    209208        /// Copy constructor.
    210         ///
    211209        Edge(const Edge &) : Parent() {}
    212         /// \brief Invalid constructor \& conversion.
    213         ///
    214         /// This constructor initializes the item to be invalid.
     210
     211        /// \brief Constructor for conversion from \c INVALID.
     212        ///
     213        /// Constructor for conversion from \c INVALID.
     214        /// It initializes the item to be invalid.
    215215        /// \sa Invalid for more details.
    216216        Edge(Invalid) {}
    217         /// \brief Converter from arc to edge.
    218         ///
     217
     218        /// \brief Constructor for conversion from an arc.
     219        ///
     220        /// Constructor for conversion from an arc.
    219221        /// Besides the core graph item functionality each arc should
    220222        /// be convertible to the represented edge.
    221223        Edge(const Arc&) {}
    222         /// \brief Assign arc to edge.
    223         ///
     224
     225        /// \brief Assign an arc to an edge.
     226        ///
     227        /// This function assigns an arc to an edge.
    224228        /// Besides the core graph item functionality each arc should
    225229        /// be convertible to the represented edge.
    … …  
    227231      };
    228232
    229       /// \brief Returns the direction of the arc.
     233      /// \brief Return one end node of an edge.
     234      ///
     235      /// This function returns one end node of an edge.
     236      Node u(const Edge&) const { return INVALID; }
     237
     238      /// \brief Return the other end node of an edge.
     239      ///
     240      /// This function returns the other end node of an edge.
     241      Node v(const Edge&) const { return INVALID; }
     242
     243      /// \brief Return a directed arc related to an edge.
     244      ///
     245      /// This function returns a directed arc from its direction and the
     246      /// represented edge.
     247      Arc direct(const Edge&, bool) const { return INVALID; }
     248
     249      /// \brief Return a directed arc related to an edge.
     250      ///
     251      /// This function returns a directed arc from its source node and the
     252      /// represented edge.
     253      Arc direct(const Edge&, const Node&) const { return INVALID; }
     254
     255      /// \brief Return the direction of the arc.
    230256      ///
    231257      /// Returns the direction of the arc. Each arc represents an
    … …  
    234260      bool direction(const Arc&) const { return true; }
    235261
    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;}
     262      /// \brief Return the opposite arc.
     263      ///
     264      /// This function returns the opposite arc, i.e. the arc representing
     265      /// the same edge and has opposite direction.
     266      Arc oppositeArc(const Arc&) const { return INVALID; }
    263267
    264268      template <typename _Graph>
    … …  
    270274        void constraints() {
    271275          checkConcept<BaseDigraphComponent, _Graph>();
    272           checkConcept<GraphItem<'u'>, Edge>();
     276          checkConcept<GraphItem<'e'>, Edge>();
    273277          {
    274278            Node n;
    … …  
    278282            n = graph.v(ue);
    279283            e = graph.direct(ue, true);
     284            e = graph.direct(ue, false);
    280285            e = graph.direct(ue, n);
    281286            e = graph.oppositeArc(e);
    … …  
    291296    };
    292297
    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 be 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;
     298    /// \brief Skeleton class for \e idable directed graphs.
     299    ///
     300    /// This class describes the interface of \e idable directed graphs.
     301    /// It extends \ref BaseDigraphComponent with the core ID functions.
     302    /// The ids of the items must be unique and immutable.
     303    /// This concept is part of the Digraph concept.
     304    template <typename BAS = BaseDigraphComponent>
     305    class IDableDigraphComponent : public BAS {
     306    public:
     307
     308      typedef BAS Base;
    304309      typedef typename Base::Node Node;
    305310      typedef typename Base::Arc Arc;
    306311
    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;}
     312      /// \brief Return a unique integer id for the given node.
     313      ///
     314      /// This function returns a unique integer id for the given node.
     315      int id(const Node&) const { return -1; }
     316
     317      /// \brief Return the node by its unique id.
     318      ///
     319      /// This function returns the node by its unique id.
     320      /// If the digraph does not contain a node with the given id,
     321      /// then the result of the function is undefined.
     322      Node nodeFromId(int) const { return INVALID; }
     323
     324      /// \brief Return a unique integer id for the given arc.
     325      ///
     326      /// This function returns a unique integer id for the given arc.
     327      int id(const Arc&) const { return -1; }
     328
     329      /// \brief Return the arc by its unique id.
     330      ///
     331      /// This function returns the arc by its unique id.
     332      /// If the digraph does not contain an arc with the given id,
     333      /// then the result of the function is undefined.
     334      Arc arcFromId(int) const { return INVALID; }
     335
     336      /// \brief Return an integer greater or equal to the maximum
     337      /// node id.
     338      ///
     339      /// This function returns an integer greater or equal to the
     340      /// maximum node id.
     341      int maxNodeId() const { return -1; }
     342
     343      /// \brief Return an integer greater or equal to the maximum
     344      /// arc id.
     345      ///
     346      /// This function returns an integer greater or equal to the
     347      /// maximum arc id.
     348      int maxArcId() const { return -1; }
    346349
    347350      template <typename _Digraph>
    … …  
    369372    };
    370373
    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 be 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;
     374    /// \brief Skeleton class for \e idable undirected graphs.
     375    ///
     376    /// This class describes the interface of \e idable undirected
     377    /// graphs. It extends \ref IDableDigraphComponent with the core ID
     378    /// functions of undirected graphs.
     379    /// The ids of the items must be unique and immutable.
     380    /// This concept is part of the Graph concept.
     381    template <typename BAS = BaseGraphComponent>
     382    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
     383    public:
     384
     385      typedef BAS Base;
    382386      typedef typename Base::Edge Edge;
    383387
    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;}
     388      using IDableDigraphComponent<Base>::id;
     389
     390      /// \brief Return a unique integer id for the given edge.
     391      ///
     392      /// This function returns a unique integer id for the given edge.
     393      int id(const Edge&) const { return -1; }
     394
     395      /// \brief Return the edge by its unique id.
     396      ///
     397      /// This function returns the edge by its unique id.
     398      /// If the graph does not contain an edge with the given id,
     399      /// then the result of the function is undefined.
     400      Edge edgeFromId(int) const { return INVALID; }
     401
     402      /// \brief Return an integer greater or equal to the maximum
     403      /// edge id.
     404      ///
     405      /// This function returns an integer greater or equal to the
     406      /// maximum edge id.
     407      int maxEdgeId() const { return -1; }
    405408
    406409      template <typename _Graph>
    … …  
    408411
    409412        void constraints() {
    410           checkConcept<Base, _Graph >();
    411413          checkConcept<IDableDigraphComponent<Base>, _Graph >();
    412414          typename _Graph::Edge edge;
    … …  
    422424    };
    423425
    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 {
     426    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
     427    ///
     428    /// This class describes the concept of \c NodeIt, \c ArcIt and
     429    /// \c EdgeIt subtypes of digraph and graph types.
     430    template <typename GR, typename Item>
     431    class GraphItemIt : public Item {
    430432    public:
    431433      /// \brief Default constructor.
    432434      ///
    433       /// @warning The default constructor sets the iterator
    434       /// to an undefined value.
     435      /// Default constructor.
     436      /// \warning The default constructor is not required to set
     437      /// the iterator to some well-defined value. So you should consider it
     438      /// as uninitialized.
    435439      GraphItemIt() {}
     440
    436441      /// \brief Copy constructor.
    437442      ///
    438443      /// 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.
     444      GraphItemIt(const GraphItemIt& it) : Item(it) {}
     445
     446      /// \brief Constructor that sets the iterator to the first item.
     447      ///
     448      /// Constructor that sets the iterator to the first item.
     449      explicit GraphItemIt(const GR&) {}
     450
     451      /// \brief Constructor for conversion from \c INVALID.
     452      ///
     453      /// Constructor for conversion from \c INVALID.
     454      /// It initializes the iterator to be invalid.
    449455      /// \sa Invalid for more details.
    450456      GraphItemIt(Invalid) {}
    451       /// \brief Assign operator for items.
    452       ///
    453       /// The items are assignable.
    454       ///
     457
     458      /// \brief Assignment operator.
     459      ///
     460      /// Assignment operator for the iterator.
    455461      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
    456       /// \brief Next item.
    457       ///
    458       /// Assign the iterator to the next item.
    459       ///
     462
     463      /// \brief Increment the iterator.
     464      ///
     465      /// This operator increments the iterator, i.e. assigns it to the
     466      /// next item.
    460467      GraphItemIt& operator++() { return *this; }
     468 
    461469      /// \brief Equality operator
    462470      ///
     471      /// Equality operator.
    463472      /// Two iterators are equal if and only if they point to the
    464473      /// same object or both are invalid.
    465474      bool operator==(const GraphItemIt&) const { return true;}
     475
    466476      /// \brief Inequality operator
    467477      ///
    468       /// \sa operator==(Node n)
    469       ///
     478      /// Inequality operator.
     479      /// Two iterators are equal if and only if they point to the
     480      /// same object or both are invalid.
    470481      bool operator!=(const GraphItemIt&) const { return true;}
    471482
    … …  
    473484      struct Constraints {
    474485        void constraints() {
     486          checkConcept<GraphItem<>, _GraphItemIt>();
    475487          _GraphItemIt it1(g);
    476488          _GraphItemIt it2;
     489          _GraphItemIt it3 = it1;
     490          _GraphItemIt it4 = INVALID;
    477491
    478492          it2 = ++it1;
    … …  
    480494          ++(++it1);
    481495
    482           _Item bi = it1;
     496          Item bi = it1;
    483497          bi = it2;
    484498        }
    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 {
     499        const GR& g;
     500      };
     501    };
     502
     503    /// \brief Concept class for \c InArcIt, \c OutArcIt and
     504    /// \c IncEdgeIt types.
     505    ///
     506    /// This class describes the concept of \c InArcIt, \c OutArcIt
     507    /// and \c IncEdgeIt subtypes of digraph and graph types.
     508    ///
     509    /// \note Since these iterator classes do not inherit from the same
     510    /// base class, there is an additional template parameter (selector)
     511    /// \c sel. For \c InArcIt you should instantiate it with character
     512    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
     513    template <typename GR,
     514              typename Item = typename GR::Arc,
     515              typename Base = typename GR::Node,
     516              char sel = '0'>
     517    class GraphIncIt : public Item {
    500518    public:
    501519      /// \brief Default constructor.
    502520      ///
    503       /// @warning The default constructor sets the iterator
    504       /// to an undefined value.
     521      /// Default constructor.
     522      /// \warning The default constructor is not required to set
     523      /// the iterator to some well-defined value. So you should consider it
     524      /// as uninitialized.
    505525      GraphIncIt() {}
     526
    506527      /// \brief Copy constructor.
    507528      ///
    508529      /// 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.
     530      GraphIncIt(const GraphIncIt& it) : Item(it) {}
     531
     532      /// \brief Constructor that sets the iterator to the first
     533      /// incoming or outgoing arc.
     534      ///
     535      /// Constructor that sets the iterator to the first arc
     536      /// incoming to or outgoing from the given node.
     537      explicit GraphIncIt(const GR&, const Base&) {}
     538
     539      /// \brief Constructor for conversion from \c INVALID.
     540      ///
     541      /// Constructor for conversion from \c INVALID.
     542      /// It initializes the iterator to be invalid.
    521543      /// \sa Invalid for more details.
    522544      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       ///
     545
     546      /// \brief Assignment operator.
     547      ///
     548      /// Assignment operator for the iterator.
     549      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
     550
     551      /// \brief Increment the iterator.
     552      ///
     553      /// This operator increments the iterator, i.e. assigns it to the
     554      /// next arc incoming to or outgoing from the given node.
    532555      GraphIncIt& operator++() { return *this; }
    533556
    534557      /// \brief Equality operator
    535558      ///
     559      /// Equality operator.
    536560      /// Two iterators are equal if and only if they point to the
    537561      /// same object or both are invalid.
    … …  
    540564      /// \brief Inequality operator
    541565      ///
    542       /// \sa operator==(Node n)
    543       ///
     566      /// Inequality operator.
     567      /// Two iterators are equal if and only if they point to the
     568      /// same object or both are invalid.
    544569      bool operator!=(const GraphIncIt&) const { return true;}
    545570
    … …  
    547572      struct Constraints {
    548573        void constraints() {
    549           checkConcept<GraphItem<_selector>, _GraphIncIt>();
     574          checkConcept<GraphItem<sel>, _GraphIncIt>();
    550575          _GraphIncIt it1(graph, node);
    551576          _GraphIncIt it2;
     577          _GraphIncIt it3 = it1;
     578          _GraphIncIt it4 = INVALID;
    552579
    553580          it2 = ++it1;
    554581          ++it2 = it1;
    555582          ++(++it1);
    556           _Item e = it1;
     583          Item e = it1;
    557584          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.
     585        }
     586        const Base& node;
     587        const GR& graph;
     588      };
     589    };
     590
     591    /// \brief Skeleton class for iterable directed graphs.
     592    ///
     593    /// This class describes the interface of iterable directed
     594    /// graphs. It extends \ref BaseDigraphComponent with the core
     595    /// iterable interface.
    573596    /// 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;
     597    template <typename BAS = BaseDigraphComponent>
     598    class IterableDigraphComponent : public BAS {
     599
     600    public:
     601
     602      typedef BAS Base;
    580603      typedef typename Base::Node Node;
    581604      typedef typename Base::Arc Arc;
    … …  
    583606      typedef IterableDigraphComponent Digraph;
    584607
    585       /// \name Base iteration
    586       ///
    587       /// This interface provides functions for iteration on digraph items
     608      /// \name Base Iteration
     609      ///
     610      /// This interface provides functions for iteration on digraph items.
    588611      ///
    589612      /// @{
    590613
    591       /// \brief Gives back the first node in the iterating order.
    592       ///
    593       /// Gives back the first node in the iterating order.
    594       ///
     614      /// \brief Return the first node.
     615      ///
     616      /// This function gives back the first node in the iteration order.
    595617      void first(Node&) const {}
    596618
    597       /// \brief Gives back the next node in the iterating order.
    598       ///
    599       /// Gives back the next node in the iterating order.
    600       ///
     619      /// \brief Return the next node.
     620      ///
     621      /// This function gives back the next node in the iteration order.
    601622      void next(Node&) const {}
    602623
    603       /// \brief Gives back the first arc in the iterating order.
    604       ///
    605       /// Gives back the first arc in the iterating order.
    606       ///
     624      /// \brief Return the first arc.
     625      ///
     626      /// This function gives back the first arc in the iteration order.
    607627      void first(Arc&) const {}
    608628
    609       /// \brief Gives back the next arc in the iterating order.
    610       ///
    611       /// Gives back the next arc in the iterating order.
    612       ///
     629      /// \brief Return the next arc.
     630      ///
     631      /// This function gives back the next arc in the iteration order.
    613632      void next(Arc&) const {}
    614633
    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       ///
     634      /// \brief Return the first arc incomming to the given node.
     635      ///
     636      /// This function gives back the first arc incomming to the
     637      /// given node.
    621638      void firstIn(Arc&, const Node&) const {}
    622639
    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       ///
     640      /// \brief Return the next arc incomming to the given node.
     641      ///
     642      /// This function gives back the next arc incomming to the
     643      /// given node.
    628644      void nextIn(Arc&) const {}
    629645
    630       /// \brief Gives back the first of the arcs start from the
     646      /// \brief Return the first arc outgoing form the given node.
     647      ///
     648      /// This function gives back the first arc outgoing form the
    631649      /// given node.
    632       ///
    633       /// Gives back the first of the arcs start from the given node.
    634       ///
    635650      void firstOut(Arc&, const Node&) const {}
    636651
    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       ///
     652      /// \brief Return the next arc outgoing form the given node.
     653      ///
     654      /// This function gives back the next arc outgoing form the
     655      /// given node.
    642656      void nextOut(Arc&) const {}
    643657
    644658      /// @}
    645659
    646       /// \name Class based iteration
    647       ///
    648       /// This interface provides functions for iteration on digraph items
     660      /// \name Class Based Iteration
     661      ///
     662      /// This interface provides iterator classes for digraph items.
    649663      ///
    650664      /// @{
    … …  
    656670      typedef GraphItemIt<Digraph, Node> NodeIt;
    657671
    658       /// \brief This iterator goes through each node.
    659       ///
    660       /// This iterator goes through each node.
     672      /// \brief This iterator goes through each arc.
     673      ///
     674      /// This iterator goes through each arc.
    661675      ///
    662676      typedef GraphItemIt<Digraph, Arc> ArcIt;
    … …  
    664678      /// \brief This iterator goes trough the incoming arcs of a node.
    665679      ///
    666       /// This iterator goes trough the \e inccoming arcs of a certain node
     680      /// This iterator goes trough the \e incoming arcs of a certain node
    667681      /// of a digraph.
    668682      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
    … …  
    676690      /// \brief The base node of the iterator.
    677691      ///
    678       /// Gives back the base node of the iterator.
    679       /// It is always the target of the pointed arc.
     692      /// This function gives back the base node of the iterator.
     693      /// It is always the target node of the pointed arc.
    680694      Node baseNode(const InArcIt&) const { return INVALID; }
    681695
    682696      /// \brief The running node of the iterator.
    683697      ///
    684       /// Gives back the running node of the iterator.
    685       /// It is always the source of the pointed arc.
     698      /// This function gives back the running node of the iterator.
     699      /// It is always the source node of the pointed arc.
    686700      Node runningNode(const InArcIt&) const { return INVALID; }
    687701
    688702      /// \brief The base node of the iterator.
    689703      ///
    690       /// Gives back the base node of the iterator.
    691       /// It is always the source of the pointed arc.
     704      /// This function gives back the base node of the iterator.
     705      /// It is always the source node of the pointed arc.
    692706      Node baseNode(const OutArcIt&) const { return INVALID; }
    693707
    694708      /// \brief The running node of the iterator.
    695709      ///
    696       /// Gives back the running node of the iterator.
    697       /// It is always the target of the pointed arc.
     710      /// This function gives back the running node of the iterator.
     711      /// It is always the target node of the pointed arc.
    698712      Node runningNode(const OutArcIt&) const { return INVALID; }
    699713
    … …  
    737751
    738752            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);
     753            const typename _Digraph::InArcIt iait(INVALID);
     754            const typename _Digraph::OutArcIt oait(INVALID);
     755            n = digraph.baseNode(iait);
     756            n = digraph.runningNode(iait);
     757            n = digraph.baseNode(oait);
     758            n = digraph.runningNode(oait);
    745759            ignore_unused_variable_warning(n);
    746760          }
    … …  
    748762
    749763        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.
     764      };
     765    };
     766
     767    /// \brief Skeleton class for iterable undirected graphs.
     768    ///
     769    /// This class describes the interface of iterable undirected
     770    /// graphs. It extends \ref IterableDigraphComponent with the core
     771    /// iterable interface of undirected graphs.
    758772    /// 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;
     773    template <typename BAS = BaseGraphComponent>
     774    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
     775    public:
     776
     777      typedef BAS Base;
    764778      typedef typename Base::Node Node;
    765779      typedef typename Base::Arc Arc;
    … …  
    769783      typedef IterableGraphComponent Graph;
    770784
    771       /// \name Base iteration
    772       ///
    773       /// This interface provides functions for iteration on graph items
     785      /// \name Base Iteration
     786      ///
     787      /// This interface provides functions for iteration on edges.
     788      ///
    774789      /// @{
    775790
    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       ///
     791      using IterableDigraphComponent<Base>::first;
     792      using IterableDigraphComponent<Base>::next;
     793
     794      /// \brief Return the first edge.
     795      ///
     796      /// This function gives back the first edge in the iteration order.
    784797      void first(Edge&) const {}
    785798
    786       /// \brief Gives back the next edge in the iterating
    787       /// order.
    788       ///
    789       /// Gives back the next edge in the iterating order.
    790       ///
     799      /// \brief Return the next edge.
     800      ///
     801      /// This function gives back the next edge in the iteration order.
    791802      void next(Edge&) const {}
    792803
    793 
    794       /// \brief Gives back the first of the edges from the
     804      /// \brief Return the first edge incident to the given node.
     805      ///
     806      /// This function gives back the first edge incident to the given
     807      /// node. The bool parameter gives back the direction for which the
     808      /// source node of the directed arc representing the edge is the
    795809      /// 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.
    801810      void firstInc(Edge&, bool&, const Node&) const {}
    802811
    … …  
    804813      /// given node.
    805814      ///
    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.
     815      /// This function gives back the next edge incident to the given
     816      /// node. The bool parameter should be used as \c firstInc() use it.
    809817      void nextInc(Edge&, bool&) const {}
    810818
    811       using IterableDigraphComponent<_Base>::baseNode;
    812       using IterableDigraphComponent<_Base>::runningNode;
     819      using IterableDigraphComponent<Base>::baseNode;
     820      using IterableDigraphComponent<Base>::runningNode;
    813821
    814822      /// @}
    815823
    816       /// \name Class based iteration
    817       ///
    818       /// This interface provides functions for iteration on graph items
     824      /// \name Class Based Iteration
     825      ///
     826      /// This interface provides iterator classes for edges.
    819827      ///
    820828      /// @{
    821829
    822       /// \brief This iterator goes through each node.
    823       ///
    824       /// This iterator goes through each node.
     830      /// \brief This iterator goes through each edge.
     831      ///
     832      /// This iterator goes through each edge.
    825833      typedef GraphItemIt<Graph, Edge> EdgeIt;
    826       /// \brief This iterator goes trough the incident arcs of a
     834
     835      /// \brief This iterator goes trough the incident edges of a
    827836      /// node.
    828837      ///
    829       /// This iterator goes trough the incident arcs of a certain
     838      /// This iterator goes trough the incident edges of a certain
    830839      /// node of a graph.
    831       typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt;
     840      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
     841
    832842      /// \brief The base node of the iterator.
    833843      ///
    834       /// Gives back the base node of the iterator.
     844      /// This function gives back the base node of the iterator.
    835845      Node baseNode(const IncEdgeIt&) const { return INVALID; }
    836846
    837847      /// \brief The running node of the iterator.
    838848      ///
    839       /// Gives back the running node of the iterator.
     849      /// This function gives back the running node of the iterator.
    840850      Node runningNode(const IncEdgeIt&) const { return INVALID; }
    841851
    … …  
    866876              typename _Graph::EdgeIt >();
    867877            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
    868               typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
     878              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
    869879
    870880            typename _Graph::Node n;
    871             typename _Graph::IncEdgeIt ueit(INVALID);
    872             n = graph.baseNode(ueit);
    873             n = graph.runningNode(ueit);
     881            const typename _Graph::IncEdgeIt ieit(INVALID);
     882            n = graph.baseNode(ieit);
     883            n = graph.runningNode(ieit);
    874884          }
    875885        }
    876886
    877887        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
     888      };
     889    };
     890
     891    /// \brief Skeleton class for alterable directed graphs.
     892    ///
     893    /// This class describes the interface of alterable directed
     894    /// graphs. It extends \ref BaseDigraphComponent with the alteration
     895    /// notifier interface. It implements
    886896    /// an observer-notifier pattern for each digraph item. More
    887897    /// obsevers can be registered into the notifier and whenever an
    888     /// alteration occured in the digraph all the observers will
     898    /// alteration occured in the digraph all the observers will be
    889899    /// notified about it.
    890     template <typename _Base = BaseDigraphComponent>
    891     class AlterableDigraphComponent : public _Base {
    892     public:
    893 
    894       typedef _Base Base;
     900    template <typename BAS = BaseDigraphComponent>
     901    class AlterableDigraphComponent : public BAS {
     902    public:
     903
     904      typedef BAS Base;
    895905      typedef typename Base::Node Node;
    896906      typedef typename Base::Arc Arc;
    897907
    898908
    899       /// The node observer registry.
     909      /// Node alteration notifier class.
    900910      typedef AlterationNotifier<AlterableDigraphComponent, Node>
    901911      NodeNotifier;
    902       /// The arc observer registry.
     912      /// Arc alteration notifier class.
    903913      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
    904914      ArcNotifier;
    905915
    906       /// \brief Gives back the node alteration notifier.
    907       ///
    908       /// Gives back the node alteration notifier.
     916      /// \brief Return the node alteration notifier.
     917      ///
     918      /// This function gives back the node alteration notifier.
    909919      NodeNotifier& notifier(Node) const {
    910         return NodeNotifier();
     920         return NodeNotifier();
    911921      }
    912922
    913       /// \brief Gives back the arc alteration notifier.
    914       ///
    915       /// Gives back the arc alteration notifier.
     923      /// \brief Return the arc alteration notifier.
     924      ///
     925      /// This function gives back the arc alteration notifier.
    916926      ArcNotifier& notifier(Arc) const {
    917927        return ArcNotifier();
    … …  
    933943
    934944        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
     945      };
     946    };
     947
     948    /// \brief Skeleton class for alterable undirected graphs.
     949    ///
     950    /// This class describes the interface of alterable undirected
     951    /// graphs. It extends \ref AlterableDigraphComponent with the alteration
     952    /// notifier interface of undirected graphs. It implements
     953    /// an observer-notifier pattern for the edges. More
    945954    /// obsevers can be registered into the notifier and whenever an
    946     /// alteration occured in the graph all the observers will
     955    /// alteration occured in the graph all the observers will be
    947956    /// notified about it.
    948     template <typename _Base = BaseGraphComponent>
    949     class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
    950     public:
    951 
    952       typedef _Base Base;
     957    template <typename BAS = BaseGraphComponent>
     958    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
     959    public:
     960
     961      typedef BAS Base;
    953962      typedef typename Base::Edge Edge;
    954963
    955964
    956       /// The arc observer registry.
     965      /// Edge alteration notifier class.
    957966      typedef AlterationNotifier<AlterableGraphComponent, Edge>
    958967      EdgeNotifier;
    959968
    960       /// \brief Gives back the arc alteration notifier.
    961       ///
    962       /// Gives back the arc alteration notifier.
     969      /// \brief Return the edge alteration notifier.
     970      ///
     971      /// This function gives back the edge alteration notifier.
    963972      EdgeNotifier& notifier(Edge) const {
    964973        return EdgeNotifier();
    … …  
    968977      struct Constraints {
    969978        void constraints() {
    970           checkConcept<AlterableGraphComponent<Base>, _Graph>();
     979          checkConcept<AlterableDigraphComponent<Base>, _Graph>();
    971980          typename _Graph::EdgeNotifier& uen
    972981            = graph.notifier(typename _Graph::Edge());
    … …  
    975984
    976985        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;
    992 
    993       /// The graph type of the map.
    994       typedef _Graph Graph;
     986      };
     987    };
     988
     989    /// \brief Concept class for standard graph maps.
     990    ///
     991    /// This class describes the concept of standard graph maps, i.e.
     992    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
     993