COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [330:34e185734b42:331:a412d990f043] in lemon-1.0


Ignore:
Files:
9 added
2 deleted
71 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r155 r298  
    3030syntax: regexp
    3131(.*/)?\#[^/]*\#$
     32(.*/)?\.\#[^/]*$
    3233^doc/html/.*
     34^doc/.*\.tag
    3335^autom4te.cache/.*
    3436^build-aux/.*

  • CMakeLists.txt

    r141 r274  
    1 project (LEMON)
    2 enable_testing ()
    3 add_subdirectory (lemon)
    4 add_subdirectory (demo)
    5 add_subdirectory (test)
     1CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
     2
     3SET(PROJECT_NAME "LEMON")
     4SET(PROJECT_VERSION "hg-tip" CACHE STRING "The version string.")
     5
     6PROJECT(${PROJECT_NAME})
     7
     8SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
     9
     10INCLUDE(FindDoxygen)
     11INCLUDE(FindGhostscript)
     12
     13ENABLE_TESTING()
     14
     15ADD_SUBDIRECTORY(lemon)
     16ADD_SUBDIRECTORY(demo)
     17ADD_SUBDIRECTORY(doc)
     18ADD_SUBDIRECTORY(test)
     19
     20IF(WIN32)
     21  INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico
     22    DESTINATION bin)
     23ENDIF(WIN32)
     24
     25IF(WIN32)
     26  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
     27  SET(CPACK_PACKAGE_VENDOR
     28    "EGRES - Egervary Research Group on Combinatorial Optimization")
     29  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
     30    "LEMON - Library of Efficient Models and Optimization in Networks")
     31  SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
     32
     33  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     34
     35  SET(CPACK_PACKAGE_INSTALL_DIRECTORY
     36    "${PROJECT_NAME} ${PROJECT_VERSION}")
     37  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
     38    "${PROJECT_NAME} ${PROJECT_VERSION}")
     39
     40  # Variables to generate a component-based installer.
     41  #SET(CPACK_COMPONENTS_ALL headers library html_documentation)
     42
     43  #SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
     44  #SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Static library")
     45  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
     46
     47  #SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
     48  #  "C++ header files for use with the LEMON library")
     49  #SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     50  #  "Static library used to build programs with LEMON")
     51  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     52  #  "Doxygen generated documentation")
     53
     54  #SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     55
     56  #SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     57  #SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     58  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     59
     60  #SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
     61  #  "Components needed to develop software using LEMON")
     62  #SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
     63  #  "Documentation of LEMON")
     64
     65  #SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     66
     67  #SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
     68  #SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
     69  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
     70
     71  SET(CPACK_GENERATOR "NSIS")
     72  SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
     73  SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     74  #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
     75  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
     76  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     77  SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
     78  SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
     79  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
     80  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
     81    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\"
     82    ")
     83  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
     84    !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
     85    Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
     86    ")
     87
     88  INCLUDE(CPack)
     89ENDIF(WIN32)

  • INSTALL

    r5 r325  
    22=========================
    33
    4    Since you are reading this I assume you already obtained one of the release
     4Since you are reading this I assume you already obtained one of the release
    55tarballs and successfully extracted it. The latest version of LEMON is
    6 available at our webpage (http://lemon.cs.elte.hu/).
     6available at our web page (http://lemon.cs.elte.hu/).
    77
    8    In order to install LEMON from the extracted source tarball you have to
     8In order to install LEMON from the extracted source tarball you have to
    99issue the following commands:
    1010
    11   1. `cd lemon-x.y.z'
     11   1. `cd lemon-x.y.z'
    1212
    13      This changes to the directory which was created when you extracted the
    14      sources. The x.y.z part is a version number.
     13      This command changes to the directory which was created when you
     14      extracted the sources. The x.y.z part is a version number.
    1515
    16   2. `./configure'
     16   2. `./configure'
    1717
    18      This runs the configure shell script, which does some checks and
    19      configuration (creates makefiles etc).
     18      This command runs the configure shell script, which does some checks and
     19      creates the makefiles.
    2020
    21   3. `make'
     21   3. `make'
    2222
    23      This command compiles the non-template part of LEMON into libemon.a file.
    24      It also compiles the benchmark and demo programs when enabled.
     23      This command compiles the non-template part of LEMON into libemon.a
     24      file. It also compiles the programs in the tools and demo subdirectories
     25      when enabled.
    2526
    26   4. `make check'
     27   4. `make check'
    2728
    28      This step is optional, but recommended. It runs the test programs that we
    29      developed for LEMON to check whether the library works properly on your
    30      platform.
     29      This step is optional, but recommended. It runs the test programs that
     30      we developed for LEMON to check whether the library works properly on
     31      your platform.
    3132
    32   5. `make install'
     33   5. `make install'
    3334
    34      This command installs LEMON under /usr/local (you will need root
    35      privileges to be able to do that). If you want to install it to some
    36      other location, then pass the --prefix=DIRECTORY flag to configure in
    37      step 1. For example: `./configure --prefix=/home/username/lemon'
     35      This command installs LEMON under /usr/local (you will need root
     36      privileges to be able to do that). If you want to install it to some
     37      other location, then pass the --prefix=DIRECTORY flag to configure in
     38      step 2. For example: `./configure --prefix=/home/username/lemon'.
     39
     40   6. `make install-html'
     41
     42      This command installs the documentation under share/doc/lemon/docs. The
     43      generated documentation is included in the tarball. If you want to
     44      generate it yourself, then run `make html'. Note that for this you need
     45      to have the following programs installed: Doxygen, Graphviz, Ghostscript,
     46      Latex.
    3847
    3948
    40 Configure Flags
    41 ===============
     49Configure Options and Variables
     50===============================
    4251
    43    You can pass the following flags to configure in step 1
    44 (see ./configure --help for more):
     52In step 2 you can customize the actions of configure by setting variables
     53and passing options to it. This can be done like this:
     54`./configure [OPTION]... [VARIABLE=VALUE]...'
    4555
    46 CXX=comp
     56Below you will find some useful variables and options (see `./configure --help'
     57for more):
     58
     59CXX='comp'
    4760
    4861  Change the C++ compiler to 'comp'.
    … …  
    5063CXXFLAGS='flags'
    5164
    52   Pass the 'flags' to the compiler. For example
    53   CXXFLAGS='-O3 -march=pentium-m'
    54   turns  on generation of aggressively optimized
    55   Pentium-M specific code.
     65  Pass the 'flags' to the compiler. For example CXXFLAGS='-O3 -march=pentium-m'
     66  turns on generation of aggressively optimized Pentium-M specific code.
     67
     68--prefix=PREFIX
     69
     70  Set the installation prefix to PREFIX. By default it is /usr/local.
    5671
    5772--enable-demo
    5873
    59    Build the demo programs too.
     74   Build the examples in the demo subdirectory.
    6075
    6176--disable-demo
    6277
    63    Do not build the demo programs (default).
     78   Do not build the examples in the demo subdirectory (default).
    6479
    65 --enable-benchmark
     80--enable-tools
    6681
    67    Build the benchmark programs too.
     82   Build the programs in the tools subdirectory (default).
    6883
    69 --disable-benchmark
     84--disable-tools
    7085
    71    Do not build the benchmark programs (default).
     86   Do not build the programs in the tools subdirectory.
    7287
    7388--with-glpk[=PREFIX]
    … …  
    116131
    117132   Disable CPLEX support.
     133
     134--with-soplex[=PREFIX]
     135
     136   Enable SoPlex support (default). You should specify the prefix too if
     137   you installed SoPlex to some non-standard location (e.g. your home
     138   directory). If it is not found, SoPlex support will be disabled.
     139
     140--with-soplex-includedir=DIR
     141
     142   The directory where the SoPlex header files are located. This is only
     143   useful when the SoPlex headers and libraries are not under the same
     144   prefix (which is unlikely).
     145
     146--with-soplex-libdir=DIR
     147
     148   The directory where the SoPlex libraries are located. This is only
     149   useful when the SoPlex headers and libraries are not under the same
     150   prefix (which is unlikely).
     151
     152--without-soplex
     153
     154   Disable SoPlex support.

  • Makefile.am

    r330 r331  
    1010        m4/lx_check_glpk.m4 \
    1111        m4/lx_check_soplex.m4 \
    12         CMakeLists.txt
     12        CMakeLists.txt \
     13        cmake
    1314
    1415pkgconfigdir = $(libdir)/pkgconfig
    … …  
    2526bin_PROGRAMS =
    2627check_PROGRAMS =
     28dist_bin_SCRIPTS =
    2729TESTS =
    2830XFAIL_TESTS =
    … …  
    3234include doc/Makefile.am
    3335include demo/Makefile.am
    34 include benchmark/Makefile.am
    3536include tools/Makefile.am
    3637

  • NEWS

    r5 r262  
     120XX-XX-XX Version 1.0 released
     2
     3        This is the first stable release of LEMON. Compared to the 0.x
     4        release series, it features a considerably smaller but more
     5        matured set of tools. The API has also completely revised and
     6        changed in several places.
     7
     8        * The major name changes compared to the 0.x series
     9          * Graph -> Digraph, UGraph -> Graph
     10          * Edge -> Arc, UEdge -> Edge
     11          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
     12        * Other improvements
     13          * Better documentation
     14          * Reviewed and cleaned up codebase
     15          * CMake based build system (along with the autotools based one)
     16        * Contents of the library (ported from 0.x)
     17          * Algorithms
     18            * breadth-first search (bfs.h)
     19            * depth-first search (dfs.h)
     20            * Dijkstra's algorithm (dijkstra.h)
     21            * Kruskal's algorithm (kruskal.h)
     22          * Data structures
     23            * graph data structures (list_graph.h, smart_graph.h)
     24            * path data structures (path.h)
     25            * binary heap data structure (bin_heap.h)
     26            * union-find data structures (unionfind.h)
     27            * miscellaneous property maps (maps.h)
     28            * two dimensional vector and bounding box (dim2.h)
     29          * Concepts
     30            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     31              concepts/graph_components.h)
     32            * concepts for other structures (concepts/heap.h, concepts/maps.h,
     33              concepts/path.h)
     34          * Tools
     35            * Mersenne twister random number generator (random.h)
     36            * tools for measuring cpu and wall clock time (time_measure.h)
     37            * tools for counting steps and events (counter.h)
     38            * tool for parsing command line arguments (arg_parser.h)
     39            * tool for visualizing graphs (graph_to_eps.h)
     40            * tools for reading and writing data in LEMON Graph Format
     41              (lgf_reader.h, lgf_writer.h)
     42            * tools to handle the anomalies of calculations with
     43              floating point numbers (tolerance.h)
     44            * tools to manage RGB colors (color.h)
     45          * Infrastructure
     46            * extended assertion handling (assert.h)
     47            * exception classes and error handling (error.h)
     48            * concept checking (concept_check.h)
     49            * commonly used mathematical constants (math.h)

  • README

    r24 r325  
    1 ------------------------------------------------------------------
     1==================================================================
    22LEMON - a Library of Efficient Models and Optimization in Networks
    3 ------------------------------------------------------------------
     3==================================================================
    44
    5 LEMON is the abbreviation of Library of Efficient Models and
    6 Optimization in Networks. It is an open source library written in
    7 C++. It provides a set of easy-to-use implementation of common data
    8 structures and algorithms in the area of optimization and helps
    9 implementing new ones. It is an especially suitable tool to solve the
    10 design and optimization problems of telecommunications networks. To
    11 achieve wide usability, a fundamental design requirement is the
    12 genericity of interface of data structures and algorithms. LEMON is an
    13 open source library end invites people all around the world in its
    14 development.
     5LEMON is an open source library written in C++. It provides
     6easy-to-use implementations of common data structures and algorithms
     7in the area of optimization and helps implementing new ones. The main
     8focus is on graphs and graph algorithms, thus it is especially
     9suitable for solving design and optimization problems of
     10telecommunication networks. To achieve wide usability its data
     11structures and algorithms provide generic interfaces.
    1512
    16 --------
    1713Contents
    18 --------
     14========
    1915
    20 COPYING, LICENSE
     16LICENSE
    2117
    22   Copying, distribution and modification conditions and terms.
     18   Copying, distribution and modification conditions and terms.
    2319
    2420INSTALL
    2521
    26   For general building and installation instructions, see the file.
     22   General building and installation instructions.
    2723
    2824lemon/
    2925
    30   Source code of LEMON itself.
     26   Source code of LEMON library.
    3127
    3228doc/
    3329
    34   Documentation of LEMON. The starting page is doc/html/index.html.
    35   The documentation installs into the directory
    36 
    37     /usr/local/share/doc/lemon/html
    38 
    39   or -- if you use different prefix -- into
    40 
    41     ${prefix}/share/doc/lemon/html
    42 
    43   (see also INSTALL).
     30   Documentation of LEMON. The starting page is doc/html/index.html.
    4431
    4532demo/
    4633
    47   Some demonstration programs to make you easier to get familiar with
    48   LEMON. Use --enable-demo configure option to also compile these codes
    49   (see also INSTALL).
     34   Some example programs to make you easier to get familiar with LEMON.
    5035
    5136test/
    5237
    53   Contains programs to check the integrity and correctness of
    54   LEMON. The command 'make check' performs these tests.
     38   Programs to check the integrity and correctness of LEMON.
    5539
    56 benchmark/
    57  
    58   Contains programs measuring the performance of LEMON. Use
    59   --enable-benchmark configure option to also compile these codes (see
    60   also INSTALL).
     40tools/
     41
     42   Various utilities related to LEMON.

  • configure.ac

    r219 r314  
    22
    33dnl Version information.
    4 m4_define([lemon_version_number], [])
     4m4_define([lemon_version_number],
     5        [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
     6dnl m4_define([lemon_version_number], [])
     7m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
    58m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
    6 m4_define([lemon_version], [ifelse(lemon_version_number(), [], [lemon_hg_revision()], [lemon_version_number()])])
     9m4_define([lemon_version], [ifelse(lemon_version_number(),
     10                           [],
     11                           [lemon_hg_path().lemon_hg_revision()],
     12                           [lemon_version_number()])])
    713
    814AC_PREREQ([2.59])
    9 AC_INIT([LEMON], [lemon_version()], [lemon-devel@lemon.cs.elte.hu], [lemon])
     15AC_INIT([LEMON], [lemon_version()], [lemon-user@lemon.cs.elte.hu], [lemon])
    1016AC_CONFIG_AUX_DIR([build-aux])
    1117AC_CONFIG_MACRO_DIR([m4])
    … …  
    1521
    1622lx_cmdline_cxxflags_set=${CXXFLAGS+set}
     23
     24dnl Do compilation tests using the C++ compiler.
     25AC_LANG([C++])
    1726
    1827dnl Checks for programs.
    … …  
    2635AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    2736
    28 if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then
     37dnl Detect Intel compiler.
     38AC_MSG_CHECKING([whether we are using the Intel C++ compiler])
     39AC_COMPILE_IFELSE([#ifndef __INTEL_COMPILER
     40choke me
     41#endif], [ICC=[yes]], [ICC=[no]])
     42if test x"$ICC" = x"yes"; then
     43  AC_MSG_RESULT([yes])
     44else
     45  AC_MSG_RESULT([no])
     46fi
     47
     48dnl Set custom compiler flags when using g++.
     49if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
    2950  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"
    3051fi
    3152
    3253dnl Checks for libraries.
    33 LX_CHECK_GLPK
    34 LX_CHECK_CPLEX
    35 LX_CHECK_SOPLEX
     54#LX_CHECK_GLPK
     55#LX_CHECK_CPLEX
     56#LX_CHECK_SOPLEX
    3657
    37 dnl Disable/enable building the demo programs
     58dnl Disable/enable building the demo programs.
    3859AC_ARG_ENABLE([demo],
    3960AS_HELP_STRING([--enable-demo], [build the demo programs])
    … …  
    4869AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
    4970
    50 dnl Disable/enable building the binary tools
     71dnl Disable/enable building the binary tools.
    5172AC_ARG_ENABLE([tools],
    5273AS_HELP_STRING([--enable-tools], [build additional tools @<:@default@:>@])
    … …  
    6081fi
    6182AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
    62 
    63 dnl Disable/enable building the benchmarks
    64 AC_ARG_ENABLE([benchmark],
    65 AS_HELP_STRING([--enable-benchmark], [build the benchmarks])
    66 AS_HELP_STRING([--disable-benchmark], [do not build the benchmarks @<:@default@:>@]),
    67               [], [enable_benchmark=no])
    68 AC_MSG_CHECKING([whether to build the benchmarks])
    69 if test x"$enable_benchmark" != x"no"; then
    70   AC_MSG_RESULT([yes])
    71 else
    72   AC_MSG_RESULT([no])
    73 fi
    74 AM_CONDITIONAL([WANT_BENCHMARK], [test x"$enable_benchmark" != x"no"])
    7583
    7684dnl Checks for header files.
    … …  
    108116echo C++ compiles flags............ : $CXXFLAGS
    109117echo
    110 echo GLPK support.................. : $lx_glpk_found
    111 echo CPLEX support................. : $lx_cplex_found
    112 echo SOPLEX support................ : $lx_soplex_found
    113 echo
    114 echo Build benchmarks.............. : $enable_benchmark
     118#echo GLPK support.................. : $lx_glpk_found
     119#echo CPLEX support................. : $lx_cplex_found
     120#echo SOPLEX support................ : $lx_soplex_found
     121#echo
    115122echo Build demo programs........... : $enable_demo
    116123echo Build additional tools........ : $enable_tools

  • demo/CMakeLists.txt

    r141 r225  
    1 include_directories (${LEMON_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
    22
    3 link_directories (${LEMON_BINARY_DIR}/lemon)
     3LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
    44
    5 set (DEMOS
     5SET(DEMOS
    66  arg_parser_demo
    77  graph_to_eps_demo
    88  lgf_demo)
    99
    10 foreach (DEMO_NAME ${DEMOS})
    11   add_executable (${DEMO_NAME} ${DEMO_NAME}.cc)
    12   target_link_libraries (${DEMO_NAME} lemon)
    13   endforeach (DEMO_NAME)
     10FOREACH(DEMO_NAME ${DEMOS})
     11  ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc)
     12  TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
     13ENDFOREACH(DEMO_NAME)

  • demo/arg_parser_demo.cc

    r209 r315  
    2828
    2929using namespace lemon;
    30 int main(int argc, const char **argv)
     30int main(int argc, char **argv)
    3131{
    3232  // Initialize the argument parser

  • demo/graph_to_eps_demo.cc

    r220 r317  
    2727/// how to handle parallel egdes, how to change the properties (like
    2828/// color, shape, size, title etc.) of nodes and arcs individually
    29 /// using appropriate \ref maps-page "graph maps".
     29/// using appropriate graph maps.
    3030///
    3131/// \include graph_to_eps_demo.cc

  • demo/lgf_demo.cc

    r209 r294  
    4545
    4646  try {
    47     digraphReader("digraph.lgf", g). // read the directed graph into g
     47    digraphReader(g, "digraph.lgf"). // read the directed graph into g
    4848      arcMap("capacity", cap).       // read the 'capacity' arc map into cap
    4949      node("source", s).             // read 'source' node to s
    5050      node("target", t).             // read 'target' node to t
    5151      run();
    52   } catch (DataFormatError& error) { // check if there was any error
     52  } catch (Exception& error) { // check if there was any error
    5353    std::cerr << "Error: " << error.what() << std::endl;
    5454    return -1;
    … …  
    6161  std::cout << "We can write it to the standard output:" << std::endl;
    6262
    63   digraphWriter(std::cout, g).     // write g to the standard output
     63  digraphWriter(g).                // write g to the standard output
    6464    arcMap("capacity", cap).       // write cap into 'capacity'
    6565    node("source", s).             // write s to 'source'

  • doc/Doxyfile.in

    r219 r321  
    1 # Doxyfile 1.5.5
     1# Doxyfile 1.5.7.1
    22
    33#---------------------------------------------------------------------------
    … …  
    1616INLINE_INHERITED_MEMB  = NO
    1717FULL_PATH_NAMES        = YES
    18 STRIP_FROM_PATH        = @abs_top_srcdir@
    19 STRIP_FROM_INC_PATH    = @abs_top_srcdir@
     18STRIP_FROM_PATH        = "@abs_top_srcdir@"
     19STRIP_FROM_INC_PATH    = "@abs_top_srcdir@"
    2020SHORT_NAMES            = YES
    2121JAVADOC_AUTOBRIEF      = NO
    … …  
    3434CPP_CLI_SUPPORT        = NO
    3535SIP_SUPPORT            = NO
     36IDL_PROPERTY_SUPPORT   = YES
    3637DISTRIBUTE_GROUP_DOC   = NO
    3738SUBGROUPING            = YES
    3839TYPEDEF_HIDES_STRUCT   = NO
     40SYMBOL_CACHE_SIZE      = 0
    3941#---------------------------------------------------------------------------
    4042# Build related configuration options
    … …  
    6769SHOW_USED_FILES        = YES
    6870SHOW_DIRECTORIES       = YES
     71SHOW_FILES             = YES
     72SHOW_NAMESPACES        = YES
    6973FILE_VERSION_FILTER    =
     74LAYOUT_FILE            = DoxygenLayout.xml
    7075#---------------------------------------------------------------------------
    7176# configuration options related to warning and progress messages
    … …  
    7681WARN_IF_DOC_ERROR      = YES
    7782WARN_NO_PARAMDOC       = NO
    78 WARN_FORMAT            = "$file:$line: $text  "
     83WARN_FORMAT            = "$file:$line: $text"
    7984WARN_LOGFILE           = doxygen.log
    8085#---------------------------------------------------------------------------
    8186# configuration options related to the input files
    8287#---------------------------------------------------------------------------
    83 INPUT                  = @abs_top_srcdir@/doc \
    84                          @abs_top_srcdir@/lemon \
    85                          @abs_top_srcdir@/lemon/bits \
    86                          @abs_top_srcdir@/lemon/concepts \
    87                          @abs_top_srcdir@/demo \
    88                          @abs_top_srcdir@/tools \
    89                          @abs_top_srcdir@/test/test_tools.h
     88INPUT                  = "@abs_top_srcdir@/doc" \
     89                         "@abs_top_srcdir@/lemon" \
     90                         "@abs_top_srcdir@/lemon/bits" \
     91                         "@abs_top_srcdir@/lemon/concepts" \
     92                         "@abs_top_srcdir@/demo" \
     93                         "@abs_top_srcdir@/tools" \
     94                         "@abs_top_srcdir@/test/test_tools.h"
    9095INPUT_ENCODING         = UTF-8
    9196FILE_PATTERNS          = *.h \
    … …  
    97102EXCLUDE_PATTERNS       =
    98103EXCLUDE_SYMBOLS        =
    99 EXAMPLE_PATH           = @abs_top_srcdir@/demo \
    100                          @abs_top_srcdir@/LICENSE \
    101                          @abs_top_srcdir@/doc
     104EXAMPLE_PATH           = "@abs_top_srcdir@/demo" \
     105                         "@abs_top_srcdir@/LICENSE" \
     106                         "@abs_top_srcdir@/doc"
    102107EXAMPLE_PATTERNS       =
    103108EXAMPLE_RECURSIVE      = NO
    104 IMAGE_PATH             = @abs_top_srcdir@/doc/images \
    105                          @abs_top_builddir@/doc/gen-images
     109IMAGE_PATH             = "@abs_top_srcdir@/doc/images" \
     110                         "@abs_top_builddir@/doc/gen-images"
    106111INPUT_FILTER           =
    107112FILTER_PATTERNS        =
    … …  
    134139HTML_STYLESHEET        =
    135140HTML_ALIGN_MEMBERS     = YES
    136 GENERATE_HTMLHELP      = NO
     141HTML_DYNAMIC_SECTIONS  = NO
    137142GENERATE_DOCSET        = NO
    138143DOCSET_FEEDNAME        = "Doxygen generated docs"
    139144DOCSET_BUNDLE_ID       = org.doxygen.Project
    140 HTML_DYNAMIC_SECTIONS  = NO
     145GENERATE_HTMLHELP      = NO
    141146CHM_FILE               =
    142147HHC_LOCATION           =
    143148GENERATE_CHI           = NO
     149CHM_INDEX_ENCODING     =
    144150BINARY_TOC             = NO
    145151TOC_EXPAND             = NO
     152GENERATE_QHP           = NO
     153QCH_FILE               =
     154QHP_NAMESPACE          = org.doxygen.Project
     155QHP_VIRTUAL_FOLDER     = doc
     156QHG_LOCATION           =
    146157DISABLE_INDEX          = NO
    147158ENUM_VALUES_PER_LINE   = 4
    148159GENERATE_TREEVIEW      = NO
    149160TREEVIEW_WIDTH         = 250
     161FORMULA_FONTSIZE       = 10
    150162#---------------------------------------------------------------------------
    151163# configuration options related to the LaTeX output
    … …  
    222234# Configuration options related to the dot tool   
    223235#---------------------------------------------------------------------------
    224 CLASS_DIAGRAMS         = NO
     236CLASS_DIAGRAMS         = YES
    225237MSCGEN_PATH            =
    226238HIDE_UNDOC_RELATIONS   = YES
    227239HAVE_DOT               = YES
     240DOT_FONTNAME           = FreeSans
     241DOT_FONTSIZE           = 10
     242DOT_FONTPATH           =
    228243CLASS_GRAPH            = YES
    229244COLLABORATION_GRAPH    = NO

  • doc/Makefile.am

    r156 r322  
    11EXTRA_DIST += \
    22        doc/Doxyfile.in \
     3        doc/DoxygenLayout.xml \
    34        doc/coding_style.dox \
    45        doc/dirs.dox \
    … …  
    78        doc/license.dox \
    89        doc/mainpage.dox \
     10        doc/migration.dox \
     11        doc/named-param.dox \
    912        doc/namespaces.dox \
    10         doc/html
     13        doc/html \
     14        doc/CMakeLists.txt
    1115
    1216DOC_EPS_IMAGES18 = \

  • doc/dirs.dox

    r209 r325  
    1919/**
    2020\dir demo
    21 \brief A collection of demo application.
     21\brief A collection of demo applications.
    2222
    23 This directory contains several simple demo application, mainly
     23This directory contains several simple demo applications, mainly
    2424for educational purposes.
    2525*/
    … …  
    2929\brief Auxiliary (and the whole generated) documentation.
    3030
    31 Auxiliary (and the whole generated) documentation.
     31This directory contains some auxiliary pages and the whole generated
     32documentation.
    3233*/
    3334
    … …  
    4243/**
    4344\dir tools
    44 \brief Some useful executables
     45\brief Some useful executables.
    4546
    4647This directory contains the sources of some useful complete executables.
    47 
    4848*/
    49 
    50 
    5149
    5250/**
    5351\dir lemon
    54 \brief Base include directory of LEMON
     52\brief Base include directory of LEMON.
    5553
    56 This is the base directory of lemon includes, so each include file must be
     54This is the base directory of LEMON includes, so each include file must be
    5755prefixed with this, e.g.
    5856\code
    … …  
    6462/**
    6563\dir concepts
    66 \brief Concept descriptors and checking classes
     64\brief Concept descriptors and checking classes.
    6765
    68 This directory contains the concept descriptors and concept checkers. As a user
    69 you typically don't have to deal with these files.
     66This directory contains the concept descriptors and concept checking tools.
     67For more information see the \ref concept "Concepts" module.
    7068*/
    7169
    7270/**
    7371\dir bits
    74 \brief Implementation helper files
     72\brief Auxiliary tools for implementation.
    7573
    76 This directory contains some helper classes to implement graphs, maps and
    77 some other classes. As a user you typically don't have to deal with these
    78 files.
     74This directory contains some auxiliary classes for implementing graphs,
     75maps and some other classes.
     76As a user you typically don't have to deal with these files.
    7977*/

  • doc/groups.dox

    r210 r325  
    5555You are free to use the graph structure that fit your requirements
    5656the best, most graph algorithms and auxiliary data structures can be used
    57 with any graph structures.
     57with any graph structure.
     58
     59<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
    5860*/
    5961
    … …  
    7577This group describes the map structures implemented in LEMON.
    7678
    77 LEMON provides several special purpose maps that e.g. combine
     79LEMON provides several special purpose maps and map adaptors that e.g. combine
    7880new maps from existing ones.
     81
     82<b>See also:</b> \ref map_concepts "Map Concepts".
    7983*/
    8084
    … …  
    8791values to the nodes and arcs of graphs.
    8892*/
    89 
    9093
    9194/**
    … …  
    105108algorithms.  If a function type algorithm is called then the function
    106109type map adaptors can be used comfortable. For example let's see the
    107 usage of map adaptors with the \c digraphToEps() function.
     110usage of map adaptors with the \c graphToEps() function.
    108111\code
    109112  Color nodeColor(int deg) {
    … …  
    119122  Digraph::NodeMap<int> degree_map(graph);
    120123
    121   digraphToEps(graph, "graph.eps")
     124  graphToEps(graph, "graph.eps")
    122125    .coords(coords).scaleToA4().undirected()
    123126    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
    … …  
    125128\endcode
    126129The \c functorToMap() function makes an \c int to \c Color map from the
    127 \e nodeColor() function. The \c composeMap() compose the \e degree_map
     130\c nodeColor() function. The \c composeMap() compose the \c degree_map
    128131and the previously created map. The composed map is a proper function to
    129132get the color of each node.
    … …  
    163166@defgroup paths Path Structures
    164167@ingroup datas
    165 \brief Path structures implemented in LEMON.
     168\brief %Path structures implemented in LEMON.
    166169
    167170This group describes the path structures implemented in LEMON.
    … …  
    174177
    175178\sa lemon::concepts::Path
    176 
    177179*/
    178180
    … …  
    186188*/
    187189
    188 
    189190/**
    190191@defgroup algs Algorithms
    … …  
    202203
    203204This group describes the common graph search algorithms like
    204 Breadth-first search (Bfs) and Depth-first search (Dfs).
    205 */
    206 
    207 /**
    208 @defgroup shortest_path Shortest Path algorithms
     205Breadth-First Search (BFS) and Depth-First Search (DFS).
     206*/
     207
     208/**
     209@defgroup shortest_path Shortest Path Algorithms
    209210@ingroup algs
    210211\brief Algorithms for finding shortest paths.
    … …  
    214215
    215216/**
    216 @defgroup max_flow Maximum Flow algorithms
     217@defgroup max_flow Maximum Flow Algorithms
    217218@ingroup algs
    218219\brief Algorithms for finding maximum flows.
    … …  
    242243provides functions to query the minimum cut, which is the dual linear
    243244programming problem of the maximum flow.
    244 
    245 */
    246 
    247 /**
    248 @defgroup min_cost_flow Minimum Cost Flow algorithms
     245*/
     246
     247/**
     248@defgroup min_cost_flow Minimum Cost Flow Algorithms
    249249@ingroup algs
    250250
    … …  
    256256
    257257/**
    258 @defgroup min_cut Minimum Cut algorithms
     258@defgroup min_cut Minimum Cut Algorithms
    259259@ingroup algs
    260260
    … …  
    283283If you want to find minimum cut just between two distinict nodes,
    284284please see the \ref max_flow "Maximum Flow page".
    285 
    286 */
    287 
    288 /**
    289 @defgroup graph_prop Connectivity and other graph properties
     285*/
     286
     287/**
     288@defgroup graph_prop Connectivity and Other Graph Properties
    290289@ingroup algs
    291290\brief Algorithms for discovering the graph properties
    … …  
    299298
    300299/**
    301 @defgroup planar Planarity embedding and drawing
     300@defgroup planar Planarity Embedding and Drawing
    302301@ingroup algs
    303302\brief Algorithms for planarity checking, embedding and drawing
    … …  
    311310
    312311/**
    313 @defgroup matching Matching algorithms
     312@defgroup matching Matching Algorithms
    314313@ingroup algs
    315314\brief Algorithms for finding matchings in graphs and bipartite graphs.
    … …  
    326325maximum cardinality matching.
    327326
    328 Lemon contains the next algorithms:
     327LEMON contains the next algorithms:
    329328- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
    330329  augmenting path algorithm for calculate maximum cardinality matching in
    … …  
    349348\image html bipartite_matching.png
    350349\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    351 
    352 */
    353 
    354 /**
    355 @defgroup spantree Minimum Spanning Tree algorithms
     350*/
     351
     352/**
     353@defgroup spantree Minimum Spanning Tree Algorithms
    356354@ingroup algs
    357355\brief Algorithms for finding a minimum cost spanning tree in a graph.
    … …  
    361359*/
    362360
    363 
    364 /**
    365 @defgroup auxalg Auxiliary algorithms
     361/**
     362@defgroup auxalg Auxiliary Algorithms
    366363@ingroup algs
    367364\brief Auxiliary algorithms implemented in LEMON.
    … …  
    372369
    373370/**
    374 @defgroup approx Approximation algorithms
     371@defgroup approx Approximation Algorithms
     372@ingroup algs
    375373\brief Approximation algorithms.
    376374
    … …  
    386384This group describes some general optimization frameworks
    387385implemented in LEMON.
    388 
    389 */
    390 
    391 /**
    392 @defgroup lp_group Lp and Mip solvers
     386*/
     387
     388/**
     389@defgroup lp_group Lp and Mip Solvers
    393390@ingroup gen_opt_group
    394391\brief Lp and Mip solver interfaces for LEMON.
    … …  
    397394various LP solvers could be used in the same manner with this
    398395interface.
    399 
    400 */
    401 
    402 /**
    403 @defgroup lp_utils Tools for Lp and Mip solvers
     396*/
     397
     398/**
     399@defgroup lp_utils Tools for Lp and Mip Solvers
    404400@ingroup lp_group
    405401\brief Helper tools to the Lp and Mip solvers.
    … …  
    442438
    443439/**
    444 @defgroup timecount Time measuring and Counting
     440@defgroup timecount Time Measuring and Counting
    445441@ingroup misc
    446442\brief Simple tools for measuring the performance of algorithms.
    … …  
    448444This group describes simple tools for measuring the performance
    449445of algorithms.
    450 */
    451 
    452 /**
    453 @defgroup graphbits Tools for Graph Implementation
    454 @ingroup utils
    455 \brief Tools to make it easier to create graphs.
    456 
    457 This group describes the tools that makes it easier to create graphs and
    458 the maps that dynamically update with the graph changes.
    459446*/
    460447
    … …  
    472459
    473460This group describes the tools for importing and exporting graphs
    474 and graph related data. Now it supports the LEMON format, the
    475 \c DIMACS format and the encapsulated postscript (EPS) format.
    476 */
    477 
    478 /**
    479 @defgroup lemon_io Lemon Input-Output
     461and graph related data. Now it supports the \ref lgf-format
     462"LEMON Graph Format", the \c DIMACS format and the encapsulated
     463postscript (EPS) format.
     464*/
     465
     466/**
     467@defgroup lemon_io LEMON Input-Output
    480468@ingroup io_group
    481 \brief Reading and writing \ref lgf-format "Lemon Graph Format".
     469\brief Reading and writing LEMON Graph Format.
    482470
    483471This group describes methods for reading and writing
    484 \ref lgf-format "Lemon Graph Format".
    485 */
    486 
    487 /**
    488 @defgroup eps_io Postscript exporting
     472\ref lgf-format "LEMON Graph Format".
     473*/
     474
     475/**
     476@defgroup eps_io Postscript Exporting
    489477@ingroup io_group
    490478\brief General \c EPS drawer and graph exporter
    … …  
    494482*/
    495483
    496 
    497484/**
    498485@defgroup concept Concepts
    … …  
    504491The purpose of the classes in this group is fourfold.
    505492
    506 - These classes contain the documentations of the concepts. In order
     493- These classes contain the documentations of the %concepts. In order
    507494  to avoid document multiplications, an implementation of a concept
    508495  simply refers to the corresponding concept class.
    509496
    510497- These classes declare every functions, <tt>typedef</tt>s etc. an
    511   implementation of the concepts should provide, however completely
     498  implementation of the %concepts should provide, however completely
    512499  without implementations and real data structures behind the
    513500  interface. On the other hand they should provide nothing else. All
    … …  
    522509
    523510- Finally, They can serve as a skeleton of a new implementation of a concept.
    524 
    525 */
    526 
     511*/
    527512
    528513/**
    … …  
    535520*/
    536521
    537 /* --- Unused group
    538 @defgroup experimental Experimental Structures and Algorithms
    539 This group describes some Experimental structures and algorithms.
    540 The stuff here is subject to change.
     522/**
     523@defgroup map_concepts Map Concepts
     524@ingroup concept
     525\brief Skeleton and concept checking classes for maps
     526
     527This group describes the skeletons and concept checking classes of maps.
    541528*/
    542529

  • doc/lgf.dox

    r212 r317  
    2222
    2323
    24 \page lgf-format Lemon Graph Format (LGF)
     24\page lgf-format LEMON Graph Format (LGF)
    2525
    2626The \e LGF is a <em>column oriented</em>
    … …  
    7979\endcode
    8080
    81 The \c \@edges is just a synonym of \c \@arcs. The @arcs section can
     81The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
    8282also store the edge set of an undirected graph. In such case there is
    8383a conventional method for store arc maps in the file, if two columns

  • doc/mainpage.dox

    r209 r318  
    5151If you
    5252want to see how LEMON works, see
    53 some \ref demoprograms "demo programs"!
     53some \ref demoprograms "demo programs".
    5454
    5555If you know what you are looking for then try to find it under the
    … …  
    5757section.
    5858
    59 
     59If you are a user of the old (0.x) series of LEMON, please check out the
     60\ref migration "Migration Guide" for the backward incompatibilities.
    6061*/

  • lemon/CMakeLists.txt

    r141 r225  
    1 include_directories (${LEMON_SOURCE_DIR})
    2 add_library (lemon arg_parser.cc base.cc color.cc random.cc)
     1INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     2
     3ADD_LIBRARY(lemon
     4  arg_parser.cc
     5  base.cc
     6  color.cc
     7  random.cc)
     8
     9INSTALL(
     10  TARGETS lemon
     11  ARCHIVE DESTINATION lib
     12  COMPONENT library)
     13
     14INSTALL(
     15  DIRECTORY . bits concepts
     16  DESTINATION include/lemon
     17  COMPONENT headers
     18  FILES_MATCHING PATTERN "*.h")

  • lemon/Makefile.am

    r220 r259  
    1313        lemon/random.cc
    1414
    15 
    16 lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    17 lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     15#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
     16#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    1817
    1918lemon_HEADERS += \

  • lemon/arg_parser.cc

    r214 r315  
    2727  }
    2828
    29   ArgParser::ArgParser(int argc, const char **argv) :_argc(argc), _argv(argv),
    30                                                     _command_name(argv[0]) {
     29  ArgParser::ArgParser(int argc, const char * const *argv)
     30    :_argc(argc), _argv(argv), _command_name(argv[0]) {
    3131    funcOption("-help","Print a short help message",_showHelp,this);
    3232    synonym("help","-help");
    3333    synonym("h","-help");
    34 
    3534  }
    3635

  • lemon/arg_parser.h

    r214 r315  
    1717 */
    1818
    19 #ifndef LEMON_ARG_PARSER
    20 #define LEMON_ARG_PARSER
     19#ifndef LEMON_ARG_PARSER_H
     20#define LEMON_ARG_PARSER_H
    2121
    2222#include <vector>
    … …  
    4747
    4848    int _argc;
    49     const char **_argv;
     49    const char * const *_argv;
    5050
    5151    enum OptType { UNKNOWN=0, BOOL=1, STRING=2, DOUBLE=3, INTEGER=4, FUNC=5 };
    … …  
    120120
    121121    ///Constructor
    122     ArgParser(int argc, const char **argv);
     122    ArgParser(int argc, const char * const *argv);
    123123
    124124    ~ArgParser();
    … …  
    311311    ///This is the type of the return value of ArgParser::operator[]().
    312312    ///It automatically converts to \c int, \c double, \c bool or
    313     ///\c std::string if the type of the option matches, otherwise it
    314     ///throws an exception (i.e. it performs runtime type checking).
     313    ///\c std::string if the type of the option matches, which is checked
     314    ///with an \ref LEMON_ASSERT "assertion" (i.e. it performs runtime
     315    ///type checking).
    315316    class RefType
    316317    {
    … …  
    383384}
    384385
    385 #endif // LEMON_ARG_PARSER
     386#endif // LEMON_ARG_PARSER_H

  • lemon/assert.h

    r218 r290  
    2828namespace lemon {
    2929
    30   inline void assert_fail_log(const char *file, int line, const char *function,
    31                               const char *message, const char *assertion)
     30  inline void assert_fail_abort(const char *file, int line,
     31                                const char *function, const char* message,
     32                                const char *assertion)
    3233  {
    3334    std::cerr << file << ":" << line << ": ";
    … …  
    3839      std::cerr << " (assertion '" << assertion << "' failed)";
    3940    std::cerr << std::endl;
    40   }
    41 
    42   inline void assert_fail_abort(const char *file, int line,
    43                                 const char *function, const char* message,
    44                                 const char *assertion)
    45   {
    46     assert_fail_log(file, line, function, message, assertion);
    4741    std::abort();
    4842  }
    … …  
    6458
    6559#undef LEMON_ASSERT
    66 #undef LEMON_FIXME
    6760#undef LEMON_DEBUG
    6861
    69 #if (defined(LEMON_ASSERT_LOG) ? 1 : 0) +               \
    70   (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +               \
     62#if (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +               \
    7163  (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1
    7264#error "LEMON assertion system is not set properly"
    7365#endif
    7466
    75 #if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) +              \
    76      (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +            \
     67#if ((defined(LEMON_ASSERT_ABORT) ? 1 : 0) +            \
    7768     (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 ||     \
    7869     defined(LEMON_ENABLE_ASSERTS)) &&                  \
    … …  
    8374
    8475
    85 #if defined LEMON_ASSERT_LOG
    86 #  undef LEMON_ASSERT_HANDLER
    87 #  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_log
    88 #elif defined LEMON_ASSERT_ABORT
     76#if defined LEMON_ASSERT_ABORT
    8977#  undef LEMON_ASSERT_HANDLER
    9078#  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort
    … …  
    10896#  elif defined _MSC_VER
    10997#    define LEMON_FUNCTION_NAME (__FUNCSIG__)
     98#  elif __STDC_VERSION__ >= 199901L
     99#    define LEMON_FUNCTION_NAME (__func__)
    110100#  else
    111 #    define LEMON_FUNCTION_NAME (__func__)
     101#    define LEMON_FUNCTION_NAME ("<unknown>")
    112102#  endif
    113103#endif
    … …  
    119109/// \brief Macro for assertion with customizable message
    120110///
    121 /// Macro for assertion with customizable message.  \param exp An
    122 /// expression that must be convertible to \c bool.  If it is \c
    123 /// false, then an assertion is raised. The concrete behaviour depends
    124 /// on the settings of the assertion system.  \param msg A <tt>const
    125 /// char*</tt> parameter, which can be used to provide information
    126 /// about the circumstances of the failed assertion.
     111/// Macro for assertion with customizable message.
     112/// \param exp An expression that must be convertible to \c bool.  If it is \c
     113/// false, then an assertion is raised. The concrete behaviour depends on the
     114/// settings of the assertion system.
     115/// \param msg A <tt>const char*</tt> parameter, which can be used to provide
     116/// information about the circumstances of the failed assertion.
    127117///
    128118/// The assertions are enabled in the default behaviour.
    … …  
    138128/// The checking is also disabled when the standard macro \c NDEBUG is defined.
    139129///
    140 /// The LEMON assertion system has a wide range of customization
    141 /// properties. As a default behaviour the failed assertion prints a
    142 /// short log message to the standard error and aborts the execution.
    143 ///
    144 /// The following modes can be used in the assertion system:
    145 ///
    146 /// - \c LEMON_ASSERT_LOG The failed assertion prints a short log
    147 ///   message to the standard error and continues the execution.
    148 /// - \c LEMON_ASSERT_ABORT This mode is similar to the \c
    149 ///   LEMON_ASSERT_LOG, but it aborts the program. It is the default
    150 ///   behaviour.
     130/// As a default behaviour the failed assertion prints a short log message to
     131/// the standard error and aborts the execution.
     132///
     133/// However, the following modes can be used in the assertion system:
     134/// - \c LEMON_ASSERT_ABORT The failed assertion prints a short log message to
     135///   the standard error and aborts the program. It is the default behaviour.
    151136/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler
    152137///   function.
    … …  
    176161/// \ingroup exceptions
    177162///
    178 /// \brief Macro for mark not yet implemented features.
    179 ///
    180 /// Macro for mark not yet implemented features and outstanding bugs.
    181 /// It is close to be the shortcut of the following code:
    182 /// \code
    183 ///   LEMON_ASSERT(false, msg);
    184 /// \endcode
    185 ///
    186 /// \see LEMON_ASSERT
    187 #  define LEMON_FIXME(msg)                                              \
    188   (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,        \
    189                         ::lemon::_assert_bits::cstringify(msg),         \
    190                         static_cast<const char*>(0)))
    191 
    192 /// \ingroup exceptions
    193 ///
    194163/// \brief Macro for internal assertions
    195164///
    … …  
    223192#  ifndef LEMON_ASSERT_HANDLER
    224193#    define LEMON_ASSERT(exp, msg)  (static_cast<void>(0))
    225 #    define LEMON_FIXME(msg) (static_cast<void>(0))
    226194#    define LEMON_DEBUG(exp, msg) (static_cast<void>(0))
    227195#  else
    … …  
    232200                             ::lemon::_assert_bits::cstringify(msg),    \
    233201                             #exp), 0)))
    234 #    define LEMON_FIXME(msg)                                            \
    235        (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,   \
    236                              ::lemon::_assert_bits::cstringify(msg),    \
    237                              static_cast<const char*>(0)))
    238 
    239202#    if LEMON_ENABLE_DEBUG
    240203#      define LEMON_DEBUG(exp, msg)                                     \

  • lemon/bfs.h

    r220 r305  
    2222///\ingroup search
    2323///\file
    24 ///\brief Bfs algorithm.
     24///\brief BFS algorithm.
    2525
    2626#include <lemon/list_graph.h>
    … …  
    2929#include <lemon/error.h>
    3030#include <lemon/maps.h>
     31#include <lemon/path.h>
    3132
    3233namespace lemon {
    33 
    34 
    3534
    3635  ///Default traits class of Bfs class.
    … …  
    4140  struct BfsDefaultTraits
    4241  {
    43     ///The digraph type the algorithm runs on.
     42    ///The type of the digraph the algorithm runs on.
    4443    typedef GR Digraph;
    45     ///\brief The type of the map that stores the last
     44
     45    ///\brief The type of the map that stores the predecessor
    4646    ///arcs of the shortest paths.
    4747    ///
    48     ///The type of the map that stores the last
     48    ///The type of the map that stores the predecessor
    4949    ///arcs of the shortest paths.
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    51     ///
    52     typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
     51    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5352    ///Instantiates a PredMap.
    5453
    55     ///This function instantiates a \ref PredMap.
    56     ///\param G is the digraph, to which we would like to define the PredMap.
    57     ///\todo The digraph alone may be insufficient to initialize
    58     static PredMap *createPredMap(const GR &G)
    59     {
    60       return new PredMap(G);
    61     }
     54    ///This function instantiates a PredMap.
     55    ///\param g is the digraph, to which we would like to define the
     56    ///PredMap.
     57    static PredMap *createPredMap(const Digraph &g)
     58    {
     59      return new PredMap(g);
     60    }
     61
    6262    ///The type of the map that indicates which nodes are processed.
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    66     ///\todo named parameter to set this type, function to read and write.
    6766    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6867    ///Instantiates a ProcessedMap.
    6968
    70     ///This function instantiates a \ref ProcessedMap.
     69    ///This function instantiates a ProcessedMap.
    7170    ///\param g is the digraph, to which
    72     ///we would like to define the \ref ProcessedMap
     71    ///we would like to define the ProcessedMap
    7372#ifdef DOXYGEN
    74     static ProcessedMap *createProcessedMap(const GR &g)
     73    static ProcessedMap *createProcessedMap(const Digraph &g)
    7574#else
    76     static ProcessedMap *createProcessedMap(const GR &)
     75    static ProcessedMap *createProcessedMap(const Digraph &)
    7776#endif
    7877    {
    7978      return new ProcessedMap();
    8079    }
     80
    8181    ///The type of the map that indicates which nodes are reached.
    8282
    8383    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    85     ///\todo named parameter to set this type, function to read and write.
     84    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8685    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8786    ///Instantiates a ReachedMap.
    8887
    89     ///This function instantiates a \ref ReachedMap.
    90     ///\param G is the digraph, to which
    91     ///we would like to define the \ref ReachedMap.
    92     static ReachedMap *createReachedMap(const GR &G)
    93     {
    94       return new ReachedMap(G);
    95     }
    96     ///The type of the map that stores the dists of the nodes.
    97 
    98     ///The type of the map that stores the dists of the nodes.
     88    ///This function instantiates a ReachedMap.
     89    ///\param g is the digraph, to which
     90    ///we would like to define the ReachedMap.
     91    static ReachedMap *createReachedMap(const Digraph &g)
     92    {
     93      return new ReachedMap(g);
     94    }
     95
     96    ///The type of the map that stores the distances of the nodes.
     97
     98    ///The type of the map that stores the distances of the nodes.
    9999    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100     ///
    101100    typedef typename Digraph::template NodeMap<int> DistMap;
    102101    ///Instantiates a DistMap.
    103102
    104     ///This function instantiates a \ref DistMap.
    105     ///\param G is the digraph, to which we would like to define
    106     ///the \ref DistMap
    107     static DistMap *createDistMap(const GR &G)
    108     {
    109       return new DistMap(G);
     103    ///This function instantiates a DistMap.
     104    ///\param g is the digraph, to which we would like to define the
     105    ///DistMap.
     106    static DistMap *createDistMap(const Digraph &g)
     107    {
     108      return new DistMap(g);
    110109    }
    111110  };
    … …  
    116115  ///This class provides an efficient implementation of the %BFS algorithm.
    117116  ///
    118   ///\tparam GR The digraph type the algorithm runs on. The default value is
    119   ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
    120   ///is only passed to \ref BfsDefaultTraits.
     117  ///There is also a \ref bfs() "function-type interface" for the BFS
     118  ///algorithm, which is convenient in the simplier cases and it can be
     119  ///used easier.
     120  ///
     121  ///\tparam GR The type of the digraph the algorithm runs on.
     122  ///The default value is \ref ListDigraph. The value of GR is not used
     123  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
    121124  ///\tparam TR Traits class to set various data types used by the algorithm.
    122125  ///The default traits class is
    … …  
    124127  ///See \ref BfsDefaultTraits for the documentation of
    125128  ///a Bfs traits class.
    126 
    127129#ifdef DOXYGEN
    128130  template <typename GR,
    … …  
    134136  class Bfs {
    135137  public:
    136     /**
    137      * \brief \ref Exception for uninitialized parameters.
    138      *
    139      * This error represents problems in the initialization
    140      * of the parameters of the algorithms.
    141      */
    142     class UninitializedParameter : public lemon::UninitializedParameter {
    143     public:
    144       virtual const char* what() const throw() {
    145         return "lemon::Bfs::UninitializedParameter";
    146       }
    147     };
    148 
     138
     139    ///The type of the digraph the algorithm runs on.
     140    typedef typename TR::Digraph Digraph;
     141
     142    ///\brief The type of the map that stores the predecessor arcs of the
     143    ///shortest paths.
     144    typedef typename TR::PredMap PredMap;
     145    ///The type of the map that stores the distances of the nodes.
     146    typedef typename TR::DistMap DistMap;
     147    ///The type of the map that indicates which nodes are reached.
     148    typedef typename TR::ReachedMap ReachedMap;
     149    ///The type of the map that indicates which nodes are processed.
     150    typedef typename TR::ProcessedMap ProcessedMap;
     151    ///The type of the paths.
     152    typedef PredMapPath<Digraph, PredMap> Path;
     153
     154    ///The traits class.
    149155    typedef TR Traits;
    150     ///The type of the underlying digraph.
    151     typedef typename TR::Digraph Digraph;
    152 
    153     ///\brief The type of the map that stores the last
    154     ///arcs of the shortest paths.
    155     typedef typename TR::PredMap PredMap;
    156     ///The type of the map indicating which nodes are reached.
    157     typedef typename TR::ReachedMap ReachedMap;
    158     ///The type of the map indicating which nodes are processed.
    159     typedef typename TR::ProcessedMap ProcessedMap;
    160     ///The type of the map that stores the dists of the nodes.
    161     typedef typename TR::DistMap DistMap;
     156
    162157  private:
    163158
    … …  
    167162    typedef typename Digraph::OutArcIt OutArcIt;
    168163
    169     /// Pointer to the underlying digraph.
     164    //Pointer to the underlying digraph.
    170165    const Digraph *G;
    171     ///Pointer to the map of predecessors arcs.
     166    //Pointer to the map of predecessor arcs.
    172167    PredMap *_pred;
    173     ///Indicates if \ref _pred is locally allocated (\c true) or not.
     168    //Indicates if _pred is locally allocated (true) or not.
    174169    bool local_pred;
    175     ///Pointer to the map of distances.
     170    //Pointer to the map of distances.
    176171    DistMap *_dist;
    177     ///Indicates if \ref _dist is locally allocated (\c true) or not.
     172    //Indicates if _dist is locally allocated (true) or not.
    178173    bool local_dist;
    179     ///Pointer to the map of reached status of the nodes.
     174    //Pointer to the map of reached status of the nodes.
    180175    ReachedMap *_reached;
    181     ///Indicates if \ref _reached is locally allocated (\c true) or not.
     176    //Indicates if _reached is locally allocated (true) or not.
    182177    bool local_reached;
    183     ///Pointer to the map of processed status of the nodes.
     178    //Pointer to the map of processed status of the nodes.
    184179    ProcessedMap *_processed;
    185     ///Indicates if \ref _processed is locally allocated (\c true) or not.
     180    //Indicates if _processed is locally allocated (true) or not.
    186181    bool local_processed;
    187182
    … …  
    190185    int _curr_dist;
    191186
    192     ///Creates the maps if necessary.
    193 
    194     ///\todo Better memory allocation (instead of new).
     187    //Creates the maps if necessary.
    195188    void create_maps()
    196189    {
    … …  
    226219
    227220    template <class T>
    228     struct DefPredMapTraits : public Traits {
     221    struct SetPredMapTraits : public Traits {
    229222      typedef T PredMap;
    230223      static PredMap *createPredMap(const Digraph &)
    231224      {
    232         throw UninitializedParameter();
     225        LEMON_ASSERT(false, "PredMap is not initialized");
     226        return 0; // ignore warnings
    233227      }
    234228    };
    235229    ///\brief \ref named-templ-param "Named parameter" for setting
    236     ///PredMap type
    237     ///
    238     ///\ref named-templ-param "Named parameter" for setting PredMap type
    239     ///
     230    ///PredMap type.
     231    ///
     232    ///\ref named-templ-param "Named parameter" for setting
     233    ///PredMap type.
    240234    template <class T>
    241     struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
    242       typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
     235    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     236      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
    243237    };
    244238
    245239    template <class T>
    246     struct DefDistMapTraits : public Traits {
     240    struct SetDistMapTraits : public Traits {
    247241      typedef T DistMap;
    248242      static DistMap *createDistMap(const Digraph &)
    249243      {
    250         throw UninitializedParameter();
     244        LEMON_ASSERT(false, "DistMap is not initialized");
     245        return 0; // ignore warnings
    251246      }
    252247    };
    253248    ///\brief \ref named-templ-param "Named parameter" for setting
    254     ///DistMap type
    255     ///
    256     ///\ref named-templ-param "Named parameter" for setting DistMap type
    257     ///
     249    ///DistMap type.
     250    ///
     251    ///\ref named-templ-param "Named parameter" for setting
     252    ///DistMap type.
    258253    template <class T>
    259     struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
    260       typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
     254    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     255      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
    261256    };
    262257
    263258    template <class T>
    264     struct DefReachedMapTraits : public Traits {
     259    struct SetReachedMapTraits : public Traits {
    265260      typedef T ReachedMap;
    266261      static ReachedMap *createReachedMap(const Digraph &)
    267262      {
    268         throw UninitializedParameter();
     263        LEMON_ASSERT(false, "ReachedMap is not initialized");
     264        return 0; // ignore warnings
    269265      }
    270266    };
    271267    ///\brief \ref named-templ-param "Named parameter" for setting
    272     ///ReachedMap type
    273     ///
    274     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
    275     ///
     268    ///ReachedMap type.
     269    ///
     270    ///\ref named-templ-param "Named parameter" for setting
     271    ///ReachedMap type.
    276272    template <class T>
    277     struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
    278       typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
     273    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     274      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
    279275    };
    280276
    281277    template <class T>
    282     struct DefProcessedMapTraits : public Traits {
     278    struct SetProcessedMapTraits : public Traits {
    283279      typedef T ProcessedMap;
    284280      static ProcessedMap *createProcessedMap(const Digraph &)
    285281      {
    286         throw UninitializedParameter();
     282        LEMON_ASSERT(false, "ProcessedMap is not initialized");
     283        return 0; // ignore warnings
    287284      }
    288285    };
    289286    ///\brief \ref named-templ-param "Named parameter" for setting
    290     ///ProcessedMap type
    291     ///
    292     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    293     ///
     287    ///ProcessedMap type.
     288    ///
     289    ///\ref named-templ-param "Named parameter" for setting
     290    ///ProcessedMap type.
    294291    template <class T>
    295     struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
    296       typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
     292    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     293      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
    297294    };
    298295
    299     struct DefDigraphProcessedMapTraits : public Traits {
     296    struct SetStandardProcessedMapTraits : public Traits {
    300297      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    301       static ProcessedMap *createProcessedMap(const Digraph &G)
     298      static ProcessedMap *createProcessedMap(const Digraph &g)
    302299      {
    303         return new ProcessedMap(G);
     300        return new ProcessedMap(g);
     301        return 0; // ignore warnings
    304302      }
    305303    };
    306     ///\brief \ref named-templ-param "Named parameter"
    307     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    308     ///
    309     ///\ref named-templ-param "Named parameter"
    310     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
     304    ///\brief \ref named-templ-param "Named parameter" for setting
     305    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     306    ///
     307    ///\ref named-templ-param "Named parameter" for setting
     308    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    311309    ///If you don't set it explicitly, it will be automatically allocated.
    312     template <class T>
    313     struct DefProcessedMapToBeDefaultMap :
    314       public Bfs< Digraph, DefDigraphProcessedMapTraits> {
    315       typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
     310    struct SetStandardProcessedMap :
     311      public Bfs< Digraph, SetStandardProcessedMapTraits > {
     312      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
    316313    };
    317314
    … …  
    322319    ///Constructor.
    323320
    324     ///\param _G the digraph the algorithm will run on.
    325     ///
    326     Bfs(const Digraph& _G) :
    327       G(&_G),
     321    ///Constructor.
     322    ///\param g The digraph the algorithm runs on.
     323    Bfs(const Digraph &g) :
     324      G(&g),
    328325      _pred(NULL), local_pred(false),
    329326      _dist(NULL), local_dist(false),
    … …  
    341338    }
    342339
    343     ///Sets the map storing the predecessor arcs.
    344 
    345     ///Sets the map storing the predecessor arcs.
     340    ///Sets the map that stores the predecessor arcs.
     341
     342    ///Sets the map that stores the predecessor arcs.
    346343    ///If you don't use this function before calling \ref run(),
    347344    ///it will allocate one. The destructor deallocates this
    … …  
    358355    }
    359356
    360     ///Sets the map indicating the reached nodes.
    361 
    362     ///Sets the map indicating the reached nodes.
     357    ///Sets the map that indicates which nodes are reached.
     358
     359    ///Sets the map that indicates which nodes are reached.
    363360    ///If you don't use this function before calling \ref run(),
    364361    ///it will allocate one. The destructor deallocates this
    … …  
    375372    }
    376373
    377     ///Sets the map indicating the processed nodes.
    378 
    379     ///Sets the map indicating the processed nodes.
     374    ///Sets the map that indicates which nodes are processed.
     375
     376    ///Sets the map that indicates which nodes are processed.
    380377    ///If you don't use this function before calling \ref run(),
    381378    ///it will allocate one. The destructor deallocates this
    … …  
    392389    }
    393390
    394     ///Sets the map storing the distances calculated by the algorithm.
    395 
    396     ///Sets the map storing the distances calculated by the algorithm.
     391    ///Sets the map that stores the distances of the nodes.
     392
     393    ///Sets the map that stores the distances of the nodes calculated by
     394    ///the algorithm.
    397395    ///If you don't use this function before calling \ref run(),
    398396    ///it will allocate one. The destructor deallocates this
    … …  
    410408
    411409  public:
     410
    412411    ///\name Execution control
    413412    ///The simplest way to execute the algorithm is to use
    414     ///one of the member functions called \c run(...).
     413    ///one of the member functions called \ref lemon::Bfs::run() "run()".
    415414    ///\n
    416     ///If you need more control on the execution,
    417     ///first you must call \ref init(), then you can add several source nodes
    418     ///with \ref addSource().
    419     ///Finally \ref start() will perform the actual path
    420     ///computation.
     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.
    421420
    422421    ///@{
    423422
    424     ///\brief Initializes the internal data structures.
    425     ///
     423    ///Initializes the internal data structures.
     424
    426425    ///Initializes the internal data structures.
    427426    ///
    … …  
    461460    ///\return The processed node.
    462461    ///
    463     ///\warning The queue must not be empty!
     462    ///\pre The queue must not be empty.
    464463    Node processNextNode()
    465464    {
    … …  
    483482    ///Processes the next node.
    484483
    485     ///Processes the next node. And checks that the given target node
     484    ///Processes the next node and checks if the given target node
    486485    ///is reached. If the target node is reachable from the processed
    487     ///node then the reached parameter will be set true. The reached
    488     ///parameter should be initially false.
     486    ///node, then the \c reach parameter will be set to \c true.
    489487    ///
    490488    ///\param target The target node.
    491     ///\retval reach Indicates that the target node is reached.
     489    ///\retval reach Indicates if the target node is reached.
     490    ///It should be initially \c false.
     491    ///
    492492    ///\return The processed node.
    493493    ///
    494     ///\warning The queue must not be empty!
     494    ///\pre The queue must not be empty.
    495495    Node processNextNode(Node target, bool& reach)
    496496    {
    … …  
    515515    ///Processes the next node.
    516516
    517     ///Processes the next node. And checks that at least one of
    518     ///reached node has true value in the \c nm node map. If one node
    519     ///with true value is reachable from the processed node then the
    520     ///rnode parameter will be set to the first of such nodes.
    521     ///
    522     ///\param nm The node map of possible targets.
     517    ///Processes the next node and checks if at least one of reached
     518    ///nodes has \c true value in the \c nm node map. If one node
     519    ///with \c true value is reachable from the processed node, then the
     520    ///\c rnode parameter will be set to the first of such nodes.
     521    ///
     522    ///\param nm A \c bool (or convertible) node map that indicates the
     523    ///possible targets.
    523524    ///\retval rnode The reached target node.
     525    ///It should be initially \c INVALID.
     526    ///
    524527    ///\return The processed node.
    525528    ///
    526     ///\warning The queue must not be empty!
     529    ///\pre The queue must not be empty.
    527530    template<class NM>
    528531    Node processNextNode(const NM& nm, Node& rnode)
    … …  
    546549    }
    547550
    548     ///Next node to be processed.
    549 
    550     ///Next node to be processed.
    551     ///
    552     ///\return The next node to be processed or INVALID if the queue is
    553     /// empty.
    554     Node nextNode()
     551    ///The next node to be processed.
     552
     553    ///Returns the next node to be processed or \c INVALID if the queue
     554    ///is empty.
     555    Node nextNode() const
    555556    {
    556557      return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
    … …  
    558559
    559560    ///\brief Returns \c false if there are nodes
    560     ///to be processed in the queue
     561    ///to be processed.
    561562    ///
    562563    ///Returns \c false if there are nodes
    563     ///to be processed in the queue
    564     bool emptyQueue() { return _queue_tail==_queue_head; }
     564    ///to be processed in the queue.
     565    bool emptyQueue() const { return _queue_tail==_queue_head; }
     566
    565567    ///Returns the number of the nodes to be processed.
    566568
    567569    ///Returns the number of the nodes to be processed in the queue.
    568     int queueSize() { return _queue_head-_queue_tail; }
     570    int queueSize() const { return _queue_head-_queue_tail; }
    569571
    570572    ///Executes the algorithm.
    … …  
    572574    ///Executes the algorithm.
    573575    ///
    574     ///\pre init() must be called and at least one node should be added
    575     ///with addSource() before using this function.
    576     ///
    577576    ///This method runs the %BFS algorithm from the root node(s)
    578     ///in order to
    579     ///compute the
    580     ///shortest path to each node. The algorithm computes
    581     ///- The shortest path tree.
    582     ///- The distance of each node from the root(s).
     577    ///in order to compute the shortest path to each node.
     578    ///
     579    ///The algorithm computes
     580    ///- the shortest path tree (forest),
     581    ///- the distance of each node from the root(s).
     582    ///
     583    ///\pre init() must be called and at least one root node should be
     584    ///added with addSource() before using this function.
     585    ///
     586    ///\note <tt>b.start()</tt> is just a shortcut of the following code.
     587    ///\code
     588    ///  while ( !b.emptyQueue() ) {
     589    ///    b.processNextNode();
     590    ///  }
     591    ///\endcode
    583592    void start()
    584593    {
    … …  
    586595    }
    587596
    588     ///Executes the algorithm until \c dest is reached.
    589 
    590     ///Executes the algorithm until \c dest is reached.
    591     ///
    592     ///\pre init() must be called and at least one node should be added
    593     ///with addSource() before using this function.
     597    ///Executes the algorithm until the given target node is reached.
     598
     599    ///Executes the algorithm until the given target node is reached.
    594600    ///
    595601    ///This method runs the %BFS algorithm from the root node(s)
    596     ///in order to compute the shortest path to \c dest.
     602    ///in order to compute the shortest path to \c t.
     603    ///
    597604    ///The algorithm computes
    598     ///- The shortest path to \c  dest.
    599     ///- The distance of \c dest from the root(s).
    600     void start(Node dest)
     605    ///- the shortest path to \c t,
     606    ///- the distance of \c t from the root(s).
     607    ///
     608    ///\pre init() must be called and at least one root node should be
     609    ///added with addSource() before using this function.
     610    ///
     611    ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
     612    ///\code
     613    ///  bool reach = false;
     614    ///  while ( !b.emptyQueue() && !reach ) {
     615    ///    b.processNextNode(t, reach);
     616    ///  }
     617    ///\endcode
     618    void start(Node t)
    601619    {
    602620      bool reach = false;
    603       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
     621      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
    604622    }
    605623
    … …  
    608626    ///Executes the algorithm until a condition is met.
    609627    ///
    610     ///\pre init() must be called and at least one node should be added
    611     ///with addSource() before using this function.
    612     ///
    613     ///\param nm must be a bool (or convertible) node map. The
    614     ///algorithm will stop when it reaches a node \c v with
    615     /// <tt>nm[v]</tt> true.
     628    ///This method runs the %BFS algorithm from the root node(s) in
     629    ///order to compute the shortest path to a node \c v with
     630    /// <tt>nm[v]</tt> true, if such a node can be found.
     631    ///
     632    ///\param nm A \c bool (or convertible) node map. The algorithm
     633    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
    616634    ///
    617635    ///\return The reached node \c v with <tt>nm[v]</tt> true or
    618636    ///\c INVALID if no such node was found.
    619     template<class NM>
    620     Node start(const NM &nm)
     637    ///
     638    ///\pre init() must be called and at least one root node should be
     639    ///added with addSource() before using this function.
     640    ///
     641    ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
     642    ///\code
     643    ///  Node rnode = INVALID;
     644    ///  while ( !b.emptyQueue() && rnode == INVALID ) {
     645    ///    b.processNextNode(nm, rnode);
     646    ///  }
     647    ///  return rnode;
     648    ///\endcode
     649    template<class NodeBoolMap>
     650    Node start(const NodeBoolMap &nm)
    621651    {
    622652      Node rnode = INVALID;
    … …  
    627657    }
    628658
    629     ///Runs %BFS algorithm from node \c s.
    630 
    631     ///This method runs the %BFS algorithm from a root node \c s
    632     ///in order to
    633     ///compute the
    634     ///shortest path to each node. The algorithm computes
    635     ///- The shortest path tree.
    636     ///- The distance of each node from the root.
    637     ///
    638     ///\note b.run(s) is just a shortcut of the following code.
     659    ///Runs the algorithm from the given source node.
     660
     661    ///This method runs the %BFS algorithm from node \c s
     662    ///in order to compute the shortest path to each node.
     663    ///
     664    ///The algorithm computes
     665    ///- the shortest path tree,
     666    ///- the distance of each node from the root.
     667    ///
     668    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
    639669    ///\code
    640670    ///  b.init();
    … …  
    650680    ///Finds the shortest path between \c s and \c t.
    651681
    652     ///Finds the shortest path between \c s and \c t.
    653     ///
    654     ///\return The length of the shortest s---t path if there exists one,
    655     ///0 otherwise.
    656     ///\note Apart from the return value, b.run(s) is
    657     ///just a shortcut of the following code.
     682    ///This method runs the %BFS algorithm from node \c s
     683    ///in order to compute the shortest path to node \c t
     684    ///(it stops searching when \c t is processed).
     685    ///
     686    ///\return \c true if \c t is reachable form \c s.
     687    ///
     688    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     689    ///shortcut of the following code.
    658690    ///\code
    659691    ///  b.init();
    … …  
    661693    ///  b.start(t);
    662694    ///\endcode
    663     int run(Node s,Node t) {
     695    bool run(Node s,Node t) {
    664696      init();
    665697      addSource(s);
    666698      start(t);
    667       return reached(t) ? _curr_dist : 0;
     699      return reached(t);
     700    }
     701
     702    ///Runs the algorithm to visit all nodes in the digraph.
     703
     704    ///This method runs the %BFS algorithm in order to
     705    ///compute the shortest path to each node.
     706    ///
     707    ///The algorithm computes
     708    ///- the shortest path tree (forest),
     709    ///- the distance of each node from the root(s).
     710    ///
     711    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
     712    ///\code
     713    ///  b.init();
     714    ///  for (NodeIt n(gr); n != INVALID; ++n) {
     715    ///    if (!b.reached(n)) {
     716    ///      b.addSource(n);
     717    ///      b.start();
     718    ///    }
     719    ///  }
     720    ///\endcode
     721    void run() {
     722      init();
     723      for (NodeIt n(*G); n != INVALID; ++n) {
     724        if (!reached(n)) {
     725          addSource(n);
     726          start();
     727        }
     728      }
    668729    }
    669730
    … …  
    673734    ///The result of the %BFS algorithm can be obtained using these
    674735    ///functions.\n
    675     ///Before the use of these functions,
    676     ///either run() or start() must be calleb.
     736    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
     737    ///"start()" must be called before using them.
    677738
    678739    ///@{
    679740
    680     typedef PredMapPath<Digraph, PredMap> Path;
    681 
    682     ///Gives back the shortest path.
    683 
    684     ///Gives back the shortest path.
    685     ///\pre The \c t should be reachable from the source.
    686     Path path(Node t)
    687     {
    688       return Path(*G, *_pred, t);
    689     }
     741    ///The shortest path to a node.
     742
     743    ///Returns the shortest path to a node.
     744    ///
     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.
     749    Path path(Node t) const { return Path(*G, *_pred, t); }
    690750
    691751    ///The distance of a node from the root(s).
    692752
    693753    ///Returns the distance of a node from the root(s).
    694     ///\pre \ref run() must be called before using this function.
    695     ///\warning If node \c v in unreachable from the root(s) the return value
    696     ///of this function is undefined.
     754    ///
     755    ///\warning If node \c v is not reachable from the root(s), then
     756    ///the return value of this function is undefined.
     757    ///
     758    ///\pre Either \ref run() or \ref start() must be called before
     759    ///using this function.
    697760    int dist(Node v) const { return (*_dist)[v]; }
    698761
    699     ///Returns the 'previous arc' of the shortest path tree.
    700 
    701     ///For a node \c v it returns the 'previous arc'
    702     ///of the shortest path tree,
    703     ///i.e. it returns the last arc of a shortest path from the root(s) to \c
    704     ///v. It is \ref INVALID
    705     ///if \c v is unreachable from the root(s) or \c v is a root. The
    706     ///shortest path tree used here is equal to the shortest path tree used in
    707     ///\ref predNode().
    708     ///\pre Either \ref run() or \ref start() must be called before using
    709     ///this function.
     762    ///Returns the 'previous arc' of the shortest path tree for a node.
     763
     764    ///This function returns the 'previous arc' of the shortest path
     765    ///tree for the node \c v, i.e. it returns the last arc of a
     766    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
     767    ///is not reachable from the root(s) or if \c v is a root.
     768    ///
     769    ///The shortest path tree used here is equal to the shortest path
     770    ///tree used in \ref predNode().
     771    ///
     772    ///\pre Either \ref run() or \ref start() must be called before
     773    ///using this function.
    710774    Arc predArc(Node v) const { return (*_pred)[v];}
    711775
    712     ///Returns the 'previous node' of the shortest path tree.
    713 
    714     ///For a node \c v it returns the 'previous node'
    715     ///of the shortest path tree,
    716     ///i.e. it returns the last but one node from a shortest path from the
    717     ///root(a) to \c /v.
    718     ///It is INVALID if \c v is unreachable from the root(s) or
    719     ///if \c v itself a root.
     776    ///Returns the 'previous node' of the shortest path tree for a node.
     777
     778    ///This function returns the 'previous node' of the shortest path
     779    ///tree for the node \c v, i.e. it returns the last but one node
     780    ///from a shortest path from the root(s) to \c v. It is \c INVALID
     781    ///if \c v is not reachable from the root(s) or if \c v is a root.
     782    ///
    720783    ///The shortest path tree used here is equal to the shortest path
    721784    ///tree used in \ref predArc().
     785    ///
    722786    ///\pre Either \ref run() or \ref start() must be called before
    723787    ///using this function.
    … …  
    725789                                  G->source((*_pred)[v]); }
    726790
    727     ///Returns a reference to the NodeMap of distances.
    728 
    729     ///Returns a reference to the NodeMap of distances.
    730     ///\pre Either \ref run() or \ref init() must
    731     ///be called before using this function.
     791    ///\brief Returns a const reference to the node map that stores the
     792    /// distances of the nodes.
     793    ///
     794    ///Returns a const reference to the node map that stores the distances
     795    ///of the nodes calculated by the algorithm.
     796    ///
     797    ///\pre Either \ref run() or \ref init()
     798    ///must be called before using this function.
    732799    const DistMap &distMap() const { return *_dist;}
    733800
    734     ///Returns a reference to the shortest path tree map.
    735 
    736     ///Returns a reference to the NodeMap of the arcs of the
    737     ///shortest path tree.
     801    ///\brief Returns a const reference to the node map that stores the
     802    ///predecessor arcs.
     803    ///
     804    ///Returns a const reference to the node map that stores the predecessor
     805    ///arcs, which form the shortest path tree.
     806    ///
    738807    ///\pre Either \ref run() or \ref init()
    739808    ///must be called before using this function.
    740809    const PredMap &predMap() const { return *_pred;}
    741810
    742     ///Checks if a node is reachable from the root.
    743 
    744     ///Returns \c true if \c v is reachable from the root.
    745     ///\warning The source nodes are indicated as unreached.
     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).
    746814    ///\pre Either \ref run() or \ref start()
    747815    ///must be called before using this function.
    748     ///
    749     bool reached(Node v) { return (*_reached)[v]; }
     816    bool reached(Node v) const { return (*_reached)[v]; }
    750817
    751818    ///@}
    752819  };
    753820
    754   ///Default traits class of Bfs function.
    755 
    756   ///Default traits class of Bfs function.
     821  ///Default traits class of bfs() function.
     822
     823  ///Default traits class of bfs() function.
    757824  ///\tparam GR Digraph type.
    758825  template<class GR>
    759826  struct BfsWizardDefaultTraits
    760827  {
    761     ///The digraph type the algorithm runs on.
     828    ///The type of the digraph the algorithm runs on.
    762829    typedef GR Digraph;
    763     ///\brief The type of the map that stores the last
     830
     831    ///\brief The type of the map that stores the predecessor
    764832    ///arcs of the shortest paths.
    765833    ///
    766     ///The type of the map that stores the last
     834    ///The type of the map that stores the predecessor
    767835    ///arcs of the shortest paths.
    768836    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    769     ///
    770     typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
     837    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    771838    ///Instantiates a PredMap.
    772839
    773     ///This function instantiates a \ref PredMap.
    774     ///\param g is the digraph, to which we would like to define the PredMap.
    775     ///\todo The digraph alone may be insufficient to initialize
    776 #ifdef DOXYGEN
    777     static PredMap *createPredMap(const GR &g)
    778 #else
    779     static PredMap *createPredMap(const GR &)
    780 #endif
    781     {
    782       return new PredMap();
     840    ///This function instantiates a PredMap.
     841    ///\param g is the digraph, to which we would like to define the
     842    ///PredMap.
     843    static PredMap *createPredMap(const Digraph &g)
     844    {
     845      return new PredMap(g);
    783846    }
    784847
    … …  
    787850    ///The type of the map that indicates which nodes are processed.
    788851    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    789     ///\todo named parameter to set this type, function to read and write.
     852    ///By default it is a NullMap.
    790853    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    791854    ///Instantiates a ProcessedMap.
    792855
    793     ///This function instantiates a \ref ProcessedMap.
     856    ///This function instantiates a ProcessedMap.
    794857    ///\param g is the digraph, to which
    795     ///we would like to define the \ref ProcessedMap
     858    ///we would like to define the ProcessedMap.
    796859#ifdef DOXYGEN
    797     static ProcessedMap *createProcessedMap(const GR &g)
     860    static ProcessedMap *createProcessedMap(const Digraph &g)
    798861#else
    799     static ProcessedMap *createProcessedMap(const GR &)
     862    static ProcessedMap *createProcessedMap(const Digraph &)
    800863#endif
    801864    {
    802865      return new ProcessedMap();
    803866    }
     867
    804868    ///The type of the map that indicates which nodes are reached.
    805869
    806870    ///The type of the map that indicates which nodes are reached.
    807     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    808     ///\todo named parameter to set this type, function to read and write.
     871    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    809872    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    810873    ///Instantiates a ReachedMap.
    811874
    812     ///This function instantiates a \ref ReachedMap.
    813     ///\param G is the digraph, to which
    814     ///we would like to define the \ref ReachedMap.
    815     static ReachedMap *createReachedMap(const GR &G)
    816     {
    817       return new ReachedMap(G);
    818     }
    819     ///The type of the map that stores the dists of the nodes.
    820 
    821     ///The type of the map that stores the dists of the nodes.
     875    ///This function instantiates a ReachedMap.
     876    ///\param g is the digraph, to which
     877    ///we would like to define the ReachedMap.
     878    static ReachedMap *createReachedMap(const Digraph &g)
     879    {
     880      return new ReachedMap(g);
     881    }
     882
     883    ///The type of the map that stores the distances of the nodes.
     884
     885    ///The type of the map that stores the distances of the nodes.
    822886    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    823     ///
    824     typedef NullMap<typename Digraph::Node,int> DistMap;
     887    typedef typename Digraph::template NodeMap<int> DistMap;
    825888    ///Instantiates a DistMap.
    826889
    827     ///This function instantiates a \ref DistMap.
     890    ///This function instantiates a DistMap.
    828891    ///\param g is the digraph, to which we would like to define
    829     ///the \ref DistMap
    830 #ifdef DOXYGEN
    831     static DistMap *createDistMap(const GR &g)
    832 #else
    833     static DistMap *createDistMap(const GR &)
    834 #endif
    835     {
    836       return new DistMap();
    837     }
     892    ///the DistMap
     893    static DistMap *createDistMap(const Digraph &g)
     894    {
     895      return new DistMap(g);
     896    }
     897
     898    ///The type of the shortest paths.
     899
     900    ///The type of the shortest paths.
     901    ///It must meet the \ref concepts::Path "Path" concept.
     902    typedef lemon::Path<Digraph> Path;
    838903  };
    839904
    840   /// Default traits used by \ref BfsWizard
     905  /// Default traits class used by BfsWizard
    841906
    842907  /// To make it easier to use Bfs algorithm
    843   ///we have created a wizard class.
     908  /// we have created a wizard class.
    844909  /// This \ref BfsWizard class needs default traits,
    845   ///as well as the \ref Bfs class.
     910  /// as well as the \ref Bfs class.
    846911  /// The \ref BfsWizardBase is a class to be the default traits of the
    847912  /// \ref BfsWizard class.
    … …  
    852917    typedef BfsWizardDefaultTraits<GR> Base;
    853918  protected:
    854     /// Type of the nodes in the digraph.
     919    //The type of the nodes in the digraph.
    855920    typedef typename Base::Digraph::Node Node;
    856921
    857     /// Pointer to the underlying digraph.
     922    //Pointer to the digraph the algorithm runs on.
    858923    void *_g;
    859     ///Pointer to the map of reached nodes.
     924    //Pointer to the map of reached nodes.
    860925    void *_reached;
    861     ///Pointer to the map of processed nodes.
     926    //Pointer to the map of processed nodes.
    862927    void *_processed;
    863     ///Pointer to the map of predecessors arcs.
     928    //Pointer to the map of predecessors arcs.
    864929    void *_pred;
    865     ///Pointer to the map of distances.
     930    //Pointer to the map of distances.
    866931    void *_dist;
    867     ///Pointer to the source node.
    868     Node _source;
     932    //Pointer to the shortest path to the target node.
     933    void *_path;
     934    //Pointer to the distance of the target node.
     935    int *_di;
    869936
    870937    public:
    … …  
    872939
    873940    /// This constructor does not require parameters, therefore it initiates
    874     /// all of the attributes to default values (0, INVALID).
     941    /// all of the attributes to \c 0.
    875942    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    876                            _dist(0), _source(INVALID) {}
     943                      _dist(0), _path(0), _di(0) {}
    877944
    878945    /// Constructor.
    879946
    880     /// This constructor requires some parameters,
    881     /// listed in the parameters list.
    882     /// Others are initiated to 0.
    883     /// \param g is the initial value of  \ref _g
    884     /// \param s is the initial value of  \ref _source
    885     BfsWizardBase(const GR &g, Node s=INVALID) :
     947    /// This constructor requires one parameter,
     948    /// others are initiated to \c 0.
     949    /// \param g The digraph the algorithm runs on.
     950    BfsWizardBase(const GR &g) :
    886951      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    887       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
     952      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
    888953
    889954  };
    890955
    891   /// A class to make the usage of Bfs algorithm easier
    892 
    893   /// This class is created to make it easier to use Bfs algorithm.
    894   /// It uses the functions and features of the plain \ref Bfs,
    895   /// but it is much simpler to use it.
     956  /// Auxiliary class for the function-type interface of BFS algorithm.
     957
     958  /// This auxiliary class is created to implement the
     959  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
     960  /// It does not have own \ref run() method, it uses the functions
     961  /// and features of the plain \ref Bfs.
    896962  ///
    897   /// Simplicity means that the way to change the types defined
    898   /// in the traits class is based on functions that returns the new class
    899   /// and not on templatable built-in classes.
    900   /// When using the plain \ref Bfs
    901   /// the new class with the modified type comes from
    902   /// the original class by using the ::
    903   /// operator. In the case of \ref BfsWizard only
    904   /// a function have to be called and it will
    905   /// return the needed class.
    906   ///
    907   /// It does not have own \ref run method. When its \ref run method is called
    908   /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
    909   /// method of it.
     963  /// This class should only be used through the \ref bfs() function,
     964  /// which makes it easier to use the algorithm.
    910965  template<class TR>
    911966  class BfsWizard : public TR
    … …  
    913968    typedef TR Base;
    914969
    915     ///The type of the underlying digraph.
     970    ///The type of the digraph the algorithm runs on.
    916971    typedef typename TR::Digraph Digraph;
    917     //\e
     972
    918973    typedef typename Digraph::Node Node;
    919     //\e
    920974    typedef typename Digraph::NodeIt NodeIt;
    921     //\e
    922975    typedef typename Digraph::Arc Arc;
    923     //\e
    924976    typedef typename Digraph::OutArcIt OutArcIt;
    925977
    926     ///\brief The type of the map that stores
    927     ///the reached nodes
    928     typedef typename TR::ReachedMap ReachedMap;
    929     ///\brief The type of the map that stores
    930     ///the processed nodes
    931     typedef typename TR::ProcessedMap ProcessedMap;
    932     ///\brief The type of the map that stores the last
     978    ///\brief The type of the map that stores the predecessor
    933979    ///arcs of the shortest paths.
    934980    typedef typename TR::PredMap PredMap;
    935     ///The type of the map that stores the dists of the nodes.
     981    ///\brief The type of the map that stores the distances of the nodes.
    936982    typedef typename TR::DistMap DistMap;
     983    ///\brief The type of the map that indicates which nodes are reached.
     984    typedef typename TR::ReachedMap ReachedMap;
     985    ///\brief The type of the map that indicates which nodes are processed.
     986    typedef typename TR::ProcessedMap ProcessedMap;
     987    ///The type of the shortest paths
     988    typedef typename TR::Path Path;
    937989
    938990  public:
     991
    939992    /// Constructor.
    940993    BfsWizard() : TR() {}
    … …  
    944997    /// Constructor that requires parameters.
    945998    /// These parameters will be the default values for the traits class.
    946     BfsWizard(const Digraph &g, Node s=INVALID) :
    947       TR(g,s) {}
     999    /// \param g The digraph the algorithm runs on.
     1000    BfsWizard(const Digraph &g) :
     1001      TR(g) {}
    9481002
    9491003    ///Copy constructor
    … …  
    9521006    ~BfsWizard() {}
    9531007
    954     ///Runs Bfs algorithm from a given node.
    955 
    956     ///Runs Bfs algorithm from a given node.
    957     ///The node can be given by the \ref source function.
     1008    ///Runs BFS algorithm from the given source node.
     1009
     1010    ///This method runs BFS algorithm from node \c s
     1011    ///in order to compute the shortest path to each node.
     1012    void run(Node s)
     1013    {
     1014      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     1015      if (Base::_pred)
     1016        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1017      if (Base::_dist)
     1018        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1019      if (Base::_reached)
     1020        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     1021      if (Base::_processed)
     1022        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1023      if (s!=INVALID)
     1024        alg.run(s);
     1025      else
     1026        alg.run();
     1027    }
     1028
     1029    ///Finds the shortest path between \c s and \c t.
     1030
     1031    ///This method runs BFS algorithm from node \c s
     1032    ///in order to compute the shortest path to node \c t
     1033    ///(it stops searching when \c t is processed).
     1034    ///
     1035    ///\return \c true if \c t is reachable form \c s.
     1036    bool run(Node s, Node t)
     1037    {
     1038      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     1039      if (Base::_pred)
     1040        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1041      if (Base::_dist)
     1042        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1043      if (Base::_reached)
     1044        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     1045      if (Base::_processed)
     1046        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1047      alg.run(s,t);
     1048      if (Base::_path)
     1049        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
     1050      if (Base::_di)
     1051        *Base::_di = alg.dist(t);
     1052      return alg.reached(t);
     1053    }
     1054
     1055    ///Runs BFS algorithm to visit all nodes in the digraph.
     1056
     1057    ///This method runs BFS algorithm in order to compute
     1058    ///the shortest path to each node.
    9581059    void run()
    9591060    {
    960       if(Base::_source==INVALID) throw UninitializedParameter();
    961       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
    962       if(Base::_reached)
    963         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
    964       if(Base::_processed)
    965         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    966       if(Base::_pred)
    967         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    968       if(Base::_dist)
    969         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    970       alg.run(Base::_source);
    971     }
    972 
    973     ///Runs Bfs algorithm from the given node.
    974 
    975     ///Runs Bfs algorithm from the given node.
    976     ///\param s is the given source.
    977     void run(Node s)
    978     {
    979       Base::_source=s;
    980       run();
     1061      run(INVALID);
    9811062    }
    9821063
    9831064    template<class T>
    984     struct DefPredMapBase : public Base {
     1065    struct SetPredMapBase : public Base {
    9851066      typedef T PredMap;
    9861067      static PredMap *createPredMap(const Digraph &) { return 0; };
    987       DefPredMapBase(const TR &b) : TR(b) {}
     1068      SetPredMapBase(const TR &b) : TR(b) {}
    9881069    };
    989 
    990     ///\brief \ref named-templ-param "Named parameter"
    991     ///function for setting PredMap
    992     ///
    993     /// \ref named-templ-param "Named parameter"
    994     ///function for setting PredMap
    995     ///
     1070    ///\brief \ref named-func-param "Named parameter"
     1071    ///for setting PredMap object.
     1072    ///
     1073    ///\ref named-func-param "Named parameter"
     1074    ///for setting PredMap object.
    9961075    template<class T>
    997     BfsWizard<DefPredMapBase<T> > predMap(const T &t)
     1076    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
    9981077    {
    9991078      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    1000       return BfsWizard<DefPredMapBase<T> >(*this);
    1001     }
    1002 
     1079      return BfsWizard<SetPredMapBase<T> >(*this);
     1080    }
    10031081
    10041082    template<class T>
    1005     struct DefReachedMapBase : public Base {
     1083    struct SetReachedMapBase : public Base {
    10061084      typedef T ReachedMap;
    10071085      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
    1008       DefReachedMapBase(const TR &b) : TR(b) {}
     1086      SetReachedMapBase(const TR &b) : TR(b) {}
    10091087    };
    1010 
    1011     ///\brief \ref named-templ-param "Named parameter"
    1012     ///function for setting ReachedMap
    1013     ///
    1014     /// \ref named-templ-param "Named parameter"
    1015     ///function for setting ReachedMap
    1016     ///
     1088    ///\brief \ref named-func-param "Named parameter"
     1089    ///for setting ReachedMap object.
     1090    ///
     1091    /// \ref named-func-param "Named parameter"
     1092    ///for setting ReachedMap object.
    10171093    template<class T>
    1018     BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
     1094    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    10191095    {
    10201096      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
    1021       return BfsWizard<DefReachedMapBase<T> >(*this);
    1022     }
    1023 
     1097      return BfsWizard<SetReachedMapBase<T> >(*this);
     1098    }
    10241099
    10251100    template<class T>
    1026     struct DefProcessedMapBase : public Base {
     1101    struct SetDistMapBase : public Base {
     1102      typedef T DistMap;
     1103      static DistMap *createDistMap(const Digraph &) { return 0; };
     1104      SetDistMapBase(const TR &b) : TR(b) {}
     1105    };
     1106    ///\brief \ref named-func-param "Named parameter"
     1107    ///for setting DistMap object.
     1108    ///
     1109    /// \ref named-func-param "Named parameter"
     1110    ///for setting DistMap object.
     1111    template<class T>
     1112    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     1113    {
     1114      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
     1115      return BfsWizard<SetDistMapBase<T> >(*this);
     1116    }
     1117
     1118    template<class T>
     1119    struct SetProcessedMapBase : public Base {
    10271120      typedef T ProcessedMap;
    10281121      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
    1029       DefProcessedMapBase(const TR &b) : TR(b) {}
     1122      SetProcessedMapBase(const TR &b) : TR(b) {}
    10301123    };
    1031 
    1032     ///\brief \ref named-templ-param "Named parameter"
    1033     ///function for setting ProcessedMap
    1034     ///
    1035     /// \ref named-templ-param "Named parameter"
    1036     ///function for setting ProcessedMap
    1037     ///
     1124    ///\brief \ref named-func-param "Named parameter"
     1125    ///for setting ProcessedMap object.
     1126    ///
     1127    /// \ref named-func-param "Named parameter"
     1128    ///for setting ProcessedMap object.
    10381129    template<class T>
    1039     BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     1130    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    10401131    {
    10411132      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
    1042       return BfsWizard<DefProcessedMapBase<T> >(*this);
    1043     }
    1044 
     1133      return BfsWizard<SetProcessedMapBase<T> >(*this);
     1134    }
    10451135
    10461136    template<class T>
    1047     struct DefDistMapBase : public Base {
    1048       typedef T DistMap;
    1049       static DistMap *createDistMap(const Digraph &) { return 0; };
    1050       DefDistMapBase(const TR &b) : TR(b) {}
     1137    struct SetPathBase : public Base {
     1138      typedef T Path;
     1139      SetPathBase(const TR &b) : TR(b) {}
    10511140    };
    1052 
    1053     ///\brief \ref named-templ-param "Named parameter"
    1054     ///function for setting DistMap type
    1055     ///
    1056     /// \ref named-templ-param "Named parameter"
    1057     ///function for setting DistMap type
    1058     ///
     1141    ///\brief \ref named-func-param "Named parameter"
     1142    ///for getting the shortest path to the target node.
     1143    ///
     1144    ///\ref named-func-param "Named parameter"
     1145    ///for getting the shortest path to the target node.
    10591146    template<class T>
    1060     BfsWizard<DefDistMapBase<T> > distMap(const T &t)
    1061     {
    1062       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    1063       return BfsWizard<DefDistMapBase<T> >(*this);
    1064     }
    1065 
    1066     /// Sets the source node, from which the Bfs algorithm runs.
    1067 
    1068     /// Sets the source node, from which the Bfs algorithm runs.
    1069     /// \param s is the source node.
    1070     BfsWizard<TR> &source(Node s)
    1071     {
    1072       Base::_source=s;
     1147    BfsWizard<SetPathBase<T> > path(const T &t)
     1148    {
     1149      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1150      return BfsWizard<SetPathBase<T> >(*this);
     1151    }
     1152
     1153    ///\brief \ref named-func-param "Named parameter"
     1154    ///for getting the distance of the target node.
     1155    ///
     1156    ///\ref named-func-param "Named parameter"
     1157    ///for getting the distance of the target node.
     1158    BfsWizard dist(const int &d)
     1159    {
     1160      Base::_di=const_cast<int*>(&d);
    10731161      return *this;
    10741162    }
    … …  
    10761164  };
    10771165
    1078   ///Function type interface for Bfs algorithm.
     1166  ///Function-type interface for BFS algorithm.
    10791167
    10801168  /// \ingroup search
    1081   ///Function type interface for Bfs algorithm.
     1169  ///Function-type interface for BFS algorithm.
    10821170  ///
    1083   ///This function also has several
    1084   ///\ref named-templ-func-param "named parameters",
     1171  ///This function also has several \ref named-func-param "named parameters",
    10851172  ///they are declared as the members of class \ref BfsWizard.
    1086   ///The following
    1087   ///example shows how to use these parameters.
     1173  ///The following examples show how to use these parameters.
    10881174  ///\code
    1089   ///  bfs(g,source).predMap(preds).run();
     1175  ///  // Compute shortest path from node s to each node
     1176  ///  bfs(g).predMap(preds).distMap(dists).run(s);
     1177  ///
     1178  ///  // Compute shortest path from s to t
     1179  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    10901180  ///\endcode
    10911181  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
    … …  
    10951185  template<class GR>
    10961186  BfsWizard<BfsWizardBase<GR> >
    1097   bfs(const GR &g,typename GR::Node s=INVALID)
     1187  bfs(const GR &digraph)
    10981188  {
    1099     return BfsWizard<BfsWizardBase<GR> >(g,s);
     1189    return BfsWizard<BfsWizardBase<GR> >(digraph);
    11001190  }
    11011191
    11021192#ifdef DOXYGEN
    1103   /// \brief Visitor class for bfs.
     1193  /// \brief Visitor class for BFS.
    11041194  ///
    11051195  /// This class defines the interface of the BfsVisit events, and
    1106   /// it could be the base of a real Visitor class.
     1196  /// it could be the base of a real visitor class.
    11071197  template <typename _Digraph>
    11081198  struct BfsVisitor {
    … …  
    11101200    typedef typename Digraph::Arc Arc;
    11111201    typedef typename Digraph::Node Node;
    1112     /// \brief Called when the arc reach a node.
    1113     ///
    1114     /// It is called when the bfs find an arc which target is not
    1115     /// reached yet.
     1202    /// \brief Called for the source node(s) of the BFS.
     1203    ///
     1204    /// This function is called for the source node(s) of the BFS.
     1205    void start(const Node& node) {}
     1206    /// \brief Called when a node is reached first time.
     1207    ///
     1208    /// This function is called when a node is reached first time.
     1209    void reach(const Node& node) {}
     1210    /// \brief Called when a node is processed.
     1211    ///
     1212    /// This function is called when a node is processed.
     1213    void process(const Node& node) {}
     1214    /// \brief Called when an arc reaches a new node.
     1215    ///
     1216    /// This function is called when the BFS finds an arc whose target node
     1217    /// is not reached yet.
    11161218    void discover(const Arc& arc) {}
    1117     /// \brief Called when the node reached first time.
    1118     ///
    1119     /// It is Called when the node reached first time.
    1120     void reach(const Node& node) {}
    1121     /// \brief Called when the arc examined but target of the arc
     1219    /// \brief Called when an arc is examined but its target node is
    11221220    /// already discovered.
    11231221    ///
    1124     /// It called when the arc examined but the target of the arc
     1222    /// This function is called when an arc is examined but its target node is
    11251223    /// already discovered.
    11261224    void examine(const Arc& arc) {}
    1127     /// \brief Called for the source node of the bfs.
    1128     ///
    1129     /// It is called for the source node of the bfs.
    1130     void start(const Node& node) {}
    1131     /// \brief Called when the node processed.
    1132     ///
    1133     /// It is Called when the node processed.
    1134     void process(const Node& node) {}
    11351225  };
    11361226#else
    … …  
    11401230    typedef typename Digraph::Arc Arc;
    11411231    typedef typename Digraph::Node Node;
     1232    void start(const Node&) {}
     1233    void reach(const Node&) {}
     1234    void process(const Node&) {}
    11421235    void discover(const Arc&) {}
    1143     void reach(const Node&) {}
    11441236    void examine(const Arc&) {}
    1145     void start(const Node&) {}
    1146     void process(const Node&) {}
    11471237
    11481238    template <typename _Visitor>
    … …  
    11511241        Arc arc;
    11521242        Node node;
     1243        visitor.start(node);
     1244        visitor.reach(node);
     1245        visitor.process(node);
    11531246        visitor.discover(arc);
    1154         visitor.reach(node);
    11551247        visitor.examine(arc);
    1156         visitor.start(node);
    1157         visitor.process(node);
    11581248      }
    11591249      _Visitor& visitor;
    … …  
    11651255  ///
    11661256  /// Default traits class of BfsVisit class.
    1167   /// \tparam _Digraph Digraph type.
     1257  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    11681258  template<class _Digraph>
    11691259  struct BfsVisitDefaultTraits {
    11701260
    1171     /// \brief The digraph type the algorithm runs on.
     1261    /// \brief The type of the digraph the algorithm runs on.
    11721262    typedef _Digraph Digraph;
    11731263
    … …  
    11751265    ///
    11761266    /// The type of the map that indicates which nodes are reached.
    1177     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1178     /// \todo named parameter to set this type, function to read and write.
     1267    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    11791268    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    11801269
    11811270    /// \brief Instantiates a ReachedMap.
    11821271    ///
    1183     /// This function instantiates a \ref ReachedMap.
     1272    /// This function instantiates a ReachedMap.
    11841273    /// \param digraph is the digraph, to which
    1185     /// we would like to define the \ref ReachedMap.
     1274    /// we would like to define the ReachedMap.
    11861275    static ReachedMap *createReachedMap(const Digraph &digraph) {
    11871276      return new ReachedMap(digraph);
    … …  
    11921281  /// \ingroup search
    11931282  ///
    1194   /// \brief %BFS Visit algorithm class.
     1283  /// \brief %BFS algorithm class with visitor interface.
    11951284  ///
    11961285  /// This class provides an efficient implementation of the %BFS algorithm
    … …  
    11991288  /// The %BfsVisit class provides an alternative interface to the Bfs
    12001289  /// class. It works with callback mechanism, the BfsVisit object calls
    1201   /// on every bfs event the \c Visitor class member functions.
     1290  /// the member functions of the \c Visitor class on every BFS event.
    12021291  ///
    1203   /// \tparam _Digraph The digraph type the algorithm runs on.
     1292  /// This interface of the BFS algorithm should be used in special cases
     1293  /// when extra actions have to be performed in connection with certain
     1294  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
     1295  /// instead.
     1296  ///
     1297  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    12041298  /// The default value is
    1205   /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
    1206   /// is only passed to \ref BfsDefaultTraits.
    1207   /// \tparam _Visitor The Visitor object for the algorithm. The
    1208   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
    1209   /// does not observe the Bfs events. If you want to observe the bfs
    1210   /// events you should implement your own Visitor class.
     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
     1303  /// does not observe the BFS events. If you want to observe the BFS
     1304  /// events, you should implement your own visitor class.
    12111305  /// \tparam _Traits Traits class to set various data types used by the
    12121306  /// algorithm. The default traits class is
    12131307  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
    12141308  /// See \ref BfsVisitDefaultTraits for the documentation of
    1215   /// a Bfs visit traits class.
     1309  /// a BFS visit traits class.
    12161310#ifdef DOXYGEN
    12171311  template <typename _Digraph, typename _Visitor, typename _Traits>
    … …  
    12191313  template <typename _Digraph = ListDigraph,
    12201314            typename _Visitor = BfsVisitor<_Digraph>,
    1221             typename _Traits = BfsDefaultTraits<_Digraph> >
     1315            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
    12221316#endif
    12231317  class BfsVisit {
    12241318  public:
    12251319
    1226     /// \brief \ref Exception for uninitialized parameters.
    1227     ///
    1228     /// This error represents problems in the initialization
    1229     /// of the parameters of the algorithms.
    1230     class UninitializedParameter : public lemon::UninitializedParameter {
    1231     public:
    1232       virtual const char* what() const throw()
    1233       {
    1234         return "lemon::BfsVisit::UninitializedParameter";
    1235       }
    1236     };
    1237 
     1320    ///The traits class.
    12381321    typedef _Traits Traits;
    12391322
     1323    ///The type of the digraph the algorithm runs on.
    12401324    typedef typename Traits::Digraph Digraph;
    12411325
     1326    ///The visitor type used by the algorithm.
    12421327    typedef _Visitor Visitor;
    12431328
    1244     ///The type of the map indicating which nodes are reached.
     1329    ///The type of the map that indicates which nodes are reached.
    12451330    typedef typename Traits::ReachedMap ReachedMap;
    12461331
    … …  
    12521337    typedef typename Digraph::OutArcIt OutArcIt;
    12531338
    1254     /// Pointer to the underlying digraph.
     1339    //Pointer to the underlying digraph.
    12551340    const Digraph *_digraph;
    1256     /// Pointer to the visitor object.
     1341    //Pointer to the visitor object.
    12571342    Visitor *_visitor;
    1258     ///Pointer to the map of reached status of the nodes.
     1343    //Pointer to the map of reached status of the nodes.
    12591344    ReachedMap *_reached;
    1260     ///Indicates if \ref _reached is locally allocated (\c true) or not.
     1345    //Indicates if _reached is locally allocated (true) or not.
    12611346    bool local_reached;
    12621347
    … …  
    12641349    int _list_front, _list_back;
    12651350
    1266     /// \brief Creates the maps if necessary.
    1267     ///
    1268     /// Creates the maps if necessary.
     1351    //Creates the maps if necessary.
    12691352    void create_maps() {
    12701353      if(!_reached) {
    … …  
    12861369    ///@{
    12871370    template <class T>
    1288     struct DefReachedMapTraits : public Traits {
     1371    struct SetReachedMapTraits : public Traits {
    12891372      typedef T ReachedMap;
    12901373      static ReachedMap *createReachedMap(const Digraph &digraph) {
    1291         throw UninitializedParameter();
     1374        LEMON_ASSERT(false, "ReachedMap is not initialized");
     1375        return 0; // ignore warnings
    12921376      }
    12931377    };
    12941378    /// \brief \ref named-templ-param "Named parameter" for setting
    1295     /// ReachedMap type
    1296     ///
    1297     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
     1379    /// ReachedMap type.
     1380    ///
     1381    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
    12981382    template <class T>
    1299     struct DefReachedMap : public BfsVisit< Digraph, Visitor,
    1300                                             DefReachedMapTraits<T> > {
    1301       typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
     1383    struct SetReachedMap : public BfsVisit< Digraph, Visitor,
     1384                                            SetReachedMapTraits<T> > {
     1385      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
    13021386    };
    13031387    ///@}
    … …  
    13091393    /// Constructor.
    13101394    ///
    1311     /// \param digraph the digraph the algorithm will run on.
    1312     /// \param visitor The visitor of the algorithm.
    1313     ///
     1395    /// \param digraph The digraph the algorithm runs on.
     1396    /// \param visitor The visitor object of the algorithm.
    13141397    BfsVisit(const Digraph& digraph, Visitor& visitor)
    13151398      : _digraph(&digraph), _visitor(&visitor),
    … …  
    13171400
    13181401    /// \brief Destructor.
    1319     ///
    1320     /// Destructor.
    13211402    ~BfsVisit() {
    13221403      if(local_reached) delete _reached;
    13231404    }
    13241405
    1325     /// \brief Sets the map indicating if a node is reached.
    1326     ///
    1327     /// Sets the map indicating if a node is reached.
     1406    /// \brief Sets the map that indicates which nodes are reached.
     1407    ///
     1408    /// Sets the map that indicates which nodes are reached.
    13281409    /// If you don't use this function before calling \ref run(),
    1329     /// it will allocate one. The destuctor deallocates this
     1410    /// it will allocate one. The destructor deallocates this
    13301411    /// automatically allocated map, of course.
    13311412    /// \return <tt> (*this) </tt>
    … …  
    13401421
    13411422  public:
     1423
    13421424    /// \name Execution control
    13431425    /// The simplest way to execute the algorithm is to use
    1344     /// one of the member functions called \c run(...).
     1426    /// one of the member functions called \ref lemon::BfsVisit::run()
     1427    /// "run()".
    13451428    /// \n
    1346     /// If you need more control on the execution,
    1347     /// first you must call \ref init(), then you can adda source node
    1348     /// with \ref addSource().
    1349     /// Finally \ref start() will perform the actual path
    1350     /// computation.
     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.
    13511434
    13521435    /// @{
     1436
    13531437    /// \brief Initializes the internal data structures.
    13541438    ///
    13551439    /// Initializes the internal data structures.
    1356     ///
    13571440    void init() {
    13581441      create_maps();
    … …  
    13821465    /// \return The processed node.
    13831466    ///
    1384     /// \pre The queue must not be empty!
     1467    /// \pre The queue must not be empty.
    13851468    Node processNextNode() {
    13861469      Node n = _list[++_list_front];
    … …  
    14031486    /// \brief Processes the next node.
    14041487    ///
    1405     /// Processes the next node. And checks that the given target node
     1488    /// Processes the next node and checks if the given target node
    14061489    /// is reached. If the target node is reachable from the processed
    1407     /// node then the reached parameter will be set true. The reached
    1408     /// parameter should be initially false.
     1490    /// node, then the \c reach parameter will be set to \c true.
    14091491    ///
    14101492    /// \param target The target node.
    1411     /// \retval reach Indicates that the target node is reached.
     1493    /// \retval reach Indicates if the target node is reached.
     1494    /// It should be initially \c false.
     1495    ///
    14121496    /// \return The processed node.
    14131497    ///
    1414     /// \warning The queue must not be empty!
     1498    /// \pre The queue must not be empty.
    14151499    Node processNextNode(Node target, bool& reach) {
    14161500      Node n = _list[++_list_front];
    … …  
    14341518    /// \brief Processes the next node.
    14351519    ///
    1436     /// Processes the next node. And checks that at least one of
    1437     /// reached node has true value in the \c nm node map. If one node
    1438     /// with true value is reachable from the processed node then the
    1439     /// rnode parameter will be set to the first of such nodes.
    1440     ///
    1441     /// \param nm The node map of possible targets.
     1520    /// Processes the next node and checks if at least one of reached
     1521    /// nodes has \c true value in the \c nm node map. If one node
     1522    /// with \c true value is reachable from the processed node, then the
     1523    /// \c rnode parameter will be set to the first of such nodes.
     1524    ///
     1525    /// \param nm A \c bool (or convertible) node map that indicates the
     1526    /// possible targets.
    14421527    /// \retval rnode The reached target node.
     1528    /// It should be initially \c INVALID.
     1529    ///
    14431530    /// \return The processed node.
    14441531    ///
    1445     /// \warning The queue must not be empty!
     1532    /// \pre The queue must not be empty.
    14461533    template <typename NM>
    14471534    Node processNextNode(const NM& nm, Node& rnode) {
    … …  
    14641551    }
    14651552
    1466     /// \brief Next node to be processed.
    1467     ///
    1468     /// Next node to be processed.
    1469     ///
    1470     /// \return The next node to be processed or INVALID if the stack is
    1471     /// empty.
    1472     Node nextNode() {
     1553    /// \brief The next node to be processed.
     1554    ///
     1555    /// Returns the next node to be processed or \c INVALID if the queue
     1556    /// is empty.
     1557    Node nextNode() const {
    14731558      return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
    14741559    }
    14751560
    14761561    /// \brief Returns \c false if there are nodes
    1477     /// to be processed in the queue
     1562    /// to be processed.
    14781563    ///
    14791564    /// Returns \c false if there are nodes
    1480     /// to be processed in the queue
    1481     bool emptyQueue() { return _list_front == _list_back; }
     1565    /// to be processed in the queue.
     1566    bool emptyQueue() const { return _list_front == _list_back; }
    14821567
    14831568    /// \brief Returns the number of the nodes to be processed.
    14841569    ///
    14851570    /// Returns the number of the nodes to be processed in the queue.
    1486     int queueSize() { return _list_back - _list_front; }
     1571    int queueSize() const { return _list_back - _list_front; }
    14871572
    14881573    /// \brief Executes the algorithm.
    … …  
    14901575    /// Executes the algorithm.
    14911576    ///
    1492     /// \pre init() must be called and at least one node should be added
     1577    /// This method runs the %BFS algorithm from the root node(s)
     1578    /// in order to compute the shortest path to each node.
     1579    ///
     1580    /// The algorithm computes
     1581    /// - the shortest path tree (forest),
     1582    /// - the distance of each node from the root(s).
     1583    ///
     1584    /// \pre init() must be called and at least one root node should be added
    14931585    /// with addSource() before using this function.
     1586    ///
     1587    /// \note <tt>b.start()</tt> is just a shortcut of the following code.
     1588    /// \code
     1589    ///   while ( !b.emptyQueue() ) {
     1590    ///     b.processNextNode();
     1591    ///   }
     1592    /// \endcode
    14941593    void start() {
    14951594      while ( !emptyQueue() ) processNextNode();
    14961595    }
    14971596
    1498     /// \brief Executes the algorithm until \c dest is reached.
    1499     ///
    1500     /// Executes the algorithm until \c dest is reached.
    1501     ///
    1502     /// \pre init() must be called and at least one node should be added
    1503     /// with addSource() before using this function.
    1504     void start(Node dest) {
     1597    /// \brief Executes the algorithm until the given target node is reached.
     1598    ///
     1599    /// Executes the algorithm until the given target node is reached.
     1600    ///
     1601    /// This method runs the %BFS algorithm from the root node(s)
     1602    /// in order to compute the shortest path to \c t.
     1603    ///
     1604    /// The algorithm computes
     1605    /// - the shortest path to \c t,
     1606    /// - the distance of \c t from the root(s).
     1607    ///
     1608    /// \pre init() must be called and at least one root node should be
     1609    /// added with addSource() before using this function.
     1610    ///
     1611    /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
     1612    /// \code
     1613    ///   bool reach = false;
     1614    ///   while ( !b.emptyQueue() && !reach ) {
     1615    ///     b.processNextNode(t, reach);
     1616    ///   }
     1617    /// \endcode
     1618    void start(Node t) {
    15051619      bool reach = false;
    1506       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
     1620      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
    15071621    }
    15081622
    … …  
    15111625    /// Executes the algorithm until a condition is met.
    15121626    ///
    1513     /// \pre init() must be called and at least one node should be added
    1514     /// with addSource() before using this function.
    1515     ///
    1516     ///\param nm must be a bool (or convertible) node map. The
    1517     ///algorithm will stop when it reaches a node \c v with
     1627    /// This method runs the %BFS algorithm from the root node(s) in
     1628    /// order to compute the shortest path to a node \c v with
     1629    /// <tt>nm[v]</tt> true, if such a node can be found.
     1630    ///
     1631    /// \param nm must be a bool (or convertible) node map. The
     1632    /// algorithm will stop when it reaches a node \c v with
    15181633    /// <tt>nm[v]</tt> true.
    15191634    ///
    1520     ///\return The reached node \c v with <tt>nm[v]</tt> true or
    1521     ///\c INVALID if no such node was found.
     1635    /// \return The reached node \c v with <tt>nm[v]</tt> true or
     1636    /// \c INVALID if no such node was found.
     1637    ///
     1638    /// \pre init() must be called and at least one root node should be
     1639    /// added with addSource() before using this function.
     1640    ///
     1641    /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
     1642    /// \code
     1643    ///   Node rnode = INVALID;
     1644    ///   while ( !b.emptyQueue() && rnode == INVALID ) {
     1645    ///     b.processNextNode(nm, rnode);
     1646    ///   }
     1647    ///   return rnode;
     1648    /// \endcode
    15221649    template <typename NM>
    15231650    Node start(const NM &nm) {
    … …  
    15291656    }
    15301657
    1531     /// \brief Runs %BFSVisit algorithm from node \c s.
    1532     ///
    1533     /// This method runs the %BFS algorithm from a root node \c s.
    1534     /// \note b.run(s) is just a shortcut of the following code.
     1658    /// \brief Runs the algorithm from the given source node.
     1659    ///
     1660    /// This method runs the %BFS algorithm from node \c s
     1661    /// in order to compute the shortest path to each node.
     1662    ///
     1663    /// The algorithm computes
     1664    /// - the shortest path tree,
     1665    /// - the distance of each node from the root.
     1666    ///
     1667    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
    15351668    ///\code
    15361669    ///   b.init();
    … …  
    15441677    }
    15451678
    1546     /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
     1679    /// \brief Finds the shortest path between \c s and \c t.
     1680    ///
     1681    /// This method runs the %BFS algorithm from node \c s
     1682    /// in order to compute the shortest path to node \c t
     1683    /// (it stops searching when \c t is processed).
     1684    ///
     1685    /// \return \c true if \c t is reachable form \c s.
     1686    ///
     1687    /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     1688    /// shortcut of the following code.
     1689    ///\code
     1690    ///   b.init();
     1691    ///   b.addSource(s);
     1692    ///   b.start(t);
     1693    ///\endcode
     1694    bool run(Node s,Node t) {
     1695      init();
     1696      addSource(s);
     1697      start(t);
     1698      return reached(t);
     1699    }
     1700
     1701    /// \brief Runs the algorithm to visit all nodes in the digraph.
    15471702    ///
    15481703    /// This method runs the %BFS algorithm in order to
    1549     /// compute the %BFS path to each node. The algorithm computes
    1550     /// - The %BFS tree.
    1551     /// - The distance of each node from the root in the %BFS tree.
    1552     ///
    1553     ///\note b.run() is just a shortcut of the following code.
     1704    /// compute the shortest path to each node.
     1705    ///
     1706    /// The algorithm computes
     1707    /// - the shortest path tree (forest),
     1708    /// - the distance of each node from the root(s).
     1709    ///
     1710    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
    15541711    ///\code
    15551712    ///  b.init();
    1556     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
    1557     ///    if (!b.reached(it)) {
    1558     ///      b.addSource(it);
     1713    ///  for (NodeIt n(gr); n != INVALID; ++n) {
     1714    ///    if (!b.reached(n)) {
     1715    ///      b.addSource(n);
    15591716    ///      b.start();
    15601717    ///    }
    … …  
    15701727      }
    15711728    }
     1729
    15721730    ///@}
    15731731
    … …  
    15751733    /// The result of the %BFS algorithm can be obtained using these
    15761734    /// functions.\n
    1577     /// Before the use of these functions,
    1578     /// either run() or start() must be called.
     1735    /// Either \ref lemon::BfsVisit::run() "run()" or
     1736    /// \ref lemon::BfsVisit::start() "start()" must be called before
     1737    /// using them.
    15791738    ///@{
    15801739
    1581     /// \brief Checks if a node is reachable from the root.
     1740    /// \brief Checks if a node is reachable from the root(s).
    15821741    ///
    15831742    /// Returns \c true if \c v is reachable from the root(s).
    1584     /// \warning The source nodes are inditated as unreachable.
    15851743    /// \pre Either \ref run() or \ref start()
    15861744    /// must be called before using this function.
    1587     ///
    15881745    bool reached(Node v) { return (*_reached)[v]; }
     1746
    15891747    ///@}
     1748
    15901749  };
    15911750
    … …  
    15931752
    15941753#endif
    1595 

  • lemon/bits/alteration_notifier.h

    r220 r318  
    2525#include <lemon/core.h>
    2626
    27 ///\ingroup graphbits
    28 ///\file
    29 ///\brief Observer notifier for graph alteration observers.
     27//\ingroup graphbits
     28//\file
     29//\brief Observer notifier for graph alteration observers.
    3030
    3131namespace lemon {
    3232
    33   /// \ingroup graphbits
    34   ///
    35   /// \brief Notifier class to notify observes about alterations in
    36   /// a container.
    37   ///
    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
    44   /// nodes and edges in the graph. Lemon would like to handle easily
    45   /// that the node and edge maps should contain values for all nodes or
    46   /// edges. If we want to check on every indicing if the map contains
    47   /// the current indicing key that cause a drawback in the performance
    48   /// in the library. We use another solution we notify all maps about
    49   /// an alteration in the graph, which cause only drawback on the
    50   /// alteration of the graph.
    51   ///
    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.
    56   ///
    57   /// For the proper functonality of this class, we should notify it
    58   /// about each alteration in the container. The alterations have four type
    59   /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
    60   /// \e erase() signals that only one or few items added or erased to or
    61   /// from the graph. If all items are erased from the graph or from an empty
    62   /// graph a new graph is builded then it can be signaled with the
    63   /// clear() and build() members. Important rule that if we erase items
    64   /// from graph we should first signal the alteration and after that erase
    65   /// them from the container, on the other way on item addition we should
    66   /// first extend the container and just after that signal the alteration.
    67   ///
    68   /// The alteration can be observed with a class inherited from the
    69   /// \e ObserverBase nested class. The signals can be handled with
    70   /// overriding the virtual functions defined in the base class.  The
    71   /// observer base can be attached to the notifier with the
    72   /// \e attach() member and can be detached with detach() function. The
    73   /// alteration handlers should not call any function which signals
    74   /// an other alteration in the same notifier and should not
    75   /// detach any observer from the notifier.
    76   ///
    77   /// Alteration observers try to be exception safe. If an \e add() or
    78   /// a \e clear() function throws an exception then the remaining
    79   /// observeres will not be notified and the fulfilled additions will
    80   /// be rolled back by calling the \e erase() or \e clear()
    81   /// functions. Thence the \e erase() and \e clear() should not throw
    82   /// exception. Actullay, it can be throw only
    83   /// \ref AlterationObserver::ImmediateDetach ImmediateDetach
    84   /// exception which detach the observer from the notifier.
    85   ///
    86   /// There are some place when the alteration observing is not completly
    87   /// reliable. If we want to carry out the node degree in the graph
    88   /// as in the \ref InDegMap and we use the reverseEdge that cause
    89   /// unreliable functionality. Because the alteration observing signals
    90   /// only erasing and adding but not the reversing it will stores bad
    91   /// degrees. The sub graph adaptors cannot signal the alterations because
    92   /// just a setting in the filter map can modify the graph and this cannot
    93   /// be watched in any way.
    94   ///
    95   /// \param _Container The container which is observed.
    96   /// \param _Item The item type which is obserbved.
     33  // \ingroup graphbits
     34  //
     35  // \brief Notifier class to notify observes about alterations in
     36  // a container.
     37  //
     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
     44  // nodes and edges in the graph. LEMON would like to handle easily
     45  // that the node and edge maps should contain values for all nodes or
     46  // edges. If we want to check on every indicing if the map contains
     47  // the current indicing key that cause a drawback in the performance
     48  // in the library. We use another solution we notify all maps about
     49  // an alteration in the graph, which cause only drawback on the
     50  // alteration of the graph.
     51  //
     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.
     56  //
     57  // For the proper functonality of this class, we should notify it
     58  // about each alteration in the container. The alterations have four type
     59  // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
     60  // \e erase() signals that only one or few items added or erased to or
     61  // from the graph. If all items are erased from the graph or from an empty
     62  // graph a new graph is builded then it can be signaled with the
     63  // clear() and build() members. Important rule that if we erase items
     64  // from graph we should first signal the alteration and after that erase
     65  // them from the container, on the other way on item addition we should
     66  // first extend the container and just after that signal the alteration.
     67  //
     68  // The alteration can be observed with a class inherited from the
     69  // \e ObserverBase nested class. The signals can be handled with
     70  // overriding the virtual functions defined in the base class.  The
     71  // observer base can be attached to the notifier with the
     72  // \e attach() member and can be detached with detach() function. The
     73  // alteration handlers should not call any function which signals
     74  // an other alteration in the same notifier and should not
     75  // detach any observer from the notifier.
     76  //
     77  // Alteration observers try to be exception safe. If an \e add() or
     78  // a \e clear() function throws an exception then the remaining
     79  // observeres will not be notified and the fulfilled additions will
     80  // be rolled back by calling the \e erase() or \e clear()
     81  // functions. Thence the \e erase() and \e clear() should not throw
     82  // exception. Actullay, it can be throw only \ref ImmediateDetach
     83  // exception which detach the observer from the notifier.
     84  //
     85  // There are some place when the alteration observing is not completly
     86  // reliable. If we want to carry out the node degree in the graph
     87  // as in the \ref InDegMap and we use the reverseEdge that cause
     88  // unreliable functionality. Because the alteration observing signals
     89  // only erasing and adding but not the reversing it will stores bad
     90  // degrees. The sub graph adaptors cannot signal the alterations because
     91  // just a setting in the filter map can modify the graph and this cannot
     92  // be watched in any way.
     93  //
     94  // \param _Container The container which is observed.
     95  // \param _Item The item type which is obserbved.
    9796
    9897  template <typename _Container, typename _Item>
    … …  
    105104    typedef _Item Item;
    106105
    107     /// \brief Exception which can be called from \e clear() and
    108     /// \e erase().
    109     ///
    110     /// From the \e clear() and \e erase() function only this
    111     /// exception is allowed to throw. The exception immediatly
    112     /// detaches the current observer from the notifier. Because the
    113     /// \e clear() and \e erase() should not throw other exceptions
    114     /// it can be used to invalidate the observer.
     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
     110    // exception is allowed to throw. The exception immediatly
     111    // detaches the current observer from the notifier. Because the
     112    // \e clear() and \e erase() should not throw other exceptions
     113    // it can be used to invalidate the observer.
    115114    struct ImmediateDetach {};
    116115
    117     /// \brief ObserverBase is the base class for the observers.
    118     ///
    119     /// ObserverBase is the abstract base class for the observers.
    120     /// It will be notified about an item was inserted into or
    121     /// erased from the graph.
    122     ///
    123     /// The observer interface contains some pure virtual functions
    124     /// to override. The add() and erase() functions are
    125     /// to notify the oberver when one item is added or
    126     /// erased.
    127     ///
    128     /// The build() and clear() members are to notify the observer
    129     /// about the container is built from an empty container or
    130     /// is cleared to an empty container.
    131 
     116    // \brief ObserverBase is the base class for the observers.
     117    //
     118    // ObserverBase is the abstract base class for the observers.
     119    // It will be notified about an item was inserted into or
     120    // erased from the graph.
     121    //
     122    // The observer interface contains some pure virtual functions
     123    // to override. The add() and erase() functions are
     124    // to notify the oberver when one item is added or
     125    // erased.
     126    //
     127    // The build() and clear() members are to notify the observer
     128    // about the container is built from an empty container or
     129    // is cleared to an empty container.
    132130    class ObserverBase {
    133131    protected:
    … …  
    136134      friend class AlterationNotifier;
    137135
    138       /// \brief Default constructor.
    139       ///
    140       /// Default constructor for ObserverBase.
    141       ///
     136      // \brief Default constructor.
     137      //
     138      // Default constructor for ObserverBase.
    142139      ObserverBase() : _notifier(0) {}
    143140
    144       /// \brief Constructor which attach the observer into notifier.
    145       ///
    146       /// Constructor which attach the observer into notifier.
     141      // \brief Constructor which attach the observer into notifier.
     142      //
     143      // Constructor which attach the observer into notifier.
    147144      ObserverBase(AlterationNotifier& nf) {
    148145        attach(nf);
    149146      }
    150147
    151       /// \brief Constructor which attach the obserever to the same notifier.
    152       ///
    153       /// Constructor which attach the obserever to the same notifier as
    154       /// the other observer is attached to.
     148      // \brief Constructor which attach the obserever to the same notifier.
     149      //
     150      // Constructor which attach the obserever to the same notifier as
     151      // the other observer is attached to.
    155152      ObserverBase(const ObserverBase& copy) {
    156153        if (copy.attached()) {
    … …  
    159156      }
    160157
    161       /// \brief Destructor
     158      // \brief Destructor
    162159      virtual ~ObserverBase() {
    163160        if (attached()) {
    … …  
    166163      }
    167164
    168       /// \brief Attaches the observer into an AlterationNotifier.
    169       ///
    170       /// This member attaches the observer into an AlterationNotifier.
    171       ///
     165      // \brief Attaches the observer into an AlterationNotifier.
     166      //
     167      // This member attaches the observer into an AlterationNotifier.
    172168      void attach(AlterationNotifier& nf) {
    173169        nf.attach(*this);
    174170      }
    175171
    176       /// \brief Detaches the observer into an AlterationNotifier.
    177       ///
    178       /// This member detaches the observer from an AlterationNotifier.
    179       ///
     172      // \brief Detaches the observer into an AlterationNotifier.
     173      //
     174      // This member detaches the observer from an AlterationNotifier.
    180175      void detach() {
    181176        _notifier->detach(*this);
    182177      }
    183178
    184       /// \brief Gives back a pointer to the notifier which the map
    185       /// attached into.
    186       ///
    187       /// This function gives back a pointer to the notifier which the map
    188       /// attached into.
    189       ///
     179      // \brief Gives back a pointer to the notifier which the map
     180      // attached into.
     181      //
     182      // This function gives back a pointer to the notifier which the map
     183      // attached into.
    190184      Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }
    191185
    192       /// Gives back true when the observer is attached into a notifier.
     186      // Gives back true when the observer is attached into a notifier.
    193187      bool attached() const { return _notifier != 0; }
    194188
    … …  
    202196      typename std::list<ObserverBase*>::iterator _index;
    203197
    204       /// \brief The member function to notificate the observer about an
    205       /// item is added to the container.
    206       ///
    207       /// The add() member function notificates the observer about an item
    208       /// is added to the container. It have to be overrided in the
    209       /// subclasses.
     198      // \brief The member function to notificate the observer about an
     199      // item is added to the container.
     200      //
     201      // The add() member function notificates the observer about an item
     202      // is added to the container. It have to be overrided in the
     203      // subclasses.
    210204      virtual void add(const Item&) = 0;
    211205
    212       /// \brief The member function to notificate the observer about
    213       /// more item is added to the container.
    214       ///
    215       /// The add() member function notificates the observer about more item
    216       /// is added to the container. It have to be overrided in the
    217       /// subclasses.
     206      // \brief The member function to notificate the observer about
     207      // more item is added to the container.
     208      //
     209      // The add() member function notificates the observer about more item
     210      // is added to the container. It have to be overrided in the
     211      // subclasses.
    218212      virtual void add(const std::vector<Item>& items) = 0;
    219213
    220       /// \brief The member function to notificate the observer about an
    221       /// item is erased from the container.
    222       ///
    223       /// The erase() member function notificates the observer about an
    224       /// item is erased from the container. It have to be overrided in
    225       /// the subclasses.
     214      // \brief The member function to notificate the observer about an
     215      // item is erased from the container.
     216      //
     217      // The erase() member function notificates the observer about an
     218      // item is erased from the container. It have to be overrided in
     219      // the subclasses.
    226220      virtual void erase(const Item&) = 0;
    227221
    228       /// \brief The member function to notificate the observer about
    229       /// more item is erased from the container.
    230       ///
    231       /// The erase() member function notificates the observer about more item
    232       /// is erased from the container. It have to be overrided in the
    233       /// subclasses.
     222      // \brief The member function to notificate the observer about
     223      // more item is erased from the container.
     224      //
     225      // The erase() member function notificates the observer about more item
     226      // is erased from the container. It have to be overrided in the
     227      // subclasses.
    234228      virtual void erase(const std::vector<Item>& items) = 0;
    235229
    236       /// \brief The member function to notificate the observer about the
    237       /// container is built.
    238       ///
    239       /// The build() member function notificates the observer about the
    240       /// container is built from an empty container. It have to be
    241       /// overrided in the subclasses.
    242 
     230      // \brief The member function to notificate the observer about the
     231      // container is built.
     232      //
     233      // The build() member function notificates the observer about the
     234      // container is built from an empty container. It have to be
     235      // overrided in the subclasses.
    243236      virtual void build() = 0;
    244237
    245       /// \brief The member function to notificate the observer about all
    246       /// items are erased from the container.
    247       ///
    248       /// The clear() member function notificates the observer about all
    249       /// items are erased from the container. It have to be overrided in
    250       /// the subclasses.
     238      // \brief The member function to notificate the observer about all
     239      // items are erased from the container.
     240      //
     241      // The clear() member function notificates the observer about all
     242      // items are erased from the container. It have to be overrided in
     243      // the subclasses.
    251244      virtual void clear() = 0;
    252245
    … …  
    263256  public:
    264257
    265     /// \brief Default constructor.
    266     ///
    267     /// The default constructor of the AlterationNotifier.
    268     /// It creates an empty notifier.
     258    // \brief Default constructor.
     259    //
     260    // The default constructor of the AlterationNotifier.
     261    // It creates an empty notifier.
    269262    AlterationNotifier()
    270263      : container(0) {}
    271264
    272     /// \brief Constructor.
    273     ///
    274     /// Constructor with the observed container parameter.
     265    // \brief Constructor.
     266    //
     267    // Constructor with the observed container parameter.
    275268    AlterationNotifier(const Container& _container)
    276269      : container(&_container) {}
    277270
    278     /// \brief Copy Constructor of the AlterationNotifier.
    279     ///
    280     /// Copy constructor of the AlterationNotifier.
    281     /// It creates only an empty notifier because the copiable
    282     /// notifier's observers have to be registered still into that notifier.
     271    // \brief Copy Constructor of the AlterationNotifier.
     272    //
     273    // Copy constructor of the AlterationNotifier.
     274    // It creates only an empty notifier because the copiable
     275    // notifier's observers have to be registered still into that notifier.
    283276    AlterationNotifier(const AlterationNotifier& _notifier)
    284277      : container(_notifier.container) {}
    285278
    286     /// \brief Destructor.
    287     ///
    288     /// Destructor of the AlterationNotifier.
    289     ///
     279    // \brief Destructor.
     280    //
     281    // Destructor of the AlterationNotifier.
    290282    ~AlterationNotifier() {
    291283      typename Observers::iterator it;
    … …  
    295287    }
    296288
    297     /// \brief Sets the container.
    298     ///
    299     /// Sets the container.
     289    // \brief Sets the container.
     290    //
     291    // Sets the container.
    300292    void setContainer(const Container& _container) {
    301293      container = &_container;
    … …  
    308300  public:
    309301
    310 
    311 
    312     /// \brief First item in the container.
    313     ///
    314     /// Returns the first item in the container. It is
    315     /// for start the iteration on the container.
     302    // \brief First item in the container.
     303    //
     304    // Returns the first item in the container. It is
     305    // for start the iteration on the container.
    316306    void first(Item& item) const {
    317307      container->first(item);
    318308    }
    319309
    320     /// \brief Next item in the container.
    321     ///
    322     /// Returns the next item in the container. It is
    323     /// for iterate on the container.
     310    // \brief Next item in the container.
     311    //
     312    // Returns the next item in the container. It is
     313    // for iterate on the container.
    324314    void next(Item& item) const {
    325315      container->next(item);
    326316    }
    327317
    328     /// \brief Returns the id of the item.
    329     ///
    330     /// Returns the id of the item provided by the container.
     318    // \brief Returns the id of the item.
     319    //
     320    // Returns the id of the item provided by the container.
    331321    int id(const Item& item) const {
    332322      return container->id(item);
    333323    }
    334324
    335     /// \brief Returns the maximum id of the container.
    336     ///
    337     /// Returns the maximum id of the container.
     325    // \brief Returns the maximum id of the container.
     326    //
     327    // Returns the maximum id of the container.
    338328    int maxId() const {
    339329      return container->maxId(Item());
    … …  
    355345  public:
    356346
    357     /// \brief Notifies all the registed observers about an item added to
    358     /// the container.
    359     ///
    360     /// It notifies all the registed observers about an item added to
    361     /// the container.
    362     ///
     347    // \brief Notifies all the registed observers about an item added to
     348    // the container.
     349    //
     350    // It notifies all the registed observers about an item added to
     351    // the container.
    363352    void add(const Item& item) {
    364353      typename Observers::reverse_iterator it;
    … …  
    376365    }
    377366
    378     /// \brief Notifies all the registed observers about more item added to
    379     /// the container.
    380     ///
    381     /// It notifies all the registed observers about more item added to
    382     /// the container.
    383     ///
     367    // \brief Notifies all the registed observers about more item added to
     368    // the container.
     369    //
     370    // It notifies all the registed observers about more item added to
     371    // the container.
    384372    void add(const std::vector<Item>& items) {
    385373      typename Observers::reverse_iterator it;
    … …  
    397385    }
    398386
    399     /// \brief Notifies all the registed observers about an item erased from
    400     /// the container.
    401     ///
    402     /// It notifies all the registed observers about an item erased from
    403     /// the container.
    404     ///
     387    // \brief Notifies all the registed observers about an item erased from
     388    // the container.
     389    //
     390    // It notifies all the registed observers about an item erased from
     391    // the container.
    405392    void erase(const Item& item) throw() {
    406393      typename Observers::iterator it = _observers.begin();
    … …  
    410397          ++it;
    411398        } catch (const ImmediateDetach&) {
    412           it = _observers.erase(it);
    413399          (*it)->_index = _observers.end();
    414400          (*it)->_notifier = 0;
    415         }
    416       }
    417     }
    418 
    419     /// \brief Notifies all the registed observers about more item erased
    420     /// from the container.
    421     ///
    422     /// It notifies all the registed observers about more item erased from
    423     /// the container.
    424     ///
     401          it = _observers.erase(it);
     402        }
     403      }
     404    }
     405
     406    // \brief Notifies all the registed observers about more item erased
     407    // from the container.
     408    //
     409    // It notifies all the registed observers about more item erased from
     410    // the container.
    425411    void erase(const std::vector<Item>& items) {
    426412      typename Observers::iterator it = _observers.begin();
    … …  
    430416          ++it;
    431417        } catch (const ImmediateDetach&) {
    432           it = _observers.erase(it);
    433418          (*it)->_index = _observers.end();
    434419          (*it)->_notifier = 0;
    435         }
    436       }
    437     }
    438 
    439     /// \brief Notifies all the registed observers about the container is
    440     /// built.
    441     ///
    442     /// Notifies all the registed observers about the container is built
    443     /// from an empty container.
     420          it = _observers.erase(it);
     421        }
     422      }
     423    }
     424
     425    // \brief Notifies all the registed observers about the container is
     426    // built.
     427    //
     428    // Notifies all the registed observers about the container is built
     429    // from an empty container.
    444430    void build() {
    445431      typename Observers::reverse_iterator it;
    … …  
    457443    }
    458444
    459     /// \brief Notifies all the registed observers about all items are
    460     /// erased.
    461     ///
    462     /// Notifies all the registed observers about all items are erased
    463     /// from the container.
     445    // \brief Notifies all the registed observers about all items are
     446    // erased.
     447    //
     448    // Notifies all the registed observers about all items are erased
     449    // from the container.
    464450    void clear() {
    465451      typename Observers::iterator it = _observers.begin();
    … …  
    469455          ++it;
    470456        } catch (const ImmediateDetach&) {
    471           it = _observers.erase(it);
    472457          (*it)->_index = _observers.end();
    473458          (*it)->_notifier = 0;
     459          it = _observers.erase(it);
    474460        }
    475461      }

  • lemon/bits/array_map.h

    r209 r318  
    2727#include <lemon/concepts/maps.h>
    2828
    29 /// \ingroup graphbits
    30 /// \file
    31 /// \brief Graph map based on the array storage.
     29// \ingroup graphbits
     30// \file
     31// \brief Graph map based on the array storage.
    3232
    3333namespace lemon {
    3434
    35   /// \ingroup graphbits
    36   ///
    37   /// \brief Graph map based on the array storage.
    38   ///
    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.
    43   ///
    44   /// The template parameters are the Graph the current Item type and
    45   /// the Value type of the map.
     35  // \ingroup graphbits
     36  //
     37  // \brief Graph map based on the array storage.
     38  //
     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.
     43  //
     44  // The template parameters are the Graph the current Item type and
     45  // the Value type of the map.
    4646  template <typename _Graph, typename _Item, typename _Value>
    4747  class ArrayMap
    4848    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4949  public:
    50     /// The graph type of the maps.
     50    // The graph type of the maps.
    5151    typedef _Graph Graph;
    52     /// The item type of the map.
     52    // The item type of the map.
    5353    typedef _Item Item;
    54     /// The reference map tag.
     54    // The reference map tag.
    5555    typedef True ReferenceMapTag;
    5656
    57     /// The key type of the maps.
     57    // The key type of the maps.
    5858    typedef _Item Key;
    59     /// The value type of the map.
     59    // The value type of the map.
    6060    typedef _Value Value;
    6161
    62     /// The const reference type of the map.
     62    // The const reference type of the map.
    6363    typedef const _Value& ConstReference;
    64     /// The reference type of the map.
     64    // The reference type of the map.
    6565    typedef _Value& Reference;
    6666
    67     /// The notifier type.
     67    // The notifier type.
    6868    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    6969
    70     /// The MapBase of the Map which imlements the core regisitry function.
     70    // The MapBase of the Map which imlements the core regisitry function.
    7171    typedef typename Notifier::ObserverBase Parent;
    7272
    … …  
    7676  public:
    7777
    78     /// \brief Graph initialized map constructor.
    79     ///
    80     /// Graph initialized map constructor.
     78    // \brief Graph initialized map constructor.
     79    //
     80    // Graph initialized map constructor.
    8181    explicit ArrayMap(const Graph& graph) {
    8282      Parent::attach(graph.notifier(Item()));
    … …  
    9090    }
    9191
    92     /// \brief Constructor to use default value to initialize the map.
    93     ///
    94     /// It constructs a map and initialize all of the the map.
     92    // \brief Constructor to use default value to initialize the map.
     93    //
     94    // It constructs a map and initialize all of the the map.
    9595    ArrayMap(const Graph& graph, const Value& value) {
    9696      Parent::attach(graph.notifier(Item()));
    … …  
    104104    }
    105105
    106     /// \brief Constructor to copy a map of the same map type.
    107     ///
    108     /// Constructor to copy a map of the same map type.
     106  private:
     107    // \brief Constructor to copy a map of the same map type.
     108    //
     109    // Constructor to copy a map of the same map type.
    109110    ArrayMap(const ArrayMap& copy) : Parent() {
    110111      if (copy.attached()) {
    … …  
    122123    }
    123124
    124     /// \brief Assign operator.
    125     ///
    126     /// This operator assigns for each item in the map the
    127     /// value mapped to the same item in the copied map.
    128     /// The parameter map should be indiced with the same
    129     /// itemset because this assign operator does not change
    130     /// the container of the map.
     125    // \brief Assign operator.
     126    //
     127    // This operator assigns for each item in the map the
     128    // value mapped to the same item in the copied map.
     129    // The parameter map should be indiced with the same
     130    // itemset because this assign operator does not change
     131    // the container of the map.
    131132    ArrayMap& operator=(const ArrayMap& cmap) {
    132133      return operator=<ArrayMap>(cmap);
    … …  
    134135
    135136
    136     /// \brief Template assign operator.
    137     ///
    138     /// The given parameter should be conform to the ReadMap
    139     /// concecpt and could be indiced by the current item set of
    140     /// the NodeMap. In this case the value for each item
    141     /// is assigned by the value of the given ReadMap.
     137    // \brief Template assign operator.
     138    //
     139    // The given parameter should be conform to the ReadMap
     140    // concecpt and could be indiced by the current item set of
     141    // the NodeMap. In this case the value for each item
     142    // is assigned by the value of the given ReadMap.
    142143    template <typename CMap>
    143144    ArrayMap& operator=(const CMap& cmap) {
    … …  
    151152    }
    152153
    153     /// \brief The destructor of the map.
    154     ///
    155     /// The destructor of the map.
     154  public:
     155    // \brief The destructor of the map.
     156    //
     157    // The destructor of the map.
    156158    virtual ~ArrayMap() {
    157159      if (attached()) {
    … …  
    169171  public:
    170172
    171     /// \brief The subscript operator.
    172     ///
    173     /// The subscript operator. The map can be subscripted by the
    174     /// actual keys of the graph.
     173    // \brief The subscript operator.
     174    //
     175    // The subscript operator. The map can be subscripted by the
     176    // actual keys of the graph.
    175177    Value& operator[](const Key& key) {
    176178      int id = Parent::notifier()->id(key);
    … …  
    178180    }
    179181
    180     /// \brief The const subscript operator.
    181     ///
    182     /// The const subscript operator. The map can be subscripted by the
    183     /// actual keys of the graph.
     182    // \brief The const subscript operator.
     183    //
     184    // The const subscript operator. The map can be subscripted by the
     185    // actual keys of the graph.
    184186    const Value& operator[](const Key& key) const {
    185187      int id = Parent::notifier()->id(key);
    … …  
    187189    }
    188190
    189     /// \brief Setter function of the map.
    190     ///
    191     /// Setter function of the map. Equivalent with map[key] = val.
    192     /// This is a compatibility feature with the not dereferable maps.
     191    // \brief Setter function of the map.
     192    //
     193    // Setter function of the map. Equivalent with map[key] = val.
     194    // This is a compatibility feature with the not dereferable maps.
    193195    void set(const Key& key, const Value& val) {
    194196      (*this)[key] = val;
    … …  
    197199  protected:
    198200
    199     /// \brief Adds a new key to the map.
    200     ///
    201     /// It adds a new key to the map. It called by the observer notifier
    202     /// and it overrides the add() member function of the observer base.
     201    // \brief Adds a new key to the map.
     202    //
     203    // It adds a new key to the map. It called by the observer notifier
     204    // and it overrides the add() member function of the observer base.
    203205    virtual void add(const Key& key) {
    204206      Notifier* nf = Parent::notifier();
    … …  
    225227    }
    226228
    227     /// \brief Adds more new keys to the map.
    228     ///
    229     /// It adds more new keys to the map. It called by the observer notifier
    230     /// and it overrides the add() member function of the observer base.
     229    // \brief Adds more new keys to the map.
     230    //
     231    // It adds more new keys to the map. It called by the observer notifier
     232    // and it overrides the add() member function of the observer base.
    231233    virtual void add(const std::vector<Key>& keys) {
    232234      Notifier* nf = Parent::notifier();
    … …  
    269271    }
    270272
    271     /// \brief Erase a key from the map.
    272     ///
    273     /// Erase a key from the map. It called by the observer notifier
    274     /// and it overrides the erase() member function of the observer base.
     273    // \brief Erase a key from the map.
     274    //
     275    // Erase a key from the map. It called by the observer notifier
     276    // and it overrides the erase() member function of the observer base.
    275277    virtual void erase(const Key& key) {
    276278      int id = Parent::notifier()->id(key);
    … …  
    278280    }
    279281
    280     /// \brief Erase more keys from the map.
    281     ///
    282     /// Erase more keys from the map. It called by the observer notifier
    283     /// and it overrides the erase() member function of the observer base.
     282    // \brief Erase more keys from the map.
     283    //
     284    // Erase more keys from the map. It called by the observer notifier
     285    // and it overrides the erase() member function of the observer base.
    284286    virtual void erase(const std::vector<Key>& keys) {
    285287      for (int i = 0; i < int(keys.size()); ++i) {
    … …  
    289291    }
    290292
    291     /// \brief Buildes the map.
    292     ///
    293     /// It buildes the map. It called by the observer notifier
    294     /// and it overrides the build() member function of the observer base.
     293    // \brief Buildes the map.
     294    //
     295    // It buildes the map. It called by the observer notifier
     296    // and it overrides the build() member function of the observer base.
    295297    virtual void build() {
    296298      Notifier* nf = Parent::notifier();
    … …  
    303305    }
    304306
    305     /// \brief Clear the map.
    306     ///
    307     /// It erase all items from the map. It called by the observer notifier
    308     /// and it overrides the clear() member function of the observer base.
     307    // \brief Clear the map.
     308    //
     309    // It erase all items from the map. It called by the observer notifier
     310    // and it overrides the clear() member function of the observer base.
    309311    virtual void clear() {
    310312      Notifier* nf = Parent::notifier();

  • lemon/bits/base_extender.h

    r220 r318  
    2929#include <lemon/concepts/maps.h>
    3030
    31 ///\ingroup digraphbits
    32 ///\file
    33 ///\brief Extenders for the digraph types
     31//\ingroup digraphbits
     32//\file
     33//\brief Extenders for the digraph types
    3434namespace lemon {
    3535
    36   /// \ingroup digraphbits
    37   ///
    38   /// \brief BaseDigraph to BaseGraph extender
     36  // \ingroup digraphbits
     37  //
     38  // \brief BaseDigraph to BaseGraph extender
    3939  template <typename Base>
    4040  class UndirDigraphExtender : public Base {
    … …  
    6060      Arc() {}
    6161
    62       /// Invalid arc constructor
     62      // Invalid arc constructor
    6363      Arc(Invalid i) : Edge(i), forward(true) {}
    6464
    … …  
    7575    };
    7676
    77 
    78 
    79     using Parent::source;
    80 
    81     /// Source of the given Arc.
     77    // First node of the edge
     78    Node u(const Edge &e) const {
     79      return Parent::source(e);
     80    }
     81
     82    // Source of the given arc
    8283    Node source(const Arc &e) const {
    8384      return e.forward ? Parent::source(e) : Parent::target(e);
    8485    }
    8586
    86     using Parent::target;
    87 
    88     /// Target of the given Arc.
     87    // Second node of the edge
     88    Node v(const Edge &e) const {
     89      return Parent::target(e);
     90    }
     91
     92    // Target of the given arc
    8993    Node target(const Arc &e) const {
    9094      return e.forward ? Parent::target(e) : Parent::source(e);
    9195    }
    9296
    93     /// \brief Directed arc from an edge.
    94     ///
    95     /// Returns a directed arc corresponding to the specified Edge.
    96     /// If the given bool is true the given edge and the
    97     /// returned arc have the same source node.
    98     static Arc direct(const Edge &ue, bool d) {
    99       return Arc(ue, d);
    100     }
    101 
    102     /// Returns whether the given directed arc is same orientation as the
    103     /// corresponding edge.
    104     ///
    105     /// \todo reference to the corresponding point of the undirected digraph
    106     /// concept. "What does the direction of an edge mean?"
    107     static bool direction(const Arc &e) { return e.forward; }
    108 
     97    // \brief Directed arc from an edge.
     98    //
     99    // Returns a directed arc corresponding to the specified edge.
     100    // If the given bool is true, the first node of the given edge and
     101    // the source node of the returned arc are the same.
     102    static Arc direct(const Edge &e, bool d) {
     103      return Arc(e, d);
     104    }
     105
     106    // Returns whether the given directed arc has the same orientation
     107    // as the corresponding edge.
     108    static bool direction(const Arc &a) { return a.forward; }
    109109
    110110    using Parent::first;
    … …  
    229229      return Parent::maxArcId();
    230230    }
    231 
    232231
    233232    int arcNum() const {
    … …  
    300299      Red() {}
    301300      Red(const Node& node) : Node(node) {
    302         LEMON_ASSERT(Parent::red(node) || node == INVALID,
    303                      typename Parent::NodeSetError());
     301        LEMON_DEBUG(Parent::red(node) || node == INVALID,
     302                    typename Parent::NodeSetError());
    304303      }
    305304      Red& operator=(const Node& node) {
    306         LEMON_ASSERT(Parent::red(node) || node == INVALID,
    307                      typename Parent::NodeSetError());
     305        LEMON_DEBUG(Parent::red(node) || node == INVALID,
     306                    typename Parent::NodeSetError());
    308307        Node::operator=(node);
    309308        return *this;
    … …  
    332331      Blue() {}
    333332      Blue(const Node& node) : Node(node) {
    334         LEMON_ASSERT(Parent::blue(node) || node == INVALID,
    335                      typename Parent::NodeSetError());
     333        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
     334                    typename Parent::NodeSetError());
    336335      }
    337336      Blue& operator=(const Node& node) {
    338         LEMON_ASSERT(Parent::blue(node) || node == INVALID,
    339                      typename Parent::NodeSetError());
     337        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
     338                    typename Parent::NodeSetError());
    340339        Node::operator=(node);
    341340        return *this;

  • lemon/bits/bezier.h

    r209 r318  
    2020#define LEMON_BEZIER_H
    2121
    22 ///\ingroup misc
    23 ///\file
    24 ///\brief Classes to compute with Bezier curves.
    25 ///
    26 ///Up to now this file is used internally by \ref graph_to_eps.h
     22//\ingroup misc
     23//\file
     24//\brief Classes to compute with Bezier curves.
     25//
     26//Up to now this file is used internally by \ref graph_to_eps.h
    2727
    2828#include<lemon/dim2.h>

  • lemon/bits/default_map.h

    r209 r318  
    2020#define LEMON_BITS_DEFAULT_MAP_H
    2121
    22 
    2322#include <lemon/bits/array_map.h>
    2423#include <lemon/bits/vector_map.h>
    2524//#include <lemon/bits/debug_map.h>
    2625
    27 ///\ingroup graphbits
    28 ///\file
    29 ///\brief Graph maps that construct and destruct their elements dynamically.
     26//\ingroup graphbits
     27//\file
     28//\brief Graph maps that construct and destruct their elements dynamically.
    3029
    3130namespace lemon {
    … …  
    150149// #endif
    151150
    152   /// \e
     151  // DefaultMap class
    153152  template <typename _Graph, typename _Item, typename _Value>
    154153  class DefaultMap

  • lemon/bits/enable_if.h

    r220 r318  
    3636#define LEMON_BITS_ENABLE_IF_H
    3737
    38 ///\file
    39 ///\brief Miscellaneous basic utilities
     38//\file
     39//\brief Miscellaneous basic utilities
    4040
    4141namespace lemon
    4242{
    4343
    44   /// Basic type for defining "tags". A "YES" condition for \c enable_if.
     44  // Basic type for defining "tags". A "YES" condition for \c enable_if.
    4545
    46   /// Basic type for defining "tags". A "YES" condition for \c enable_if.
    47   ///
    48   ///\sa False
     46  // Basic type for defining "tags". A "YES" condition for \c enable_if.
     47  //
     48  //\sa False
    4949  struct True {
    50     ///\e
     50    //\e
    5151    static const bool value = true;
    5252  };
    5353
    54   /// Basic type for defining "tags". A "NO" condition for \c enable_if.
     54  // Basic type for defining "tags". A "NO" condition for \c enable_if.
    5555
    56   /// Basic type for defining "tags". A "NO" condition for \c enable_if.
    57   ///
    58   ///\sa True
     56  // Basic type for defining "tags". A "NO" condition for \c enable_if.
     57  //
     58  //\sa True
    5959  struct False {
    60     ///\e
     60    //\e
    6161    static const bool value = false;
    6262  };

  • lemon/bits/graph_extender.h

    r220 r318  
    2828#include <lemon/concepts/maps.h>
    2929
    30 ///\ingroup graphbits
    31 ///\file
    32 ///\brief Extenders for the digraph types
     30//\ingroup graphbits
     31//\file
     32//\brief Extenders for the digraph types
    3333namespace lemon {
    3434
    35   /// \ingroup graphbits
    36   ///
    37   /// \brief Extender for the Digraphs
     35  // \ingroup graphbits
     36  //
     37  // \brief Extender for the Digraphs
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
    … …  
    187187    };
    188188
    189     /// \brief Base node of the iterator
    190     ///
    191     /// Returns the base node (i.e. the source in this case) of the iterator
     189    // \brief Base node of the iterator
     190    //
     191    // Returns the base node (i.e. the source in this case) of the iterator
    192192    Node baseNode(const OutArcIt &arc) const {
    193193      return Parent::source(arc);
    194194    }
    195     /// \brief Running node of the iterator
    196     ///
    197     /// Returns the running node (i.e. the target in this case) of the
    198     /// iterator
     195    // \brief Running node of the iterator
     196    //
     197    // Returns the running node (i.e. the target in this case) of the
     198    // iterator
    199199    Node runningNode(const OutArcIt &arc) const {
    200200      return Parent::target(arc);
    201201    }
    202202
    203     /// \brief Base node of the iterator
    204     ///
    205     /// Returns the base node (i.e. the target in this case) of the iterator
     203    // \brief Base node of the iterator
     204    //
     205    // Returns the base node (i.e. the target in this case) of the iterator
    206206    Node baseNode(const InArcIt &arc) const {
    207207      return Parent::target(arc);
    208208    }
    209     /// \brief Running node of the iterator
    210     ///
    211     /// Returns the running node (i.e. the source in this case) of the
    212     /// iterator
     209    // \brief Running node of the iterator
     210    //
     211    // Returns the running node (i.e. the source in this case) of the
     212    // iterator
    213213    Node runningNode(const InArcIt &arc) const {
    214214      return Parent::source(arc);
    … …  
    228228        : Parent(digraph, value) {}
    229229
     230    private:
    230231      NodeMap& operator=(const NodeMap& cmap) {
    231232        return operator=<NodeMap>(cmap);
    … …  
    252253        : Parent(digraph, value) {}
    253254
     255    private:
    254256      ArcMap& operator=(const ArcMap& cmap) {
    255257        return operator=<ArcMap>(cmap);
    … …  
    324326  };
    325327
    326   /// \ingroup _graphbits
    327   ///
    328   /// \brief Extender for the Graphs
     328  // \ingroup _graphbits
     329  //
     330  // \brief Extender for the Graphs
    329331  template <typename Base>
    330332  class GraphExtender : public Base {
    … …  
    554556    };
    555557
    556     /// \brief Base node of the iterator
    557     ///
    558     /// Returns the base node (ie. the source in this case) of the iterator
     558    // \brief Base node of the iterator
     559    //
     560    // Returns the base node (ie. the source in this case) of the iterator
    559561    Node baseNode(const OutArcIt &arc) const {
    560562      return Parent::source(static_cast<const Arc&>(arc));
    561563    }
    562     /// \brief Running node of the iterator
    563     ///
    564     /// Returns the running node (ie. the target in this case) of the
    565     /// iterator
     564    // \brief Running node of the iterator
     565    //
     566    // Returns the running node (ie. the target in this case) of the
     567    // iterator
    566568    Node runningNode(const OutArcIt &arc) const {
    567569      return Parent::target(static_cast<const Arc&>(arc));
    568570    }
    569571
    570     /// \brief Base node of the iterator
    571     ///
    572     /// Returns the base node (ie. the target in this case) of the iterator
     572    // \brief Base node of the iterator
     573    //
     574    // Returns the base node (ie. the target in this case) of the iterator
    573575    Node baseNode(const InArcIt &arc) const {
    574576      return Parent::target(static_cast<const Arc&>(arc));
    575577    }
    576     /// \brief Running node of the iterator
    577     ///
    578     /// Returns the running node (ie. the source in this case) of the
    579     /// iterator
     578    // \brief Running node of the iterator
     579    //
     580    // Returns the running node (ie. the source in this case) of the
     581    // iterator
    580582    Node runningNode(const InArcIt &arc) const {
    581583      return Parent::source(static_cast<const Arc&>(arc));
    582584    }
    583585
    584     /// Base node of the iterator
    585     ///
    586     /// Returns the base node of the iterator
     586    // Base node of the iterator
     587    //
     588    // Returns the base node of the iterator
    587589    Node baseNode(const IncEdgeIt &edge) const {
    588590      return edge._direction ? u(edge) : v(edge);
    589591    }
    590     /// Running node of the iterator
    591     ///
    592     /// Returns the running node of the iterator
     592    // Running node of the iterator
     593    //
     594    // Returns the running node of the iterator
    593595    Node runningNode(const IncEdgeIt &edge) const {
    594596      return edge._direction ? v(edge) : u(edge);
    … …  
    609611        : Parent(graph, value) {}
    610612
     613    private:
    611614      NodeMap& operator=(const NodeMap& cmap) {
    612615        return operator=<NodeMap>(cmap);
    … …  
    633636        : Parent(graph, value) {}
    634637
     638    private:
    635639      ArcMap& operator=(const ArcMap& cmap) {
    636640        return operator=<ArcMap>(cmap);
    … …  
    658662        : Parent(graph, value) {}
    659663
     664    private:
    660665      EdgeMap& operator=(const EdgeMap& cmap) {
    661666        return operator=<EdgeMap>(cmap);

  • lemon/bits/map_extender.h

    r209 r318  
    2727#include <lemon/concepts/maps.h>
    2828
    29 ///\file
    30 ///\brief Extenders for iterable maps.
     29//\file
     30//\brief Extenders for iterable maps.
    3131
    3232namespace lemon {
    3333
    34   /// \ingroup graphbits
    35   ///
    36   /// \brief Extender for maps
     34  // \ingroup graphbits
     35  //
     36  // \brief Extender for maps
    3737  template <typename _Map>
    3838  class MapExtender : public _Map {
    … …  
    6363      : Parent(graph, value) {}
    6464
     65  private:
    6566    MapExtender& operator=(const MapExtender& cmap) {
    6667      return operator=<MapExtender>(cmap);
    … …  
    7374    }
    7475
     76  public:
    7577    class MapIt : public Item {
    7678    public:
    … …  
    170172  };
    171173
    172   /// \ingroup graphbits
    173   ///
    174   /// \brief Extender for maps which use a subset of the items.
     174  // \ingroup graphbits
     175  //
     176  // \brief Extender for maps which use a subset of the items.
    175177  template <typename _Graph, typename _Map>
    176178  class SubMapExtender : public _Map {
    … …  
    201203      : Parent(_graph, _value), graph(_graph) {}
    202204
     205  private:
    203206    SubMapExtender& operator=(const SubMapExtender& cmap) {
    204207      return operator=<MapExtender>(cmap);
    … …  
    215218    }
    216219
     220  public:
    217221    class MapIt : public Item {
    218222    public:

  • lemon/bits/traits.h

    r220 r318  
    2020#define LEMON_BITS_TRAITS_H
    2121
    22 ///\file
    23 ///\brief Traits for graphs and maps
    24 ///
     22//\file
     23//\brief Traits for graphs and maps
     24//
    2525
    2626#include <lemon/bits/enable_if.h>

  • lemon/bits/vector_map.h

    r220 r318  
    2929#include <lemon/concepts/maps.h>
    3030
    31 ///\ingroup graphbits
    32 ///
    33 ///\file
    34 ///\brief Vector based graph maps.
     31//\ingroup graphbits
     32//
     33//\file
     34//\brief Vector based graph maps.
    3535namespace lemon {
    3636
    37   /// \ingroup graphbits
    38   ///
    39   /// \brief Graph map based on the std::vector storage.
    40   ///
    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.
    44   ///
    45   /// \tparam _Notifier The AlterationNotifier that will notify this map.
    46   /// \tparam _Item The item type of the graph items.
    47   /// \tparam _Value The value type of the map.
    48   /// \todo Fix the doc: there is _Graph parameter instead of _Notifier.
     37  // \ingroup graphbits
     38  //
     39  // \brief Graph map based on the std::vector storage.
     40  //
     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.
     44  //
     45  // \tparam _Graph The graph this map is attached to.
     46  // \tparam _Item The item type of the graph items.
     47  // \tparam _Value The value type of the map.
    4948  template <typename _Graph, typename _Item, typename _Value>
    5049  class VectorMap
    … …  
    5251  private:
    5352
    54     /// The container type of the map.
     53    // The container type of the map.
    5554    typedef std::vector<_Value> Container;
    5655
    5756  public:
    5857
    59     /// The graph type of the map.
     58    // The graph type of the map.
    6059    typedef _Graph Graph;
    61     /// The item type of the map.
     60    // The item type of the map.
    6261    typedef _Item Item;
    63     /// The reference map tag.
     62    // The reference map tag.
    6463    typedef True ReferenceMapTag;
    6564
    66     /// The key type of the map.
     65    // The key type of the map.
    6766    typedef _Item Key;
    68     /// The value type of the map.
     67    // The value type of the map.
    6968    typedef _Value Value;
    7069
    71     /// The notifier type.
     70    // The notifier type.
    7271    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    7372
    74     /// The map type.
     73    // The map type.
    7574    typedef VectorMap Map;
    76     /// The base class of the map.
     75    // The base class of the map.
    7776    typedef typename Notifier::ObserverBase Parent;
    7877
    79     /// The reference type of the map;
     78    // The reference type of the map;
    8079    typedef typename Container::reference Reference;
    81     /// The const reference type of the map;
     80    // The const reference type of the map;
    8281    typedef typename Container::const_reference ConstReference;
    8382
    8483
    85     /// \brief Constructor to attach the new map into the notifier.
    86     ///
    87     /// It constructs a map and attachs it into the notifier.
    88     /// It adds all the items of the graph to the map.
     84    // \brief Constructor to attach the new map into the notifier.
     85    //
     86    // It constructs a map and attachs it into the notifier.
     87    // It adds all the items of the graph to the map.
    8988    VectorMap(const Graph& graph) {
    9089      Parent::attach(graph.notifier(Item()));
    … …  
    9291    }
    9392
    94     /// \brief Constructor uses given value to initialize the map.
    95     ///
    96     /// It constructs a map uses a given value to initialize the map.
    97     /// It adds all the items of the graph to the map.
     93    // \brief Constructor uses given value to initialize the map.
     94    //
     95    // It constructs a map uses a given value to initialize the map.
     96    // It adds all the items of the graph to the map.
    9897    VectorMap(const Graph& graph, const Value& value) {
    9998      Parent::attach(graph.notifier(Item()));
    … …  
    101100    }
    102101
    103     /// \brief Copy constructor
    104     ///
    105     /// Copy constructor.
     102  private:
     103    // \brief Copy constructor
     104    //
     105    // Copy constructor.
    106106    VectorMap(const VectorMap& _copy) : Parent() {
    107107      if (_copy.attached()) {
    … …  
    111111    }
    112112
    113     /// \brief Assign operator.
    114     ///
    115     /// This operator assigns for each item in the map the
    116     /// value mapped to the same item in the copied map.
    117     /// The parameter map should be indiced with the same
    118     /// itemset because this assign operator does not change
    119     /// the container of the map.
     113    // \brief Assign operator.
     114    //
     115    // This operator assigns for each item in the map the
     116    // value mapped to the same item in the copied map.
     117    // The parameter map should be indiced with the same
     118    // itemset because this assign operator does not change
     119    // the container of the map.
    120120    VectorMap& operator=(const VectorMap& cmap) {
    121121      return operator=<VectorMap>(cmap);
    … …  
    123123
    124124
    125     /// \brief Template assign operator.
    126     ///
    127     /// The given parameter should be conform to the ReadMap
    128     /// concecpt and could be indiced by the current item set of
    129     /// the NodeMap. In this case the value for each item
    130     /// is assigned by the value of the given ReadMap.
     125    // \brief Template assign operator.
     126    //
     127    // The given parameter should be conform to the ReadMap
     128    // concecpt and could be indiced by the current item set of
     129    // the NodeMap. In this case the value for each item
     130    // is assigned by the value of the given ReadMap.
    131131    template <typename CMap>
    132132    VectorMap& operator=(const CMap& cmap) {
    … …  
    142142  public:
    143143
    144     /// \brief The subcript operator.
    145     ///
    146     /// The subscript operator. The map can be subscripted by the
    147     /// actual items of the graph.
     144    // \brief The subcript operator.
     145    //
     146    // The subscript operator. The map can be subscripted by the
     147    // actual items of the graph.
    148148    Reference operator[](const Key& key) {
    149149      return container[Parent::notifier()->id(key)];
    150150    }
    151151
    152     /// \brief The const subcript operator.
    153     ///
    154     /// The const subscript operator. The map can be subscripted by the
    155     /// actual items of the graph.
     152    // \brief The const subcript operator.
     153    //
     154    // The const subscript operator. The map can be subscripted by the
     155    // actual items of the graph.
    156156    ConstReference operator[](const Key& key) const {
    157157      return container[Parent::notifier()->id(key)];
    … …  
    159159
    160160
    161     /// \brief The setter function of the map.
    162     ///
    163     /// It the same as operator[](key) = value expression.
     161    // \brief The setter function of the map.
     162    //
     163    // It the same as operator[](key) = value expression.
    164164    void set(const Key& key, const Value& value) {
    165165      (*this)[key] = value;
    … …  
    168168  protected:
    169169
    170     /// \brief Adds a new key to the map.
    171     ///
    172     /// It adds a new key to the map. It called by the observer notifier
    173     /// and it overrides the add() member function of the observer base.
     170    // \brief Adds a new key to the map.
     171    //
     172    // It adds a new key to the map. It called by the observer notifier
     173    // and it overrides the add() member function of the observer base.
    174174    virtual void add(const Key& key) {
    175175      int id = Parent::notifier()->id(key);
    … …  
    179179    }
    180180
    181     /// \brief Adds more new keys to the map.
    182     ///
    183     /// It adds more new keys to the map. It called by the observer notifier
    184     /// and it overrides the add() member function of the observer base.
     181    // \brief Adds more new keys to the map.
     182    //
     183    // It adds more new keys to the map. It called by the observer notifier
     184    // and it overrides the add() member function of the observer base.
    185185    virtual void add(const std::vector<Key>& keys) {
    186186      int max = container.size() - 1;
    … …  
    194194    }
    195195
    196     /// \brief Erase a key from the map.
    197     ///
    198     /// Erase a key from the map. It called by the observer notifier
    199     /// and it overrides the erase() member function of the observer base.
     196    // \brief Erase a key from the map.
     197    //
     198    // Erase a key from the map. It called by the observer notifier
     199    // and it overrides the erase() member function of the observer base.
    200200    virtual void erase(const Key& key) {
    201201      container[Parent::notifier()->id(key)] = Value();
    202202    }
    203203
    204     /// \brief Erase more keys from the map.
    205     ///
    206     /// Erase more keys from the map. It called by the observer notifier
    207     /// and it overrides the erase() member function of the observer base.
     204    // \brief Erase more keys from the map.
     205    //
     206    // Erase more keys from the map. It called by the observer notifier
     207    // and it overrides the erase() member function of the observer base.
    208208    virtual void erase(const std::vector<Key>& keys) {
    209209      for (int i = 0; i < int(keys.size()); ++i) {
    … …  
    212212    }
    213213
    214     /// \brief Buildes the map.
    215     ///
    216     /// It buildes the map. It called by the observer notifier
    217     /// and it overrides the build() member function of the observer base.
     214    // \brief Buildes the map.
     215    //
     216    // It buildes the map. It called by the observer notifier
     217    // and it overrides the build() member function of the observer base.
    218218    virtual void build() {
    219219      int size = Parent::notifier()->maxId() + 1;
    … …  
    222222    }
    223223
    224     /// \brief Clear the map.
    225     ///
    226     /// It erase all items from the map. It called by the observer notifier
    227     /// and it overrides the clear() member function of the observer base.
     224    // \brief Clear the map.
     225    //
     226    // It erase all items from the map. It called by the observer notifier
     227    // and it overrides the clear() member function of the observer base.
    228228    virtual void clear() {
    229229      container.clear();

  • lemon/color.h

    r209 r317  
    9393  extern const Color DARK_CYAN;
    9494
    95   ///Map <tt>int</tt>s to different \ref Color "Color"s
     95  ///Map <tt>int</tt>s to different <tt>Color</tt>s
    9696
    9797  ///This map assigns one of the predefined \ref Color "Color"s to

  • lemon/concept_check.h

    r209 r285  
    1717 */
    1818
    19 // This file contains a modified version of the concept checking
    20 // utility from BOOST.
    21 // See the appropriate copyright notice below.
    22 
    23 // (C) Copyright Jeremy Siek 2000.
    24 // Distributed under the Boost Software License, Version 1.0. (See
    25 // accompanying file LICENSE_1_0.txt or copy at
    26 // http://www.boost.org/LICENSE_1_0.txt)
    27 //
    28 // Revision History:
    29 //   05 May   2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
    30 //   02 April 2001: Removed limits header altogether. (Jeremy Siek)
    31 //   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
    32 //
    33 
    34 // See http://www.boost.org/libs/concept_check for documentation.
     19// The contents of this file was inspired by the concept checking
     20// utility of the BOOST library (http://www.boost.org).
    3521
    3622///\file
    3723///\brief Basic utilities for concept checking.
    3824///
    39 ///\todo Are we still using BOOST concept checking utility?
    40 ///Is the BOOST copyright notice necessary?
    4125
    4226#ifndef LEMON_CONCEPT_CHECK_H

  • lemon/concepts/digraph.h

    r220 r263  
    435435        NodeMap(const Digraph&, T) { }
    436436
     437      private:
    437438        ///Copy constructor
    438439        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
    … …  
    457458        ///\e
    458459        ArcMap(const Digraph&, T) { }
     460      private:
    459461        ///Copy constructor
    460462        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }

  • lemon/concepts/graph.h

    r220 r263  
    513513        NodeMap(const Graph&, T) { }
    514514
     515      private:
    515516        ///Copy constructor
    516517        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
    … …  
    536537        ///\e
    537538        ArcMap(const Graph&, T) { }
     539      private:
    538540        ///Copy constructor
    539541        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
    … …  
    559561        ///\e
    560562        EdgeMap(const Graph&, T) { }
     563      private:
    561564        ///Copy constructor
    562565        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}

  • lemon/concepts/graph_components.h

    r220 r317  
    983983    ///
    984984    /// This class describes the common interface of the graph maps
    985     /// (NodeMap, ArcMap), that is \ref maps-page "maps" which can be used to
     985    /// (NodeMap, ArcMap), that is maps that can be used to
    986986    /// associate data to graph descriptors (nodes or arcs).
    987987    template <typename _Graph, typename _Item, typename _Value>
    … …  
    10061006      /// Construct a new map for the graph and initalise the values.
    10071007      GraphMap(const Graph&, const Value&) {}
     1008
     1009    private:
    10081010      /// \brief Copy constructor.
    10091011      ///
    … …  
    10221024      }
    10231025
     1026    public:
    10241027      template<typename _Map>
    10251028      struct Constraints {
    … …  
    10311034          _Map a2(g,t);
    10321035          // Copy constructor.
    1033           _Map b(c);
    1034 
    1035           ReadMap<Key, Value> cmap;
    1036           b = cmap;
    1037 
     1036          // _Map b(c);
     1037
     1038          // ReadMap<Key, Value> cmap;
     1039          // b = cmap;
     1040
     1041          ignore_unused_variable_warning(a);
    10381042          ignore_unused_variable_warning(a2);
    1039           ignore_unused_variable_warning(b);
     1043          // ignore_unused_variable_warning(b);
    10401044        }
    10411045
    … …  
    10831087          : Parent(digraph, value) {}
    10841088
     1089      private:
    10851090        /// \brief Copy constructor.
    10861091        ///
    … …  
    11201125          : Parent(digraph, value) {}
    11211126
     1127      private:
    11221128        /// \brief Copy constructor.
    11231129        ///
    … …  
    12161222          : Parent(graph, value) {}
    12171223
     1224      private:
    12181225        /// \brief Copy constructor.
    12191226        ///

  • lemon/concepts/heap.h

    r220 r290  
    130130      /// Otherwise it inserts the given item with the given priority.
    131131      ///
    132       /// It may throw an \ref UnderflowPriorityException.
    133132      /// \param i The item.
    134133      /// \param p The priority.

  • lemon/concepts/maps.h

    r220 r318  
    2323#include <lemon/concept_check.h>
    2424
    25 ///\ingroup concept
     25///\ingroup map_concepts
    2626///\file
    2727///\brief The concept of maps.
    … …  
    3131  namespace concepts {
    3232
    33     /// \addtogroup concept
     33    /// \addtogroup map_concepts
    3434    /// @{
    3535

  • lemon/concepts/path.h

    r220 r281  
    2121///\brief Classes for representing paths in digraphs.
    2222///
    23 ///\todo Iterators have obsolete style
    2423
    2524#ifndef LEMON_CONCEPT_PATH_H
    … …  
    6766      /// \brief Template assigment
    6867      template <typename CPath>
    69       Path& operator=(const CPath& cpath) {}
     68      Path& operator=(const CPath& cpath) {
     69        ignore_unused_variable_warning(cpath);
     70        return *this;
     71      }
    7072
    7173      /// Length of the path ie. the number of arcs in the path.
    … …  
    7880      void clear() {}
    7981
    80       /// \brief Lemon style iterator for path arcs
     82      /// \brief LEMON style iterator for path arcs
    8183      ///
    8284      /// This class is used to iterate on the arcs of the paths.
    … …  
    201203    /// If we would like to give back a real path from these
    202204    /// algorithms then we should create a temporarly path object. In
    203     /// Lemon such algorithms gives back a path dumper what can
     205    /// LEMON such algorithms gives back a path dumper what can
    204206    /// assigned to a real path and the dumpers can be implemented as
    205207    /// an adaptor class to the predecessor map.
    … …  
    233235      typedef False RevPathTag;
    234236
    235       /// \brief Lemon style iterator for path arcs
     237      /// \brief LEMON style iterator for path arcs
    236238      ///
    237239      /// This class is used to iterate on the arcs of the paths.
    … …  
    260262      };
    261263
    262       /// \brief Lemon style iterator for path arcs
     264      /// \brief LEMON style iterator for path arcs
    263265      ///
    264266      /// This class is used to iterate on the arcs of the paths in

  • lemon/core.h

    r220 r327  
    2525#include <lemon/bits/enable_if.h>
    2626#include <lemon/bits/traits.h>
     27#include <lemon/assert.h>
    2728
    2829///\file
    2930///\brief LEMON core utilities.
     31///
     32///This header file contains core utilities for LEMON.
     33///It is automatically included by all graph types, therefore it usually
     34///do not have to be included directly.
    3035
    3136namespace lemon {
    … …  
    5560  /// @{
    5661
    57   ///Creates convenience typedefs for the digraph types and iterators
    58 
    59   ///This \c \#define creates convenience typedefs for the following types
    60   ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
     62  ///Create convenience typedefs for the digraph types and iterators
     63
     64  ///This \c \#define creates convenient type definitions for the following
     65  ///types of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
    6166  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
    6267  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
    … …  
    7984  typedef Digraph::ArcMap<double> DoubleArcMap
    8085
    81   ///Creates convenience typedefs for the digraph types and iterators
     86  ///Create convenience typedefs for the digraph types and iterators
    8287
    8388  ///\see DIGRAPH_TYPEDEFS
    … …  
    99104  typedef typename Digraph::template ArcMap<double> DoubleArcMap
    100105
    101   ///Creates convenience typedefs for the graph types and iterators
    102 
    103   ///This \c \#define creates the same convenience typedefs as defined
     106  ///Create convenience typedefs for the graph types and iterators
     107
     108  ///This \c \#define creates the same convenient type definitions as defined
    104109  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
    105110  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
    … …  
    107112  ///
    108113  ///\note If the graph type is a dependent type, ie. the graph type depend
    109   ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
     114  ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
    110115  ///macro.
    111116#define GRAPH_TYPEDEFS(Graph)                                           \
    … …  
    118123  typedef Graph::EdgeMap<double> DoubleEdgeMap
    119124
    120   ///Creates convenience typedefs for the graph types and iterators
     125  ///Create convenience typedefs for the graph types and iterators
    121126
    122127  ///\see GRAPH_TYPEDEFS
    … …  
    133138  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
    134139
    135   /// \brief Function to count the items in the graph.
    136   ///
    137   /// This function counts the items (nodes, arcs etc) in the graph.
    138   /// The complexity of the function is O(n) because
     140  /// \brief Function to count the items in a graph.
     141  ///
     142  /// This function counts the items (nodes, arcs etc.) in a graph.
     143  /// The complexity of the function is linear because
    139144  /// it iterates on all of the items.
    140145  template <typename Graph, typename Item>
    … …  
    173178  ///
    174179  /// This function counts the nodes in the graph.
    175   /// The complexity of the function is O(n) but for some
    176   /// graph structures it is specialized to run in O(1).
    177   ///
    178   /// If the graph contains a \e nodeNum() member function and a
    179   /// \e NodeNumTag tag then this function calls directly the member
     180  /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
     181  /// graph structures it is specialized to run in <em>O</em>(1).
     182  ///
     183  /// \note If the graph contains a \c nodeNum() member function and a
     184  /// \c NodeNumTag tag then this function calls directly the member
    180185  /// function to query the cardinality of the node set.
    181186  template <typename Graph>
    … …  
    209214  ///
    210215  /// This function counts the arcs in the graph.
    211   /// The complexity of the function is O(e) but for some
    212   /// graph structures it is specialized to run in O(1).
    213   ///
    214   /// If the graph contains a \e arcNum() member function and a
    215   /// \e EdgeNumTag tag then this function calls directly the member
     216  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
     217  /// graph structures it is specialized to run in <em>O</em>(1).
     218  ///
     219  /// \note If the graph contains a \c arcNum() member function and a
     220  /// \c ArcNumTag tag then this function calls directly the member
    216221  /// function to query the cardinality of the arc set.
    217222  template <typename Graph>
    … …  
    221226
    222227  // Edge counting:
     228
    223229  namespace _core_bits {
    224230
    … …  
    244250  ///