COIN-OR::LEMON - Graph Library

Changes in / [627:20dac2104519:500:8a144437db7d] in lemon-1.2


Ignore:
Files:
67 deleted
106 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r563 r484  
    2323lemon/stamp-h2
    2424doc/Doxyfile
    25 cmake/version.cmake
     25cmake/cmake.version
    2626.dirstamp
    2727.libs/*
    2828.deps/*
    2929demo/*.eps
    30 m4/libtool.m4
    31 m4/ltoptions.m4
    32 m4/ltsugar.m4
    33 m4/ltversion.m4
    34 m4/lt~obsolete.m4
    3530
    3631syntax: regexp
     
    4136^autom4te.cache/.*
    4237^build-aux/.*
    43 ^.*objs.*/.*
     38^objs.*/.*
    4439^test/[a-z_]*$
    45 ^tools/[a-z-_]*$
    4640^demo/.*_demo$
    47 ^.*build.*/.*
     41^build/.*
    4842^doc/gen-images/.*
    4943CMakeFiles
  • CMakeLists.txt

    r627 r500  
    1010PROJECT(${PROJECT_NAME})
    1111
    12 SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
     12SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
    1313
    1414INCLUDE(FindDoxygen)
    1515INCLUDE(FindGhostscript)
    16 FIND_PACKAGE(GLPK 4.33)
    17 FIND_PACKAGE(CPLEX)
    18 FIND_PACKAGE(COIN)
    19 
    20 ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    21 
    22 IF(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
    29 ENDIF(MSVC)
    3016
    3117ADD_DEFINITIONS(-DHAVE_CONFIG_H)
     
    3723
    3824ADD_SUBDIRECTORY(lemon)
    39 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    40   ADD_SUBDIRECTORY(demo)
    41   ADD_SUBDIRECTORY(tools)
    42   ADD_SUBDIRECTORY(doc)
    43   ADD_SUBDIRECTORY(test)
    44 ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     25ADD_SUBDIRECTORY(demo)
     26ADD_SUBDIRECTORY(doc)
     27ADD_SUBDIRECTORY(test)
    4528
    46 IF(${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")
     29IF(WIN32)
     30  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
     31  SET(CPACK_PACKAGE_VENDOR "EGRES")
     32  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
     33    "LEMON - Library of Efficient Models and Optimization in Networks")
     34  SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
    5335
    54     SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     36  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
    5537
    56     SET(CPACK_PACKAGE_INSTALL_DIRECTORY
    57       "${PROJECT_NAME} ${PROJECT_VERSION}")
    58     SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
    59       "${PROJECT_NAME} ${PROJECT_VERSION}")
     38  SET(CPACK_PACKAGE_INSTALL_DIRECTORY
     39    "${PROJECT_NAME} ${PROJECT_VERSION}")
     40  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
     41    "${PROJECT_NAME} ${PROJECT_VERSION}")
    6042
    61     SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
     43  SET(CPACK_COMPONENTS_ALL headers library html_documentation)
    6244
    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")
     45  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
     46  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     47  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    6748
    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")
     49  SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
     50    "C++ header files")
     51  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     52    "DLL and import library")
     53  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     54    "Doxygen generated documentation")
    7655
    77     SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     56  SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
    7857
    79     SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
    80     SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
    81     SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     58  SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     59  SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     60  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
    8261
    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")
     62  SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
     63    "Components needed to develop software using LEMON")
     64  SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
     65    "Documentation of LEMON")
    8766
    88     SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     67  SET(CPACK_ALL_INSTALL_TYPES Full Developer)
    8968
    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)
     69  SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
     70  SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
     71  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
    9372
    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       ")
     73  SET(CPACK_GENERATOR "NSIS")
     74  SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
     75  SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     76  #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
     77  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
     78  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     79  SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
     80  SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
     81  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
     82  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
     83    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
     84    ")
     85  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
     86    !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
     87    Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
     88    ")
    11089
    111     INCLUDE(CPack)
    112   ENDIF(WIN32)
    113 ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     90  INCLUDE(CPack)
     91ENDIF(WIN32)
  • INSTALL

    r568 r493  
    2828
    2929      This command compiles the non-template part of LEMON into libemon.a
    30       file. It also compiles the programs in the tools subdirectory by
    31       default.
     30      file. It also compiles the programs in the tools and demo subdirectories
     31      when enabled.
    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).
    7785
    7886--enable-tools
     
    151159
    152160   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

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

    r567 r478  
    11ACLOCAL_AMFLAGS = -I m4
    2 
    3 AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    42
    53AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
     
    1210        m4/lx_check_glpk.m4 \
    1311        m4/lx_check_soplex.m4 \
    14         m4/lx_check_clp.m4 \
    15         m4/lx_check_cbc.m4 \
    1612        CMakeLists.txt \
    1713        cmake/FindGhostscript.cmake \
    18         cmake/FindGLPK.cmake \
    1914        cmake/version.cmake.in \
    2015        cmake/version.cmake \
     
    4237include test/Makefile.am
    4338include doc/Makefile.am
     39include demo/Makefile.am
    4440include tools/Makefile.am
    45 
    46 DIST_SUBDIRS = demo
    47 
    48 demo:
    49         $(MAKE) $(AM_MAKEFLAGS) -C demo
    5041
    5142MRPROPERFILES = \
     
    7566        bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
    7667
    77 .PHONY: demo mrproper dist-bz2 distcheck-bz2
     68.PHONY: mrproper dist-bz2 distcheck-bz2
  • configure.ac

    r627 r500  
    1919AC_CONFIG_SRCDIR([lemon/list_graph.h])
    2020AC_CONFIG_HEADERS([config.h lemon/config.h])
     21
     22lx_cmdline_cxxflags_set=${CXXFLAGS+set}
    2123
    2224dnl Do compilation tests using the C++ compiler.
     
    5153
    5254dnl Set custom compiler flags when using g++.
    53 if 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"
     55if 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"
    5557fi
    56 AC_SUBST([WARNINGCXXFLAGS])
    5758
    5859dnl Checks for libraries.
    59 LX_CHECK_GLPK
    60 LX_CHECK_CPLEX
    61 LX_CHECK_SOPLEX
    62 LX_CHECK_COIN
     60#LX_CHECK_GLPK
     61#LX_CHECK_CPLEX
     62#LX_CHECK_SOPLEX
    6363
    64 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
    65 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
     64dnl Disable/enable building the demo programs.
     65AC_ARG_ENABLE([demo],
     66AS_HELP_STRING([--enable-demo], [build the demo programs])
     67AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
     68              [], [enable_demo=no])
     69AC_MSG_CHECKING([whether to build the demo programs])
     70if test x"$enable_demo" != x"no"; then
     71  AC_MSG_RESULT([yes])
     72else
     73  AC_MSG_RESULT([no])
     74fi
     75AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
    6676
    6777dnl Disable/enable building the binary tools.
     
    98108AC_CONFIG_FILES([
    99109Makefile
    100 demo/Makefile
    101110cmake/version.cmake
    102111doc/Doxyfile
     
    112121echo
    113122echo C++ compiler.................. : $CXX
    114 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
     123echo C++ compiles flags............ : $CXXFLAGS
    115124echo
    116125echo Compiler supports long long... : $long_long_found
    117126echo
    118 echo GLPK support.................. : $lx_glpk_found
    119 echo CPLEX support................. : $lx_cplex_found
    120 echo SOPLEX support................ : $lx_soplex_found
    121 echo CLP support................... : $lx_clp_found
    122 echo CBC support................... : $lx_cbc_found
    123 echo
     127#echo GLPK support.................. : $lx_glpk_found
     128#echo CPLEX support................. : $lx_cplex_found
     129#echo SOPLEX support................ : $lx_soplex_found
     130#echo
     131echo Build demo programs........... : $enable_demo
    124132echo Build additional tools........ : $enable_tools
    125133echo
  • demo/CMakeLists.txt

    r627 r499  
    11INCLUDE_DIRECTORIES(
    2   ${PROJECT_SOURCE_DIR}
     2  ${CMAKE_SOURCE_DIR}
    33  ${PROJECT_BINARY_DIR}
    44)
    55
    6 LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
     6LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
    77
    88SET(DEMOS
  • demo/Makefile.am

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

    r440 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • demo/graph_to_eps_demo.cc

    r612 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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-2009 LEMON Project").
     88    copyright("(C) 2003-2008 LEMON Project").
    8989    run();
    9090
     
    9393    coords(coords).
    9494    title("Sample .eps figure").
    95     copyright("(C) 2003-2009 LEMON Project").
     95    copyright("(C) 2003-2008 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-2009 LEMON Project").
     108    copyright("(C) 2003-2008 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-2009 LEMON Project").
     135    copyright("(C) 2003-2008 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-2009 LEMON Project").
     150    copyright("(C) 2003-2008 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-2009 LEMON Project").
     166    copyright("(C) 2003-2008 LEMON Project").
    167167    scaleToA4().
    168168    absoluteNodeSizes().absoluteArcWidths().
     
    183183  ListDigraph::NodeMap<Point> hcoords(h);
    184184
    185   int cols=int(std::sqrt(double(palette.size())));
     185  int cols=int(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-2009 LEMON Project").
     196    copyright("(C) 2003-2008 LEMON Project").
    197197    coords(hcoords).
    198198    absoluteNodeSizes().absoluteArcWidths().
  • demo/lgf_demo.cc

    r440 r294  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/CMakeLists.txt

    r586 r489  
    11SET(PACKAGE_NAME ${PROJECT_NAME})
    22SET(PACKAGE_VERSION ${PROJECT_VERSION})
    3 SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
    4 SET(abs_top_builddir ${PROJECT_BINARY_DIR})
     3SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
     4SET(abs_top_builddir ${CMAKE_BINARY_DIR})
    55
    66CONFIGURE_FILE(
    7   ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
    8   ${PROJECT_BINARY_DIR}/doc/Doxyfile
     7  ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
     8  ${CMAKE_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
    2317      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
    2418      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
     
    2620      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
    2721      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
    2922      COMMAND rm -rf html
    3023      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     
    3427      COMMAND if exist gen-images rmdir /s /q gen-images
    3528      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
    4229      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
    4330      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
     
    4532      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
    4633      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
    4834      COMMAND if exist html rmdir /s /q html
    4935      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
  • doc/Doxyfile.in

    r367 r316  
    6767ENABLED_SECTIONS       =
    6868MAX_INITIALIZER_LINES  = 5
    69 SHOW_USED_FILES        = NO
     69SHOW_USED_FILES        = YES
    7070SHOW_DIRECTORIES       = YES
    7171SHOW_FILES             = YES
  • doc/Makefile.am

    r587 r317  
    1515
    1616DOC_EPS_IMAGES18 = \
    17         grid_graph.eps \
    1817        nodeshape_0.eps \
    1918        nodeshape_1.eps \
     
    2221        nodeshape_4.eps
    2322
    24 DOC_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 
    3223DOC_EPS_IMAGES = \
    33         $(DOC_EPS_IMAGES18) \
    34         $(DOC_EPS_IMAGES27)
     24        $(DOC_EPS_IMAGES18)
    3525
    3626DOC_PNG_IMAGES = \
     
    4838        if test ${gs_found} = yes; then \
    4939          $(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=$@ $<; \
    6140        else \
    6241          echo; \
  • doc/coding_style.dox

    r440 r210  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/dirs.dox

    r440 r318  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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

    r611 r318  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    19 namespace lemon {
    20 
    2119/**
    2220@defgroup datas Data Structures
    23 This group contains the several data structures implemented in LEMON.
     21This group describes the several data structures implemented in LEMON.
    2422*/
    2523
     
    6361
    6462/**
    65 @defgroup graph_adaptors Adaptor Classes for Graphs
    66 @ingroup graphs
    67 \brief Adaptor classes for digraphs and graphs
    68 
    69 This group contains several useful adaptor classes for digraphs and graphs.
    70 
    71 The main parts of LEMON are the different graph structures, generic
    72 graph algorithms, graph concepts, which couple them, and graph
    73 adaptors. While the previous notions are more or less clear, the
    74 latter one needs further explanation. Graph adaptors are graph classes
    75 which serve for considering graph structures in different ways.
    76 
    77 A short example makes this much clearer.  Suppose that we have an
    78 instance \c g of a directed graph type, say ListDigraph and an algorithm
    79 \code
    80 template <typename Digraph>
    81 int algorithm(const Digraph&);
    82 \endcode
    83 is 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
    85 arcs.  In this case, an adaptor class is used, which (according
    86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
    87 The adaptor uses the original digraph structure and digraph operations when
    88 methods of the reversed oriented graph are called.  This means that the adaptor
    89 have minor memory usage, and do not perform sophisticated algorithmic
    90 actions.  The purpose of it is to give a tool for the cases when a
    91 graph have to be used in a specific alteration.  If this alteration is
    92 obtained by a usual construction like filtering the node or the arc set or
    93 considering a new orientation, then an adaptor is worthwhile to use.
    94 To come back to the reverse oriented graph, in this situation
    95 \code
    96 template<typename Digraph> class ReverseDigraph;
    97 \endcode
    98 template class can be used. The code looks as follows
    99 \code
    100 ListDigraph g;
    101 ReverseDigraph<ListDigraph> rg(g);
    102 int result = algorithm(rg);
    103 \endcode
    104 During running the algorithm, the original digraph \c g is untouched.
    105 This techniques give rise to an elegant code, and based on stable
    106 graph adaptors, complex algorithms can be implemented easily.
    107 
    108 In flow, circulation and matching problems, the residual
    109 graph is of particular importance. Combining an adaptor implementing
    110 this with shortest path algorithms or minimum mean cycle algorithms,
    111 a range of weighted and cardinality optimization algorithms can be
    112 obtained. For other examples, the interested user is referred to the
    113 detailed documentation of particular adaptors.
    114 
    115 The behavior of graph adaptors can be very different. Some of them keep
    116 capabilities of the original graph while in other cases this would be
    117 meaningless. This means that the concepts that they meet depend
    118 on the graph adaptor, and the wrapped graph.
    119 For example, if an arc of a reversed digraph is deleted, this is carried
    120 out by deleting the corresponding arc of the original digraph, thus the
    121 adaptor modifies the original digraph.
    122 However in case of a residual digraph, this operation has no sense.
    123 
    124 Let us stand one more example here to simplify your work.
    125 ReverseDigraph has constructor
    126 \code
    127 ReverseDigraph(Digraph& digraph);
    128 \endcode
    129 This means that in a situation, when a <tt>const %ListDigraph&</tt>
    130 reference to a graph is given, then it have to be instantiated with
    131 <tt>Digraph=const %ListDigraph</tt>.
    132 \code
    133 int algorithm1(const ListDigraph& g) {
    134   ReverseDigraph<const ListDigraph> rg(g);
    135   return algorithm2(rg);
    136 }
    137 \endcode
    138 */
    139 
    140 /**
    14163@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    14264@ingroup graphs
    14365\brief Graph types between real graphs and graph adaptors.
    14466
    145 This group contains some graph types between real graphs and graph adaptors.
     67This group describes some graph types between real graphs and graph adaptors.
    14668These classes wrap graphs to give new functionality as the adaptors do it.
    14769On the other hand they are not light-weight structures as the adaptors.
     
    15375\brief Map structures implemented in LEMON.
    15476
    155 This group contains the map structures implemented in LEMON.
     77This group describes the map structures implemented in LEMON.
    15678
    15779LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    16688\brief Special graph-related maps.
    16789
    168 This group contains maps that are specifically designed to assign
    169 values to the nodes and arcs/edges of graphs.
    170 
    171 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
    172 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
     90This group describes maps that are specifically designed to assign
     91values to the nodes and arcs of graphs.
    17392*/
    17493
     
    17897\brief Tools to create new maps from existing ones
    17998
    180 This group contains map adaptors that are used to create "implicit"
     99This group describes map adaptors that are used to create "implicit"
    181100maps from other maps.
    182101
    183 Most of them are \ref concepts::ReadMap "read-only maps".
     102Most of them are \ref lemon::concepts::ReadMap "read-only maps".
    184103They can make arithmetic and logical operations between one or two maps
    185104(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    241160\brief Two dimensional data storages implemented in LEMON.
    242161
    243 This group contains two dimensional data storages implemented in LEMON.
     162This group describes two dimensional data storages implemented in LEMON.
    244163*/
    245164
     
    249168\brief %Path structures implemented in LEMON.
    250169
    251 This group contains the path structures implemented in LEMON.
     170This group describes the path structures implemented in LEMON.
    252171
    253172LEMON provides flexible data structures to work with paths.
     
    265184\brief Auxiliary data structures implemented in LEMON.
    266185
    267 This group contains some data structures implemented in LEMON in
     186This group describes some data structures implemented in LEMON in
    268187order to make it easier to implement combinatorial algorithms.
    269188*/
     
    271190/**
    272191@defgroup algs Algorithms
    273 \brief This group contains the several algorithms
     192\brief This group describes the several algorithms
    274193implemented in LEMON.
    275194
    276 This group contains the several algorithms
     195This group describes the several algorithms
    277196implemented in LEMON.
    278197*/
     
    283202\brief Common graph search algorithms.
    284203
    285 This group contains the common graph search algorithms, namely
    286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     204This group describes the common graph search algorithms like
     205Breadth-First Search (BFS) and Depth-First Search (DFS).
    287206*/
    288207
     
    292211\brief Algorithms for finding shortest paths.
    293212
    294 This 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.
     213This group describes the algorithms for finding shortest paths in graphs.
    308214*/
    309215
     
    313219\brief Algorithms for finding maximum flows.
    314220
    315 This group contains the algorithms for finding maximum flows and
     221This group describes the algorithms for finding maximum flows and
    316222feasible circulations.
    317223
    318 The \e maximum \e flow \e problem is to find a flow of maximum value between
    319 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    320 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    321 \f$s, t \in V\f$ source and target nodes.
    322 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
    323 following 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]
     224The maximum flow problem is to find a flow between a single source and
     225a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
     226directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
     227function and given \f$s, t \in V\f$ source and target node. The
     228maximum 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]
    329234
    330235LEMON contains several algorithms for solving maximum flow problems:
    331 - \ref EdmondsKarp Edmonds-Karp algorithm.
    332 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    333 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    334 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    335 
    336 In most cases the \ref Preflow "Preflow" algorithm provides the
    337 fastest method for computing a maximum flow. All implementations
    338 provides functions to also query the minimum cut, which is the dual
    339 problem of the maximum flow.
     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
     241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
     242fastest method to compute the maximum flow. All impelementations
     243provides functions to query the minimum cut, which is the dual linear
     244programming problem of the maximum flow.
    340245*/
    341246
     
    346251\brief Algorithms for finding minimum cost flows and circulations.
    347252
    348 This group contains the algorithms for finding minimum cost flows and
     253This group describes the algorithms for finding minimum cost flows and
    349254circulations.
    350 
    351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    352 minimum total cost from a set of supply nodes to a set of demand nodes
    353 in a network with capacity constraints (lower and upper bounds)
    354 and arc costs.
    355 Formally, let \f$G=(V,A)\f$ be a digraph,
    356 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
    357 upper 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
    360 on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
    361 signed supply values of the nodes.
    362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
    363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    364 \f$-sup(u)\f$ demand.
    365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
    366 of 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 
    373 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    374 zero or negative in order to have a feasible solution (since the sum
    375 of the expressions on the left-hand side of the inequalities is zero).
    376 It means that the total demand must be greater or equal to the total
    377 supply and all the supplies have to be carried out from the supply nodes,
    378 but there could be demands that are not satisfied.
    379 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
    380 constraints have to be satisfied with equality, i.e. all demands
    381 have to be satisfied and all supplies have to be used.
    382 
    383 If 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
    385 have to be satisfied while there could be supplies that are not used),
    386 then you could easily transform the problem to the above form by reversing
    387 the direction of the arcs and taking the negative of the supply values
    388 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
    389 However \ref NetworkSimplex algorithm also supports this form directly
    390 for the sake of convenience.
    391 
    392 A feasible solution for this problem can be found using \ref Circulation.
    393 
    394 Note that the above formulation is actually more general than the usual
    395 definition of the minimum cost flow problem, in which strict equalities
    396 are 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 
    401 However if the sum of the supply values is zero, then these two problems
    402 are equivalent. So if you need the equality form, you have to ensure this
    403 additional contraint for the algorithms.
    404 
    405 The dual solution of the minimum cost flow problem is represented by node
    406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
    407 An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
    408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
    409 node potentials the following \e complementary \e slackness optimality
    410 conditions 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  
    420 Here \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 
    424 All algorithms provide dual solution (node potentials) as well
    425 if an optimal flow is found.
    426 
    427 LEMON 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 
    437 Most of these implementations support the general inequality form of the
    438 minimum cost flow problem, but CancelAndTighten and CycleCanceling
    439 only support the equality form due to the primal method they use.
    440 
    441 In general NetworkSimplex is the most efficient implementation,
    442 but in special cases other algorithms could be faster.
    443 For example, if the total supply and/or capacities are rather small,
    444 CapacityScaling is usually the fastest algorithm (without effective scaling).
    445255*/
    446256
     
    451261\brief Algorithms for finding minimum cut in graphs.
    452262
    453 This group contains the algorithms for finding minimum cut in graphs.
    454 
    455 The \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
    457 outgoing 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
     263This group describes the algorithms for finding minimum cut in graphs.
     264
     265The 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
     267outgoing 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
    459269cut is the \f$X\f$ solution of the next optimization problem:
    460270
    461271\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    462     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     272\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
    463273
    464274LEMON contains several algorithms related to minimum cut problems:
    465275
    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.
     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
    472282
    473283If you want to find minimum cut just between two distinict nodes,
    474 see the \ref max_flow "maximum flow problem".
    475 */
    476 
    477 /**
    478 @defgroup graph_properties Connectivity and Other Graph Properties
     284please see the \ref max_flow "Maximum Flow page".
     285*/
     286
     287/**
     288@defgroup graph_prop Connectivity and Other Graph Properties
    479289@ingroup algs
    480290\brief Algorithms for discovering the graph properties
    481291
    482 This group contains the algorithms for discovering the graph properties
     292This group describes the algorithms for discovering the graph properties
    483293like connectivity, bipartiteness, euler property, simplicity etc.
    484294
     
    492302\brief Algorithms for planarity checking, embedding and drawing
    493303
    494 This group contains the algorithms for planarity checking,
     304This group describes the algorithms for planarity checking,
    495305embedding and drawing.
    496306
     
    504314\brief Algorithms for finding matchings in graphs and bipartite graphs.
    505315
    506 This group contains the algorithms for calculating
     316This group contains algorithm objects and functions to calculate
    507317matchings in graphs and bipartite graphs. The general matching problem is
    508 finding a subset of the edges for which each node has at most one incident
    509 edge.
     318finding a subset of the arcs which does not shares common endpoints.
    510319
    511320There are several different algorithms for calculate matchings in
    512321graphs.  The matching problems in bipartite graphs are generally
    513322easier than in general graphs. The goal of the matching optimization
    514 can be finding maximum cardinality, maximum weight or minimum cost
     323can be the finding maximum cardinality, maximum weight or minimum cost
    515324matching. The search can be constrained to find perfect or
    516325maximum cardinality matching.
    517326
    518 The 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.
     327LEMON 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
    536347
    537348\image html bipartite_matching.png
     
    544355\brief Algorithms for finding a minimum cost spanning tree in a graph.
    545356
    546 This group contains the algorithms for finding a minimum cost spanning
    547 tree in a graph.
     357This group describes the algorithms for finding a minimum cost spanning
     358tree in a graph
    548359*/
    549360
     
    553364\brief Auxiliary algorithms implemented in LEMON.
    554365
    555 This group contains some algorithms implemented in LEMON
     366This group describes some algorithms implemented in LEMON
    556367in order to make it easier to implement complex algorithms.
    557368*/
     
    562373\brief Approximation algorithms.
    563374
    564 This group contains the approximation and heuristic algorithms
     375This group describes the approximation and heuristic algorithms
    565376implemented in LEMON.
    566377*/
     
    568379/**
    569380@defgroup gen_opt_group General Optimization Tools
    570 \brief This group contains some general optimization frameworks
     381\brief This group describes some general optimization frameworks
    571382implemented in LEMON.
    572383
    573 This group contains some general optimization frameworks
     384This group describes some general optimization frameworks
    574385implemented in LEMON.
    575386*/
     
    580391\brief Lp and Mip solver interfaces for LEMON.
    581392
    582 This group contains Lp and Mip solver interfaces for LEMON. The
     393This group describes Lp and Mip solver interfaces for LEMON. The
    583394various LP solvers could be used in the same manner with this
    584395interface.
     
    599410\brief Metaheuristics for LEMON library.
    600411
    601 This group contains some metaheuristic optimization tools.
     412This group describes some metaheuristic optimization tools.
    602413*/
    603414
     
    614425\brief Simple basic graph utilities.
    615426
    616 This group contains some simple basic graph utilities.
     427This group describes some simple basic graph utilities.
    617428*/
    618429
     
    622433\brief Tools for development, debugging and testing.
    623434
    624 This group contains several useful tools for development,
     435This group describes several useful tools for development,
    625436debugging and testing.
    626437*/
     
    631442\brief Simple tools for measuring the performance of algorithms.
    632443
    633 This group contains simple tools for measuring the performance
     444This group describes simple tools for measuring the performance
    634445of algorithms.
    635446*/
     
    640451\brief Exceptions defined in LEMON.
    641452
    642 This group contains the exceptions defined in LEMON.
     453This group describes the exceptions defined in LEMON.
    643454*/
    644455
     
    647458\brief Graph Input-Output methods
    648459
    649 This group contains the tools for importing and exporting graphs
     460This group describes the tools for importing and exporting graphs
    650461and graph related data. Now it supports the \ref lgf-format
    651462"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    654465
    655466/**
    656 @defgroup lemon_io LEMON Graph Format
     467@defgroup lemon_io LEMON Input-Output
    657468@ingroup io_group
    658469\brief Reading and writing LEMON Graph Format.
    659470
    660 This group contains methods for reading and writing
     471This group describes methods for reading and writing
    661472\ref lgf-format "LEMON Graph Format".
    662473*/
     
    667478\brief General \c EPS drawer and graph exporter
    668479
    669 This group contains general \c EPS drawing methods and special
     480This group describes general \c EPS drawing methods and special
    670481graph 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 
    678 Tools 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 
    686 Tool to read graphs from \e Nauty format data.
    687482*/
    688483
     
    691486\brief Skeleton classes and concept checking classes
    692487
    693 This group contains the data/algorithm skeletons and concept checking
     488This group describes the data/algorithm skeletons and concept checking
    694489classes implemented in LEMON.
    695490
     
    721516\brief Skeleton and concept checking classes for graph structures
    722517
    723 This group contains the skeletons and concept checking classes of LEMON's
     518This group describes the skeletons and concept checking classes of LEMON's
    724519graph structures and helper classes used to implement these.
    725520*/
     
    730525\brief Skeleton and concept checking classes for maps
    731526
    732 This group contains the skeletons and concept checking classes of maps.
     527This group describes the skeletons and concept checking classes of maps.
    733528*/
    734529
     
    736531\anchor demoprograms
    737532
    738 @defgroup demos Demo Programs
     533@defgroup demos Demo programs
    739534
    740535Some demo programs are listed here. Their full source codes can be found in
    741536the \c demo subdirectory of the source tree.
    742537
    743 In 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
     538It order to compile them, use <tt>--enable-demo</tt> configure option when
     539build the library.
     540*/
     541
     542/**
     543@defgroup tools Standalone utility applications
    749544
    750545Some utility applications are listed here.
     
    754549*/
    755550
    756 }
  • doc/lgf.dox

    r440 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/license.dox

    r440 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/mainpage.dox

    r559 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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
    49 <a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
     48If you already feel like using our library, see the page that tells you
     49\ref getstart "How to start using LEMON".
     50
     51If you
     52want to see how LEMON works, see
     53some \ref demoprograms "demo programs".
    5054
    5155If you know what you are looking for then try to find it under the
    52 <a class="el" href="modules.html">Modules</a> section.
     56<a class="el" href="modules.html">Modules</a>
     57section.
    5358
    5459If you are a user of the old (0.x) series of LEMON, please check out the
  • doc/migration.dox

    r440 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
     28<tt>script/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>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
    58 strings, comments etc. as well as in all LEMON specific identifiers.
    59 So use the script carefully and make a backup copy of your source files
    60 before applying the script to them.</b>
     56<b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
     57the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
     58in strings, comments etc. as well as in all identifiers.</b>
    6159
    6260\section migration-lgf LGF tools
  • doc/named-param.dox

    r440 r269  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/namespaces.dox

    r440 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/template.h

    r440 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/CMakeLists.txt

    r627 r499  
    11INCLUDE_DIRECTORIES(
    2   ${PROJECT_SOURCE_DIR}
     2  ${CMAKE_SOURCE_DIR}
    33  ${PROJECT_BINARY_DIR}
    44)
     
    99)
    1010
    11 SET(LEMON_SOURCES
     11ADD_LIBRARY(lemon
    1212  arg_parser.cc
    1313  base.cc
    1414  color.cc
    15   lp_base.cc
    16   lp_skeleton.cc
    1715  random.cc
    1816  bits/windows.cc
    1917)
    20 
    21 IF(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)
    29 ENDIF(LEMON_HAVE_GLPK)
    30 
    31 IF(LEMON_HAVE_CPLEX)
    32   SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
    33   INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
    34 ENDIF(LEMON_HAVE_CPLEX)
    35 
    36 IF(LEMON_HAVE_CLP)
    37   SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
    38   INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
    39 ENDIF(LEMON_HAVE_CLP)
    40 
    41 IF(LEMON_HAVE_CBC)
    42   SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
    43   INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
    44 ENDIF(LEMON_HAVE_CBC)
    45 
    46 ADD_LIBRARY(lemon ${LEMON_SOURCES})
    4718
    4819INSTALL(
  • lemon/Makefile.am

    r627 r499  
    88
    99lemon_libemon_la_SOURCES = \
    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 \
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
     13        lemon/random.cc \
    1614        lemon/bits/windows.cc
    1715
    18 
    19 lemon_libemon_la_CXXFLAGS = \
    20         $(AM_CXXFLAGS) \
    21         $(GLPK_CFLAGS) \
    22         $(CPLEX_CFLAGS) \
    23         $(SOPLEX_CXXFLAGS) \
    24         $(CLP_CXXFLAGS) \
    25         $(CBC_CXXFLAGS)
    26 
    27 lemon_libemon_la_LDFLAGS = \
    28         $(GLPK_LIBS) \
    29         $(CPLEX_LIBS) \
    30         $(SOPLEX_LIBS) \
    31         $(CLP_LIBS) \
    32         $(CBC_LIBS)
    33 
    34 if HAVE_GLPK
    35 lemon_libemon_la_SOURCES += lemon/glpk.cc
    36 endif
    37 
    38 if HAVE_CPLEX
    39 lemon_libemon_la_SOURCES += lemon/cplex.cc
    40 endif
    41 
    42 if HAVE_SOPLEX
    43 lemon_libemon_la_SOURCES += lemon/soplex.cc
    44 endif
    45 
    46 if HAVE_CLP
    47 lemon_libemon_la_SOURCES += lemon/clp.cc
    48 endif
    49 
    50 if HAVE_CBC
    51 lemon_libemon_la_SOURCES += lemon/cbc.cc
    52 endif
     16#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
     17#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    5318
    5419lemon_HEADERS += \
    55         lemon/adaptors.h \
    56         lemon/arg_parser.h \
     20        lemon/arg_parser.h \
    5721        lemon/assert.h \
    58         lemon/bfs.h \
    59         lemon/bin_heap.h \
    60         lemon/circulation.h \
    61         lemon/clp.h \
    62         lemon/color.h \
     22        lemon/bfs.h \
     23        lemon/bin_heap.h \
     24        lemon/color.h \
    6325        lemon/concept_check.h \
    6426        lemon/config.h \
    65         lemon/connectivity.h \
    66         lemon/counter.h \
     27        lemon/counter.h \
    6728        lemon/core.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 \
     29        lemon/dfs.h \
     30        lemon/dijkstra.h \
     31        lemon/dim2.h \
    7532        lemon/error.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 \
     33        lemon/graph_to_eps.h \
    8334        lemon/kruskal.h \
    84         lemon/hao_orlin.h \
    8535        lemon/lgf_reader.h \
    8636        lemon/lgf_writer.h \
    8737        lemon/list_graph.h \
    88         lemon/lp.h \
    89         lemon/lp_base.h \
    90         lemon/lp_skeleton.h \
    91         lemon/list_graph.h \
    9238        lemon/maps.h \
    93         lemon/matching.h \
    9439        lemon/math.h \
    95         lemon/min_cost_arborescence.h \
    96         lemon/nauty_reader.h \
    97         lemon/network_simplex.h \
    9840        lemon/path.h \
    99         lemon/preflow.h \
    100         lemon/radix_sort.h \
    101         lemon/random.h \
     41        lemon/random.h \
    10242        lemon/smart_graph.h \
    103         lemon/soplex.h \
    104         lemon/suurballe.h \
    105         lemon/time_measure.h \
    106         lemon/tolerance.h \
     43        lemon/time_measure.h \
     44        lemon/tolerance.h \
    10745        lemon/unionfind.h \
    10846        lemon/bits/windows.h
     
    11250        lemon/bits/array_map.h \
    11351        lemon/bits/base_extender.h \
    114         lemon/bits/bezier.h \
     52        lemon/bits/bezier.h \
    11553        lemon/bits/default_map.h \
    116         lemon/bits/edge_set_extender.h \
    117         lemon/bits/enable_if.h \
    118         lemon/bits/graph_adaptor_extender.h \
     54        lemon/bits/enable_if.h \
    11955        lemon/bits/graph_extender.h \
    12056        lemon/bits/map_extender.h \
    12157        lemon/bits/path_dump.h \
    122         lemon/bits/solver_bits.h \
    12358        lemon/bits/traits.h \
    124         lemon/bits/variant.h \
    12559        lemon/bits/vector_map.h
    12660
  • lemon/arg_parser.cc

    r440 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/arg_parser.h

    r440 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/assert.h

    r440 r290  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/base.cc

    r507 r220  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2424namespace lemon {
    2525
    26   float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
     26  float Tolerance<float>::def_epsilon = 1e-4;
    2727  double Tolerance<double>::def_epsilon = 1e-10;
    2828  long double Tolerance<long double>::def_epsilon = 1e-14;
  • lemon/bfs.h

    r492 r301  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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 \c PredMap.
    53 
    54     ///This function instantiates a \ref PredMap.
     52    ///Instantiates a PredMap.
     53
     54    ///This function instantiates a PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///\ref PredMap.
     56    ///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 \c ProcessedMap.
    68 
    69     ///This function instantiates a \ref ProcessedMap.
     67    ///Instantiates a ProcessedMap.
     68
     69    ///This function instantiates a ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the \ref ProcessedMap
     71    ///we would like to define the 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 \c ReachedMap.
    87 
    88     ///This function instantiates a \ref ReachedMap.
     86    ///Instantiates a ReachedMap.
     87
     88    ///This function instantiates a ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the \ref ReachedMap.
     90    ///we would like to define the 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 \c DistMap.
    102 
    103     ///This function instantiates a \ref DistMap.
     101    ///Instantiates a DistMap.
     102
     103    ///This function instantiates a DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///\ref DistMap.
     105    ///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 type is \ref ListDigraph.
     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.
    123129#ifdef DOXYGEN
    124130  template <typename GR,
     
    146152    typedef PredMapPath<Digraph, PredMap> Path;
    147153
    148     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     154    ///The traits class.
    149155    typedef TR Traits;
    150156
     
    208214    typedef Bfs Create;
    209215
    210     ///\name Named Template Parameters
     216    ///\name Named template parameters
    211217
    212218    ///@{
     
    222228    };
    223229    ///\brief \ref named-templ-param "Named parameter" for setting
    224     ///\c PredMap type.
     230    ///PredMap type.
    225231    ///
    226232    ///\ref named-templ-param "Named parameter" for setting
    227     ///\c PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     233    ///PredMap type.
    229234    template <class T>
    230235    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    242247    };
    243248    ///\brief \ref named-templ-param "Named parameter" for setting
    244     ///\c DistMap type.
     249    ///DistMap type.
    245250    ///
    246251    ///\ref named-templ-param "Named parameter" for setting
    247     ///\c DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     252    ///DistMap type.
    249253    template <class T>
    250254    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    262266    };
    263267    ///\brief \ref named-templ-param "Named parameter" for setting
    264     ///\c ReachedMap type.
     268    ///ReachedMap type.
    265269    ///
    266270    ///\ref named-templ-param "Named parameter" for setting
    267     ///\c ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     271    ///ReachedMap type.
    269272    template <class T>
    270273    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    282285    };
    283286    ///\brief \ref named-templ-param "Named parameter" for setting
    284     ///\c ProcessedMap type.
     287    ///ProcessedMap type.
    285288    ///
    286289    ///\ref named-templ-param "Named parameter" for setting
    287     ///\c ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     290    ///ProcessedMap type.
    289291    template <class T>
    290292    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    301303    };
    302304    ///\brief \ref named-templ-param "Named parameter" for setting
    303     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     305    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    304306    ///
    305307    ///\ref named-templ-param "Named parameter" for setting
    306     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     308    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    307309    ///If you don't set it explicitly, it will be automatically allocated.
    308310    struct SetStandardProcessedMap :
     
    339341
    340342    ///Sets the map that stores the predecessor arcs.
    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.
     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.
    345346    ///\return <tt> (*this) </tt>
    346347    Bfs &predMap(PredMap &m)
     
    357358
    358359    ///Sets the map that indicates which nodes are reached.
    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.
     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.
    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(Node) "run()"
    378     ///or \ref init(), an instance will be allocated automatically.
    379     ///The destructor deallocates this automatically allocated map,
    380     ///of course.
     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.
    381380    ///\return <tt> (*this) </tt>
    382381    Bfs &processedMap(ProcessedMap &m)
     
    394393    ///Sets the map that stores the distances of the nodes calculated by
    395394    ///the algorithm.
    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.
     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.
    400398    ///\return <tt> (*this) </tt>
    401399    Bfs &distMap(DistMap &m)
     
    411409  public:
    412410
    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.
     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.
    420420
    421421    ///@{
    422422
    423     ///\brief Initializes the internal data structures.
    424     ///
    425423    ///Initializes the internal data structures.
     424
     425    ///Initializes the internal data structures.
     426    ///
    426427    void init()
    427428    {
     
    557558    }
    558559
    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.
     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.
    563565    bool emptyQueue() const { return _queue_tail==_queue_head; }
    564566
    565567    ///Returns the number of the nodes to be processed.
    566568
    567     ///Returns the number of the nodes to be processed
    568     ///in the queue.
     569    ///Returns the number of the nodes to be processed in the queue.
    569570    int queueSize() const { return _queue_head-_queue_tail; }
    570571
     
    731732
    732733    ///\name Query Functions
    733     ///The results of the BFS algorithm can be obtained using these
     734    ///The result of the %BFS algorithm can be obtained using these
    734735    ///functions.\n
    735     ///Either \ref run(Node) "run()" or \ref start() should be called
    736     ///before using them.
     736    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
     737    ///"start()" must be called before using them.
    737738
    738739    ///@{
     
    742743    ///Returns the shortest path to a node.
    743744    ///
    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.
     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.
    748749    Path path(Node t) const { return Path(*G, *_pred, t); }
    749750
     
    752753    ///Returns the distance of a node from the root(s).
    753754    ///
    754     ///\warning If node \c v is not reached from the root(s), then
     755    ///\warning If node \c v is not reachable from the root(s), then
    755756    ///the return value of this function is undefined.
    756757    ///
    757     ///\pre Either \ref run(Node) "run()" or \ref init()
    758     ///must be called before using this function.
     758    ///\pre Either \ref run() or \ref start() must be called before
     759    ///using this function.
    759760    int dist(Node v) const { return (*_dist)[v]; }
    760761
     
    763764    ///This function returns the 'previous arc' of the shortest path
    764765    ///tree for the node \c v, i.e. it returns the last arc of a
    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.
     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.
    767768    ///
    768769    ///The shortest path tree used here is equal to the shortest path
    769770    ///tree used in \ref predNode().
    770771    ///
    771     ///\pre Either \ref run(Node) "run()" or \ref init()
    772     ///must be called before using this function.
     772    ///\pre Either \ref run() or \ref start() must be called before
     773    ///using this function.
    773774    Arc predArc(Node v) const { return (*_pred)[v];}
    774775
     
    777778    ///This function returns the 'previous node' of the shortest path
    778779    ///tree for the node \c v, i.e. it returns the last but one node
    779     ///from a shortest path from a root to \c v. It is \c INVALID
    780     ///if \c v is not reached from the root(s) or if \c v is a root.
     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.
    781782    ///
    782783    ///The shortest path tree used here is equal to the shortest path
    783784    ///tree used in \ref predArc().
    784785    ///
    785     ///\pre Either \ref run(Node) "run()" or \ref init()
    786     ///must be called before using this function.
     786    ///\pre Either \ref run() or \ref start() must be called before
     787    ///using this function.
    787788    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    788789                                  G->source((*_pred)[v]); }
     
    794795    ///of the nodes calculated by the algorithm.
    795796    ///
    796     ///\pre Either \ref run(Node) "run()" or \ref init()
     797    ///\pre Either \ref run() or \ref init()
    797798    ///must be called before using this function.
    798799    const DistMap &distMap() const { return *_dist;}
     
    804805    ///arcs, which form the shortest path tree.
    805806    ///
    806     ///\pre Either \ref run(Node) "run()" or \ref init()
     807    ///\pre Either \ref run() or \ref init()
    807808    ///must be called before using this function.
    808809    const PredMap &predMap() const { return *_pred;}
    809810
    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()
     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()
    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(Node) "run()" method, it uses the
    961   /// functions and features of the plain \ref Bfs.
     960  /// It does not have own \ref run() method, it uses the functions
     961  /// 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(Node) "run()"
     1181  ///\warning Don't forget to put the \ref BfsWizard::run() "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 GR>
     1197  template <typename _Digraph>
    11981198  struct BfsVisitor {
    1199     typedef GR Digraph;
     1199    typedef _Digraph Digraph;
    12001200    typedef typename Digraph::Arc Arc;
    12011201    typedef typename Digraph::Node Node;
     
    12251225  };
    12261226#else
    1227   template <typename GR>
     1227  template <typename _Digraph>
    12281228  struct BfsVisitor {
    1229     typedef GR Digraph;
     1229    typedef _Digraph Digraph;
    12301230    typedef typename Digraph::Arc Arc;
    12311231    typedef typename Digraph::Node Node;
     
    12551255  ///
    12561256  /// Default traits class of BfsVisit class.
    1257   /// \tparam GR The type of the digraph the algorithm runs on.
    1258   template<class GR>
     1257  /// \tparam _Digraph The type of the digraph the algorithm runs on.
     1258  template<class _Digraph>
    12591259  struct BfsVisitDefaultTraits {
    12601260
    12611261    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef GR Digraph;
     1262    typedef _Digraph 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 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
     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
    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 TR Traits class to set various data types used by the
     1305  /// \tparam _Traits Traits class to set various data types used by the
    13061306  /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
     1307  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
    13081308  /// See \ref BfsVisitDefaultTraits for the documentation of
    13091309  /// a BFS visit traits class.
    13101310#ifdef DOXYGEN
    1311   template <typename GR, typename VS, typename TR>
     1311  template <typename _Digraph, typename _Visitor, typename _Traits>
    13121312#else
    1313   template <typename GR = ListDigraph,
    1314             typename VS = BfsVisitor<GR>,
    1315             typename TR = BfsVisitDefaultTraits<GR> >
     1313  template <typename _Digraph = ListDigraph,
     1314            typename _Visitor = BfsVisitor<_Digraph>,
     1315            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
    13161316#endif
    13171317  class BfsVisit {
     
    13191319
    13201320    ///The traits class.
    1321     typedef TR Traits;
     1321    typedef _Traits Traits;
    13221322
    13231323    ///The type of the digraph the algorithm runs on.
     
    13251325
    13261326    ///The visitor type used by the algorithm.
    1327     typedef VS Visitor;
     1327    typedef _Visitor 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(Node) "run()"
    1410     /// or \ref init(), an instance will be allocated automatically.
    1411     /// The destructor deallocates this automatically allocated map,
    1412     /// of course.
     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.
    14131412    /// \return <tt> (*this) </tt>
    14141413    BfsVisit &reachedMap(ReachedMap &m) {
     
    14231422  public:
    14241423
    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.
     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.
    14321434
    14331435    /// @{
     
    17291731
    17301732    /// \name Query Functions
    1731     /// The results of the BFS algorithm can be obtained using these
     1733    /// The result of the %BFS algorithm can be obtained using these
    17321734    /// functions.\n
    1733     /// Either \ref run(Node) "run()" or \ref start() should be called
    1734     /// before using them.
    1735 
     1735    /// Either \ref lemon::BfsVisit::run() "run()" or
     1736    /// \ref lemon::BfsVisit::start() "start()" must be called before
     1737    /// using them.
    17361738    ///@{
    17371739
    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()
     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()
    17431744    /// must be called before using this function.
    1744     bool reached(Node v) const { return (*_reached)[v]; }
     1745    bool reached(Node v) { return (*_reached)[v]; }
    17451746
    17461747    ///@}
  • lemon/bin_heap.h

    r584 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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.
    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.
     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.
    4341  ///
    44   ///\tparam PR Type of the priority of the items.
    45   ///\tparam IM A read and writable item map with int values, used internally
     42  ///\tparam _Prio Type of the priority of the items.
     43  ///\tparam _ItemIntMap A read and writable Item int map, used internally
    4644  ///to handle the cross references.
    47   ///\tparam Comp A functor class for the ordering of the priorities.
    48   ///The default is \c std::less<PR>.
     45  ///\tparam _Compare A class for the ordering of the priorities. The
     46  ///default is \c std::less<_Prio>.
    4947  ///
    5048  ///\sa FibHeap
    5149  ///\sa Dijkstra
    52   template <typename PR, typename IM, typename Comp = std::less<PR> >
     50  template <typename _Prio, typename _ItemIntMap,
     51            typename _Compare = std::less<_Prio> >
    5352  class BinHeap {
    5453
    5554  public:
    5655    ///\e
    57     typedef IM ItemIntMap;
    58     ///\e
    59     typedef PR Prio;
     56    typedef _ItemIntMap ItemIntMap;
     57    ///\e
     58    typedef _Prio Prio;
    6059    ///\e
    6160    typedef typename ItemIntMap::Key Item;
     
    6362    typedef std::pair<Item,Prio> Pair;
    6463    ///\e
    65     typedef Comp Compare;
     64    typedef _Compare Compare;
    6665
    6766    /// \brief Type to represent the items states.
     
    7170    /// heap's point of view, but may be useful to the user.
    7271    ///
    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.
     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...
    7574    enum State {
    76       IN_HEAP = 0,    ///< = 0.
    77       PRE_HEAP = -1,  ///< = -1.
    78       POST_HEAP = -2  ///< = -2.
     75      IN_HEAP = 0,
     76      PRE_HEAP = -1,
     77      POST_HEAP = -2
    7978    };
    8079
    8180  private:
    82     std::vector<Pair> _data;
    83     Compare _comp;
    84     ItemIntMap &_iim;
     81    std::vector<Pair> data;
     82    Compare comp;
     83    ItemIntMap &iim;
    8584
    8685  public:
     
    8887    ///
    8988    /// The constructor.
    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
     89    /// \param _iim should be given to the constructor, since it is used
    9990    /// internally to handle the cross references. The value of the map
    10091    /// should be PRE_HEAP (-1) for each element.
    101     ///
    102     /// \param comp The comparator function object.
    103     BinHeap(ItemIntMap &map, const Compare &comp)
    104       : _iim(map), _comp(comp) {}
     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) {}
    105104
    106105
     
    108107    ///
    109108    /// \brief Returns the number of items stored in the heap.
    110     int size() const { return _data.size(); }
     109    int size() const { return data.size(); }
    111110
    112111    /// \brief Checks if the heap stores no items.
    113112    ///
    114113    /// Returns \c true if and only if the heap stores no items.
    115     bool empty() const { return _data.empty(); }
     114    bool empty() const { return data.empty(); }
    116115
    117116    /// \brief Make empty this heap.
     
    122121    /// each item to \c PRE_HEAP.
    123122    void clear() {
    124       _data.clear();
     123      data.clear();
    125124    }
    126125
     
    130129    static int second_child(int i) { return 2*i+2; }
    131130    bool less(const Pair &p1, const Pair &p2) const {
    132       return _comp(p1.second, p2.second);
     131      return comp(p1.second, p2.second);
    133132    }
    134133
    135134    int bubble_up(int hole, Pair p) {
    136135      int par = parent(hole);
    137       while( hole>0 && less(p,_data[par]) ) {
    138         move(_data[par],hole);
     136      while( hole>0 && less(p,data[par]) ) {
     137        move(data[par],hole);
    139138        hole = par;
    140139        par = parent(hole);
     
    147146      int child = second_child(hole);
    148147      while(child < length) {
    149         if( less(_data[child-1], _data[child]) ) {
     148        if( less(data[child-1], data[child]) ) {
    150149          --child;
    151150        }
    152         if( !less(_data[child], p) )
     151        if( !less(data[child], p) )
    153152          goto ok;
    154         move(_data[child], hole);
     153        move(data[child], hole);
    155154        hole = child;
    156155        child = second_child(hole);
    157156      }
    158157      child--;
    159       if( child<length && less(_data[child], p) ) {
    160         move(_data[child], hole);
     158      if( child<length && less(data[child], p) ) {
     159        move(data[child], hole);
    161160        hole=child;
    162161      }
     
    167166
    168167    void move(const Pair &p, int i) {
    169       _data[i] = p;
    170       _iim.set(p.first, i);
     168      data[i] = p;
     169      iim.set(p.first, i);
    171170    }
    172171
     
    177176    /// \param p The pair to insert.
    178177    void push(const Pair &p) {
    179       int n = _data.size();
    180       _data.resize(n+1);
     178      int n = data.size();
     179      data.resize(n+1);
    181180      bubble_up(n, p);
    182181    }
     
    195194    /// \pre The heap must be nonempty.
    196195    Item top() const {
    197       return _data[0].first;
     196      return data[0].first;
    198197    }
    199198
     
    203202    /// \pre The heap must be nonempty.
    204203    Prio prio() const {
    205       return _data[0].second;
     204      return data[0].second;
    206205    }
    207206
     
    212211    /// \pre The heap must be non-empty.
    213212    void pop() {
    214       int n = _data.size()-1;
    215       _iim.set(_data[0].first, POST_HEAP);
     213      int n = data.size()-1;
     214      iim.set(data[0].first, POST_HEAP);
    216215      if (n > 0) {
    217         bubble_down(0, _data[n], n);
    218       }
    219       _data.pop_back();
     216        bubble_down(0, data[n], n);
     217      }
     218      data.pop_back();
    220219    }
    221220
     
    226225    /// \pre The item should be in the heap.
    227226    void erase(const Item &i) {
    228       int h = _iim[i];
    229       int n = _data.size()-1;
    230       _iim.set(_data[h].first, POST_HEAP);
     227      int h = iim[i];
     228      int n = data.size()-1;
     229      iim.set(data[h].first, POST_HEAP);
    231230      if( h < n ) {
    232         if ( bubble_up(h, _data[n]) == h) {
    233           bubble_down(h, _data[n], n);
     231        if ( bubble_up(h, data[n]) == h) {
     232          bubble_down(h, data[n], n);
    234233        }
    235234      }
    236       _data.pop_back();
     235      data.pop_back();
    237236    }
    238237
     
    241240    ///
    242241    /// This function returns the priority of item \c i.
    243     /// \param i The item.
    244242    /// \pre \c i must be in the heap.
     243    /// \param i The item.
    245244    Prio operator[](const Item &i) const {
    246       int idx = _iim[i];
    247       return _data[idx].second;
     245      int idx = iim[i];
     246      return data[idx].second;
    248247    }
    249248
     
    256255    /// \param p The priority.
    257256    void set(const Item &i, const Prio &p) {
    258       int idx = _iim[i];
     257      int idx = iim[i];
    259258      if( idx < 0 ) {
    260259        push(i,p);
    261260      }
    262       else if( _comp(p, _data[idx].second) ) {
     261      else if( comp(p, data[idx].second) ) {
    263262        bubble_up(idx, Pair(i,p));
    264263      }
    265264      else {
    266         bubble_down(idx, Pair(i,p), _data.size());
     265        bubble_down(idx, Pair(i,p), data.size());
    267266      }
    268267    }
     
    271270    ///
    272271    /// This method decreases the priority of item \c i to \c p.
    273     /// \param i The item.
    274     /// \param p The priority.
    275272    /// \pre \c i must be stored in the heap with priority at least \c
    276273    /// p relative to \c Compare.
     274    /// \param i The item.
     275    /// \param p The priority.
    277276    void decrease(const Item &i, const Prio &p) {
    278       int idx = _iim[i];
     277      int idx = iim[i];
    279278      bubble_up(idx, Pair(i,p));
    280279    }
     
    283282    ///
    284283    /// This method sets the priority of item \c i to \c p.
    285     /// \param i The item.
    286     /// \param p The priority.
    287284    /// \pre \c i must be stored in the heap with priority at most \c
    288285    /// p relative to \c Compare.
     286    /// \param i The item.
     287    /// \param p The priority.
    289288    void increase(const Item &i, const Prio &p) {
    290       int idx = _iim[i];
    291       bubble_down(idx, Pair(i,p), _data.size());
     289      int idx = iim[i];
     290      bubble_down(idx, Pair(i,p), data.size());
    292291    }
    293292
     
    301300    /// \param i The item.
    302301    State state(const Item &i) const {
    303       int s = _iim[i];
     302      int s = iim[i];
    304303      if( s>=0 )
    305304        s=0;
     
    321320          erase(i);
    322321        }
    323         _iim[i] = st;
     322        iim[i] = st;
    324323        break;
    325324      case IN_HEAP:
     
    335334    /// with the same prioriority as prevoiusly the \c i item.
    336335    void replace(const Item& i, const Item& j) {
    337       int idx = _iim[i];
    338       _iim.set(i, _iim[j]);
    339       _iim.set(j, idx);
    340       _data[idx].first = j;
     336      int idx = iim[i];
     337      iim.set(i, iim[j]);
     338      iim.set(j, idx);
     339      data[idx].first = j;
    341340    }
    342341
  • lemon/bits/alteration_notifier.h

    r440 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3636  // a container.
    3737  //
    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
     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
    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 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.
     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.
    5756  //
    5857  // For the proper functonality of this class, we should notify it
    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
     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
    6463  // clear() and build() members. Important rule that if we erase items
    65   // from graphs we should first signal the alteration and after that erase
     64  // from graph we should first signal the alteration and after that erase
    6665  // them from the container, on the other way on item addition we should
    6766  // first extend the container and just after that signal the alteration.
    6867  //
    6968  // The alteration can be observed with a class inherited from the
    70   // ObserverBase nested class. The signals can be handled with
     69  // \e ObserverBase nested class. The signals can be handled with
    7170  // overriding the virtual functions defined in the base class.  The
    7271  // observer base can be attached to the notifier with the
    73   // attach() member and can be detached with detach() function. The
     72  // \e attach() member and can be detached with detach() function. The
    7473  // alteration handlers should not call any function which signals
    7574  // an other alteration in the same notifier and should not
    7675  // detach any observer from the notifier.
    7776  //
    78   // Alteration observers try to be exception safe. If an add() or
    79   // a clear() function throws an exception then the remaining
     77  // Alteration observers try to be exception safe. If an \e add() or
     78  // a \e clear() function throws an exception then the remaining
    8079  // observeres will not be notified and the fulfilled additions will
    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
     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
    8786  // reliable. If we want to carry out the node degree in the graph
    88   // as in the \ref InDegMap and we use the reverseArc(), then it cause
     87  // as in the \ref InDegMap and we use the reverseEdge that cause
    8988  // unreliable functionality. Because the alteration observing signals
    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.
     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.
    9493  //
    9594  // \param _Container The container which is observed.
     
    105104    typedef _Item Item;
    106105
    107     // \brief Exception which can be called from clear() and
    108     // erase().
    109     //
    110     // From the clear() and erase() function only this
     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
    111110    // exception is allowed to throw. The exception immediatly
    112111    // detaches the current observer from the notifier. Because the
    113     // clear() and erase() should not throw other exceptions
     112    // \e clear() and \e erase() should not throw other exceptions
    114113    // it can be used to invalidate the observer.
    115114    struct ImmediateDetach {};
     
    123122    // The observer interface contains some pure virtual functions
    124123    // to override. The add() and erase() functions are
    125     // to notify the oberver when one item is added or erased.
     124    // to notify the oberver when one item is added or
     125    // erased.
    126126    //
    127127    // The build() and clear() members are to notify the observer
  • lemon/bits/array_map.h

    r617 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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 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.
     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.
    4243  //
    43   // The template parameters are the Graph, the current Item type and
     44  // The template parameters are the Graph the current Item type and
    4445  // the Value type of the map.
    4546  template <typename _Graph, typename _Item, typename _Value>
     
    4748    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4849  public:
    49     // The graph type.
    50     typedef _Graph GraphType;
    51     // The item type.
     50    // The graph type of the maps.
     51    typedef _Graph Graph;
     52    // The item type of the map.
    5253    typedef _Item Item;
    5354    // The reference map tag.
    5455    typedef True ReferenceMapTag;
    5556
    56     // The key type of the map.
     57    // The key type of the maps.
    5758    typedef _Item Key;
    5859    // The value type of the map.
     
    6465    typedef _Value& Reference;
    6566
    66     // The map type.
    67     typedef ArrayMap Map;
    68 
    6967    // The notifier type.
    7068    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    7169
    72   private:
    73  
    7470    // The MapBase of the Map which imlements the core regisitry function.
    7571    typedef typename Notifier::ObserverBase Parent;
    7672
     73  private:
    7774    typedef std::allocator<Value> Allocator;
    7875
     
    8279    //
    8380    // Graph initialized map constructor.
    84     explicit ArrayMap(const GraphType& graph) {
     81    explicit ArrayMap(const Graph& graph) {
    8582      Parent::attach(graph.notifier(Item()));
    8683      allocate_memory();
     
    9693    //
    9794    // It constructs a map and initialize all of the the map.
    98     ArrayMap(const GraphType& graph, const Value& value) {
     95    ArrayMap(const Graph& graph, const Value& value) {
    9996      Parent::attach(graph.notifier(Item()));
    10097      allocate_memory();
     
    140137    // \brief Template assign operator.
    141138    //
    142     // The given parameter should conform to the ReadMap
     139    // The given parameter should be conform to the ReadMap
    143140    // concecpt and could be indiced by the current item set of
    144141    // the NodeMap. In this case the value for each item
     
    204201    // \brief Adds a new key to the map.
    205202    //
    206     // It adds a new key to the map. It is called by the observer notifier
     203    // It adds a new key to the map. It called by the observer notifier
    207204    // and it overrides the add() member function of the observer base.
    208205    virtual void add(const Key& key) {
     
    232229    // \brief Adds more new keys to the map.
    233230    //
    234     // It adds more new keys to the map. It is called by the observer notifier
     231    // It adds more new keys to the map. It called by the observer notifier
    235232    // and it overrides the add() member function of the observer base.
    236233    virtual void add(const std::vector<Key>& keys) {
     
    276273    // \brief Erase a key from the map.
    277274    //
    278     // Erase a key from the map. It is called by the observer notifier
     275    // Erase a key from the map. It called by the observer notifier
    279276    // and it overrides the erase() member function of the observer base.
    280277    virtual void erase(const Key& key) {
     
    285282    // \brief Erase more keys from the map.
    286283    //
    287     // Erase more keys from the map. It is called by the observer notifier
     284    // Erase more keys from the map. It called by the observer notifier
    288285    // and it overrides the erase() member function of the observer base.
    289286    virtual void erase(const std::vector<Key>& keys) {
     
    294291    }
    295292
    296     // \brief Builds the map.
    297     //
    298     // It builds the map. It is called by the observer notifier
     293    // \brief Buildes the map.
     294    //
     295    // It buildes the map. It called by the observer notifier
    299296    // and it overrides the build() member function of the observer base.
    300297    virtual void build() {
     
    310307    // \brief Clear the map.
    311308    //
    312     // It erase all items from the map. It is called by the observer notifier
     309    // It erase all items from the map. It called by the observer notifier
    313310    // and it overrides the clear() member function of the observer base.
    314311    virtual void clear() {
  • lemon/bits/base_extender.h

    r617 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3131//\ingroup digraphbits
    3232//\file
    33 //\brief Extenders for the graph types
     33//\brief Extenders for the digraph types
    3434namespace lemon {
    3535
     
    3939  template <typename Base>
    4040  class UndirDigraphExtender : public Base {
     41
     42  public:
     43
    4144    typedef Base Parent;
    42 
    43   public:
    44 
    4545    typedef typename Parent::Arc Edge;
    4646    typedef typename Parent::Node Node;
     
    281281  template <typename Base>
    282282  class BidirBpGraphExtender : public Base {
     283  public:
    283284    typedef Base Parent;
    284 
    285   public:
    286285    typedef BidirBpGraphExtender Digraph;
    287286
  • lemon/bits/bezier.h

    r440 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/default_map.h

    r627 r500  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    154154  class DefaultMap
    155155    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
     156  public:
    156157    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     158    typedef DefaultMap<_Graph, _Item, _Value> Map;
    157159
    158   public:
    159     typedef DefaultMap<_Graph, _Item, _Value> Map;
    160    
    161     typedef typename Parent::GraphType GraphType;
     160    typedef typename Parent::Graph Graph;
    162161    typedef typename Parent::Value Value;
    163162
    164     explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
    165     DefaultMap(const GraphType& graph, const Value& value)
     163    explicit DefaultMap(const Graph& graph) : Parent(graph) {}
     164    DefaultMap(const Graph& graph, const Value& value)
    166165      : Parent(graph, value) {}
    167166
  • lemon/bits/enable_if.h

    r440 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/graph_extender.h

    r617 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030//\ingroup graphbits
    3131//\file
    32 //\brief Extenders for the graph types
     32//\brief Extenders for the digraph types
    3333namespace lemon {
    3434
    3535  // \ingroup graphbits
    3636  //
    37   // \brief Extender for the digraph implementations
     37  // \brief Extender for the Digraphs
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
     40  public:
     41
    4042    typedef Base Parent;
    41 
    42   public:
    43 
    4443    typedef DigraphExtender Digraph;
    4544
     
    220219    class NodeMap
    221220      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
     221    public:
     222      typedef DigraphExtender Digraph;
    222223      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    223224
    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;
    246248      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    247249
    248     public:
    249250      explicit ArcMap(const Digraph& digraph)
    250251        : Parent(digraph) {}
     
    330331  template <typename Base>
    331332  class GraphExtender : public Base {
     333  public:
     334
    332335    typedef Base Parent;
    333 
    334   public:
    335 
    336336    typedef GraphExtender Graph;
    337337
     
    602602    class NodeMap
    603603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
     604    public:
     605      typedef GraphExtender Graph;
    604606      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    605607
    606     public:
    607608      NodeMap(const Graph& graph)
    608609        : Parent(graph) {}
     
    626627    class ArcMap
    627628      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
     629    public:
     630      typedef GraphExtender Graph;
    628631      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    629632
    630     public:
    631633      ArcMap(const Graph& graph)
    632634        : Parent(graph) {}
     
    650652    class EdgeMap
    651653      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     654    public:
     655      typedef GraphExtender Graph;
    652656      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    653657
    654     public:
    655658      EdgeMap(const Graph& graph)
    656659        : Parent(graph) {}
  • lemon/bits/map_extender.h

    r617 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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
    3941    typedef _Map Parent;
    40     typedef typename Parent::GraphType GraphType;
    41 
    42   public:
    43 
    4442    typedef MapExtender Map;
     43
     44
     45    typedef typename Parent::Graph Graph;
    4546    typedef typename Parent::Key Item;
    4647
    4748    typedef typename Parent::Key Key;
    4849    typedef typename Parent::Value Value;
    49     typedef typename Parent::Reference Reference;
    50     typedef typename Parent::ConstReference ConstReference;
    5150
    5251    class MapIt;
     
    5857  public:
    5958
    60     MapExtender(const GraphType& graph)
     59    MapExtender(const Graph& graph)
    6160      : Parent(graph) {}
    6261
    63     MapExtender(const GraphType& graph, const Value& value)
     62    MapExtender(const Graph& graph, const Value& value)
    6463      : Parent(graph, value) {}
    6564
     
    7776  public:
    7877    class MapIt : public Item {
    79       typedef Item Parent;
    80 
    81     public:
    82 
     78    public:
     79
     80      typedef Item Parent;
    8381      typedef typename Map::Value Value;
    8482
     
    117115
    118116    class ConstMapIt : public Item {
    119       typedef Item Parent;
    120 
    121     public:
     117    public:
     118
     119      typedef Item Parent;
    122120
    123121      typedef typename Map::Value Value;
     
    148146
    149147    class ItemIt : public Item {
    150       typedef Item Parent;
    151 
    152     public:
     148    public:
     149
     150      typedef Item Parent;
    153151
    154152      ItemIt() {}
     
    179177  template <typename _Graph, typename _Map>
    180178  class SubMapExtender : public _Map {
     179  public:
     180
    181181    typedef _Map Parent;
    182     typedef _Graph GraphType;
    183 
    184   public:
    185 
    186182    typedef SubMapExtender Map;
     183
     184    typedef _Graph Graph;
     185
    187186    typedef typename Parent::Key Item;
    188187
    189188    typedef typename Parent::Key Key;
    190189    typedef typename Parent::Value Value;
    191     typedef typename Parent::Reference Reference;
    192     typedef typename Parent::ConstReference ConstReference;
    193190
    194191    class MapIt;
     
    200197  public:
    201198
    202     SubMapExtender(const GraphType& _graph)
     199    SubMapExtender(const Graph& _graph)
    203200      : Parent(_graph), graph(_graph) {}
    204201
    205     SubMapExtender(const GraphType& _graph, const Value& _value)
     202    SubMapExtender(const Graph& _graph, const Value& _value)
    206203      : Parent(_graph, _value), graph(_graph) {}
    207204
     
    223220  public:
    224221    class MapIt : public Item {
    225       typedef Item Parent;
    226 
    227     public:
     222    public:
     223
     224      typedef Item Parent;
    228225      typedef typename Map::Value Value;
    229226
     
    262259
    263260    class ConstMapIt : public Item {
    264       typedef Item Parent;
    265 
    266     public:
     261    public:
     262
     263      typedef Item Parent;
    267264
    268265      typedef typename Map::Value Value;
     
    293290
    294291    class ItemIt : public Item {
    295       typedef Item Parent;
    296 
    297     public:
     292    public:
     293
     294      typedef Item Parent;
    298295
    299296      ItemIt() {}
     
    320317  private:
    321318
    322     const GraphType& graph;
     319    const Graph& graph;
    323320
    324321  };
  • lemon/bits/path_dump.h

    r529 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    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>
     19#ifndef LEMON_BITS_PRED_MAP_PATH_H
     20#define LEMON_BITS_PRED_MAP_PATH_H
    2421
    2522namespace lemon {
  • lemon/bits/traits.h

    r616 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030  struct InvalidType {};
    3131
    32   template <typename GR, typename _Item>
     32  template <typename _Graph, typename _Item>
    3333  class ItemSetTraits {};
    3434
    3535
    36   template <typename GR, typename Enable = void>
     36  template <typename Graph, typename Enable = void>
    3737  struct NodeNotifierIndicator {
    3838    typedef InvalidType Type;
    3939  };
    40   template <typename GR>
     40  template <typename Graph>
    4141  struct NodeNotifierIndicator<
    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> {
     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> {
    5050  public:
    5151
    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 
     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> {
    6461    public:
    65       typedef typename GR::template NodeMap<V> Type;
     62      typedef typename Graph::template NodeMap<_Value> Parent;
     63      typedef typename Graph::template NodeMap<_Value> Type;
    6664      typedef typename Parent::Value Value;
    6765
    68       Map(const GR& _digraph) : Parent(_digraph) {}
    69       Map(const GR& _digraph, const Value& _value)
     66      Map(const Graph& _digraph) : Parent(_digraph) {}
     67      Map(const Graph& _digraph, const Value& _value)
    7068        : Parent(_digraph, _value) {}
    7169
     
    7472  };
    7573
    76   template <typename GR, typename Enable = void>
     74  template <typename Graph, typename Enable = void>
    7775  struct ArcNotifierIndicator {
    7876    typedef InvalidType Type;
    7977  };
    80   template <typename GR>
     78  template <typename Graph>
    8179  struct ArcNotifierIndicator<
    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> {
     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> {
    9088  public:
    9189
    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 
     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> {
    10499    public:
    105       typedef typename GR::template ArcMap<V> Type;
     100      typedef typename Graph::template ArcMap<_Value> Parent;
     101      typedef typename Graph::template ArcMap<_Value> Type;
    106102      typedef typename Parent::Value Value;
    107103
    108       Map(const GR& _digraph) : Parent(_digraph) {}
    109       Map(const GR& _digraph, const Value& _value)
     104      Map(const Graph& _digraph) : Parent(_digraph) {}
     105      Map(const Graph& _digraph, const Value& _value)
    110106        : Parent(_digraph, _value) {}
    111107    };
     
    113109  };
    114110
    115   template <typename GR, typename Enable = void>
     111  template <typename Graph, typename Enable = void>
    116112  struct EdgeNotifierIndicator {
    117113    typedef InvalidType Type;
    118114  };
    119   template <typename GR>
     115  template <typename Graph>
    120116  struct EdgeNotifierIndicator<
    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> {
     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> {
    129125  public:
    130126
    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 
     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> {
    143136    public:
    144       typedef typename GR::template EdgeMap<V> Type;
     137      typedef typename Graph::template EdgeMap<_Value> Parent;
     138      typedef typename Graph::template EdgeMap<_Value> Type;
    145139      typedef typename Parent::Value Value;
    146140
    147       Map(const GR& _digraph) : Parent(_digraph) {}
    148       Map(const GR& _digraph, const Value& _value)
     141      Map(const Graph& _digraph) : Parent(_digraph) {}
     142      Map(const Graph& _digraph, const Value& _value)
    149143        : Parent(_digraph, _value) {}
    150144    };
     
    211205  // Indicators for the tags
    212206
    213   template <typename GR, typename Enable = void>
     207  template <typename Graph, typename Enable = void>
    214208  struct NodeNumTagIndicator {
    215209    static const bool value = false;
    216210  };
    217211
    218   template <typename GR>
     212  template <typename Graph>
    219213  struct NodeNumTagIndicator<
    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>
     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>
    240221  struct EdgeNumTagIndicator {
    241222    static const bool value = false;
    242223  };
    243224
    244   template <typename GR>
     225  template <typename Graph>
    245226  struct EdgeNumTagIndicator<
    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>
     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>
    266234  struct FindEdgeTagIndicator {
    267235    static const bool value = false;
    268236  };
    269237
    270   template <typename GR>
     238  template <typename Graph>
    271239  struct FindEdgeTagIndicator<
    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>
     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>
    279247  struct UndirectedTagIndicator {
    280248    static const bool value = false;
    281249  };
    282250
    283   template <typename GR>
     251  template <typename Graph>
    284252  struct UndirectedTagIndicator<
    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>
     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>
    292260  struct BuildTagIndicator {
    293261    static const bool value = false;
    294262  };
    295263
    296   template <typename GR>
     264  template <typename Graph>
    297265  struct BuildTagIndicator<
    298     GR,
    299     typename enable_if<typename GR::BuildTag, void>::type
     266    Graph,
     267    typename enable_if<typename Graph::BuildTag, void>::type
    300268  > {
    301269    static const bool value = true;
  • lemon/bits/vector_map.h

    r617 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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 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.
     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.
    4444  //
    4545  // \tparam _Graph The graph this map is attached to.
     
    5757
    5858    // The graph type of the map.
    59     typedef _Graph GraphType;
     59    typedef _Graph Graph;
    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;
    7577
    7678    // The reference type of the map;
     
    7981    typedef typename Container::const_reference ConstReference;
    8082
    81   private:
    82 
    83     // The base class of the map.
    84     typedef typename Notifier::ObserverBase Parent;
    85 
    86   public:
    8783
    8884    // \brief Constructor to attach the new map into the notifier.
     
    9086    // It constructs a map and attachs it into the notifier.
    9187    // It adds all the items of the graph to the map.
    92     VectorMap(const GraphType& graph) {
     88    VectorMap(const Graph& graph) {
    9389      Parent::attach(graph.notifier(Item()));
    9490      container.resize(Parent::notifier()->maxId() + 1);
     
    9995    // It constructs a map uses a given value to initialize the map.
    10096    // It adds all the items of the graph to the map.
    101     VectorMap(const GraphType& graph, const Value& value) {
     97    VectorMap(const Graph& graph, const Value& value) {
    10298      Parent::attach(graph.notifier(Item()));
    10399      container.resize(Parent::notifier()->maxId() + 1, value);
     
    129125    // \brief Template assign operator.
    130126    //
    131     // The given parameter should conform to the ReadMap
     127    // The given parameter should be conform to the ReadMap
    132128    // concecpt and could be indiced by the current item set of
    133129    // the NodeMap. In this case the value for each item
     
    174170    // \brief Adds a new key to the map.
    175171    //
    176     // It adds a new key to the map. It is called by the observer notifier
     172    // It adds a new key to the map. It called by the observer notifier
    177173    // and it overrides the add() member function of the observer base.
    178174    virtual void add(const Key& key) {
     
    185181    // \brief Adds more new keys to the map.
    186182    //
    187     // It adds more new keys to the map. It is called by the observer notifier
     183    // It adds more new keys to the map. It called by the observer notifier
    188184    // and it overrides the add() member function of the observer base.
    189185    virtual void add(const std::vector<Key>& keys) {
     
    200196    // \brief Erase a key from the map.
    201197    //
    202     // Erase a key from the map. It is called by the observer notifier
     198    // Erase a key from the map. It called by the observer notifier
    203199    // and it overrides the erase() member function of the observer base.
    204200    virtual void erase(const Key& key) {
     
    208204    // \brief Erase more keys from the map.
    209205    //
    210     // It erases more keys from the map. It is called by the observer notifier
     206    // Erase more keys from the map. It called by the observer notifier
    211207    // and it overrides the erase() member function of the observer base.
    212208    virtual void erase(const std::vector<Key>& keys) {
     
    216212    }
    217213
    218     // \brief Build the map.
    219     //
    220     // It builds the map. It is called by the observer notifier
     214    // \brief Buildes the map.
     215    //
     216    // It buildes the map. It called by the observer notifier
    221217    // and it overrides the build() member function of the observer base.
    222218    virtual void build() {
     
    228224    // \brief Clear the map.
    229225    //
    230     // It erases all items from the map. It is called by the observer notifier
     226    // It erase all items from the map. It called by the observer notifier
    231227    // and it overrides the clear() member function of the observer base.
    232228    virtual void clear() {
  • lemon/bits/windows.h

    r529 r482  
    1717 */
    1818
    19 #ifndef LEMON_BITS_WINDOWS_H
    20 #define LEMON_BITS_WINDOWS_H
     19#ifndef LEMON_WINDOWS_H
     20#define LEMON_WINDOWS_H
    2121
    2222#include <string>
  • lemon/color.cc

    r440 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/color.h

    r440 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/concept_check.h

    r440 r285  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/concepts/digraph.h

    r580 r263  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    19 #ifndef LEMON_CONCEPTS_DIGRAPH_H
    20 #define LEMON_CONCEPTS_DIGRAPH_H
     19#ifndef LEMON_CONCEPT_DIGRAPH_H
     20#define LEMON_CONCEPT_DIGRAPH_H
    2121
    2222///\ingroup graph_concepts
     
    422422      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
    423423
    424       /// \brief Reference map of the nodes to type \c T.
    425       ///
    426       /// Reference map of the nodes to type \c T.
     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
    427428      template<class T>
    428       class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
     429      class NodeMap : public ReadWriteMap< Node, T > {
    429430      public:
    430431
     
    436437      private:
    437438        ///Copy constructor
    438         NodeMap(const NodeMap& nm) :
    439           ReferenceMap<Node, T, T&, const T&>(nm) { }
     439        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
    440440        ///Assignment operator
    441441        template <typename CMap>
     
    446446      };
    447447
    448       /// \brief Reference map of the arcs to type \c T.
     448      /// \brief Read write map of the arcs to type \c T.
    449449      ///
    450450      /// Reference map of the arcs to type \c T.
     451      /// \sa Reference
    451452      template<class T>
    452       class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
     453      class ArcMap : public ReadWriteMap<Arc,T> {
    453454      public:
    454455
     
    459460      private:
    460461        ///Copy constructor
    461         ArcMap(const ArcMap& em) :
    462           ReferenceMap<Arc, T, T&, const T&>(em) { }
     462        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
    463463        ///Assignment operator
    464464        template <typename CMap>
     
    472472      struct Constraints {
    473473        void constraints() {
    474           checkConcept<BaseDigraphComponent, _Digraph>();
    475474          checkConcept<IterableDigraphComponent<>, _Digraph>();
    476475          checkConcept<IDableDigraphComponent<>, _Digraph>();
     
    486485
    487486
    488 #endif
     487#endif // LEMON_CONCEPT_DIGRAPH_H
  • lemon/concepts/graph.h

    r580 r263  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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_CONCEPTS_GRAPH_H
    24 #define LEMON_CONCEPTS_GRAPH_H
     23#ifndef LEMON_CONCEPT_GRAPH_H
     24#define LEMON_CONCEPT_GRAPH_H
    2525
    2626#include <lemon/concepts/graph_components.h>
     27#include <lemon/concepts/graph.h>
    2728#include <lemon/core.h>
    2829
     
    498499      };
    499500
    500       /// \brief Reference map of the nodes to type \c T.
    501       ///
    502       /// Reference map of the nodes to type \c T.
     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
    503505      template<class T>
    504       class NodeMap : public ReferenceMap<Node, T, T&, const T&>
     506      class NodeMap : public ReadWriteMap< Node, T >
    505507      {
    506508      public:
     
    513515      private:
    514516        ///Copy constructor
    515         NodeMap(const NodeMap& nm) :
    516           ReferenceMap<Node, T, T&, const T&>(nm) { }
     517        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
    517518        ///Assignment operator
    518519        template <typename CMap>
     
    523524      };
    524525
    525       /// \brief Reference map of the arcs to type \c T.
    526       ///
    527       /// Reference map of the arcs to type \c T.
     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
    528530      template<class T>
    529       class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
     531      class ArcMap : public ReadWriteMap<Arc,T>
    530532      {
    531533      public:
     
    537539      private:
    538540        ///Copy constructor
    539         ArcMap(const ArcMap& em) :
    540           ReferenceMap<Arc, T, T&, const T&>(em) { }
     541        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
    541542        ///Assignment operator
    542543        template <typename CMap>
     
    547548      };
    548549
    549       /// Reference map of the edges to type \c T.
    550 
    551       /// Reference map of the edges to type \c T.
     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
    552554      template<class T>
    553       class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
     555      class EdgeMap : public ReadWriteMap<Edge,T>
    554556      {
    555557      public:
     
    561563      private:
    562564        ///Copy constructor
    563         EdgeMap(const EdgeMap& em) :
    564           ReferenceMap<Edge, T, T&, const T&>(em) {}
     565        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
    565566        ///Assignment operator
    566567        template <typename CMap>
     
    602603      /// \brief Opposite node on an arc
    603604      ///
    604       /// \return The opposite of the given node on the given edge.
     605      /// \return the opposite of the given Node on the given Edge
    605606      Node oppositeNode(Node, Edge) const { return INVALID; }
    606607
    607608      /// \brief First node of the edge.
    608609      ///
    609       /// \return The first node of the given edge.
     610      /// \return the first node of the given Edge.
    610611      ///
    611612      /// Naturally edges don't have direction and thus
    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
     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
    615616      /// edge, and is used to define the "default" direction
    616617      /// of the directed versions of the arcs.
    617       /// \sa v()
    618       /// \sa direction()
     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()
    633622      Node v(Edge) const { return INVALID; }
    634623
     
    749738      struct Constraints {
    750739        void constraints() {
    751           checkConcept<BaseGraphComponent, _Graph>();
    752740          checkConcept<IterableGraphComponent<>, _Graph>();
    753741          checkConcept<IDableGraphComponent<>, _Graph>();
  • lemon/concepts/graph_components.h

    r617 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2121///\brief The concept of graph components.
    2222
    23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    24 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     23
     24#ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
     25#define LEMON_CONCEPT_GRAPH_COMPONENTS_H
    2526
    2627#include <lemon/core.h>
     
    3233  namespace concepts {
    3334
    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.
     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.
    3839    ///
    3940    /// \note This class is a template class so that we can use it to
    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'.
     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
    4446#ifndef DOXYGEN
    45     template <char sel = '0'>
     47    template <char _selector = '0'>
    4648#endif
    4749    class GraphItem {
     
    4951      /// \brief Default constructor.
    5052      ///
    51       /// Default constructor.
    5253      /// \warning The default constructor is not required to set
    5354      /// the item to some well-defined value. So you should consider it
    5455      /// as uninitialized.
    5556      GraphItem() {}
    56 
    5757      /// \brief Copy constructor.
    5858      ///
    5959      /// Copy constructor.
     60      ///
    6061      GraphItem(const GraphItem &) {}
    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.
     62      /// \brief Invalid constructor \& conversion.
     63      ///
     64      /// This constructor initializes the item to be invalid.
    6665      /// \sa Invalid for more details.
    6766      GraphItem(Invalid) {}
    68 
    69       /// \brief Assignment operator.
    70       ///
    71       /// Assignment operator for the item.
    72       GraphItem& operator=(const GraphItem&) { return *this; }
    73 
     67      /// \brief Assign operator for nodes.
     68      ///
     69      /// The nodes are assignable.
     70      ///
     71      GraphItem& operator=(GraphItem const&) { return *this; }
    7472      /// \brief Equality operator.
    7573      ///
    76       /// Equality operator.
    77       bool operator==(const GraphItem&) const { return false; }
    78 
     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; }
    7977      /// \brief Inequality operator.
    8078      ///
    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).
     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.
    8987      ///
    9088      /// \note This operator only have to define some strict ordering of
    9189      /// the items; this order has nothing to do with the iteration
    9290      /// ordering of the items.
    93       bool operator<(const GraphItem&) const { return false; }
     91      bool operator<(GraphItem) const { return false; }
    9492
    9593      template<typename _GraphItem>
     
    103101
    104102          bool b;
     103          //          b = (ia == ib) && (ia != ib) && (ia < ib);
    105104          b = (ia == ib) && (ia != ib);
    106105          b = (ia == INVALID) && (ib != INVALID);
     
    113112    };
    114113
    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.
     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.
    121121    class BaseDigraphComponent {
    122122    public:
     
    126126      /// \brief Node class of the digraph.
    127127      ///
    128       /// This class represents the nodes of the digraph.
     128      /// This class represents the Nodes of the digraph.
     129      ///
    129130      typedef GraphItem<'n'> Node;
    130131
    131132      /// \brief Arc class of the digraph.
    132133      ///
    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.
     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.
    149153      Node oppositeNode(const Node&, const Arc&) const {
    150154        return INVALID;
     
    172176    };
    173177
    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.
     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.
    181187    class BaseGraphComponent : public BaseDigraphComponent {
    182188    public:
    183 
    184       typedef BaseGraphComponent Graph;
    185 
    186189      typedef BaseDigraphComponent::Node Node;
    187190      typedef BaseDigraphComponent::Arc Arc;
    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 
     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'> {
    197199      public:
     200        typedef GraphItem<'u'> Parent;
    198201        /// \brief Default constructor.
    199202        ///
    200         /// Default constructor.
    201203        /// \warning The default constructor is not required to set
    202204        /// the item to some well-defined value. So you should consider it
    203205        /// as uninitialized.
    204206        Edge() {}
    205 
    206207        /// \brief Copy constructor.
    207208        ///
    208209        /// Copy constructor.
     210        ///
    209211        Edge(const Edge &) : Parent() {}
    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.
     212        /// \brief Invalid constructor \& conversion.
     213        ///
     214        /// This constructor initializes the item to be invalid.
    215215        /// \sa Invalid for more details.
    216216        Edge(Invalid) {}
    217 
    218         /// \brief Constructor for conversion from an arc.
    219         ///
    220         /// Constructor for conversion from an arc.
     217        /// \brief Converter from arc to edge.
     218        ///
    221219        /// Besides the core graph item functionality each arc should
    222220        /// be convertible to the represented edge.
    223221        Edge(const Arc&) {}
    224 
    225         /// \brief Assign an arc to an edge.
    226         ///
    227         /// This function assigns an arc to an edge.
     222        /// \brief Assign arc to edge.
     223        ///
    228224        /// Besides the core graph item functionality each arc should
    229225        /// be convertible to the represented edge.
     
    231227      };
    232228
    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.
     229      /// \brief Returns the direction of the arc.
    256230      ///
    257231      /// Returns the direction of the arc. Each arc represents an
     
    260234      bool direction(const Arc&) const { return true; }
    261235
    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; }
     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;}
    267263
    268264      template <typename _Graph>
     
    274270        void constraints() {
    275271          checkConcept<BaseDigraphComponent, _Graph>();
    276           checkConcept<GraphItem<'e'>, Edge>();
     272          checkConcept<GraphItem<'u'>, Edge>();
    277273          {
    278274            Node n;
     
    282278            n = graph.v(ue);
    283279            e = graph.direct(ue, true);
    284             e = graph.direct(ue, false);
    285280            e = graph.direct(ue, n);
    286281            e = graph.oppositeArc(e);
     
    296291    };
    297292
    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;
     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;
    309304      typedef typename Base::Node Node;
    310305      typedef typename Base::Arc Arc;
    311306
    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; }
     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;}
    349346
    350347      template <typename _Digraph>
     
    372369    };
    373370
    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;
     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;
    386382      typedef typename Base::Edge Edge;
    387383
    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; }
     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;}
    408405
    409406      template <typename _Graph>
     
    411408
    412409        void constraints() {
     410          checkConcept<Base, _Graph >();
    413411          checkConcept<IDableDigraphComponent<Base>, _Graph >();
    414412          typename _Graph::Edge edge;
     
    424422    };
    425423
    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 {
     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 {
    432430    public:
    433431      /// \brief Default constructor.
    434432      ///
    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.
     433      /// @warning The default constructor sets the iterator
     434      /// to an undefined value.
    439435      GraphItemIt() {}
    440 
    441436      /// \brief Copy constructor.
    442437      ///
    443438      /// Copy constructor.
    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.
     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.
    455449      /// \sa Invalid for more details.
    456450      GraphItemIt(Invalid) {}
    457 
    458       /// \brief Assignment operator.
    459       ///
    460       /// Assignment operator for the iterator.
     451      /// \brief Assign operator for items.
     452      ///
     453      /// The items are assignable.
     454      ///
    461455      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
    462 
    463       /// \brief Increment the iterator.
    464       ///
    465       /// This operator increments the iterator, i.e. assigns it to the
    466       /// next item.
     456      /// \brief Next item.
     457      ///
     458      /// Assign the iterator to the next item.
     459      ///
    467460      GraphItemIt& operator++() { return *this; }
    468  
    469461      /// \brief Equality operator
    470462      ///
    471       /// Equality operator.
    472463      /// Two iterators are equal if and only if they point to the
    473464      /// same object or both are invalid.
    474465      bool operator==(const GraphItemIt&) const { return true;}
    475 
    476466      /// \brief Inequality operator
    477467      ///
    478       /// Inequality operator.
    479       /// Two iterators are equal if and only if they point to the
    480       /// same object or both are invalid.
     468      /// \sa operator==(Node n)
     469      ///
    481470      bool operator!=(const GraphItemIt&) const { return true;}
    482471
     
    484473      struct Constraints {
    485474        void constraints() {
    486           checkConcept<GraphItem<>, _GraphItemIt>();
    487475          _GraphItemIt it1(g);
    488476          _GraphItemIt it2;
    489           _GraphItemIt it3 = it1;
    490           _GraphItemIt it4 = INVALID;
    491477
    492478          it2 = ++it1;
     
    494480          ++(++it1);
    495481
    496           Item bi = it1;
     482          _Item bi = it1;
    497483          bi = it2;
    498484        }
    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 {
     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 {
    518500    public:
    519501      /// \brief Default constructor.
    520502      ///
    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.
     503      /// @warning The default constructor sets the iterator
     504      /// to an undefined value.
    525505      GraphIncIt() {}
    526 
    527506      /// \brief Copy constructor.
    528507      ///
    529508      /// Copy constructor.
    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.
     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.
    543521      /// \sa Invalid for more details.
    544522      GraphIncIt(Invalid) {}
    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.
     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      ///
    555532      GraphIncIt& operator++() { return *this; }
    556533
    557534      /// \brief Equality operator
    558535      ///
    559       /// Equality operator.
    560536      /// Two iterators are equal if and only if they point to the
    561537      /// same object or both are invalid.
     
    564540      /// \brief Inequality operator
    565541      ///
    566       /// Inequality operator.
    567       /// Two iterators are equal if and only if they point to the
    568       /// same object or both are invalid.
     542      /// \sa operator==(Node n)
     543      ///
    569544      bool operator!=(const GraphIncIt&) const { return true;}
    570545
     
    572547      struct Constraints {
    573548        void constraints() {
    574           checkConcept<GraphItem<sel>, _GraphIncIt>();
     549          checkConcept<GraphItem<_selector>, _GraphIncIt>();
    575550          _GraphIncIt it1(graph, node);
    576551          _GraphIncIt it2;
    577           _GraphIncIt it3 = it1;
    578           _GraphIncIt it4 = INVALID;
    579552
    580553          it2 = ++it1;
    581554          ++it2 = it1;
    582555          ++(++it1);
    583           Item e = it1;
     556          _Item e = it1;
    584557          e = it2;
    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.
     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.
    596573    /// This concept is part of the Digraph concept.
    597     template <typename BAS = BaseDigraphComponent>
    598     class IterableDigraphComponent : public BAS {
    599 
    600     public:
    601 
    602       typedef BAS Base;
     574    template <typename _Base = BaseDigraphComponent>
     575    class IterableDigraphComponent : public _Base {
     576
     577    public:
     578
     579      typedef _Base Base;
    603580      typedef typename Base::Node Node;
    604581      typedef typename Base::Arc Arc;
     
    606583      typedef IterableDigraphComponent Digraph;
    607584
    608       /// \name Base Iteration
    609       ///
    610       /// This interface provides functions for iteration on digraph items.
     585      /// \name Base iteration
     586      ///
     587      /// This interface provides functions for iteration on digraph items
    611588      ///
    612589      /// @{
    613590
    614       /// \brief Return the first node.
    615       ///
    616       /// This function gives back the first node in the iteration order.
     591      /// \brief Gives back the first node in the iterating order.
     592      ///
     593      /// Gives back the first node in the iterating order.
     594      ///
    617595      void first(Node&) const {}
    618596
    619       /// \brief Return the next node.
    620       ///
    621       /// This function gives back the next node in the iteration order.
     597      /// \brief Gives back the next node in the iterating order.
     598      ///
     599      /// Gives back the next node in the iterating order.
     600      ///
    622601      void next(Node&) const {}
    623602
    624       /// \brief Return the first arc.
    625       ///
    626       /// This function gives back the first arc in the iteration order.
     603      /// \brief Gives back the first arc in the iterating order.
     604      ///
     605      /// Gives back the first arc in the iterating order.
     606      ///
    627607      void first(Arc&) const {}
    628608
    629       /// \brief Return the next arc.
    630       ///
    631       /// This function gives back the next arc in the iteration order.
     609      /// \brief Gives back the next arc in the iterating order.
     610      ///
     611      /// Gives back the next arc in the iterating order.
     612      ///
    632613      void next(Arc&) const {}
    633614
    634       /// \brief Return the first arc incomming to the given node.
    635       ///
    636       /// This function gives back the first arc incomming to the
     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      ///
     621      void firstIn(Arc&, const Node&) const {}
     622
     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      ///
     628      void nextIn(Arc&) const {}
     629
     630      /// \brief Gives back the first of the arcs start from the
    637631      /// given node.
    638       void firstIn(Arc&, const Node&) const {}
    639 
    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.
    644       void nextIn(Arc&) const {}
    645 
    646       /// \brief Return the first arc outgoing form the given node.
    647       ///
    648       /// This function gives back the first arc outgoing form the
    649       /// given node.
     632      ///
     633      /// Gives back the first of the arcs start from the given node.
     634      ///
    650635      void firstOut(Arc&, const Node&) const {}
    651636
    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.
     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      ///
    656642      void nextOut(Arc&) const {}
    657643
    658644      /// @}
    659645
    660       /// \name Class Based Iteration
    661       ///
    662       /// This interface provides iterator classes for digraph items.
     646      /// \name Class based iteration
     647      ///
     648      /// This interface provides functions for iteration on digraph items
    663649      ///
    664650      /// @{
     
    670656      typedef GraphItemIt<Digraph, Node> NodeIt;
    671657
    672       /// \brief This iterator goes through each arc.
    673       ///
    674       /// This iterator goes through each arc.
     658      /// \brief This iterator goes through each node.
     659      ///
     660      /// This iterator goes through each node.
    675661      ///
    676662      typedef GraphItemIt<Digraph, Arc> ArcIt;
     
    678664      /// \brief This iterator goes trough the incoming arcs of a node.
    679665      ///
    680       /// This iterator goes trough the \e incoming arcs of a certain node
     666      /// This iterator goes trough the \e inccoming arcs of a certain node
    681667      /// of a digraph.
    682668      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
     
    690676      /// \brief The base node of the iterator.
    691677      ///
    692       /// This function gives back the base node of the iterator.
    693       /// It is always the target node of the pointed arc.
     678      /// Gives back the base node of the iterator.
     679      /// It is always the target of the pointed arc.
    694680      Node baseNode(const InArcIt&) const { return INVALID; }
    695681
    696682      /// \brief The running node of the iterator.
    697683      ///
    698       /// This function gives back the running node of the iterator.
    699       /// It is always the source node of the pointed arc.
     684      /// Gives back the running node of the iterator.
     685      /// It is always the source of the pointed arc.
    700686      Node runningNode(const InArcIt&) const { return INVALID; }
    701687
    702688      /// \brief The base node of the iterator.
    703689      ///
    704       /// This function gives back the base node of the iterator.
    705       /// It is always the source node of the pointed arc.
     690      /// Gives back the base node of the iterator.
     691      /// It is always the source of the pointed arc.
    706692      Node baseNode(const OutArcIt&) const { return INVALID; }
    707693
    708694      /// \brief The running node of the iterator.
    709695      ///
    710       /// This function gives back the running node of the iterator.
    711       /// It is always the target node of the pointed arc.
     696      /// Gives back the running node of the iterator.
     697      /// It is always the target of the pointed arc.
    712698      Node runningNode(const OutArcIt&) const { return INVALID; }
    713699
     
    751737
    752738            typename _Digraph::Node n;
    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);
     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);
    759745            ignore_unused_variable_warning(n);
    760746          }
     
    762748
    763749        const _Digraph& digraph;
    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.
     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.
    772758    /// This concept is part of the Graph concept.
    773     template <typename BAS = BaseGraphComponent>
    774     class IterableGraphComponent : public IterableDigraphComponent<BAS> {
    775     public:
    776 
    777       typedef BAS Base;
     759    template <typename _Base = BaseGraphComponent>
     760    class IterableGraphComponent : public IterableDigraphComponent<_Base> {
     761    public:
     762
     763      typedef _Base Base;
    778764      typedef typename Base::Node Node;
    779765      typedef typename Base::Arc Arc;
     
    783769      typedef IterableGraphComponent Graph;
    784770
    785       /// \name Base Iteration
    786       ///
    787       /// This interface provides functions for iteration on edges.
    788       ///
     771      /// \name Base iteration
     772      ///
     773      /// This interface provides functions for iteration on graph items
    789774      /// @{
    790775
    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.
     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      ///
    797784      void first(Edge&) const {}
    798785
    799       /// \brief Return the next edge.
    800       ///
    801       /// This function gives back the next edge in the iteration order.
     786      /// \brief Gives back the next edge in the iterating
     787      /// order.
     788      ///
     789      /// Gives back the next edge in the iterating order.
     790      ///
    802791      void next(Edge&) const {}
    803792
    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
     793
     794      /// \brief Gives back the first of the edges from the
    809795      /// 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.
    810801      void firstInc(Edge&, bool&, const Node&) const {}
    811802
     
    813804      /// given node.
    814805      ///
    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.
     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.
    817809      void nextInc(Edge&, bool&) const {}
    818810
    819       using IterableDigraphComponent<Base>::baseNode;
    820       using IterableDigraphComponent<Base>::runningNode;
     811      using IterableDigraphComponent<_Base>::baseNode;
     812      using IterableDigraphComponent<_Base>::runningNode;
    821813
    822814      /// @}
    823815
    824       /// \name Class Based Iteration
    825       ///
    826       /// This interface provides iterator classes for edges.
     816      /// \name Class based iteration
     817      ///
     818      /// This interface provides functions for iteration on graph items
    827819      ///
    828820      /// @{
    829821
    830       /// \brief This iterator goes through each edge.
    831       ///
    832       /// This iterator goes through each edge.
     822      /// \brief This iterator goes through each node.
     823      ///
     824      /// This iterator goes through each node.
    833825      typedef GraphItemIt<Graph, Edge> EdgeIt;
    834 
    835       /// \brief This iterator goes trough the incident edges of a
     826      /// \brief This iterator goes trough the incident arcs of a
    836827      /// node.
    837828      ///
    838       /// This iterator goes trough the incident edges of a certain
     829      /// This iterator goes trough the incident arcs of a certain
    839830      /// node of a graph.
    840       typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
    841 
     831      typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt;
    842832      /// \brief The base node of the iterator.
    843833      ///
    844       /// This function gives back the base node of the iterator.
     834      /// Gives back the base node of the iterator.
    845835      Node baseNode(const IncEdgeIt&) const { return INVALID; }
    846836
    847837      /// \brief The running node of the iterator.
    848838      ///
    849       /// This function gives back the running node of the iterator.
     839      /// Gives back the running node of the iterator.
    850840      Node runningNode(const IncEdgeIt&) const { return INVALID; }
    851841
     
    876866              typename _Graph::EdgeIt >();
    877867            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
    878               typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
     868              typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
    879869
    880870            typename _Graph::Node n;
    881             const typename _Graph::IncEdgeIt ieit(INVALID);
    882             n = graph.baseNode(ieit);
    883             n = graph.runningNode(ieit);
     871            typename _Graph::IncEdgeIt ueit(INVALID);
     872            n = graph.baseNode(ueit);
     873            n = graph.runningNode(ueit);
    884874          }
    885875        }
    886876
    887877        const _Graph& graph;
    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
     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
    896886    /// an observer-notifier pattern for each digraph item. More
    897887    /// obsevers can be registered into the notifier and whenever an
    898     /// alteration occured in the digraph all the observers will be
     888    /// alteration occured in the digraph all the observers will
    899889    /// notified about it.
    900     template <typename BAS = BaseDigraphComponent>
    901     class AlterableDigraphComponent : public BAS {
    902     public:
    903 
    904       typedef BAS Base;
     890    template <typename _Base = BaseDigraphComponent>
     891    class AlterableDigraphComponent : public _Base {
     892    public:
     893
     894      typedef _Base Base;
    905895      typedef typename Base::Node Node;
    906896      typedef typename Base::Arc Arc;
    907897
    908898
    909       /// Node alteration notifier class.
     899      /// The node observer registry.
    910900      typedef AlterationNotifier<AlterableDigraphComponent, Node>
    911901      NodeNotifier;
    912       /// Arc alteration notifier class.
     902      /// The arc observer registry.
    913903      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
    914904      ArcNotifier;
    915905
    916       /// \brief Return the node alteration notifier.
    917       ///
    918       /// This function gives back the node alteration notifier.
     906      /// \brief Gives back the node alteration notifier.
     907      ///
     908      /// Gives back the node alteration notifier.
    919909      NodeNotifier& notifier(Node) const {
    920          return NodeNotifier();
     910        return NodeNotifier();
    921911      }
    922912
    923       /// \brief Return the arc alteration notifier.
    924       ///
    925       /// This function gives back the arc alteration notifier.
     913      /// \brief Gives back the arc alteration notifier.
     914      ///
     915      /// Gives back the arc alteration notifier.
    926916      ArcNotifier& notifier(Arc) const {
    927917        return ArcNotifier();
     
    943933
    944934        const _Digraph& digraph;
    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
     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
    954945    /// obsevers can be registered into the notifier and whenever an
    955     /// alteration occured in the graph all the observers will be
     946    /// alteration occured in the graph all the observers will
    956947    /// notified about it.
    957     template <typename BAS = BaseGraphComponent>
    958     class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
    959     public:
    960 
    961       typedef BAS Base;
     948    template <typename _Base = BaseGraphComponent>
     949    class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
     950    public:
     951
     952      typedef _Base Base;
    962953      typedef typename Base::Edge Edge;
    963954
    964955
    965       /// Edge alteration notifier class.
     956      /// The arc observer registry.
    966957      typedef AlterationNotifier<AlterableGraphComponent, Edge>
    967958      EdgeNotifier;
    968959
    969       /// \brief Return the edge alteration notifier.
    970       ///
    971       /// This function gives back the edge alteration notifier.
     960      /// \brief Gives back the arc alteration notifier.
     961      ///
     962      /// Gives back the arc alteration notifier.
    972963      EdgeNotifier& notifier(Edge) const {
    973964        return EdgeNotifier();
     
    977968      struct Constraints {
    978969        void constraints() {
    979           checkConcept<AlterableDigraphComponent<Base>, _Graph>();
     970          checkConcept<AlterableGraphComponent<Base>, _Graph>();
    980971          typename _Graph::EdgeNotifier& uen
    981972            = graph.notifier(typename _Graph::Edge());
     
    984975
    985976        const _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     /// graph types, which can be used for associating data to graph items.
    994     /// The standard graph maps must conform to the ReferenceMap concept.
    995     template <typename GR, typename K, typename V>
    996     class GraphMap : public ReferenceMap<K, V, V&, const V&> {
    997       typedef ReferenceMap<K, V, V&, const V&> Parent;
    998 
    999     public:
    1000