Index: .hgignore
===================================================================
--- .hgignore (revision 155)
+++ .hgignore (revision 298)
@@ -30,5 +30,7 @@
syntax: regexp
(.*/)?\#[^/]*\#$
+(.*/)?\.\#[^/]*$
^doc/html/.*
+^doc/.*\.tag
^autom4te.cache/.*
^build-aux/.*
Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt (revision 141)
+++ CMakeLists.txt (revision 274)
@@ -1,5 +1,89 @@
-project (LEMON)
-enable_testing ()
-add_subdirectory (lemon)
-add_subdirectory (demo)
-add_subdirectory (test)
+CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
+
+SET(PROJECT_NAME "LEMON")
+SET(PROJECT_VERSION "hg-tip" CACHE STRING "The version string.")
+
+PROJECT(${PROJECT_NAME})
+
+SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
+
+INCLUDE(FindDoxygen)
+INCLUDE(FindGhostscript)
+
+ENABLE_TESTING()
+
+ADD_SUBDIRECTORY(lemon)
+ADD_SUBDIRECTORY(demo)
+ADD_SUBDIRECTORY(doc)
+ADD_SUBDIRECTORY(test)
+
+IF(WIN32)
+ INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico
+ DESTINATION bin)
+ENDIF(WIN32)
+
+IF(WIN32)
+ SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
+ SET(CPACK_PACKAGE_VENDOR
+ "EGRES - Egervary Research Group on Combinatorial Optimization")
+ SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
+ "LEMON - Library of Efficient Models and Optimization in Networks")
+ SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
+
+ SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
+
+ SET(CPACK_PACKAGE_INSTALL_DIRECTORY
+ "${PROJECT_NAME} ${PROJECT_VERSION}")
+ SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
+ "${PROJECT_NAME} ${PROJECT_VERSION}")
+
+ # Variables to generate a component-based installer.
+ #SET(CPACK_COMPONENTS_ALL headers library html_documentation)
+
+ #SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
+ #SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Static library")
+ #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
+
+ #SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
+ # "C++ header files for use with the LEMON library")
+ #SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
+ # "Static library used to build programs with LEMON")
+ #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
+ # "Doxygen generated documentation")
+
+ #SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
+
+ #SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
+ #SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
+ #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
+
+ #SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
+ # "Components needed to develop software using LEMON")
+ #SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
+ # "Documentation of LEMON")
+
+ #SET(CPACK_ALL_INSTALL_TYPES Full Developer)
+
+ #SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
+ #SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
+ #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
+
+ SET(CPACK_GENERATOR "NSIS")
+ SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
+ SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
+ #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
+ SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
+ SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
+ SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
+ SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
+ SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
+ SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
+ CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\"
+ ")
+ SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
+ !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
+ Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
+ ")
+
+ INCLUDE(CPack)
+ENDIF(WIN32)
Index: INSTALL
===================================================================
--- INSTALL (revision 5)
+++ INSTALL (revision 325)
@@ -2,47 +2,60 @@
=========================
- Since you are reading this I assume you already obtained one of the release
+Since you are reading this I assume you already obtained one of the release
tarballs and successfully extracted it. The latest version of LEMON is
-available at our webpage (http://lemon.cs.elte.hu/).
+available at our web page (http://lemon.cs.elte.hu/).
- In order to install LEMON from the extracted source tarball you have to
+In order to install LEMON from the extracted source tarball you have to
issue the following commands:
- 1. `cd lemon-x.y.z'
+ 1. `cd lemon-x.y.z'
- This changes to the directory which was created when you extracted the
- sources. The x.y.z part is a version number.
+ This command changes to the directory which was created when you
+ extracted the sources. The x.y.z part is a version number.
- 2. `./configure'
+ 2. `./configure'
- This runs the configure shell script, which does some checks and
- configuration (creates makefiles etc).
+ This command runs the configure shell script, which does some checks and
+ creates the makefiles.
- 3. `make'
+ 3. `make'
- This command compiles the non-template part of LEMON into libemon.a file.
- It also compiles the benchmark and demo programs when enabled.
+ This command compiles the non-template part of LEMON into libemon.a
+ file. It also compiles the programs in the tools and demo subdirectories
+ when enabled.
- 4. `make check'
+ 4. `make check'
- This step is optional, but recommended. It runs the test programs that we
- developed for LEMON to check whether the library works properly on your
- platform.
+ This step is optional, but recommended. It runs the test programs that
+ we developed for LEMON to check whether the library works properly on
+ your platform.
- 5. `make install'
+ 5. `make install'
- This command installs LEMON under /usr/local (you will need root
- privileges to be able to do that). If you want to install it to some
- other location, then pass the --prefix=DIRECTORY flag to configure in
- step 1. For example: `./configure --prefix=/home/username/lemon'
+ This command installs LEMON under /usr/local (you will need root
+ privileges to be able to do that). If you want to install it to some
+ other location, then pass the --prefix=DIRECTORY flag to configure in
+ step 2. For example: `./configure --prefix=/home/username/lemon'.
+
+ 6. `make install-html'
+
+ This command installs the documentation under share/doc/lemon/docs. The
+ generated documentation is included in the tarball. If you want to
+ generate it yourself, then run `make html'. Note that for this you need
+ to have the following programs installed: Doxygen, Graphviz, Ghostscript,
+ Latex.
-Configure Flags
-===============
+Configure Options and Variables
+===============================
- You can pass the following flags to configure in step 1
-(see ./configure --help for more):
+In step 2 you can customize the actions of configure by setting variables
+and passing options to it. This can be done like this:
+`./configure [OPTION]... [VARIABLE=VALUE]...'
-CXX=comp
+Below you will find some useful variables and options (see `./configure --help'
+for more):
+
+CXX='comp'
Change the C++ compiler to 'comp'.
@@ -50,24 +63,26 @@
CXXFLAGS='flags'
- Pass the 'flags' to the compiler. For example
- CXXFLAGS='-O3 -march=pentium-m'
- turns on generation of aggressively optimized
- Pentium-M specific code.
+ Pass the 'flags' to the compiler. For example CXXFLAGS='-O3 -march=pentium-m'
+ turns on generation of aggressively optimized Pentium-M specific code.
+
+--prefix=PREFIX
+
+ Set the installation prefix to PREFIX. By default it is /usr/local.
--enable-demo
- Build the demo programs too.
+ Build the examples in the demo subdirectory.
--disable-demo
- Do not build the demo programs (default).
+ Do not build the examples in the demo subdirectory (default).
---enable-benchmark
+--enable-tools
- Build the benchmark programs too.
+ Build the programs in the tools subdirectory (default).
---disable-benchmark
+--disable-tools
- Do not build the benchmark programs (default).
+ Do not build the programs in the tools subdirectory.
--with-glpk[=PREFIX]
@@ -116,2 +131,24 @@
Disable CPLEX support.
+
+--with-soplex[=PREFIX]
+
+ Enable SoPlex support (default). You should specify the prefix too if
+ you installed SoPlex to some non-standard location (e.g. your home
+ directory). If it is not found, SoPlex support will be disabled.
+
+--with-soplex-includedir=DIR
+
+ The directory where the SoPlex header files are located. This is only
+ useful when the SoPlex headers and libraries are not under the same
+ prefix (which is unlikely).
+
+--with-soplex-libdir=DIR
+
+ The directory where the SoPlex libraries are located. This is only
+ useful when the SoPlex headers and libraries are not under the same
+ prefix (which is unlikely).
+
+--without-soplex
+
+ Disable SoPlex support.
Index: Makefile.am
===================================================================
--- Makefile.am (revision 330)
+++ Makefile.am (revision 331)
@@ -10,5 +10,6 @@
m4/lx_check_glpk.m4 \
m4/lx_check_soplex.m4 \
- CMakeLists.txt
+ CMakeLists.txt \
+ cmake
pkgconfigdir = $(libdir)/pkgconfig
@@ -25,4 +26,5 @@
bin_PROGRAMS =
check_PROGRAMS =
+dist_bin_SCRIPTS =
TESTS =
XFAIL_TESTS =
@@ -32,5 +34,4 @@
include doc/Makefile.am
include demo/Makefile.am
-include benchmark/Makefile.am
include tools/Makefile.am
Index: NEWS
===================================================================
--- NEWS (revision 5)
+++ NEWS (revision 262)
@@ -0,0 +1,49 @@
+20XX-XX-XX Version 1.0 released
+
+ This is the first stable release of LEMON. Compared to the 0.x
+ release series, it features a considerably smaller but more
+ matured set of tools. The API has also completely revised and
+ changed in several places.
+
+ * The major name changes compared to the 0.x series
+ * Graph -> Digraph, UGraph -> Graph
+ * Edge -> Arc, UEdge -> Edge
+ * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
+ * Other improvements
+ * Better documentation
+ * Reviewed and cleaned up codebase
+ * CMake based build system (along with the autotools based one)
+ * Contents of the library (ported from 0.x)
+ * Algorithms
+ * breadth-first search (bfs.h)
+ * depth-first search (dfs.h)
+ * Dijkstra's algorithm (dijkstra.h)
+ * Kruskal's algorithm (kruskal.h)
+ * Data structures
+ * graph data structures (list_graph.h, smart_graph.h)
+ * path data structures (path.h)
+ * binary heap data structure (bin_heap.h)
+ * union-find data structures (unionfind.h)
+ * miscellaneous property maps (maps.h)
+ * two dimensional vector and bounding box (dim2.h)
+ * Concepts
+ * graph structure concepts (concepts/digraph.h, concepts/graph.h,
+ concepts/graph_components.h)
+ * concepts for other structures (concepts/heap.h, concepts/maps.h,
+ concepts/path.h)
+ * Tools
+ * Mersenne twister random number generator (random.h)
+ * tools for measuring cpu and wall clock time (time_measure.h)
+ * tools for counting steps and events (counter.h)
+ * tool for parsing command line arguments (arg_parser.h)
+ * tool for visualizing graphs (graph_to_eps.h)
+ * tools for reading and writing data in LEMON Graph Format
+ (lgf_reader.h, lgf_writer.h)
+ * tools to handle the anomalies of calculations with
+ floating point numbers (tolerance.h)
+ * tools to manage RGB colors (color.h)
+ * Infrastructure
+ * extended assertion handling (assert.h)
+ * exception classes and error handling (error.h)
+ * concept checking (concept_check.h)
+ * commonly used mathematical constants (math.h)
Index: README
===================================================================
--- README (revision 24)
+++ README (revision 325)
@@ -1,60 +1,42 @@
-------------------------------------------------------------------
+==================================================================
LEMON - a Library of Efficient Models and Optimization in Networks
-------------------------------------------------------------------
+==================================================================
-LEMON is the abbreviation of Library of Efficient Models and
-Optimization in Networks. It is an open source library written in
-C++. It provides a set of easy-to-use implementation of common data
-structures and algorithms in the area of optimization and helps
-implementing new ones. It is an especially suitable tool to solve the
-design and optimization problems of telecommunications networks. To
-achieve wide usability, a fundamental design requirement is the
-genericity of interface of data structures and algorithms. LEMON is an
-open source library end invites people all around the world in its
-development.
+LEMON is an open source library written in C++. It provides
+easy-to-use implementations of common data structures and algorithms
+in the area of optimization and helps implementing new ones. The main
+focus is on graphs and graph algorithms, thus it is especially
+suitable for solving design and optimization problems of
+telecommunication networks. To achieve wide usability its data
+structures and algorithms provide generic interfaces.
---------
Contents
---------
+========
-COPYING, LICENSE
+LICENSE
- Copying, distribution and modification conditions and terms.
+ Copying, distribution and modification conditions and terms.
INSTALL
- For general building and installation instructions, see the file.
+ General building and installation instructions.
lemon/
- Source code of LEMON itself.
+ Source code of LEMON library.
doc/
- Documentation of LEMON. The starting page is doc/html/index.html.
- The documentation installs into the directory
-
- /usr/local/share/doc/lemon/html
-
- or -- if you use different prefix -- into
-
- ${prefix}/share/doc/lemon/html
-
- (see also INSTALL).
+ Documentation of LEMON. The starting page is doc/html/index.html.
demo/
- Some demonstration programs to make you easier to get familiar with
- LEMON. Use --enable-demo configure option to also compile these codes
- (see also INSTALL).
+ Some example programs to make you easier to get familiar with LEMON.
test/
- Contains programs to check the integrity and correctness of
- LEMON. The command 'make check' performs these tests.
+ Programs to check the integrity and correctness of LEMON.
-benchmark/
-
- Contains programs measuring the performance of LEMON. Use
- --enable-benchmark configure option to also compile these codes (see
- also INSTALL).
+tools/
+
+ Various utilities related to LEMON.
Index: nchmark/Makefile.am
===================================================================
--- benchmark/Makefile.am (revision 146)
+++ (revision )
@@ -1,7 +1,0 @@
-if WANT_BENCHMARK
-
-noinst_HEADERS +=
-
-noinst_PROGRAMS +=
-
-endif WANT_BENCHMARK
Index: cmake/FindGhostscript.cmake
===================================================================
--- cmake/FindGhostscript.cmake (revision 225)
+++ cmake/FindGhostscript.cmake (revision 225)
@@ -0,0 +1,10 @@
+INCLUDE(FindPackageHandleStandardArgs)
+
+FIND_PROGRAM(GHOSTSCRIPT_EXECUTABLE
+ NAMES gs gswin32c
+ PATHS "$ENV{ProgramFiles}/gs"
+ PATH_SUFFIXES gs8.61/bin gs8.62/bin
+ DOC "Ghostscript: PostScript and PDF language interpreter and previewer."
+)
+
+FIND_PACKAGE_HANDLE_STANDARD_ARGS(Ghostscript DEFAULT_MSG GHOSTSCRIPT_EXECUTABLE)
Index: configure.ac
===================================================================
--- configure.ac (revision 219)
+++ configure.ac (revision 314)
@@ -2,10 +2,16 @@
dnl Version information.
-m4_define([lemon_version_number], [])
+m4_define([lemon_version_number],
+ [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
+dnl m4_define([lemon_version_number], [])
+m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
-m4_define([lemon_version], [ifelse(lemon_version_number(), [], [lemon_hg_revision()], [lemon_version_number()])])
+m4_define([lemon_version], [ifelse(lemon_version_number(),
+ [],
+ [lemon_hg_path().lemon_hg_revision()],
+ [lemon_version_number()])])
AC_PREREQ([2.59])
-AC_INIT([LEMON], [lemon_version()], [lemon-devel@lemon.cs.elte.hu], [lemon])
+AC_INIT([LEMON], [lemon_version()], [lemon-user@lemon.cs.elte.hu], [lemon])
AC_CONFIG_AUX_DIR([build-aux])
AC_CONFIG_MACRO_DIR([m4])
@@ -15,4 +21,7 @@
lx_cmdline_cxxflags_set=${CXXFLAGS+set}
+
+dnl Do compilation tests using the C++ compiler.
+AC_LANG([C++])
dnl Checks for programs.
@@ -26,14 +35,26 @@
AC_CHECK_PROG([gs_found],[gs],[yes],[no])
-if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then
+dnl Detect Intel compiler.
+AC_MSG_CHECKING([whether we are using the Intel C++ compiler])
+AC_COMPILE_IFELSE([#ifndef __INTEL_COMPILER
+choke me
+#endif], [ICC=[yes]], [ICC=[no]])
+if test x"$ICC" = x"yes"; then
+ AC_MSG_RESULT([yes])
+else
+ AC_MSG_RESULT([no])
+fi
+
+dnl Set custom compiler flags when using g++.
+if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
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"
fi
dnl Checks for libraries.
-LX_CHECK_GLPK
-LX_CHECK_CPLEX
-LX_CHECK_SOPLEX
+#LX_CHECK_GLPK
+#LX_CHECK_CPLEX
+#LX_CHECK_SOPLEX
-dnl Disable/enable building the demo programs
+dnl Disable/enable building the demo programs.
AC_ARG_ENABLE([demo],
AS_HELP_STRING([--enable-demo], [build the demo programs])
@@ -48,5 +69,5 @@
AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
-dnl Disable/enable building the binary tools
+dnl Disable/enable building the binary tools.
AC_ARG_ENABLE([tools],
AS_HELP_STRING([--enable-tools], [build additional tools @<:@default@:>@])
@@ -60,17 +81,4 @@
fi
AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
-
-dnl Disable/enable building the benchmarks
-AC_ARG_ENABLE([benchmark],
-AS_HELP_STRING([--enable-benchmark], [build the benchmarks])
-AS_HELP_STRING([--disable-benchmark], [do not build the benchmarks @<:@default@:>@]),
- [], [enable_benchmark=no])
-AC_MSG_CHECKING([whether to build the benchmarks])
-if test x"$enable_benchmark" != x"no"; then
- AC_MSG_RESULT([yes])
-else
- AC_MSG_RESULT([no])
-fi
-AM_CONDITIONAL([WANT_BENCHMARK], [test x"$enable_benchmark" != x"no"])
dnl Checks for header files.
@@ -108,9 +116,8 @@
echo C++ compiles flags............ : $CXXFLAGS
echo
-echo GLPK support.................. : $lx_glpk_found
-echo CPLEX support................. : $lx_cplex_found
-echo SOPLEX support................ : $lx_soplex_found
-echo
-echo Build benchmarks.............. : $enable_benchmark
+#echo GLPK support.................. : $lx_glpk_found
+#echo CPLEX support................. : $lx_cplex_found
+#echo SOPLEX support................ : $lx_soplex_found
+#echo
echo Build demo programs........... : $enable_demo
echo Build additional tools........ : $enable_tools
Index: demo/CMakeLists.txt
===================================================================
--- demo/CMakeLists.txt (revision 141)
+++ demo/CMakeLists.txt (revision 225)
@@ -1,13 +1,13 @@
-include_directories (${LEMON_SOURCE_DIR})
+INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
-link_directories (${LEMON_BINARY_DIR}/lemon)
+LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
-set (DEMOS
+SET(DEMOS
arg_parser_demo
graph_to_eps_demo
lgf_demo)
-foreach (DEMO_NAME ${DEMOS})
- add_executable (${DEMO_NAME} ${DEMO_NAME}.cc)
- target_link_libraries (${DEMO_NAME} lemon)
- endforeach (DEMO_NAME)
+FOREACH(DEMO_NAME ${DEMOS})
+ ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc)
+ TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
+ENDFOREACH(DEMO_NAME)
Index: demo/arg_parser_demo.cc
===================================================================
--- demo/arg_parser_demo.cc (revision 209)
+++ demo/arg_parser_demo.cc (revision 315)
@@ -28,5 +28,5 @@
using namespace lemon;
-int main(int argc, const char **argv)
+int main(int argc, char **argv)
{
// Initialize the argument parser
Index: demo/graph_to_eps_demo.cc
===================================================================
--- demo/graph_to_eps_demo.cc (revision 220)
+++ demo/graph_to_eps_demo.cc (revision 317)
@@ -27,5 +27,5 @@
/// how to handle parallel egdes, how to change the properties (like
/// color, shape, size, title etc.) of nodes and arcs individually
-/// using appropriate \ref maps-page "graph maps".
+/// using appropriate graph maps.
///
/// \include graph_to_eps_demo.cc
Index: demo/lgf_demo.cc
===================================================================
--- demo/lgf_demo.cc (revision 209)
+++ demo/lgf_demo.cc (revision 294)
@@ -45,10 +45,10 @@
try {
- digraphReader("digraph.lgf", g). // read the directed graph into g
+ digraphReader(g, "digraph.lgf"). // read the directed graph into g
arcMap("capacity", cap). // read the 'capacity' arc map into cap
node("source", s). // read 'source' node to s
node("target", t). // read 'target' node to t
run();
- } catch (DataFormatError& error) { // check if there was any error
+ } catch (Exception& error) { // check if there was any error
std::cerr << "Error: " << error.what() << std::endl;
return -1;
@@ -61,5 +61,5 @@
std::cout << "We can write it to the standard output:" << std::endl;
- digraphWriter(std::cout, g). // write g to the standard output
+ digraphWriter(g). // write g to the standard output
arcMap("capacity", cap). // write cap into 'capacity'
node("source", s). // write s to 'source'
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt (revision 225)
+++ doc/CMakeLists.txt (revision 225)
@@ -0,0 +1,42 @@
+SET(PACKAGE_NAME ${PROJECT_NAME})
+SET(PACKAGE_VERSION ${PROJECT_VERSION})
+SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
+SET(abs_top_builddir ${CMAKE_BINARY_DIR})
+
+CONFIGURE_FILE(
+ ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
+ ${CMAKE_BINARY_DIR}/doc/Doxyfile
+ @ONLY)
+
+IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
+ IF(UNIX)
+ ADD_CUSTOM_TARGET(html
+ COMMAND rm -rf gen-images
+ COMMAND mkdir gen-images
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+ COMMAND rm -rf html
+ COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
+ WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
+ ELSEIF(WIN32)
+ ADD_CUSTOM_TARGET(html
+ COMMAND if exist gen-images rmdir /s /q gen-images
+ COMMAND mkdir gen-images
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
+ COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+ COMMAND if exist html rmdir /s /q html
+ COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
+ WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
+ ENDIF(UNIX)
+ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
+
+INSTALL(
+ DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
+ DESTINATION doc
+ COMPONENT html_documentation)
Index: doc/Doxyfile.in
===================================================================
--- doc/Doxyfile.in (revision 219)
+++ doc/Doxyfile.in (revision 321)
@@ -1,3 +1,3 @@
-# Doxyfile 1.5.5
+# Doxyfile 1.5.7.1
#---------------------------------------------------------------------------
@@ -16,6 +16,6 @@
INLINE_INHERITED_MEMB = NO
FULL_PATH_NAMES = YES
-STRIP_FROM_PATH = @abs_top_srcdir@
-STRIP_FROM_INC_PATH = @abs_top_srcdir@
+STRIP_FROM_PATH = "@abs_top_srcdir@"
+STRIP_FROM_INC_PATH = "@abs_top_srcdir@"
SHORT_NAMES = YES
JAVADOC_AUTOBRIEF = NO
@@ -34,7 +34,9 @@
CPP_CLI_SUPPORT = NO
SIP_SUPPORT = NO
+IDL_PROPERTY_SUPPORT = YES
DISTRIBUTE_GROUP_DOC = NO
SUBGROUPING = YES
TYPEDEF_HIDES_STRUCT = NO
+SYMBOL_CACHE_SIZE = 0
#---------------------------------------------------------------------------
# Build related configuration options
@@ -67,5 +69,8 @@
SHOW_USED_FILES = YES
SHOW_DIRECTORIES = YES
+SHOW_FILES = YES
+SHOW_NAMESPACES = YES
FILE_VERSION_FILTER =
+LAYOUT_FILE = DoxygenLayout.xml
#---------------------------------------------------------------------------
# configuration options related to warning and progress messages
@@ -76,16 +81,16 @@
WARN_IF_DOC_ERROR = YES
WARN_NO_PARAMDOC = NO
-WARN_FORMAT = "$file:$line: $text "
+WARN_FORMAT = "$file:$line: $text"
WARN_LOGFILE = doxygen.log
#---------------------------------------------------------------------------
# configuration options related to the input files
#---------------------------------------------------------------------------
-INPUT = @abs_top_srcdir@/doc \
- @abs_top_srcdir@/lemon \
- @abs_top_srcdir@/lemon/bits \
- @abs_top_srcdir@/lemon/concepts \
- @abs_top_srcdir@/demo \
- @abs_top_srcdir@/tools \
- @abs_top_srcdir@/test/test_tools.h
+INPUT = "@abs_top_srcdir@/doc" \
+ "@abs_top_srcdir@/lemon" \
+ "@abs_top_srcdir@/lemon/bits" \
+ "@abs_top_srcdir@/lemon/concepts" \
+ "@abs_top_srcdir@/demo" \
+ "@abs_top_srcdir@/tools" \
+ "@abs_top_srcdir@/test/test_tools.h"
INPUT_ENCODING = UTF-8
FILE_PATTERNS = *.h \
@@ -97,11 +102,11 @@
EXCLUDE_PATTERNS =
EXCLUDE_SYMBOLS =
-EXAMPLE_PATH = @abs_top_srcdir@/demo \
- @abs_top_srcdir@/LICENSE \
- @abs_top_srcdir@/doc
+EXAMPLE_PATH = "@abs_top_srcdir@/demo" \
+ "@abs_top_srcdir@/LICENSE" \
+ "@abs_top_srcdir@/doc"
EXAMPLE_PATTERNS =
EXAMPLE_RECURSIVE = NO
-IMAGE_PATH = @abs_top_srcdir@/doc/images \
- @abs_top_builddir@/doc/gen-images
+IMAGE_PATH = "@abs_top_srcdir@/doc/images" \
+ "@abs_top_builddir@/doc/gen-images"
INPUT_FILTER =
FILTER_PATTERNS =
@@ -134,18 +139,25 @@
HTML_STYLESHEET =
HTML_ALIGN_MEMBERS = YES
-GENERATE_HTMLHELP = NO
+HTML_DYNAMIC_SECTIONS = NO
GENERATE_DOCSET = NO
DOCSET_FEEDNAME = "Doxygen generated docs"
DOCSET_BUNDLE_ID = org.doxygen.Project
-HTML_DYNAMIC_SECTIONS = NO
+GENERATE_HTMLHELP = NO
CHM_FILE =
HHC_LOCATION =
GENERATE_CHI = NO
+CHM_INDEX_ENCODING =
BINARY_TOC = NO
TOC_EXPAND = NO
+GENERATE_QHP = NO
+QCH_FILE =
+QHP_NAMESPACE = org.doxygen.Project
+QHP_VIRTUAL_FOLDER = doc
+QHG_LOCATION =
DISABLE_INDEX = NO
ENUM_VALUES_PER_LINE = 4
GENERATE_TREEVIEW = NO
TREEVIEW_WIDTH = 250
+FORMULA_FONTSIZE = 10
#---------------------------------------------------------------------------
# configuration options related to the LaTeX output
@@ -222,8 +234,11 @@
# Configuration options related to the dot tool
#---------------------------------------------------------------------------
-CLASS_DIAGRAMS = NO
+CLASS_DIAGRAMS = YES
MSCGEN_PATH =
HIDE_UNDOC_RELATIONS = YES
HAVE_DOT = YES
+DOT_FONTNAME = FreeSans
+DOT_FONTSIZE = 10
+DOT_FONTPATH =
CLASS_GRAPH = YES
COLLABORATION_GRAPH = NO
Index: doc/DoxygenLayout.xml
===================================================================
--- doc/DoxygenLayout.xml (revision 321)
+++ doc/DoxygenLayout.xml (revision 321)
@@ -0,0 +1,182 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 156)
+++ doc/Makefile.am (revision 322)
@@ -1,4 +1,5 @@
EXTRA_DIST += \
doc/Doxyfile.in \
+ doc/DoxygenLayout.xml \
doc/coding_style.dox \
doc/dirs.dox \
@@ -7,6 +8,9 @@
doc/license.dox \
doc/mainpage.dox \
+ doc/migration.dox \
+ doc/named-param.dox \
doc/namespaces.dox \
- doc/html
+ doc/html \
+ doc/CMakeLists.txt
DOC_EPS_IMAGES18 = \
Index: doc/dirs.dox
===================================================================
--- doc/dirs.dox (revision 209)
+++ doc/dirs.dox (revision 325)
@@ -19,7 +19,7 @@
/**
\dir demo
-\brief A collection of demo application.
+\brief A collection of demo applications.
-This directory contains several simple demo application, mainly
+This directory contains several simple demo applications, mainly
for educational purposes.
*/
@@ -29,5 +29,6 @@
\brief Auxiliary (and the whole generated) documentation.
-Auxiliary (and the whole generated) documentation.
+This directory contains some auxiliary pages and the whole generated
+documentation.
*/
@@ -42,17 +43,14 @@
/**
\dir tools
-\brief Some useful executables
+\brief Some useful executables.
This directory contains the sources of some useful complete executables.
-
*/
-
-
/**
\dir lemon
-\brief Base include directory of LEMON
+\brief Base include directory of LEMON.
-This is the base directory of lemon includes, so each include file must be
+This is the base directory of LEMON includes, so each include file must be
prefixed with this, e.g.
\code
@@ -64,16 +62,16 @@
/**
\dir concepts
-\brief Concept descriptors and checking classes
+\brief Concept descriptors and checking classes.
-This directory contains the concept descriptors and concept checkers. As a user
-you typically don't have to deal with these files.
+This directory contains the concept descriptors and concept checking tools.
+For more information see the \ref concept "Concepts" module.
*/
/**
\dir bits
-\brief Implementation helper files
+\brief Auxiliary tools for implementation.
-This directory contains some helper classes to implement graphs, maps and
-some other classes. As a user you typically don't have to deal with these
-files.
+This directory contains some auxiliary classes for implementing graphs,
+maps and some other classes.
+As a user you typically don't have to deal with these files.
*/
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 210)
+++ doc/groups.dox (revision 325)
@@ -55,5 +55,7 @@
You are free to use the graph structure that fit your requirements
the best, most graph algorithms and auxiliary data structures can be used
-with any graph structures.
+with any graph structure.
+
+See also: \ref graph_concepts "Graph Structure Concepts".
*/
@@ -75,6 +77,8 @@
This group describes the map structures implemented in LEMON.
-LEMON provides several special purpose maps that e.g. combine
+LEMON provides several special purpose maps and map adaptors that e.g. combine
new maps from existing ones.
+
+See also: \ref map_concepts "Map Concepts".
*/
@@ -87,5 +91,4 @@
values to the nodes and arcs of graphs.
*/
-
/**
@@ -105,5 +108,5 @@
algorithms. If a function type algorithm is called then the function
type map adaptors can be used comfortable. For example let's see the
-usage of map adaptors with the \c digraphToEps() function.
+usage of map adaptors with the \c graphToEps() function.
\code
Color nodeColor(int deg) {
@@ -119,5 +122,5 @@
Digraph::NodeMap degree_map(graph);
- digraphToEps(graph, "graph.eps")
+ graphToEps(graph, "graph.eps")
.coords(coords).scaleToA4().undirected()
.nodeColors(composeMap(functorToMap(nodeColor), degree_map))
@@ -125,5 +128,5 @@
\endcode
The \c functorToMap() function makes an \c int to \c Color map from the
-\e nodeColor() function. The \c composeMap() compose the \e degree_map
+\c nodeColor() function. The \c composeMap() compose the \c degree_map
and the previously created map. The composed map is a proper function to
get the color of each node.
@@ -163,5 +166,5 @@
@defgroup paths Path Structures
@ingroup datas
-\brief Path structures implemented in LEMON.
+\brief %Path structures implemented in LEMON.
This group describes the path structures implemented in LEMON.
@@ -174,5 +177,4 @@
\sa lemon::concepts::Path
-
*/
@@ -186,5 +188,4 @@
*/
-
/**
@defgroup algs Algorithms
@@ -202,9 +203,9 @@
This group describes the common graph search algorithms like
-Breadth-first search (Bfs) and Depth-first search (Dfs).
-*/
-
-/**
-@defgroup shortest_path Shortest Path algorithms
+Breadth-First Search (BFS) and Depth-First Search (DFS).
+*/
+
+/**
+@defgroup shortest_path Shortest Path Algorithms
@ingroup algs
\brief Algorithms for finding shortest paths.
@@ -214,5 +215,5 @@
/**
-@defgroup max_flow Maximum Flow algorithms
+@defgroup max_flow Maximum Flow Algorithms
@ingroup algs
\brief Algorithms for finding maximum flows.
@@ -242,9 +243,8 @@
provides functions to query the minimum cut, which is the dual linear
programming problem of the maximum flow.
-
-*/
-
-/**
-@defgroup min_cost_flow Minimum Cost Flow algorithms
+*/
+
+/**
+@defgroup min_cost_flow Minimum Cost Flow Algorithms
@ingroup algs
@@ -256,5 +256,5 @@
/**
-@defgroup min_cut Minimum Cut algorithms
+@defgroup min_cut Minimum Cut Algorithms
@ingroup algs
@@ -283,9 +283,8 @@
If you want to find minimum cut just between two distinict nodes,
please see the \ref max_flow "Maximum Flow page".
-
-*/
-
-/**
-@defgroup graph_prop Connectivity and other graph properties
+*/
+
+/**
+@defgroup graph_prop Connectivity and Other Graph Properties
@ingroup algs
\brief Algorithms for discovering the graph properties
@@ -299,5 +298,5 @@
/**
-@defgroup planar Planarity embedding and drawing
+@defgroup planar Planarity Embedding and Drawing
@ingroup algs
\brief Algorithms for planarity checking, embedding and drawing
@@ -311,5 +310,5 @@
/**
-@defgroup matching Matching algorithms
+@defgroup matching Matching Algorithms
@ingroup algs
\brief Algorithms for finding matchings in graphs and bipartite graphs.
@@ -326,5 +325,5 @@
maximum cardinality matching.
-Lemon contains the next algorithms:
+LEMON contains the next algorithms:
- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
augmenting path algorithm for calculate maximum cardinality matching in
@@ -349,9 +348,8 @@
\image html bipartite_matching.png
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
-
-*/
-
-/**
-@defgroup spantree Minimum Spanning Tree algorithms
+*/
+
+/**
+@defgroup spantree Minimum Spanning Tree Algorithms
@ingroup algs
\brief Algorithms for finding a minimum cost spanning tree in a graph.
@@ -361,7 +359,6 @@
*/
-
-/**
-@defgroup auxalg Auxiliary algorithms
+/**
+@defgroup auxalg Auxiliary Algorithms
@ingroup algs
\brief Auxiliary algorithms implemented in LEMON.
@@ -372,5 +369,6 @@
/**
-@defgroup approx Approximation algorithms
+@defgroup approx Approximation Algorithms
+@ingroup algs
\brief Approximation algorithms.
@@ -386,9 +384,8 @@
This group describes some general optimization frameworks
implemented in LEMON.
-
-*/
-
-/**
-@defgroup lp_group Lp and Mip solvers
+*/
+
+/**
+@defgroup lp_group Lp and Mip Solvers
@ingroup gen_opt_group
\brief Lp and Mip solver interfaces for LEMON.
@@ -397,9 +394,8 @@
various LP solvers could be used in the same manner with this
interface.
-
-*/
-
-/**
-@defgroup lp_utils Tools for Lp and Mip solvers
+*/
+
+/**
+@defgroup lp_utils Tools for Lp and Mip Solvers
@ingroup lp_group
\brief Helper tools to the Lp and Mip solvers.
@@ -442,5 +438,5 @@
/**
-@defgroup timecount Time measuring and Counting
+@defgroup timecount Time Measuring and Counting
@ingroup misc
\brief Simple tools for measuring the performance of algorithms.
@@ -448,13 +444,4 @@
This group describes simple tools for measuring the performance
of algorithms.
-*/
-
-/**
-@defgroup graphbits Tools for Graph Implementation
-@ingroup utils
-\brief Tools to make it easier to create graphs.
-
-This group describes the tools that makes it easier to create graphs and
-the maps that dynamically update with the graph changes.
*/
@@ -472,19 +459,20 @@
This group describes the tools for importing and exporting graphs
-and graph related data. Now it supports the LEMON format, the
-\c DIMACS format and the encapsulated postscript (EPS) format.
-*/
-
-/**
-@defgroup lemon_io Lemon Input-Output
+and graph related data. Now it supports the \ref lgf-format
+"LEMON Graph Format", the \c DIMACS format and the encapsulated
+postscript (EPS) format.
+*/
+
+/**
+@defgroup lemon_io LEMON Input-Output
@ingroup io_group
-\brief Reading and writing \ref lgf-format "Lemon Graph Format".
+\brief Reading and writing LEMON Graph Format.
This group describes methods for reading and writing
-\ref lgf-format "Lemon Graph Format".
-*/
-
-/**
-@defgroup eps_io Postscript exporting
+\ref lgf-format "LEMON Graph Format".
+*/
+
+/**
+@defgroup eps_io Postscript Exporting
@ingroup io_group
\brief General \c EPS drawer and graph exporter
@@ -494,5 +482,4 @@
*/
-
/**
@defgroup concept Concepts
@@ -504,10 +491,10 @@
The purpose of the classes in this group is fourfold.
-- These classes contain the documentations of the concepts. In order
+- These classes contain the documentations of the %concepts. In order
to avoid document multiplications, an implementation of a concept
simply refers to the corresponding concept class.
- These classes declare every functions, typedefs etc. an
- implementation of the concepts should provide, however completely
+ implementation of the %concepts should provide, however completely
without implementations and real data structures behind the
interface. On the other hand they should provide nothing else. All
@@ -522,7 +509,5 @@
- Finally, They can serve as a skeleton of a new implementation of a concept.
-
-*/
-
+*/
/**
@@ -535,8 +520,10 @@
*/
-/* --- Unused group
-@defgroup experimental Experimental Structures and Algorithms
-This group describes some Experimental structures and algorithms.
-The stuff here is subject to change.
+/**
+@defgroup map_concepts Map Concepts
+@ingroup concept
+\brief Skeleton and concept checking classes for maps
+
+This group describes the skeletons and concept checking classes of maps.
*/
Index: doc/lgf.dox
===================================================================
--- doc/lgf.dox (revision 212)
+++ doc/lgf.dox (revision 317)
@@ -22,5 +22,5 @@
-\page lgf-format Lemon Graph Format (LGF)
+\page lgf-format LEMON Graph Format (LGF)
The \e LGF is a column oriented
@@ -79,5 +79,5 @@
\endcode
-The \c \@edges is just a synonym of \c \@arcs. The @arcs section can
+The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
also store the edge set of an undirected graph. In such case there is
a conventional method for store arc maps in the file, if two columns
Index: doc/mainpage.dox
===================================================================
--- doc/mainpage.dox (revision 209)
+++ doc/mainpage.dox (revision 318)
@@ -51,5 +51,5 @@
If you
want to see how LEMON works, see
-some \ref demoprograms "demo programs"!
+some \ref demoprograms "demo programs".
If you know what you are looking for then try to find it under the
@@ -57,4 +57,5 @@
section.
-
+If you are a user of the old (0.x) series of LEMON, please check out the
+\ref migration "Migration Guide" for the backward incompatibilities.
*/
Index: doc/migration.dox
===================================================================
--- doc/migration.dox (revision 318)
+++ doc/migration.dox (revision 318)
@@ -0,0 +1,143 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+namespace lemon {
+/*!
+
+\page migration Migration from the 0.x Series
+
+This guide gives an in depth description on what has changed compared
+to the 0.x release series.
+
+Many of these changes adjusted automatically by the
+script/lemon-0.x-to-1.x.sh tool. Those requiring manual
+update are typeset boldface.
+
+\section migration-graph Graph Related Name Changes
+
+- \ref concepts::Digraph "Directed graphs" are called \c Digraph and
+ they have Arcs (instead of Edges), while
+ \ref concepts::Graph "undirected graphs" are called \c Graph
+ (instead of \c UGraph) and they have Edges (instead of
+ UEdges). These changes reflected thoroughly everywhere in
+ the library. Namely,
+ - \c Graph -> \c Digraph
+ - \c %ListGraph -> \c ListDigraph, \c %SmartGraph -> \c SmartDigraph etc.
+ - \c UGraph -> \c Graph
+ - \c ListUGraph -> \c ListGraph, \c SmartUGraph -> \c SmartGraph etc.
+ - \c Edge -> \c Arc, \c UEdge -> \c Edge
+ - \c EdgeMap -> \c ArcMap, \c UEdgeMap -> \c EdgeMap
+ - \c EdgeIt -> \c ArcIt, \c UEdgeIt -> \c EdgeIt
+ - Class names and function names containing the words \c graph,
+ \c ugraph, \e edge or \e arc should also be updated.
+- The two endpoints of an (\e undirected) \c Edge can be obtained by the
+ u() and v() member function of the graph
+ (instead of source() and target()). This change
+ must be done by hand.
+ \n Of course, you can still use source() and target()
+ for Arcs (directed edges).
+
+\warning
+The script/lemon-0.x-to-1.x.sh tool replaces all instances of
+the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
+in strings, comments etc. as well as in all identifiers.
+
+\section migration-lgf LGF tools
+ - The \ref lgf-format "LGF file format" has changed,
+ \@nodeset has changed to \@nodes,
+ \@edgeset and \@uedgeset to \@arcs or
+ \@edges, which become completely equivalents. The
+ \@nodes, \@edges and \@uedges sections are
+ removed from the format, the content of them should be
+ the part of \@attributes section. The data fields in
+ the sections must follow a strict format, they must be either character
+ sequences without whitespaces or quoted strings.
+ - The LemonReader and LemonWriter core interfaces
+ are no longer available.
+ - The implementation of the general section readers and writers has changed
+ they are simple functors now. Beside the old
+ stream based section handling, currently line oriented section
+ reading and writing are also supported. In the
+ section readers the lines must be counted manually. The sections
+ should be read and written with the SectionWriter and SectionReader
+ classes.
+ - Instead of the item readers and writers, item converters should be
+ used. The converters are functors, which map the type to
+ std::string or std::string to the type. The converters for standard
+ containers hasn't yet been implemented in the new LEMON. The converters
+ can return strings in any format, because if it is necessary, the LGF
+ writer and reader will quote and unquote the given value.
+ - The DigraphReader and DigraphWriter can used similarly to the
+ 0.x series, however the read or write prefix of
+ the member functions are removed.
+ - The new LEMON supports the function like interface, the \c
+ digraphReader and \c digraphWriter functions are more convenient than
+ using the classes directly.
+
+\section migration-search BFS, DFS and Dijkstra
+- Using the function interface of BFS, DFS and %Dijkstra both source and
+ target nodes can be given as parameters of the run() function
+ (instead of \c bfs(), \c dfs() or \c dijkstra() itself).
+- \ref named-templ-param "Named class template parameters" of \c Bfs,
+ \c Dfs, \c Dijkstra, \c BfsVisit, \c DfsVisit are renamed to start
+ with "Set" instead of "Def". Namely,
+ - \c DefPredMap -> \c SetPredMap
+ - \c DefDistMap -> \c SetDistMap
+ - \c DefReachedMap -> \c SetReachedMap
+ - \c DefProcessedMap -> \c SetProcessedMap
+ - \c DefHeap -> \c SetHeap
+ - \c DefStandardHeap -> \c SetStandardHeap
+ - \c DefOperationTraits -> \c SetOperationTraits
+ - \c DefProcessedMapToBeDefaultMap -> \c SetStandardProcessedMap
+
+\section migration-error Exceptions and Debug tools
+
+The class hierarchy of exceptions has largely been simplified. Now,
+only the i/o related tools may throw exceptions. All other exceptions
+have been replaced with either the \c LEMON_ASSERT or the \c LEMON_DEBUG
+macros.
+
+On the other hand, the parameter order of constructors of the
+exceptions has been changed. See \ref IoError and \ref FormatError for
+more details.
+
+\section migration-other Others
+- The contents of graph_utils.h are moved to core.h
+ and maps.h. core.h is included by all graph types,
+ therefore it usually do not have to be included directly.
+- path_utils.h is merged to \c path.h.
+- The semantic of the assignment operations and copy constructors of maps
+ are still under discussion. So, you must copy them by hand (i.e. copy
+ each entry one-by-one)
+- The parameters of the graph copying tools (i.e. \c GraphCopy,
+ \c DigraphCopy) have to be given in the from-to order.
+- \c copyDigraph() and \c copyGraph() are renamed to \c digraphCopy()
+ and \c graphCopy(), respectively.
+- The interface of \ref DynArcLookUp has changed. It is now the same as
+ of \ref ArcLookUp and \ref AllArcLookUp
+- Some map types should also been renamed. Namely,
+ - \c IntegerMap -> \c RangeMap
+ - \c StdMap -> \c SparseMap
+ - \c FunctorMap -> \c FunctorToMap
+ - \c MapFunctor -> \c MapToFunctor
+ - \c ForkWriteMap -> \c ForkMap
+ - \c StoreBoolMap -> \c LoggerBoolMap
+- \c dim2::BoundingBox -> \c dim2::Box
+
+*/
+}
Index: doc/named-param.dox
===================================================================
--- doc/named-param.dox (revision 269)
+++ doc/named-param.dox (revision 269)
@@ -0,0 +1,119 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+/*!
+
+\page named-param Named Parameters
+
+\section named-func-param Named Function Parameters
+
+Several modern languages provide a convenient way to refer the
+function parameters by name also when you call the function. It is
+especially comfortable in case of a function having tons of parameters
+with natural default values. Sadly, C++ lack this amenity.
+
+However, with a crafty trick and with some little
+inconvenience, it is possible to emulate is.
+The example below shows how to do it.
+
+\code
+class namedFn
+{
+ int _id;
+ double _val;
+ int _dim;
+
+ public:
+ namedFn() : _id(0), _val(1), _dim(2) {}
+ namedFn& id(int p) { _id = p ; return *this; }
+ namedFn& val(double p) { _val = p ; return *this; }
+ namedFn& dim(int p) { _dim = p ; return *this; }
+
+ run() {
+ std::cout << "Here comes the function itself\n" <<
+ << "With parameters "
+ << _id << ", " << _val << ", " << _dim << std::endl;
+ }
+};
+\endcode
+
+Then you can use it like this.
+
+\code
+namedFn().id(3).val(2).run();
+\endcode
+
+The trick is obvious, each "named parameter" changes one component of
+the underlying class, then gives back a reference to it. Finally,
+run() executes the algorithm itself.
+
+\note Although it is a class, namedFn is used pretty much like as it were
+a function. That it why we called it namedFn instead of \c NamedFn.
+
+\note In fact, the final .run() could be made unnecessary,
+because the algorithm could also be implemented in the destructor of
+\c namedFn instead. This however would make it impossible to implement
+functions with return values, and would also cause serious problems when
+implementing \ref named-templ-func-param "named template parameters".
+Therefore, by convention, .run() must be used
+explicitly to execute a function having named parameters
+everywhere in LEMON.
+
+\section named-templ-func-param Named Function Template Parameters
+
+A named parameter can also be a template function. The usage is
+exactly the same, but the implementation behind is a kind of black
+magic and they are the dirtiest part of the LEMON code.
+
+You will probably never need to know how it works, but if you really
+committed, have a look at \ref lemon/graph_to_eps.h for an example.
+
+\section traits-classes Traits Classes
+
+A similar game can also be played when defining classes. In this case
+the type of the class attributes can be changed. Initially we have to
+define a special class called Traits Class defining the
+default type of the attributes. Then the types of these attributes can
+be changed in the same way as described in the next section.
+
+See \ref lemon::DijkstraDefaultTraits for an
+example how a traits class implementation looks like.
+
+\section named-templ-param Named Class Template Parameters
+
+If we would like to change the type of an attribute in a class that
+was instantiated by using a traits class as a template parameter, and
+the class contains named parameters, we do not have to instantiate again
+the class with new traits class, but instead adaptor classes can
+be used as shown in the following example.
+
+\code
+Dijkstra<>::SetPredMap >::Create
+\endcode
+
+It can also be used in conjunction with other named template
+parameters in arbitrary order.
+
+\code
+Dijkstra<>::SetDistMap::SetPredMap >::Create
+\endcode
+
+The result will be an instantiated Dijkstra class, in which the
+DistMap and the PredMap is modified.
+
+*/
Index: lemon/CMakeLists.txt
===================================================================
--- lemon/CMakeLists.txt (revision 141)
+++ lemon/CMakeLists.txt (revision 225)
@@ -1,2 +1,18 @@
-include_directories (${LEMON_SOURCE_DIR})
-add_library (lemon arg_parser.cc base.cc color.cc random.cc)
+INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
+
+ADD_LIBRARY(lemon
+ arg_parser.cc
+ base.cc
+ color.cc
+ random.cc)
+
+INSTALL(
+ TARGETS lemon
+ ARCHIVE DESTINATION lib
+ COMPONENT library)
+
+INSTALL(
+ DIRECTORY . bits concepts
+ DESTINATION include/lemon
+ COMPONENT headers
+ FILES_MATCHING PATTERN "*.h")
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am (revision 220)
+++ lemon/Makefile.am (revision 259)
@@ -13,7 +13,6 @@
lemon/random.cc
-
-lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
-lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
+#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
+#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
lemon_HEADERS += \
Index: lemon/arg_parser.cc
===================================================================
--- lemon/arg_parser.cc (revision 214)
+++ lemon/arg_parser.cc (revision 315)
@@ -27,10 +27,9 @@
}
- ArgParser::ArgParser(int argc, const char **argv) :_argc(argc), _argv(argv),
- _command_name(argv[0]) {
+ ArgParser::ArgParser(int argc, const char * const *argv)
+ :_argc(argc), _argv(argv), _command_name(argv[0]) {
funcOption("-help","Print a short help message",_showHelp,this);
synonym("help","-help");
synonym("h","-help");
-
}
Index: lemon/arg_parser.h
===================================================================
--- lemon/arg_parser.h (revision 214)
+++ lemon/arg_parser.h (revision 315)
@@ -17,6 +17,6 @@
*/
-#ifndef LEMON_ARG_PARSER
-#define LEMON_ARG_PARSER
+#ifndef LEMON_ARG_PARSER_H
+#define LEMON_ARG_PARSER_H
#include
@@ -47,5 +47,5 @@
int _argc;
- const char **_argv;
+ const char * const *_argv;
enum OptType { UNKNOWN=0, BOOL=1, STRING=2, DOUBLE=3, INTEGER=4, FUNC=5 };
@@ -120,5 +120,5 @@
///Constructor
- ArgParser(int argc, const char **argv);
+ ArgParser(int argc, const char * const *argv);
~ArgParser();
@@ -311,6 +311,7 @@
///This is the type of the return value of ArgParser::operator[]().
///It automatically converts to \c int, \c double, \c bool or
- ///\c std::string if the type of the option matches, otherwise it
- ///throws an exception (i.e. it performs runtime type checking).
+ ///\c std::string if the type of the option matches, which is checked
+ ///with an \ref LEMON_ASSERT "assertion" (i.e. it performs runtime
+ ///type checking).
class RefType
{
@@ -383,3 +384,3 @@
}
-#endif // LEMON_ARG_PARSER
+#endif // LEMON_ARG_PARSER_H
Index: lemon/assert.h
===================================================================
--- lemon/assert.h (revision 218)
+++ lemon/assert.h (revision 290)
@@ -28,6 +28,7 @@
namespace lemon {
- inline void assert_fail_log(const char *file, int line, const char *function,
- const char *message, const char *assertion)
+ inline void assert_fail_abort(const char *file, int line,
+ const char *function, const char* message,
+ const char *assertion)
{
std::cerr << file << ":" << line << ": ";
@@ -38,11 +39,4 @@
std::cerr << " (assertion '" << assertion << "' failed)";
std::cerr << std::endl;
- }
-
- inline void assert_fail_abort(const char *file, int line,
- const char *function, const char* message,
- const char *assertion)
- {
- assert_fail_log(file, line, function, message, assertion);
std::abort();
}
@@ -64,15 +58,12 @@
#undef LEMON_ASSERT
-#undef LEMON_FIXME
#undef LEMON_DEBUG
-#if (defined(LEMON_ASSERT_LOG) ? 1 : 0) + \
- (defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \
+#if (defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1
#error "LEMON assertion system is not set properly"
#endif
-#if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) + \
- (defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \
+#if ((defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 || \
defined(LEMON_ENABLE_ASSERTS)) && \
@@ -83,8 +74,5 @@
-#if defined LEMON_ASSERT_LOG
-# undef LEMON_ASSERT_HANDLER
-# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_log
-#elif defined LEMON_ASSERT_ABORT
+#if defined LEMON_ASSERT_ABORT
# undef LEMON_ASSERT_HANDLER
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort
@@ -108,6 +96,8 @@
# elif defined _MSC_VER
# define LEMON_FUNCTION_NAME (__FUNCSIG__)
+# elif __STDC_VERSION__ >= 199901L
+# define LEMON_FUNCTION_NAME (__func__)
# else
-# define LEMON_FUNCTION_NAME (__func__)
+# define LEMON_FUNCTION_NAME ("")
# endif
#endif
@@ -119,10 +109,10 @@
/// \brief Macro for assertion with customizable message
///
-/// Macro for assertion with customizable message. \param exp An
-/// expression that must be convertible to \c bool. If it is \c
-/// false, then an assertion is raised. The concrete behaviour depends
-/// on the settings of the assertion system. \param msg A const
-/// char* parameter, which can be used to provide information
-/// about the circumstances of the failed assertion.
+/// Macro for assertion with customizable message.
+/// \param exp An expression that must be convertible to \c bool. If it is \c
+/// false, then an assertion is raised. The concrete behaviour depends on the
+/// settings of the assertion system.
+/// \param msg A const char* parameter, which can be used to provide
+/// information about the circumstances of the failed assertion.
///
/// The assertions are enabled in the default behaviour.
@@ -138,15 +128,10 @@
/// The checking is also disabled when the standard macro \c NDEBUG is defined.
///
-/// The LEMON assertion system has a wide range of customization
-/// properties. As a default behaviour the failed assertion prints a
-/// short log message to the standard error and aborts the execution.
-///
-/// The following modes can be used in the assertion system:
-///
-/// - \c LEMON_ASSERT_LOG The failed assertion prints a short log
-/// message to the standard error and continues the execution.
-/// - \c LEMON_ASSERT_ABORT This mode is similar to the \c
-/// LEMON_ASSERT_LOG, but it aborts the program. It is the default
-/// behaviour.
+/// As a default behaviour the failed assertion prints a short log message to
+/// the standard error and aborts the execution.
+///
+/// However, the following modes can be used in the assertion system:
+/// - \c LEMON_ASSERT_ABORT The failed assertion prints a short log message to
+/// the standard error and aborts the program. It is the default behaviour.
/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler
/// function.
@@ -176,20 +161,4 @@
/// \ingroup exceptions
///
-/// \brief Macro for mark not yet implemented features.
-///
-/// Macro for mark not yet implemented features and outstanding bugs.
-/// It is close to be the shortcut of the following code:
-/// \code
-/// LEMON_ASSERT(false, msg);
-/// \endcode
-///
-/// \see LEMON_ASSERT
-# define LEMON_FIXME(msg) \
- (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME, \
- ::lemon::_assert_bits::cstringify(msg), \
- static_cast(0)))
-
-/// \ingroup exceptions
-///
/// \brief Macro for internal assertions
///
@@ -223,5 +192,4 @@
# ifndef LEMON_ASSERT_HANDLER
# define LEMON_ASSERT(exp, msg) (static_cast(0))
-# define LEMON_FIXME(msg) (static_cast(0))
# define LEMON_DEBUG(exp, msg) (static_cast(0))
# else
@@ -232,9 +200,4 @@
::lemon::_assert_bits::cstringify(msg), \
#exp), 0)))
-# define LEMON_FIXME(msg) \
- (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME, \
- ::lemon::_assert_bits::cstringify(msg), \
- static_cast(0)))
-
# if LEMON_ENABLE_DEBUG
# define LEMON_DEBUG(exp, msg) \
Index: lemon/bfs.h
===================================================================
--- lemon/bfs.h (revision 220)
+++ lemon/bfs.h (revision 305)
@@ -22,5 +22,5 @@
///\ingroup search
///\file
-///\brief Bfs algorithm.
+///\brief BFS algorithm.
#include
@@ -29,8 +29,7 @@
#include
#include
+#include
namespace lemon {
-
-
///Default traits class of Bfs class.
@@ -41,71 +40,71 @@
struct BfsDefaultTraits
{
- ///The digraph type the algorithm runs on.
+ ///The type of the digraph the algorithm runs on.
typedef GR Digraph;
- ///\brief The type of the map that stores the last
+
+ ///\brief The type of the map that stores the predecessor
///arcs of the shortest paths.
///
- ///The type of the map that stores the last
+ ///The type of the map that stores the predecessor
///arcs of the shortest paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///
- typedef typename Digraph::template NodeMap PredMap;
+ typedef typename Digraph::template NodeMap PredMap;
///Instantiates a PredMap.
- ///This function instantiates a \ref PredMap.
- ///\param G is the digraph, to which we would like to define the PredMap.
- ///\todo The digraph alone may be insufficient to initialize
- static PredMap *createPredMap(const GR &G)
- {
- return new PredMap(G);
- }
+ ///This function instantiates a PredMap.
+ ///\param g is the digraph, to which we would like to define the
+ ///PredMap.
+ static PredMap *createPredMap(const Digraph &g)
+ {
+ return new PredMap(g);
+ }
+
///The type of the map that indicates which nodes are processed.
///The type of the map that indicates which nodes are processed.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///\todo named parameter to set this type, function to read and write.
typedef NullMap ProcessedMap;
///Instantiates a ProcessedMap.
- ///This function instantiates a \ref ProcessedMap.
+ ///This function instantiates a ProcessedMap.
///\param g is the digraph, to which
- ///we would like to define the \ref ProcessedMap
+ ///we would like to define the ProcessedMap
#ifdef DOXYGEN
- static ProcessedMap *createProcessedMap(const GR &g)
+ static ProcessedMap *createProcessedMap(const Digraph &g)
#else
- static ProcessedMap *createProcessedMap(const GR &)
+ static ProcessedMap *createProcessedMap(const Digraph &)
#endif
{
return new ProcessedMap();
}
+
///The type of the map that indicates which nodes are reached.
///The type of the map that indicates which nodes are reached.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///\todo named parameter to set this type, function to read and write.
+ ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a ReachedMap.
- ///This function instantiates a \ref ReachedMap.
- ///\param G is the digraph, to which
- ///we would like to define the \ref ReachedMap.
- static ReachedMap *createReachedMap(const GR &G)
- {
- return new ReachedMap(G);
- }
- ///The type of the map that stores the dists of the nodes.
-
- ///The type of the map that stores the dists of the nodes.
+ ///This function instantiates a ReachedMap.
+ ///\param g is the digraph, to which
+ ///we would like to define the ReachedMap.
+ static ReachedMap *createReachedMap(const Digraph &g)
+ {
+ return new ReachedMap(g);
+ }
+
+ ///The type of the map that stores the distances of the nodes.
+
+ ///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///
typedef typename Digraph::template NodeMap DistMap;
///Instantiates a DistMap.
- ///This function instantiates a \ref DistMap.
- ///\param G is the digraph, to which we would like to define
- ///the \ref DistMap
- static DistMap *createDistMap(const GR &G)
- {
- return new DistMap(G);
+ ///This function instantiates a DistMap.
+ ///\param g is the digraph, to which we would like to define the
+ ///DistMap.
+ static DistMap *createDistMap(const Digraph &g)
+ {
+ return new DistMap(g);
}
};
@@ -116,7 +115,11 @@
///This class provides an efficient implementation of the %BFS algorithm.
///
- ///\tparam GR The digraph type the algorithm runs on. The default value is
- ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
- ///is only passed to \ref BfsDefaultTraits.
+ ///There is also a \ref bfs() "function-type interface" for the BFS
+ ///algorithm, which is convenient in the simplier cases and it can be
+ ///used easier.
+ ///
+ ///\tparam GR The type of the digraph the algorithm runs on.
+ ///The default value is \ref ListDigraph. The value of GR is not used
+ ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
///\tparam TR Traits class to set various data types used by the algorithm.
///The default traits class is
@@ -124,5 +127,4 @@
///See \ref BfsDefaultTraits for the documentation of
///a Bfs traits class.
-
#ifdef DOXYGEN
template Path;
+
+ ///The traits class.
typedef TR Traits;
- ///The type of the underlying digraph.
- typedef typename TR::Digraph Digraph;
-
- ///\brief The type of the map that stores the last
- ///arcs of the shortest paths.
- typedef typename TR::PredMap PredMap;
- ///The type of the map indicating which nodes are reached.
- typedef typename TR::ReachedMap ReachedMap;
- ///The type of the map indicating which nodes are processed.
- typedef typename TR::ProcessedMap ProcessedMap;
- ///The type of the map that stores the dists of the nodes.
- typedef typename TR::DistMap DistMap;
+
private:
@@ -167,21 +162,21 @@
typedef typename Digraph::OutArcIt OutArcIt;
- /// Pointer to the underlying digraph.
+ //Pointer to the underlying digraph.
const Digraph *G;
- ///Pointer to the map of predecessors arcs.
+ //Pointer to the map of predecessor arcs.
PredMap *_pred;
- ///Indicates if \ref _pred is locally allocated (\c true) or not.
+ //Indicates if _pred is locally allocated (true) or not.
bool local_pred;
- ///Pointer to the map of distances.
+ //Pointer to the map of distances.
DistMap *_dist;
- ///Indicates if \ref _dist is locally allocated (\c true) or not.
+ //Indicates if _dist is locally allocated (true) or not.
bool local_dist;
- ///Pointer to the map of reached status of the nodes.
+ //Pointer to the map of reached status of the nodes.
ReachedMap *_reached;
- ///Indicates if \ref _reached is locally allocated (\c true) or not.
+ //Indicates if _reached is locally allocated (true) or not.
bool local_reached;
- ///Pointer to the map of processed status of the nodes.
+ //Pointer to the map of processed status of the nodes.
ProcessedMap *_processed;
- ///Indicates if \ref _processed is locally allocated (\c true) or not.
+ //Indicates if _processed is locally allocated (true) or not.
bool local_processed;
@@ -190,7 +185,5 @@
int _curr_dist;
- ///Creates the maps if necessary.
-
- ///\todo Better memory allocation (instead of new).
+ //Creates the maps if necessary.
void create_maps()
{
@@ -226,92 +219,96 @@
template
- struct DefPredMapTraits : public Traits {
+ struct SetPredMapTraits : public Traits {
typedef T PredMap;
static PredMap *createPredMap(const Digraph &)
{
- throw UninitializedParameter();
+ LEMON_ASSERT(false, "PredMap is not initialized");
+ return 0; // ignore warnings
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///PredMap type
- ///
- ///\ref named-templ-param "Named parameter" for setting PredMap type
- ///
+ ///PredMap type.
+ ///
+ ///\ref named-templ-param "Named parameter" for setting
+ ///PredMap type.
template
- struct DefPredMap : public Bfs< Digraph, DefPredMapTraits > {
- typedef Bfs< Digraph, DefPredMapTraits > Create;
+ struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > {
+ typedef Bfs< Digraph, SetPredMapTraits > Create;
};
template
- struct DefDistMapTraits : public Traits {
+ struct SetDistMapTraits : public Traits {
typedef T DistMap;
static DistMap *createDistMap(const Digraph &)
{
- throw UninitializedParameter();
+ LEMON_ASSERT(false, "DistMap is not initialized");
+ return 0; // ignore warnings
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///DistMap type
- ///
- ///\ref named-templ-param "Named parameter" for setting DistMap type
- ///
+ ///DistMap type.
+ ///
+ ///\ref named-templ-param "Named parameter" for setting
+ ///DistMap type.
template
- struct DefDistMap : public Bfs< Digraph, DefDistMapTraits > {
- typedef Bfs< Digraph, DefDistMapTraits > Create;
+ struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > {
+ typedef Bfs< Digraph, SetDistMapTraits > Create;
};
template
- struct DefReachedMapTraits : public Traits {
+ struct SetReachedMapTraits : public Traits {
typedef T ReachedMap;
static ReachedMap *createReachedMap(const Digraph &)
{
- throw UninitializedParameter();
+ LEMON_ASSERT(false, "ReachedMap is not initialized");
+ return 0; // ignore warnings
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///ReachedMap type
- ///
- ///\ref named-templ-param "Named parameter" for setting ReachedMap type
- ///
+ ///ReachedMap type.
+ ///
+ ///\ref named-templ-param "Named parameter" for setting
+ ///ReachedMap type.
template
- struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits > {
- typedef Bfs< Digraph, DefReachedMapTraits > Create;
+ struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > {
+ typedef Bfs< Digraph, SetReachedMapTraits > Create;
};
template
- struct DefProcessedMapTraits : public Traits {
+ struct SetProcessedMapTraits : public Traits {
typedef T ProcessedMap;
static ProcessedMap *createProcessedMap(const Digraph &)
{
- throw UninitializedParameter();
+ LEMON_ASSERT(false, "ProcessedMap is not initialized");
+ return 0; // ignore warnings
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///ProcessedMap type
- ///
- ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
- ///
+ ///ProcessedMap type.
+ ///
+ ///\ref named-templ-param "Named parameter" for setting
+ ///ProcessedMap type.
template
- struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits > {
- typedef Bfs< Digraph, DefProcessedMapTraits > Create;
+ struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > {
+ typedef Bfs< Digraph, SetProcessedMapTraits > Create;
};
- struct DefDigraphProcessedMapTraits : public Traits {
+ struct SetStandardProcessedMapTraits : public Traits {
typedef typename Digraph::template NodeMap ProcessedMap;
- static ProcessedMap *createProcessedMap(const Digraph &G)
+ static ProcessedMap *createProcessedMap(const Digraph &g)
{
- return new ProcessedMap(G);
+ return new ProcessedMap(g);
+ return 0; // ignore warnings
}
};
- ///\brief \ref named-templ-param "Named parameter"
- ///for setting the ProcessedMap type to be Digraph::NodeMap.
- ///
- ///\ref named-templ-param "Named parameter"
- ///for setting the ProcessedMap type to be Digraph::NodeMap.
+ ///\brief \ref named-templ-param "Named parameter" for setting
+ ///ProcessedMap type to be Digraph::NodeMap.
+ ///
+ ///\ref named-templ-param "Named parameter" for setting
+ ///ProcessedMap type to be Digraph::NodeMap.
///If you don't set it explicitly, it will be automatically allocated.
- template
- struct DefProcessedMapToBeDefaultMap :
- public Bfs< Digraph, DefDigraphProcessedMapTraits> {
- typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
+ struct SetStandardProcessedMap :
+ public Bfs< Digraph, SetStandardProcessedMapTraits > {
+ typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
};
@@ -322,8 +319,8 @@
///Constructor.
- ///\param _G the digraph the algorithm will run on.
- ///
- Bfs(const Digraph& _G) :
- G(&_G),
+ ///Constructor.
+ ///\param g The digraph the algorithm runs on.
+ Bfs(const Digraph &g) :
+ G(&g),
_pred(NULL), local_pred(false),
_dist(NULL), local_dist(false),
@@ -341,7 +338,7 @@
}
- ///Sets the map storing the predecessor arcs.
-
- ///Sets the map storing the predecessor arcs.
+ ///Sets the map that stores the predecessor arcs.
+
+ ///Sets the map that stores the predecessor arcs.
///If you don't use this function before calling \ref run(),
///it will allocate one. The destructor deallocates this
@@ -358,7 +355,7 @@
}
- ///Sets the map indicating the reached nodes.
-
- ///Sets the map indicating the reached nodes.
+ ///Sets the map that indicates which nodes are reached.
+
+ ///Sets the map that indicates which nodes are reached.
///If you don't use this function before calling \ref run(),
///it will allocate one. The destructor deallocates this
@@ -375,7 +372,7 @@
}
- ///Sets the map indicating the processed nodes.
-
- ///Sets the map indicating the processed nodes.
+ ///Sets the map that indicates which nodes are processed.
+
+ ///Sets the map that indicates which nodes are processed.
///If you don't use this function before calling \ref run(),
///it will allocate one. The destructor deallocates this
@@ -392,7 +389,8 @@
}
- ///Sets the map storing the distances calculated by the algorithm.
-
- ///Sets the map storing the distances calculated by the algorithm.
+ ///Sets the map that stores the distances of the nodes.
+
+ ///Sets the map that stores the distances of the nodes calculated by
+ ///the algorithm.
///If you don't use this function before calling \ref run(),
///it will allocate one. The destructor deallocates this
@@ -410,18 +408,19 @@
public:
+
///\name Execution control
///The simplest way to execute the algorithm is to use
- ///one of the member functions called \c run(...).
+ ///one of the member functions called \ref lemon::Bfs::run() "run()".
///\n
- ///If you need more control on the execution,
- ///first you must call \ref init(), then you can add several source nodes
- ///with \ref addSource().
- ///Finally \ref start() will perform the actual path
- ///computation.
+ ///If you need more control on the execution, first you must call
+ ///\ref lemon::Bfs::init() "init()", then you can add several source
+ ///nodes with \ref lemon::Bfs::addSource() "addSource()".
+ ///Finally \ref lemon::Bfs::start() "start()" will perform the
+ ///actual path computation.
///@{
- ///\brief Initializes the internal data structures.
- ///
+ ///Initializes the internal data structures.
+
///Initializes the internal data structures.
///
@@ -461,5 +460,5 @@
///\return The processed node.
///
- ///\warning The queue must not be empty!
+ ///\pre The queue must not be empty.
Node processNextNode()
{
@@ -483,14 +482,15 @@
///Processes the next node.
- ///Processes the next node. And checks that the given target node
+ ///Processes the next node and checks if the given target node
///is reached. If the target node is reachable from the processed
- ///node then the reached parameter will be set true. The reached
- ///parameter should be initially false.
+ ///node, then the \c reach parameter will be set to \c true.
///
///\param target The target node.
- ///\retval reach Indicates that the target node is reached.
+ ///\retval reach Indicates if the target node is reached.
+ ///It should be initially \c false.
+ ///
///\return The processed node.
///
- ///\warning The queue must not be empty!
+ ///\pre The queue must not be empty.
Node processNextNode(Node target, bool& reach)
{
@@ -515,14 +515,17 @@
///Processes the next node.
- ///Processes the next node. And checks that at least one of
- ///reached node has true value in the \c nm node map. If one node
- ///with true value is reachable from the processed node then the
- ///rnode parameter will be set to the first of such nodes.
- ///
- ///\param nm The node map of possible targets.
+ ///Processes the next node and checks if at least one of reached
+ ///nodes has \c true value in the \c nm node map. If one node
+ ///with \c true value is reachable from the processed node, then the
+ ///\c rnode parameter will be set to the first of such nodes.
+ ///
+ ///\param nm A \c bool (or convertible) node map that indicates the
+ ///possible targets.
///\retval rnode The reached target node.
+ ///It should be initially \c INVALID.
+ ///
///\return The processed node.
///
- ///\warning The queue must not be empty!
+ ///\pre The queue must not be empty.
template
Node processNextNode(const NM& nm, Node& rnode)
@@ -546,11 +549,9 @@
}
- ///Next node to be processed.
-
- ///Next node to be processed.
- ///
- ///\return The next node to be processed or INVALID if the queue is
- /// empty.
- Node nextNode()
+ ///The next node to be processed.
+
+ ///Returns the next node to be processed or \c INVALID if the queue
+ ///is empty.
+ Node nextNode() const
{
return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
@@ -558,13 +559,14 @@
///\brief Returns \c false if there are nodes
- ///to be processed in the queue
+ ///to be processed.
///
///Returns \c false if there are nodes
- ///to be processed in the queue
- bool emptyQueue() { return _queue_tail==_queue_head; }
+ ///to be processed in the queue.
+ bool emptyQueue() const { return _queue_tail==_queue_head; }
+
///Returns the number of the nodes to be processed.
///Returns the number of the nodes to be processed in the queue.
- int queueSize() { return _queue_head-_queue_tail; }
+ int queueSize() const { return _queue_head-_queue_tail; }
///Executes the algorithm.
@@ -572,13 +574,20 @@
///Executes the algorithm.
///
- ///\pre init() must be called and at least one node should be added
- ///with addSource() before using this function.
- ///
///This method runs the %BFS algorithm from the root node(s)
- ///in order to
- ///compute the
- ///shortest path to each node. The algorithm computes
- ///- The shortest path tree.
- ///- The distance of each node from the root(s).
+ ///in order to compute the shortest path to each node.
+ ///
+ ///The algorithm computes
+ ///- the shortest path tree (forest),
+ ///- the distance of each node from the root(s).
+ ///
+ ///\pre init() must be called and at least one root node should be
+ ///added with addSource() before using this function.
+ ///
+ ///\note b.start() is just a shortcut of the following code.
+ ///\code
+ /// while ( !b.emptyQueue() ) {
+ /// b.processNextNode();
+ /// }
+ ///\endcode
void start()
{
@@ -586,20 +595,29 @@
}
- ///Executes the algorithm until \c dest is reached.
-
- ///Executes the algorithm until \c dest is reached.
- ///
- ///\pre init() must be called and at least one node should be added
- ///with addSource() before using this function.
+ ///Executes the algorithm until the given target node is reached.
+
+ ///Executes the algorithm until the given target node is reached.
///
///This method runs the %BFS algorithm from the root node(s)
- ///in order to compute the shortest path to \c dest.
+ ///in order to compute the shortest path to \c t.
+ ///
///The algorithm computes
- ///- The shortest path to \c dest.
- ///- The distance of \c dest from the root(s).
- void start(Node dest)
+ ///- the shortest path to \c t,
+ ///- the distance of \c t from the root(s).
+ ///
+ ///\pre init() must be called and at least one root node should be
+ ///added with addSource() before using this function.
+ ///
+ ///\note b.start(t) is just a shortcut of the following code.
+ ///\code
+ /// bool reach = false;
+ /// while ( !b.emptyQueue() && !reach ) {
+ /// b.processNextNode(t, reach);
+ /// }
+ ///\endcode
+ void start(Node t)
{
bool reach = false;
- while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+ while ( !emptyQueue() && !reach ) processNextNode(t, reach);
}
@@ -608,15 +626,27 @@
///Executes the algorithm until a condition is met.
///
- ///\pre init() must be called and at least one node should be added
- ///with addSource() before using this function.
- ///
- ///\param nm must be a bool (or convertible) node map. The
- ///algorithm will stop when it reaches a node \c v with
- /// nm[v] true.
+ ///This method runs the %BFS algorithm from the root node(s) in
+ ///order to compute the shortest path to a node \c v with
+ /// nm[v] true, if such a node can be found.
+ ///
+ ///\param nm A \c bool (or convertible) node map. The algorithm
+ ///will stop when it reaches a node \c v with nm[v] true.
///
///\return The reached node \c v with nm[v] true or
///\c INVALID if no such node was found.
- template
- Node start(const NM &nm)
+ ///
+ ///\pre init() must be called and at least one root node should be
+ ///added with addSource() before using this function.
+ ///
+ ///\note b.start(nm) is just a shortcut of the following code.
+ ///\code
+ /// Node rnode = INVALID;
+ /// while ( !b.emptyQueue() && rnode == INVALID ) {
+ /// b.processNextNode(nm, rnode);
+ /// }
+ /// return rnode;
+ ///\endcode
+ template
+ Node start(const NodeBoolMap &nm)
{
Node rnode = INVALID;
@@ -627,14 +657,14 @@
}
- ///Runs %BFS algorithm from node \c s.
-
- ///This method runs the %BFS algorithm from a root node \c s
- ///in order to
- ///compute the
- ///shortest path to each node. The algorithm computes
- ///- The shortest path tree.
- ///- The distance of each node from the root.
- ///
- ///\note b.run(s) is just a shortcut of the following code.
+ ///Runs the algorithm from the given source node.
+
+ ///This method runs the %BFS algorithm from node \c s
+ ///in order to compute the shortest path to each node.
+ ///
+ ///The algorithm computes
+ ///- the shortest path tree,
+ ///- the distance of each node from the root.
+ ///
+ ///\note b.run(s) is just a shortcut of the following code.
///\code
/// b.init();
@@ -650,10 +680,12 @@
///Finds the shortest path between \c s and \c t.
- ///Finds the shortest path between \c s and \c t.
- ///
- ///\return The length of the shortest s---t path if there exists one,
- ///0 otherwise.
- ///\note Apart from the return value, b.run(s) is
- ///just a shortcut of the following code.
+ ///This method runs the %BFS algorithm from node \c s
+ ///in order to compute the shortest path to node \c t
+ ///(it stops searching when \c t is processed).
+ ///
+ ///\return \c true if \c t is reachable form \c s.
+ ///
+ ///\note Apart from the return value, b.run(s,t) is just a
+ ///shortcut of the following code.
///\code
/// b.init();
@@ -661,9 +693,38 @@
/// b.start(t);
///\endcode
- int run(Node s,Node t) {
+ bool run(Node s,Node t) {
init();
addSource(s);
start(t);
- return reached(t) ? _curr_dist : 0;
+ return reached(t);
+ }
+
+ ///Runs the algorithm to visit all nodes in the digraph.
+
+ ///This method runs the %BFS algorithm in order to
+ ///compute the shortest path to each node.
+ ///
+ ///The algorithm computes
+ ///- the shortest path tree (forest),
+ ///- the distance of each node from the root(s).
+ ///
+ ///\note b.run(s) is just a shortcut of the following code.
+ ///\code
+ /// b.init();
+ /// for (NodeIt n(gr); n != INVALID; ++n) {
+ /// if (!b.reached(n)) {
+ /// b.addSource(n);
+ /// b.start();
+ /// }
+ /// }
+ ///\endcode
+ void run() {
+ init();
+ for (NodeIt n(*G); n != INVALID; ++n) {
+ if (!reached(n)) {
+ addSource(n);
+ start();
+ }
+ }
}
@@ -673,51 +734,54 @@
///The result of the %BFS algorithm can be obtained using these
///functions.\n
- ///Before the use of these functions,
- ///either run() or start() must be calleb.
+ ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
+ ///"start()" must be called before using them.
///@{
- typedef PredMapPath Path;
-
- ///Gives back the shortest path.
-
- ///Gives back the shortest path.
- ///\pre The \c t should be reachable from the source.
- Path path(Node t)
- {
- return Path(*G, *_pred, t);
- }
+ ///The shortest path to a node.
+
+ ///Returns the shortest path to a node.
+ ///
+ ///\warning \c t should be reachable from the root(s).
+ ///
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
+ Path path(Node t) const { return Path(*G, *_pred, t); }
///The distance of a node from the root(s).
///Returns the distance of a node from the root(s).
- ///\pre \ref run() must be called before using this function.
- ///\warning If node \c v in unreachable from the root(s) the return value
- ///of this function is undefined.
+ ///
+ ///\warning If node \c v is not reachable from the root(s), then
+ ///the return value of this function is undefined.
+ ///
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
int dist(Node v) const { return (*_dist)[v]; }
- ///Returns the 'previous arc' of the shortest path tree.
-
- ///For a node \c v it returns the 'previous arc'
- ///of the shortest path tree,
- ///i.e. it returns the last arc of a shortest path from the root(s) to \c
- ///v. It is \ref INVALID
- ///if \c v is unreachable from the root(s) or \c v is a root. The
- ///shortest path tree used here is equal to the shortest path tree used in
- ///\ref predNode().
- ///\pre Either \ref run() or \ref start() must be called before using
- ///this function.
+ ///Returns the 'previous arc' of the shortest path tree for a node.
+
+ ///This function returns the 'previous arc' of the shortest path
+ ///tree for the node \c v, i.e. it returns the last arc of a
+ ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
+ ///is not reachable from the root(s) or if \c v is a root.
+ ///
+ ///The shortest path tree used here is equal to the shortest path
+ ///tree used in \ref predNode().
+ ///
+ ///\pre Either \ref run() or \ref start() must be called before
+ ///using this function.
Arc predArc(Node v) const { return (*_pred)[v];}
- ///Returns the 'previous node' of the shortest path tree.
-
- ///For a node \c v it returns the 'previous node'
- ///of the shortest path tree,
- ///i.e. it returns the last but one node from a shortest path from the
- ///root(a) to \c /v.
- ///It is INVALID if \c v is unreachable from the root(s) or
- ///if \c v itself a root.
+ ///Returns the 'previous node' of the shortest path tree for a node.
+
+ ///This function returns the 'previous node' of the shortest path
+ ///tree for the node \c v, i.e. it returns the last but one node
+ ///from a shortest path from the root(s) to \c v. It is \c INVALID
+ ///if \c v is not reachable from the root(s) or if \c v is a root.
+ ///
///The shortest path tree used here is equal to the shortest path
///tree used in \ref predArc().
+ ///
///\pre Either \ref run() or \ref start() must be called before
///using this function.
@@ -725,60 +789,59 @@
G->source((*_pred)[v]); }
- ///Returns a reference to the NodeMap of distances.
-
- ///Returns a reference to the NodeMap of distances.
- ///\pre Either \ref run() or \ref init() must
- ///be called before using this function.
+ ///\brief Returns a const reference to the node map that stores the
+ /// distances of the nodes.
+ ///
+ ///Returns a const reference to the node map that stores the distances
+ ///of the nodes calculated by the algorithm.
+ ///
+ ///\pre Either \ref run() or \ref init()
+ ///must be called before using this function.
const DistMap &distMap() const { return *_dist;}
- ///Returns a reference to the shortest path tree map.
-
- ///Returns a reference to the NodeMap of the arcs of the
- ///shortest path tree.
+ ///\brief Returns a const reference to the node map that stores the
+ ///predecessor arcs.
+ ///
+ ///Returns a const reference to the node map that stores the predecessor
+ ///arcs, which form the shortest path tree.
+ ///
///\pre Either \ref run() or \ref init()
///must be called before using this function.
const PredMap &predMap() const { return *_pred;}
- ///Checks if a node is reachable from the root.
-
- ///Returns \c true if \c v is reachable from the root.
- ///\warning The source nodes are indicated as unreached.
+ ///Checks if a node is reachable from the root(s).
+
+ ///Returns \c true if \c v is reachable from the root(s).
///\pre Either \ref run() or \ref start()
///must be called before using this function.
- ///
- bool reached(Node v) { return (*_reached)[v]; }
+ bool reached(Node v) const { return (*_reached)[v]; }
///@}
};
- ///Default traits class of Bfs function.
-
- ///Default traits class of Bfs function.
+ ///Default traits class of bfs() function.
+
+ ///Default traits class of bfs() function.
///\tparam GR Digraph type.
template
struct BfsWizardDefaultTraits
{
- ///The digraph type the algorithm runs on.
+ ///The type of the digraph the algorithm runs on.
typedef GR Digraph;
- ///\brief The type of the map that stores the last
+
+ ///\brief The type of the map that stores the predecessor
///arcs of the shortest paths.
///
- ///The type of the map that stores the last
+ ///The type of the map that stores the predecessor
///arcs of the shortest paths.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///
- typedef NullMap PredMap;
+ typedef typename Digraph::template NodeMap PredMap;
///Instantiates a PredMap.
- ///This function instantiates a \ref PredMap.
- ///\param g is the digraph, to which we would like to define the PredMap.
- ///\todo The digraph alone may be insufficient to initialize
-#ifdef DOXYGEN
- static PredMap *createPredMap(const GR &g)
-#else
- static PredMap *createPredMap(const GR &)
-#endif
- {
- return new PredMap();
+ ///This function instantiates a PredMap.
+ ///\param g is the digraph, to which we would like to define the
+ ///PredMap.
+ static PredMap *createPredMap(const Digraph &g)
+ {
+ return new PredMap(g);
}
@@ -787,61 +850,63 @@
///The type of the map that indicates which nodes are processed.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///\todo named parameter to set this type, function to read and write.
+ ///By default it is a NullMap.
typedef NullMap ProcessedMap;
///Instantiates a ProcessedMap.
- ///This function instantiates a \ref ProcessedMap.
+ ///This function instantiates a ProcessedMap.
///\param g is the digraph, to which
- ///we would like to define the \ref ProcessedMap
+ ///we would like to define the ProcessedMap.
#ifdef DOXYGEN
- static ProcessedMap *createProcessedMap(const GR &g)
+ static ProcessedMap *createProcessedMap(const Digraph &g)
#else
- static ProcessedMap *createProcessedMap(const GR &)
+ static ProcessedMap *createProcessedMap(const Digraph &)
#endif
{
return new ProcessedMap();
}
+
///The type of the map that indicates which nodes are reached.
///The type of the map that indicates which nodes are reached.
- ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///\todo named parameter to set this type, function to read and write.
+ ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
///Instantiates a ReachedMap.
- ///This function instantiates a \ref ReachedMap.
- ///\param G is the digraph, to which
- ///we would like to define the \ref ReachedMap.
- static ReachedMap *createReachedMap(const GR &G)
- {
- return new ReachedMap(G);
- }
- ///The type of the map that stores the dists of the nodes.
-
- ///The type of the map that stores the dists of the nodes.
+ ///This function instantiates a ReachedMap.
+ ///\param g is the digraph, to which
+ ///we would like to define the ReachedMap.
+ static ReachedMap *createReachedMap(const Digraph &g)
+ {
+ return new ReachedMap(g);
+ }
+
+ ///The type of the map that stores the distances of the nodes.
+
+ ///The type of the map that stores the distances of the nodes.
///It must meet the \ref concepts::WriteMap "WriteMap" concept.
- ///
- typedef NullMap DistMap;
+ typedef typename Digraph::template NodeMap DistMap;
///Instantiates a DistMap.
- ///This function instantiates a \ref DistMap.
+ ///This function instantiates a DistMap.
///\param g is the digraph, to which we would like to define
- ///the \ref DistMap
-#ifdef DOXYGEN
- static DistMap *createDistMap(const GR &g)
-#else
- static DistMap *createDistMap(const GR &)
-#endif
- {
- return new DistMap();
- }
+ ///the DistMap
+ static DistMap *createDistMap(const Digraph &g)
+ {
+ return new DistMap(g);
+ }
+
+ ///The type of the shortest paths.
+
+ ///The type of the shortest paths.
+ ///It must meet the \ref concepts::Path "Path" concept.
+ typedef lemon::Path Path;
};
- /// Default traits used by \ref BfsWizard
+ /// Default traits class used by BfsWizard
/// To make it easier to use Bfs algorithm
- ///we have created a wizard class.
+ /// we have created a wizard class.
/// This \ref BfsWizard class needs default traits,
- ///as well as the \ref Bfs class.
+ /// as well as the \ref Bfs class.
/// The \ref BfsWizardBase is a class to be the default traits of the
/// \ref BfsWizard class.
@@ -852,19 +917,21 @@
typedef BfsWizardDefaultTraits Base;
protected:
- /// Type of the nodes in the digraph.
+ //The type of the nodes in the digraph.
typedef typename Base::Digraph::Node Node;
- /// Pointer to the underlying digraph.
+ //Pointer to the digraph the algorithm runs on.
void *_g;
- ///Pointer to the map of reached nodes.
+ //Pointer to the map of reached nodes.
void *_reached;
- ///Pointer to the map of processed nodes.
+ //Pointer to the map of processed nodes.
void *_processed;
- ///Pointer to the map of predecessors arcs.
+ //Pointer to the map of predecessors arcs.
void *_pred;
- ///Pointer to the map of distances.
+ //Pointer to the map of distances.
void *_dist;
- ///Pointer to the source node.
- Node _source;
+ //Pointer to the shortest path to the target node.
+ void *_path;
+ //Pointer to the distance of the target node.
+ int *_di;
public:
@@ -872,40 +939,28 @@
/// This constructor does not require parameters, therefore it initiates
- /// all of the attributes to default values (0, INVALID).
+ /// all of the attributes to \c 0.
BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
- _dist(0), _source(INVALID) {}
+ _dist(0), _path(0), _di(0) {}
/// Constructor.
- /// This constructor requires some parameters,
- /// listed in the parameters list.
- /// Others are initiated to 0.
- /// \param g is the initial value of \ref _g
- /// \param s is the initial value of \ref _source
- BfsWizardBase(const GR &g, Node s=INVALID) :
+ /// This constructor requires one parameter,
+ /// others are initiated to \c 0.
+ /// \param g The digraph the algorithm runs on.
+ BfsWizardBase(const GR &g) :
_g(reinterpret_cast(const_cast(&g))),
- _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
+ _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
};
- /// A class to make the usage of Bfs algorithm easier
-
- /// This class is created to make it easier to use Bfs algorithm.
- /// It uses the functions and features of the plain \ref Bfs,
- /// but it is much simpler to use it.
+ /// Auxiliary class for the function-type interface of BFS algorithm.
+
+ /// This auxiliary class is created to implement the
+ /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
+ /// It does not have own \ref run() method, it uses the functions
+ /// and features of the plain \ref Bfs.
///
- /// Simplicity means that the way to change the types defined
- /// in the traits class is based on functions that returns the new class
- /// and not on templatable built-in classes.
- /// When using the plain \ref Bfs
- /// the new class with the modified type comes from
- /// the original class by using the ::
- /// operator. In the case of \ref BfsWizard only
- /// a function have to be called and it will
- /// return the needed class.
- ///
- /// It does not have own \ref run method. When its \ref run method is called
- /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
- /// method of it.
+ /// This class should only be used through the \ref bfs() function,
+ /// which makes it easier to use the algorithm.
template
class BfsWizard : public TR
@@ -913,28 +968,26 @@
typedef TR Base;
- ///The type of the underlying digraph.
+ ///The type of the digraph the algorithm runs on.
typedef typename TR::Digraph Digraph;
- //\e
+
typedef typename Digraph::Node Node;
- //\e
typedef typename Digraph::NodeIt NodeIt;
- //\e
typedef typename Digraph::Arc Arc;
- //\e
typedef typename Digraph::OutArcIt OutArcIt;
- ///\brief The type of the map that stores
- ///the reached nodes
- typedef typename TR::ReachedMap ReachedMap;
- ///\brief The type of the map that stores
- ///the processed nodes
- typedef typename TR::ProcessedMap ProcessedMap;
- ///\brief The type of the map that stores the last
+ ///\brief The type of the map that stores the predecessor
///arcs of the shortest paths.
typedef typename TR::PredMap PredMap;
- ///The type of the map that stores the dists of the nodes.
+ ///\brief The type of the map that stores the distances of the nodes.
typedef typename TR::DistMap DistMap;
+ ///\brief The type of the map that indicates which nodes are reached.
+ typedef typename TR::ReachedMap ReachedMap;
+ ///\brief The type of the map that indicates which nodes are processed.
+ typedef typename TR::ProcessedMap ProcessedMap;
+ ///The type of the shortest paths
+ typedef typename TR::Path Path;
public:
+
/// Constructor.
BfsWizard() : TR() {}
@@ -944,6 +997,7 @@
/// Constructor that requires parameters.
/// These parameters will be the default values for the traits class.
- BfsWizard(const Digraph &g, Node s=INVALID) :
- TR(g,s) {}
+ /// \param g The digraph the algorithm runs on.
+ BfsWizard(const Digraph &g) :
+ TR(g) {}
///Copy constructor
@@ -952,123 +1006,157 @@
~BfsWizard() {}
- ///Runs Bfs algorithm from a given node.
-
- ///Runs Bfs algorithm from a given node.
- ///The node can be given by the \ref source function.
+ ///Runs BFS algorithm from the given source node.
+
+ ///This method runs BFS algorithm from node \c s
+ ///in order to compute the shortest path to each node.
+ void run(Node s)
+ {
+ Bfs alg(*reinterpret_cast(Base::_g));
+ if (Base::_pred)
+ alg.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist)
+ alg.distMap(*reinterpret_cast(Base::_dist));
+ if (Base::_reached)
+ alg.reachedMap(*reinterpret_cast(Base::_reached));
+ if (Base::_processed)
+ alg.processedMap(*reinterpret_cast(Base::_processed));
+ if (s!=INVALID)
+ alg.run(s);
+ else
+ alg.run();
+ }
+
+ ///Finds the shortest path between \c s and \c t.
+
+ ///This method runs BFS algorithm from node \c s
+ ///in order to compute the shortest path to node \c t
+ ///(it stops searching when \c t is processed).
+ ///
+ ///\return \c true if \c t is reachable form \c s.
+ bool run(Node s, Node t)
+ {
+ Bfs alg(*reinterpret_cast(Base::_g));
+ if (Base::_pred)
+ alg.predMap(*reinterpret_cast(Base::_pred));
+ if (Base::_dist)
+ alg.distMap(*reinterpret_cast(Base::_dist));
+ if (Base::_reached)
+ alg.reachedMap(*reinterpret_cast(Base::_reached));
+ if (Base::_processed)
+ alg.processedMap(*reinterpret_cast(Base::_processed));
+ alg.run(s,t);
+ if (Base::_path)
+ *reinterpret_cast(Base::_path) = alg.path(t);
+ if (Base::_di)
+ *Base::_di = alg.dist(t);
+ return alg.reached(t);
+ }
+
+ ///Runs BFS algorithm to visit all nodes in the digraph.
+
+ ///This method runs BFS algorithm in order to compute
+ ///the shortest path to each node.
void run()
{
- if(Base::_source==INVALID) throw UninitializedParameter();
- Bfs alg(*reinterpret_cast(Base::_g));
- if(Base::_reached)
- alg.reachedMap(*reinterpret_cast(Base::_reached));
- if(Base::_processed)
- alg.processedMap(*reinterpret_cast(Base::_processed));
- if(Base::_pred)
- alg.predMap(*reinterpret_cast(Base::_pred));
- if(Base::_dist)
- alg.distMap(*reinterpret_cast(Base::_dist));
- alg.run(Base::_source);
- }
-
- ///Runs Bfs algorithm from the given node.
-
- ///Runs Bfs algorithm from the given node.
- ///\param s is the given source.
- void run(Node s)
- {
- Base::_source=s;
- run();
+ run(INVALID);
}
template
- struct DefPredMapBase : public Base {
+ struct SetPredMapBase : public Base {
typedef T PredMap;
static PredMap *createPredMap(const Digraph &) { return 0; };
- DefPredMapBase(const TR &b) : TR(b) {}
+ SetPredMapBase(const TR &b) : TR(b) {}
};
-
- ///\brief \ref named-templ-param "Named parameter"
- ///function for setting PredMap
- ///
- /// \ref named-templ-param "Named parameter"
- ///function for setting PredMap
- ///
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting PredMap object.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for setting PredMap object.
template
- BfsWizard > predMap(const T &t)
+ BfsWizard > predMap(const T &t)
{
Base::_pred=reinterpret_cast(const_cast(&t));
- return BfsWizard >(*this);
- }
-
+ return BfsWizard >(*this);
+ }
template
- struct DefReachedMapBase : public Base {
+ struct SetReachedMapBase : public Base {
typedef T ReachedMap;
static ReachedMap *createReachedMap(const Digraph &) { return 0; };
- DefReachedMapBase(const TR &b) : TR(b) {}
+ SetReachedMapBase(const TR &b) : TR(b) {}
};
-
- ///\brief \ref named-templ-param "Named parameter"
- ///function for setting ReachedMap
- ///
- /// \ref named-templ-param "Named parameter"
- ///function for setting ReachedMap
- ///
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting ReachedMap object.
+ ///
+ /// \ref named-func-param "Named parameter"
+ ///for setting ReachedMap object.
template
- BfsWizard > reachedMap(const T &t)
+ BfsWizard > reachedMap(const T &t)
{
Base::_reached=reinterpret_cast(const_cast(&t));
- return BfsWizard >(*this);
- }
-
+ return BfsWizard >(*this);
+ }
template
- struct DefProcessedMapBase : public Base {
+ struct SetDistMapBase : public Base {
+ typedef T DistMap;
+ static DistMap *createDistMap(const Digraph &) { return 0; };
+ SetDistMapBase(const TR &b) : TR(b) {}
+ };
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting DistMap object.
+ ///
+ /// \ref named-func-param "Named parameter"
+ ///for setting DistMap object.
+ template
+ BfsWizard > distMap(const T &t)
+ {
+ Base::_dist=reinterpret_cast(const_cast(&t));
+ return BfsWizard >(*this);
+ }
+
+ template
+ struct SetProcessedMapBase : public Base {
typedef T ProcessedMap;
static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
- DefProcessedMapBase(const TR &b) : TR(b) {}
+ SetProcessedMapBase(const TR &b) : TR(b) {}
};
-
- ///\brief \ref named-templ-param "Named parameter"
- ///function for setting ProcessedMap
- ///
- /// \ref named-templ-param "Named parameter"
- ///function for setting ProcessedMap
- ///
+ ///\brief \ref named-func-param "Named parameter"
+ ///for setting ProcessedMap object.
+ ///
+ /// \ref named-func-param "Named parameter"
+ ///for setting ProcessedMap object.
template
- BfsWizard > processedMap(const T &t)
+ BfsWizard > processedMap(const T &t)
{
Base::_processed=reinterpret_cast(const_cast(&t));
- return BfsWizard >(*this);
- }
-
+ return BfsWizard >(*this);
+ }
template
- struct DefDistMapBase : public Base {
- typedef T DistMap;
- static DistMap *createDistMap(const Digraph &) { return 0; };
- DefDistMapBase(const TR &b) : TR(b) {}
+ struct SetPathBase : public Base {
+ typedef T Path;
+ SetPathBase(const TR &b) : TR(b) {}
};
-
- ///\brief \ref named-templ-param "Named parameter"
- ///function for setting DistMap type
- ///
- /// \ref named-templ-param "Named parameter"
- ///function for setting DistMap type
- ///
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the shortest path to the target node.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for getting the shortest path to the target node.
template
- BfsWizard > distMap(const T &t)
- {
- Base::_dist=reinterpret_cast(const_cast(&t));
- return BfsWizard >(*this);
- }
-
- /// Sets the source node, from which the Bfs algorithm runs.
-
- /// Sets the source node, from which the Bfs algorithm runs.
- /// \param s is the source node.
- BfsWizard &source(Node s)
- {
- Base::_source=s;
+ BfsWizard > path(const T &t)
+ {
+ Base::_path=reinterpret_cast(const_cast(&t));
+ return BfsWizard >(*this);
+ }
+
+ ///\brief \ref named-func-param "Named parameter"
+ ///for getting the distance of the target node.
+ ///
+ ///\ref named-func-param "Named parameter"
+ ///for getting the distance of the target node.
+ BfsWizard dist(const int &d)
+ {
+ Base::_di=const_cast(&d);
return *this;
}
@@ -1076,16 +1164,18 @@
};
- ///Function type interface for Bfs algorithm.
+ ///Function-type interface for BFS algorithm.
/// \ingroup search
- ///Function type interface for Bfs algorithm.
+ ///Function-type interface for BFS algorithm.
///
- ///This function also has several
- ///\ref named-templ-func-param "named parameters",
+ ///This function also has several \ref named-func-param "named parameters",
///they are declared as the members of class \ref BfsWizard.
- ///The following
- ///example shows how to use these parameters.
+ ///The following examples show how to use these parameters.
///\code
- /// bfs(g,source).predMap(preds).run();
+ /// // Compute shortest path from node s to each node
+ /// bfs(g).predMap(preds).distMap(dists).run(s);
+ ///
+ /// // Compute shortest path from s to t
+ /// bool reached = bfs(g).path(p).dist(d).run(s,t);
///\endcode
///\warning Don't forget to put the \ref BfsWizard::run() "run()"
@@ -1095,14 +1185,14 @@
template
BfsWizard >
- bfs(const GR &g,typename GR::Node s=INVALID)
+ bfs(const GR &digraph)
{
- return BfsWizard >(g,s);
+ return BfsWizard >(digraph);
}
#ifdef DOXYGEN
- /// \brief Visitor class for bfs.
+ /// \brief Visitor class for BFS.
///
/// This class defines the interface of the BfsVisit events, and
- /// it could be the base of a real Visitor class.
+ /// it could be the base of a real visitor class.
template
struct BfsVisitor {
@@ -1110,27 +1200,27 @@
typedef typename Digraph::Arc Arc;
typedef typename Digraph::Node Node;
- /// \brief Called when the arc reach a node.
- ///
- /// It is called when the bfs find an arc which target is not
- /// reached yet.
+ /// \brief Called for the source node(s) of the BFS.
+ ///
+ /// This function is called for the source node(s) of the BFS.
+ void start(const Node& node) {}
+ /// \brief Called when a node is reached first time.
+ ///
+ /// This function is called when a node is reached first time.
+ void reach(const Node& node) {}
+ /// \brief Called when a node is processed.
+ ///
+ /// This function is called when a node is processed.
+ void process(const Node& node) {}
+ /// \brief Called when an arc reaches a new node.
+ ///
+ /// This function is called when the BFS finds an arc whose target node
+ /// is not reached yet.
void discover(const Arc& arc) {}
- /// \brief Called when the node reached first time.
- ///
- /// It is Called when the node reached first time.
- void reach(const Node& node) {}
- /// \brief Called when the arc examined but target of the arc
+ /// \brief Called when an arc is examined but its target node is
/// already discovered.
///
- /// It called when the arc examined but the target of the arc
+ /// This function is called when an arc is examined but its target node is
/// already discovered.
void examine(const Arc& arc) {}
- /// \brief Called for the source node of the bfs.
- ///
- /// It is called for the source node of the bfs.
- void start(const Node& node) {}
- /// \brief Called when the node processed.
- ///
- /// It is Called when the node processed.
- void process(const Node& node) {}
};
#else
@@ -1140,9 +1230,9 @@
typedef typename Digraph::Arc Arc;
typedef typename Digraph::Node Node;
+ void start(const Node&) {}
+ void reach(const Node&) {}
+ void process(const Node&) {}
void discover(const Arc&) {}
- void reach(const Node&) {}
void examine(const Arc&) {}
- void start(const Node&) {}
- void process(const Node&) {}
template
@@ -1151,9 +1241,9 @@
Arc arc;
Node node;
+ visitor.start(node);
+ visitor.reach(node);
+ visitor.process(node);
visitor.discover(arc);
- visitor.reach(node);
visitor.examine(arc);
- visitor.start(node);
- visitor.process(node);
}
_Visitor& visitor;
@@ -1165,9 +1255,9 @@
///
/// Default traits class of BfsVisit class.
- /// \tparam _Digraph Digraph type.
+ /// \tparam _Digraph The type of the digraph the algorithm runs on.
template
struct BfsVisitDefaultTraits {
- /// \brief The digraph type the algorithm runs on.
+ /// \brief The type of the digraph the algorithm runs on.
typedef _Digraph Digraph;
@@ -1175,13 +1265,12 @@
///
/// The type of the map that indicates which nodes are reached.
- /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
- /// \todo named parameter to set this type, function to read and write.
+ /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
typedef typename Digraph::template NodeMap ReachedMap;
/// \brief Instantiates a ReachedMap.
///
- /// This function instantiates a \ref ReachedMap.
+ /// This function instantiates a ReachedMap.
/// \param digraph is the digraph, to which
- /// we would like to define the \ref ReachedMap.
+ /// we would like to define the ReachedMap.
static ReachedMap *createReachedMap(const Digraph &digraph) {
return new ReachedMap(digraph);
@@ -1192,5 +1281,5 @@
/// \ingroup search
///
- /// \brief %BFS Visit algorithm class.
+ /// \brief %BFS algorithm class with visitor interface.
///
/// This class provides an efficient implementation of the %BFS algorithm
@@ -1199,19 +1288,24 @@
/// The %BfsVisit class provides an alternative interface to the Bfs
/// class. It works with callback mechanism, the BfsVisit object calls
- /// on every bfs event the \c Visitor class member functions.
+ /// the member functions of the \c Visitor class on every BFS event.
///
- /// \tparam _Digraph The digraph type the algorithm runs on.
+ /// This interface of the BFS algorithm should be used in special cases
+ /// when extra actions have to be performed in connection with certain
+ /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
+ /// instead.
+ ///
+ /// \tparam _Digraph The type of the digraph the algorithm runs on.
/// The default value is
- /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
- /// is only passed to \ref BfsDefaultTraits.
- /// \tparam _Visitor The Visitor object for the algorithm. The
- /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
- /// does not observe the Bfs events. If you want to observe the bfs
- /// events you should implement your own Visitor class.
+ /// \ref ListDigraph. The value of _Digraph is not used directly by
+ /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
+ /// \tparam _Visitor The Visitor type that is used by the algorithm.
+ /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
+ /// does not observe the BFS events. If you want to observe the BFS
+ /// events, you should implement your own visitor class.
/// \tparam _Traits Traits class to set various data types used by the
/// algorithm. The default traits class is
/// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
/// See \ref BfsVisitDefaultTraits for the documentation of
- /// a Bfs visit traits class.
+ /// a BFS visit traits class.
#ifdef DOXYGEN
template
@@ -1219,28 +1313,19 @@
template ,
- typename _Traits = BfsDefaultTraits<_Digraph> >
+ typename _Traits = BfsVisitDefaultTraits<_Digraph> >
#endif
class BfsVisit {
public:
- /// \brief \ref Exception for uninitialized parameters.
- ///
- /// This error represents problems in the initialization
- /// of the parameters of the algorithms.
- class UninitializedParameter : public lemon::UninitializedParameter {
- public:
- virtual const char* what() const throw()
- {
- return "lemon::BfsVisit::UninitializedParameter";
- }
- };
-
+ ///The traits class.
typedef _Traits Traits;
+ ///The type of the digraph the algorithm runs on.
typedef typename Traits::Digraph Digraph;
+ ///The visitor type used by the algorithm.
typedef _Visitor Visitor;
- ///The type of the map indicating which nodes are reached.
+ ///The type of the map that indicates which nodes are reached.
typedef typename Traits::ReachedMap ReachedMap;
@@ -1252,11 +1337,11 @@
typedef typename Digraph::OutArcIt OutArcIt;
- /// Pointer to the underlying digraph.
+ //Pointer to the underlying digraph.
const Digraph *_digraph;
- /// Pointer to the visitor object.
+ //Pointer to the visitor object.
Visitor *_visitor;
- ///Pointer to the map of reached status of the nodes.
+ //Pointer to the map of reached status of the nodes.
ReachedMap *_reached;
- ///Indicates if \ref _reached is locally allocated (\c true) or not.
+ //Indicates if _reached is locally allocated (true) or not.
bool local_reached;
@@ -1264,7 +1349,5 @@
int _list_front, _list_back;
- /// \brief Creates the maps if necessary.
- ///
- /// Creates the maps if necessary.
+ //Creates the maps if necessary.
void create_maps() {
if(!_reached) {
@@ -1286,18 +1369,19 @@
///@{
template
- struct DefReachedMapTraits : public Traits {
+ struct SetReachedMapTraits : public Traits {
typedef T ReachedMap;
static ReachedMap *createReachedMap(const Digraph &digraph) {
- throw UninitializedParameter();
+ LEMON_ASSERT(false, "ReachedMap is not initialized");
+ return 0; // ignore warnings
}
};
/// \brief \ref named-templ-param "Named parameter" for setting
- /// ReachedMap type
- ///
- /// \ref named-templ-param "Named parameter" for setting ReachedMap type
+ /// ReachedMap type.
+ ///
+ /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
template
- struct DefReachedMap : public BfsVisit< Digraph, Visitor,
- DefReachedMapTraits > {
- typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits > Create;
+ struct SetReachedMap : public BfsVisit< Digraph, Visitor,
+ SetReachedMapTraits > {
+ typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits > Create;
};
///@}
@@ -1309,7 +1393,6 @@
/// Constructor.
///
- /// \param digraph the digraph the algorithm will run on.
- /// \param visitor The visitor of the algorithm.
- ///
+ /// \param digraph The digraph the algorithm runs on.
+ /// \param visitor The visitor object of the algorithm.
BfsVisit(const Digraph& digraph, Visitor& visitor)
: _digraph(&digraph), _visitor(&visitor),
@@ -1317,15 +1400,13 @@
/// \brief Destructor.
- ///
- /// Destructor.
~BfsVisit() {
if(local_reached) delete _reached;
}
- /// \brief Sets the map indicating if a node is reached.
- ///
- /// Sets the map indicating if a node is reached.
+ /// \brief Sets the map that indicates which nodes are reached.
+ ///
+ /// Sets the map that indicates which nodes are reached.
/// If you don't use this function before calling \ref run(),
- /// it will allocate one. The destuctor deallocates this
+ /// it will allocate one. The destructor deallocates this
/// automatically allocated map, of course.
/// \return (*this)
@@ -1340,19 +1421,21 @@
public:
+
/// \name Execution control
/// The simplest way to execute the algorithm is to use
- /// one of the member functions called \c run(...).
+ /// one of the member functions called \ref lemon::BfsVisit::run()
+ /// "run()".
/// \n
- /// If you need more control on the execution,
- /// first you must call \ref init(), then you can adda source node
- /// with \ref addSource().
- /// Finally \ref start() will perform the actual path
- /// computation.
+ /// If you need more control on the execution, first you must call
+ /// \ref lemon::BfsVisit::init() "init()", then you can add several
+ /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
+ /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
+ /// actual path computation.
/// @{
+
/// \brief Initializes the internal data structures.
///
/// Initializes the internal data structures.
- ///
void init() {
create_maps();
@@ -1382,5 +1465,5 @@
/// \return The processed node.
///
- /// \pre The queue must not be empty!
+ /// \pre The queue must not be empty.
Node processNextNode() {
Node n = _list[++_list_front];
@@ -1403,14 +1486,15 @@
/// \brief Processes the next node.
///
- /// Processes the next node. And checks that the given target node
+ /// Processes the next node and checks if the given target node
/// is reached. If the target node is reachable from the processed
- /// node then the reached parameter will be set true. The reached
- /// parameter should be initially false.
+ /// node, then the \c reach parameter will be set to \c true.
///
/// \param target The target node.
- /// \retval reach Indicates that the target node is reached.
+ /// \retval reach Indicates if the target node is reached.
+ /// It should be initially \c false.
+ ///
/// \return The processed node.
///
- /// \warning The queue must not be empty!
+ /// \pre The queue must not be empty.
Node processNextNode(Node target, bool& reach) {
Node n = _list[++_list_front];
@@ -1434,14 +1518,17 @@
/// \brief Processes the next node.
///
- /// Processes the next node. And checks that at least one of
- /// reached node has true value in the \c nm node map. If one node
- /// with true value is reachable from the processed node then the
- /// rnode parameter will be set to the first of such nodes.
- ///
- /// \param nm The node map of possible targets.
+ /// Processes the next node and checks if at least one of reached
+ /// nodes has \c true value in the \c nm node map. If one node
+ /// with \c true value is reachable from the processed node, then the
+ /// \c rnode parameter will be set to the first of such nodes.
+ ///
+ /// \param nm A \c bool (or convertible) node map that indicates the
+ /// possible targets.
/// \retval rnode The reached target node.
+ /// It should be initially \c INVALID.
+ ///
/// \return The processed node.
///
- /// \warning The queue must not be empty!
+ /// \pre The queue must not be empty.
template
Node processNextNode(const NM& nm, Node& rnode) {
@@ -1464,25 +1551,23 @@
}
- /// \brief Next node to be processed.
- ///
- /// Next node to be processed.
- ///
- /// \return The next node to be processed or INVALID if the stack is
- /// empty.
- Node nextNode() {
+ /// \brief The next node to be processed.
+ ///
+ /// Returns the next node to be processed or \c INVALID if the queue
+ /// is empty.
+ Node nextNode() const {
return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
}
/// \brief Returns \c false if there are nodes
- /// to be processed in the queue
+ /// to be processed.
///
/// Returns \c false if there are nodes
- /// to be processed in the queue
- bool emptyQueue() { return _list_front == _list_back; }
+ /// to be processed in the queue.
+ bool emptyQueue() const { return _list_front == _list_back; }
/// \brief Returns the number of the nodes to be processed.
///
/// Returns the number of the nodes to be processed in the queue.
- int queueSize() { return _list_back - _list_front; }
+ int queueSize() const { return _list_back - _list_front; }
/// \brief Executes the algorithm.
@@ -1490,19 +1575,48 @@
/// Executes the algorithm.
///
- /// \pre init() must be called and at least one node should be added
+ /// This method runs the %BFS algorithm from the root node(s)
+ /// in order to compute the shortest path to each node.
+ ///
+ /// The algorithm computes
+ /// - the shortest path tree (forest),
+ /// - the distance of each node from the root(s).
+ ///
+ /// \pre init() must be called and at least one root node should be added
/// with addSource() before using this function.
+ ///
+ /// \note b.start() is just a shortcut of the following code.
+ /// \code
+ /// while ( !b.emptyQueue() ) {
+ /// b.processNextNode();
+ /// }
+ /// \endcode
void start() {
while ( !emptyQueue() ) processNextNode();
}
- /// \brief Executes the algorithm until \c dest is reached.
- ///
- /// Executes the algorithm until \c dest is reached.
- ///
- /// \pre init() must be called and at least one node should be added
- /// with addSource() before using this function.
- void start(Node dest) {
+ /// \brief Executes the algorithm until the given target node is reached.
+ ///
+ /// Executes the algorithm until the given target node is reached.
+ ///
+ /// This method runs the %BFS algorithm from the root node(s)
+ /// in order to compute the shortest path to \c t.
+ ///
+ /// The algorithm computes
+ /// - the shortest path to \c t,
+ /// - the distance of \c t from the root(s).
+ ///
+ /// \pre init() must be called and at least one root node should be
+ /// added with addSource() before using this function.
+ ///
+ /// \note b.start(t) is just a shortcut of the following code.
+ /// \code
+ /// bool reach = false;
+ /// while ( !b.emptyQueue() && !reach ) {
+ /// b.processNextNode(t, reach);
+ /// }
+ /// \endcode
+ void start(Node t) {
bool reach = false;
- while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+ while ( !emptyQueue() && !reach ) processNextNode(t, reach);
}
@@ -1511,13 +1625,26 @@
/// Executes the algorithm until a condition is met.
///
- /// \pre init() must be called and at least one node should be added
- /// with addSource() before using this function.
- ///
- ///\param nm must be a bool (or convertible) node map. The
- ///algorithm will stop when it reaches a node \c v with
+ /// This method runs the %BFS algorithm from the root node(s) in
+ /// order to compute the shortest path to a node \c v with
+ /// nm[v] true, if such a node can be found.
+ ///
+ /// \param nm must be a bool (or convertible) node map. The
+ /// algorithm will stop when it reaches a node \c v with
/// nm[v] true.
///
- ///\return The reached node \c v with nm[v] true or
- ///\c INVALID if no such node was found.
+ /// \return The reached node \c v with nm[v] true or
+ /// \c INVALID if no such node was found.
+ ///
+ /// \pre init() must be called and at least one root node should be
+ /// added with addSource() before using this function.
+ ///
+ /// \note b.start(nm) is just a shortcut of the following code.
+ /// \code
+ /// Node rnode = INVALID;
+ /// while ( !b.emptyQueue() && rnode == INVALID ) {
+ /// b.processNextNode(nm, rnode);
+ /// }
+ /// return rnode;
+ /// \endcode
template
Node start(const NM &nm) {
@@ -1529,8 +1656,14 @@
}
- /// \brief Runs %BFSVisit algorithm from node \c s.
- ///
- /// This method runs the %BFS algorithm from a root node \c s.
- /// \note b.run(s) is just a shortcut of the following code.
+ /// \brief Runs the algorithm from the given source node.
+ ///
+ /// This method runs the %BFS algorithm from node \c s
+ /// in order to compute the shortest path to each node.
+ ///
+ /// The algorithm computes
+ /// - the shortest path tree,
+ /// - the distance of each node from the root.
+ ///
+ /// \note b.run(s) is just a shortcut of the following code.
///\code
/// b.init();
@@ -1544,17 +1677,41 @@
}
- /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
+ /// \brief Finds the shortest path between \c s and \c t.
+ ///
+ /// This method runs the %BFS algorithm from node \c s
+ /// in order to compute the shortest path to node \c t
+ /// (it stops searching when \c t is processed).
+ ///
+ /// \return \c true if \c t is reachable form \c s.
+ ///
+ /// \note Apart from the return value, b.run(s,t) is just a
+ /// shortcut of the following code.
+ ///\code
+ /// b.init();
+ /// b.addSource(s);
+ /// b.start(t);
+ ///\endcode
+ bool run(Node s,Node t) {
+ init();
+ addSource(s);
+ start(t);
+ return reached(t);
+ }
+
+ /// \brief Runs the algorithm to visit all nodes in the digraph.
///
/// This method runs the %BFS algorithm in order to
- /// compute the %BFS path to each node. The algorithm computes
- /// - The %BFS tree.
- /// - The distance of each node from the root in the %BFS tree.
- ///
- ///\note b.run() is just a shortcut of the following code.
+ /// compute the shortest path to each node.
+ ///
+ /// The algorithm computes
+ /// - the shortest path tree (forest),
+ /// - the distance of each node from the root(s).
+ ///
+ /// \note b.run(s) is just a shortcut of the following code.
///\code
/// b.init();
- /// for (NodeIt it(digraph); it != INVALID; ++it) {
- /// if (!b.reached(it)) {
- /// b.addSource(it);
+ /// for (NodeIt n(gr); n != INVALID; ++n) {
+ /// if (!b.reached(n)) {
+ /// b.addSource(n);
/// b.start();
/// }
@@ -1570,4 +1727,5 @@
}
}
+
///@}
@@ -1575,17 +1733,18 @@
/// The result of the %BFS algorithm can be obtained using these
/// functions.\n
- /// Before the use of these functions,
- /// either run() or start() must be called.
+ /// Either \ref lemon::BfsVisit::run() "run()" or
+ /// \ref lemon::BfsVisit::start() "start()" must be called before
+ /// using them.
///@{
- /// \brief Checks if a node is reachable from the root.
+ /// \brief Checks if a node is reachable from the root(s).
///
/// Returns \c true if \c v is reachable from the root(s).
- /// \warning The source nodes are inditated as unreachable.
/// \pre Either \ref run() or \ref start()
/// must be called before using this function.
- ///
bool reached(Node v) { return (*_reached)[v]; }
+
///@}
+
};
@@ -1593,3 +1752,2 @@
#endif
-
Index: lemon/bits/alteration_notifier.h
===================================================================
--- lemon/bits/alteration_notifier.h (revision 220)
+++ lemon/bits/alteration_notifier.h (revision 318)
@@ -25,74 +25,73 @@
#include
-///\ingroup graphbits
-///\file
-///\brief Observer notifier for graph alteration observers.
+//\ingroup graphbits
+//\file
+//\brief Observer notifier for graph alteration observers.
namespace lemon {
- /// \ingroup graphbits
- ///
- /// \brief Notifier class to notify observes about alterations in
- /// a container.
- ///
- /// The simple graph's can be refered as two containers, one node container
- /// and one edge container. But they are not standard containers they
- /// does not store values directly they are just key continars for more
- /// value containers which are the node and edge maps.
- ///
- /// The graph's node and edge sets can be changed as we add or erase
- /// nodes and edges in the graph. Lemon would like to handle easily
- /// that the node and edge maps should contain values for all nodes or
- /// edges. If we want to check on every indicing if the map contains
- /// the current indicing key that cause a drawback in the performance
- /// in the library. We use another solution we notify all maps about
- /// an alteration in the graph, which cause only drawback on the
- /// alteration of the graph.
- ///
- /// This class provides an interface to the container. The \e first() and \e
- /// next() member functions make possible to iterate on the keys of the
- /// container. The \e id() function returns an integer id for each key.
- /// The \e maxId() function gives back an upper bound of the ids.
- ///
- /// For the proper functonality of this class, we should notify it
- /// about each alteration in the container. The alterations have four type
- /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
- /// \e erase() signals that only one or few items added or erased to or
- /// from the graph. If all items are erased from the graph or from an empty
- /// graph a new graph is builded then it can be signaled with the
- /// clear() and build() members. Important rule that if we erase items
- /// from graph we should first signal the alteration and after that erase
- /// them from the container, on the other way on item addition we should
- /// first extend the container and just after that signal the alteration.
- ///
- /// The alteration can be observed with a class inherited from the
- /// \e ObserverBase nested class. The signals can be handled with
- /// overriding the virtual functions defined in the base class. The
- /// observer base can be attached to the notifier with the
- /// \e attach() member and can be detached with detach() function. The
- /// alteration handlers should not call any function which signals
- /// an other alteration in the same notifier and should not
- /// detach any observer from the notifier.
- ///
- /// Alteration observers try to be exception safe. If an \e add() or
- /// a \e clear() function throws an exception then the remaining
- /// observeres will not be notified and the fulfilled additions will
- /// be rolled back by calling the \e erase() or \e clear()
- /// functions. Thence the \e erase() and \e clear() should not throw
- /// exception. Actullay, it can be throw only
- /// \ref AlterationObserver::ImmediateDetach ImmediateDetach
- /// exception which detach the observer from the notifier.
- ///
- /// There are some place when the alteration observing is not completly
- /// reliable. If we want to carry out the node degree in the graph
- /// as in the \ref InDegMap and we use the reverseEdge that cause
- /// unreliable functionality. Because the alteration observing signals
- /// only erasing and adding but not the reversing it will stores bad
- /// degrees. The sub graph adaptors cannot signal the alterations because
- /// just a setting in the filter map can modify the graph and this cannot
- /// be watched in any way.
- ///
- /// \param _Container The container which is observed.
- /// \param _Item The item type which is obserbved.
+ // \ingroup graphbits
+ //
+ // \brief Notifier class to notify observes about alterations in
+ // a container.
+ //
+ // The simple graph's can be refered as two containers, one node container
+ // and one edge container. But they are not standard containers they
+ // does not store values directly they are just key continars for more
+ // value containers which are the node and edge maps.
+ //
+ // The graph's node and edge sets can be changed as we add or erase
+ // nodes and edges in the graph. LEMON would like to handle easily
+ // that the node and edge maps should contain values for all nodes or
+ // edges. If we want to check on every indicing if the map contains
+ // the current indicing key that cause a drawback in the performance
+ // in the library. We use another solution we notify all maps about
+ // an alteration in the graph, which cause only drawback on the
+ // alteration of the graph.
+ //
+ // This class provides an interface to the container. The \e first() and \e
+ // next() member functions make possible to iterate on the keys of the
+ // container. The \e id() function returns an integer id for each key.
+ // The \e maxId() function gives back an upper bound of the ids.
+ //
+ // For the proper functonality of this class, we should notify it
+ // about each alteration in the container. The alterations have four type
+ // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
+ // \e erase() signals that only one or few items added or erased to or
+ // from the graph. If all items are erased from the graph or from an empty
+ // graph a new graph is builded then it can be signaled with the
+ // clear() and build() members. Important rule that if we erase items
+ // from graph we should first signal the alteration and after that erase
+ // them from the container, on the other way on item addition we should
+ // first extend the container and just after that signal the alteration.
+ //
+ // The alteration can be observed with a class inherited from the
+ // \e ObserverBase nested class. The signals can be handled with
+ // overriding the virtual functions defined in the base class. The
+ // observer base can be attached to the notifier with the
+ // \e attach() member and can be detached with detach() function. The
+ // alteration handlers should not call any function which signals
+ // an other alteration in the same notifier and should not
+ // detach any observer from the notifier.
+ //
+ // Alteration observers try to be exception safe. If an \e add() or
+ // a \e clear() function throws an exception then the remaining
+ // observeres will not be notified and the fulfilled additions will
+ // be rolled back by calling the \e erase() or \e clear()
+ // functions. Thence the \e erase() and \e clear() should not throw
+ // exception. Actullay, it can be throw only \ref ImmediateDetach
+ // exception which detach the observer from the notifier.
+ //
+ // There are some place when the alteration observing is not completly
+ // reliable. If we want to carry out the node degree in the graph
+ // as in the \ref InDegMap and we use the reverseEdge that cause
+ // unreliable functionality. Because the alteration observing signals
+ // only erasing and adding but not the reversing it will stores bad
+ // degrees. The sub graph adaptors cannot signal the alterations because
+ // just a setting in the filter map can modify the graph and this cannot
+ // be watched in any way.
+ //
+ // \param _Container The container which is observed.
+ // \param _Item The item type which is obserbved.
template
@@ -105,29 +104,28 @@
typedef _Item Item;
- /// \brief Exception which can be called from \e clear() and
- /// \e erase().
- ///
- /// From the \e clear() and \e erase() function only this
- /// exception is allowed to throw. The exception immediatly
- /// detaches the current observer from the notifier. Because the
- /// \e clear() and \e erase() should not throw other exceptions
- /// it can be used to invalidate the observer.
+ // \brief Exception which can be called from \e clear() and
+ // \e erase().
+ //
+ // From the \e clear() and \e erase() function only this
+ // exception is allowed to throw. The exception immediatly
+ // detaches the current observer from the notifier. Because the
+ // \e clear() and \e erase() should not throw other exceptions
+ // it can be used to invalidate the observer.
struct ImmediateDetach {};
- /// \brief ObserverBase is the base class for the observers.
- ///
- /// ObserverBase is the abstract base class for the observers.
- /// It will be notified about an item was inserted into or
- /// erased from the graph.
- ///
- /// The observer interface contains some pure virtual functions
- /// to override. The add() and erase() functions are
- /// to notify the oberver when one item is added or
- /// erased.
- ///
- /// The build() and clear() members are to notify the observer
- /// about the container is built from an empty container or
- /// is cleared to an empty container.
-
+ // \brief ObserverBase is the base class for the observers.
+ //
+ // ObserverBase is the abstract base class for the observers.
+ // It will be notified about an item was inserted into or
+ // erased from the graph.
+ //
+ // The observer interface contains some pure virtual functions
+ // to override. The add() and erase() functions are
+ // to notify the oberver when one item is added or
+ // erased.
+ //
+ // The build() and clear() members are to notify the observer
+ // about the container is built from an empty container or
+ // is cleared to an empty container.
class ObserverBase {
protected:
@@ -136,21 +134,20 @@
friend class AlterationNotifier;
- /// \brief Default constructor.
- ///
- /// Default constructor for ObserverBase.
- ///
+ // \brief Default constructor.
+ //
+ // Default constructor for ObserverBase.
ObserverBase() : _notifier(0) {}
- /// \brief Constructor which attach the observer into notifier.
- ///
- /// Constructor which attach the observer into notifier.
+ // \brief Constructor which attach the observer into notifier.
+ //
+ // Constructor which attach the observer into notifier.
ObserverBase(AlterationNotifier& nf) {
attach(nf);
}
- /// \brief Constructor which attach the obserever to the same notifier.
- ///
- /// Constructor which attach the obserever to the same notifier as
- /// the other observer is attached to.
+ // \brief Constructor which attach the obserever to the same notifier.
+ //
+ // Constructor which attach the obserever to the same notifier as
+ // the other observer is attached to.
ObserverBase(const ObserverBase& copy) {
if (copy.attached()) {
@@ -159,5 +156,5 @@
}
- /// \brief Destructor
+ // \brief Destructor
virtual ~ObserverBase() {
if (attached()) {
@@ -166,29 +163,26 @@
}
- /// \brief Attaches the observer into an AlterationNotifier.
- ///
- /// This member attaches the observer into an AlterationNotifier.
- ///
+ // \brief Attaches the observer into an AlterationNotifier.
+ //
+ // This member attaches the observer into an AlterationNotifier.
void attach(AlterationNotifier& nf) {
nf.attach(*this);
}
- /// \brief Detaches the observer into an AlterationNotifier.
- ///
- /// This member detaches the observer from an AlterationNotifier.
- ///
+ // \brief Detaches the observer into an AlterationNotifier.
+ //
+ // This member detaches the observer from an AlterationNotifier.
void detach() {
_notifier->detach(*this);
}
- /// \brief Gives back a pointer to the notifier which the map
- /// attached into.
- ///
- /// This function gives back a pointer to the notifier which the map
- /// attached into.
- ///
+ // \brief Gives back a pointer to the notifier which the map
+ // attached into.
+ //
+ // This function gives back a pointer to the notifier which the map
+ // attached into.
Notifier* notifier() const { return const_cast(_notifier); }
- /// Gives back true when the observer is attached into a notifier.
+ // Gives back true when the observer is attached into a notifier.
bool attached() const { return _notifier != 0; }
@@ -202,51 +196,50 @@
typename std::list::iterator _index;
- /// \brief The member function to notificate the observer about an
- /// item is added to the container.
- ///
- /// The add() member function notificates the observer about an item
- /// is added to the container. It have to be overrided in the
- /// subclasses.
+ // \brief The member function to notificate the observer about an
+ // item is added to the container.
+ //
+ // The add() member function notificates the observer about an item
+ // is added to the container. It have to be overrided in the
+ // subclasses.
virtual void add(const Item&) = 0;
- /// \brief The member function to notificate the observer about
- /// more item is added to the container.
- ///
- /// The add() member function notificates the observer about more item
- /// is added to the container. It have to be overrided in the
- /// subclasses.
+ // \brief The member function to notificate the observer about
+ // more item is added to the container.
+ //
+ // The add() member function notificates the observer about more item
+ // is added to the container. It have to be overrided in the
+ // subclasses.
virtual void add(const std::vector- & items) = 0;
- /// \brief The member function to notificate the observer about an
- /// item is erased from the container.
- ///
- /// The erase() member function notificates the observer about an
- /// item is erased from the container. It have to be overrided in
- /// the subclasses.
+ // \brief The member function to notificate the observer about an
+ // item is erased from the container.
+ //
+ // The erase() member function notificates the observer about an
+ // item is erased from the container. It have to be overrided in
+ // the subclasses.
virtual void erase(const Item&) = 0;
- /// \brief The member function to notificate the observer about
- /// more item is erased from the container.
- ///
- /// The erase() member function notificates the observer about more item
- /// is erased from the container. It have to be overrided in the
- /// subclasses.
+ // \brief The member function to notificate the observer about
+ // more item is erased from the container.
+ //
+ // The erase() member function notificates the observer about more item
+ // is erased from the container. It have to be overrided in the
+ // subclasses.
virtual void erase(const std::vector
- & items) = 0;
- /// \brief The member function to notificate the observer about the
- /// container is built.
- ///
- /// The build() member function notificates the observer about the
- /// container is built from an empty container. It have to be
- /// overrided in the subclasses.
-
+ // \brief The member function to notificate the observer about the
+ // container is built.
+ //
+ // The build() member function notificates the observer about the
+ // container is built from an empty container. It have to be
+ // overrided in the subclasses.
virtual void build() = 0;
- /// \brief The member function to notificate the observer about all
- /// items are erased from the container.
- ///
- /// The clear() member function notificates the observer about all
- /// items are erased from the container. It have to be overrided in
- /// the subclasses.
+ // \brief The member function to notificate the observer about all
+ // items are erased from the container.
+ //
+ // The clear() member function notificates the observer about all
+ // items are erased from the container. It have to be overrided in
+ // the subclasses.
virtual void clear() = 0;
@@ -263,29 +256,28 @@
public:
- /// \brief Default constructor.
- ///
- /// The default constructor of the AlterationNotifier.
- /// It creates an empty notifier.
+ // \brief Default constructor.
+ //
+ // The default constructor of the AlterationNotifier.
+ // It creates an empty notifier.
AlterationNotifier()
: container(0) {}
- /// \brief Constructor.
- ///
- /// Constructor with the observed container parameter.
+ // \brief Constructor.
+ //
+ // Constructor with the observed container parameter.
AlterationNotifier(const Container& _container)
: container(&_container) {}
- /// \brief Copy Constructor of the AlterationNotifier.
- ///
- /// Copy constructor of the AlterationNotifier.
- /// It creates only an empty notifier because the copiable
- /// notifier's observers have to be registered still into that notifier.
+ // \brief Copy Constructor of the AlterationNotifier.
+ //
+ // Copy constructor of the AlterationNotifier.
+ // It creates only an empty notifier because the copiable
+ // notifier's observers have to be registered still into that notifier.
AlterationNotifier(const AlterationNotifier& _notifier)
: container(_notifier.container) {}
- /// \brief Destructor.
- ///
- /// Destructor of the AlterationNotifier.
- ///
+ // \brief Destructor.
+ //
+ // Destructor of the AlterationNotifier.
~AlterationNotifier() {
typename Observers::iterator it;
@@ -295,7 +287,7 @@
}
- /// \brief Sets the container.
- ///
- /// Sets the container.
+ // \brief Sets the container.
+ //
+ // Sets the container.
void setContainer(const Container& _container) {
container = &_container;
@@ -308,32 +300,30 @@
public:
-
-
- /// \brief First item in the container.
- ///
- /// Returns the first item in the container. It is
- /// for start the iteration on the container.
+ // \brief First item in the container.
+ //
+ // Returns the first item in the container. It is
+ // for start the iteration on the container.
void first(Item& item) const {
container->first(item);
}
- /// \brief Next item in the container.
- ///
- /// Returns the next item in the container. It is
- /// for iterate on the container.
+ // \brief Next item in the container.
+ //
+ // Returns the next item in the container. It is
+ // for iterate on the container.
void next(Item& item) const {
container->next(item);
}
- /// \brief Returns the id of the item.
- ///
- /// Returns the id of the item provided by the container.
+ // \brief Returns the id of the item.
+ //
+ // Returns the id of the item provided by the container.
int id(const Item& item) const {
return container->id(item);
}
- /// \brief Returns the maximum id of the container.
- ///
- /// Returns the maximum id of the container.
+ // \brief Returns the maximum id of the container.
+ //
+ // Returns the maximum id of the container.
int maxId() const {
return container->maxId(Item());
@@ -355,10 +345,9 @@
public:
- /// \brief Notifies all the registed observers about an item added to
- /// the container.
- ///
- /// It notifies all the registed observers about an item added to
- /// the container.
- ///
+ // \brief Notifies all the registed observers about an item added to
+ // the container.
+ //
+ // It notifies all the registed observers about an item added to
+ // the container.
void add(const Item& item) {
typename Observers::reverse_iterator it;
@@ -376,10 +365,9 @@
}
- /// \brief Notifies all the registed observers about more item added to
- /// the container.
- ///
- /// It notifies all the registed observers about more item added to
- /// the container.
- ///
+ // \brief Notifies all the registed observers about more item added to
+ // the container.
+ //
+ // It notifies all the registed observers about more item added to
+ // the container.
void add(const std::vector
- & items) {
typename Observers::reverse_iterator it;
@@ -397,10 +385,9 @@
}
- /// \brief Notifies all the registed observers about an item erased from
- /// the container.
- ///
- /// It notifies all the registed observers about an item erased from
- /// the container.
- ///
+ // \brief Notifies all the registed observers about an item erased from
+ // the container.
+ //
+ // It notifies all the registed observers about an item erased from
+ // the container.
void erase(const Item& item) throw() {
typename Observers::iterator it = _observers.begin();
@@ -410,17 +397,16 @@
++it;
} catch (const ImmediateDetach&) {
- it = _observers.erase(it);
(*it)->_index = _observers.end();
(*it)->_notifier = 0;
- }
- }
- }
-
- /// \brief Notifies all the registed observers about more item erased
- /// from the container.
- ///
- /// It notifies all the registed observers about more item erased from
- /// the container.
- ///
+ it = _observers.erase(it);
+ }
+ }
+ }
+
+ // \brief Notifies all the registed observers about more item erased
+ // from the container.
+ //
+ // It notifies all the registed observers about more item erased from
+ // the container.
void erase(const std::vector
- & items) {
typename Observers::iterator it = _observers.begin();
@@ -430,16 +416,16 @@
++it;
} catch (const ImmediateDetach&) {
- it = _observers.erase(it);
(*it)->_index = _observers.end();
(*it)->_notifier = 0;
- }
- }
- }
-
- /// \brief Notifies all the registed observers about the container is
- /// built.
- ///
- /// Notifies all the registed observers about the container is built
- /// from an empty container.
+ it = _observers.erase(it);
+ }
+ }
+ }
+
+ // \brief Notifies all the registed observers about the container is
+ // built.
+ //
+ // Notifies all the registed observers about the container is built
+ // from an empty container.
void build() {
typename Observers::reverse_iterator it;
@@ -457,9 +443,9 @@
}
- /// \brief Notifies all the registed observers about all items are
- /// erased.
- ///
- /// Notifies all the registed observers about all items are erased
- /// from the container.
+ // \brief Notifies all the registed observers about all items are
+ // erased.
+ //
+ // Notifies all the registed observers about all items are erased
+ // from the container.
void clear() {
typename Observers::iterator it = _observers.begin();
@@ -469,7 +455,7 @@
++it;
} catch (const ImmediateDetach&) {
- it = _observers.erase(it);
(*it)->_index = _observers.end();
(*it)->_notifier = 0;
+ it = _observers.erase(it);
}
}
Index: lemon/bits/array_map.h
===================================================================
--- lemon/bits/array_map.h (revision 209)
+++ lemon/bits/array_map.h (revision 318)
@@ -27,46 +27,46 @@
#include
-/// \ingroup graphbits
-/// \file
-/// \brief Graph map based on the array storage.
+// \ingroup graphbits
+// \file
+// \brief Graph map based on the array storage.
namespace lemon {
- /// \ingroup graphbits
- ///
- /// \brief Graph map based on the array storage.
- ///
- /// The ArrayMap template class is graph map structure what
- /// automatically updates the map when a key is added to or erased from
- /// the map. This map uses the allocators to implement
- /// the container functionality.
- ///
- /// The template parameters are the Graph the current Item type and
- /// the Value type of the map.
+ // \ingroup graphbits
+ //
+ // \brief Graph map based on the array storage.
+ //
+ // The ArrayMap template class is graph map structure what
+ // automatically updates the map when a key is added to or erased from
+ // the map. This map uses the allocators to implement
+ // the container functionality.
+ //
+ // The template parameters are the Graph the current Item type and
+ // the Value type of the map.
template
class ArrayMap
: public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
public:
- /// The graph type of the maps.
+ // The graph type of the maps.
typedef _Graph Graph;
- /// The item type of the map.
+ // The item type of the map.
typedef _Item Item;
- /// The reference map tag.
+ // The reference map tag.
typedef True ReferenceMapTag;
- /// The key type of the maps.
+ // The key type of the maps.
typedef _Item Key;
- /// The value type of the map.
+ // The value type of the map.
typedef _Value Value;
- /// The const reference type of the map.
+ // The const reference type of the map.
typedef const _Value& ConstReference;
- /// The reference type of the map.
+ // The reference type of the map.
typedef _Value& Reference;
- /// The notifier type.
+ // The notifier type.
typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
- /// The MapBase of the Map which imlements the core regisitry function.
+ // The MapBase of the Map which imlements the core regisitry function.
typedef typename Notifier::ObserverBase Parent;
@@ -76,7 +76,7 @@
public:
- /// \brief Graph initialized map constructor.
- ///
- /// Graph initialized map constructor.
+ // \brief Graph initialized map constructor.
+ //
+ // Graph initialized map constructor.
explicit ArrayMap(const Graph& graph) {
Parent::attach(graph.notifier(Item()));
@@ -90,7 +90,7 @@
}
- /// \brief Constructor to use default value to initialize the map.
- ///
- /// It constructs a map and initialize all of the the map.
+ // \brief Constructor to use default value to initialize the map.
+ //
+ // It constructs a map and initialize all of the the map.
ArrayMap(const Graph& graph, const Value& value) {
Parent::attach(graph.notifier(Item()));
@@ -104,7 +104,8 @@
}
- /// \brief Constructor to copy a map of the same map type.
- ///
- /// Constructor to copy a map of the same map type.
+ private:
+ // \brief Constructor to copy a map of the same map type.
+ //
+ // Constructor to copy a map of the same map type.
ArrayMap(const ArrayMap& copy) : Parent() {
if (copy.attached()) {
@@ -122,11 +123,11 @@
}
- /// \brief Assign operator.
- ///
- /// This operator assigns for each item in the map the
- /// value mapped to the same item in the copied map.
- /// The parameter map should be indiced with the same
- /// itemset because this assign operator does not change
- /// the container of the map.
+ // \brief Assign operator.
+ //
+ // This operator assigns for each item in the map the
+ // value mapped to the same item in the copied map.
+ // The parameter map should be indiced with the same
+ // itemset because this assign operator does not change
+ // the container of the map.
ArrayMap& operator=(const ArrayMap& cmap) {
return operator=(cmap);
@@ -134,10 +135,10 @@
- /// \brief Template assign operator.
- ///
- /// The given parameter should be conform to the ReadMap
- /// concecpt and could be indiced by the current item set of
- /// the NodeMap. In this case the value for each item
- /// is assigned by the value of the given ReadMap.
+ // \brief Template assign operator.
+ //
+ // The given parameter should be conform to the ReadMap
+ // concecpt and could be indiced by the current item set of
+ // the NodeMap. In this case the value for each item
+ // is assigned by the value of the given ReadMap.
template
ArrayMap& operator=(const CMap& cmap) {
@@ -151,7 +152,8 @@
}
- /// \brief The destructor of the map.
- ///
- /// The destructor of the map.
+ public:
+ // \brief The destructor of the map.
+ //
+ // The destructor of the map.
virtual ~ArrayMap() {
if (attached()) {
@@ -169,8 +171,8 @@
public:
- /// \brief The subscript operator.
- ///
- /// The subscript operator. The map can be subscripted by the
- /// actual keys of the graph.
+ // \brief The subscript operator.
+ //
+ // The subscript operator. The map can be subscripted by the
+ // actual keys of the graph.
Value& operator[](const Key& key) {
int id = Parent::notifier()->id(key);
@@ -178,8 +180,8 @@
}
- /// \brief The const subscript operator.
- ///
- /// The const subscript operator. The map can be subscripted by the
- /// actual keys of the graph.
+ // \brief The const subscript operator.
+ //
+ // The const subscript operator. The map can be subscripted by the
+ // actual keys of the graph.
const Value& operator[](const Key& key) const {
int id = Parent::notifier()->id(key);
@@ -187,8 +189,8 @@
}
- /// \brief Setter function of the map.
- ///
- /// Setter function of the map. Equivalent with map[key] = val.
- /// This is a compatibility feature with the not dereferable maps.
+ // \brief Setter function of the map.
+ //
+ // Setter function of the map. Equivalent with map[key] = val.
+ // This is a compatibility feature with the not dereferable maps.
void set(const Key& key, const Value& val) {
(*this)[key] = val;
@@ -197,8 +199,8 @@
protected:
- /// \brief Adds a new key to the map.
- ///
- /// It adds a new key to the map. It called by the observer notifier
- /// and it overrides the add() member function of the observer base.
+ // \brief Adds a new key to the map.
+ //
+ // It adds a new key to the map. It called by the observer notifier
+ // and it overrides the add() member function of the observer base.
virtual void add(const Key& key) {
Notifier* nf = Parent::notifier();
@@ -225,8 +227,8 @@
}
- /// \brief Adds more new keys to the map.
- ///
- /// It adds more new keys to the map. It called by the observer notifier
- /// and it overrides the add() member function of the observer base.
+ // \brief Adds more new keys to the map.
+ //
+ // It adds more new keys to the map. It called by the observer notifier
+ // and it overrides the add() member function of the observer base.
virtual void add(const std::vector& keys) {
Notifier* nf = Parent::notifier();
@@ -269,8 +271,8 @@
}
- /// \brief Erase a key from the map.
- ///
- /// Erase a key from the map. It called by the observer notifier
- /// and it overrides the erase() member function of the observer base.
+ // \brief Erase a key from the map.
+ //
+ // Erase a key from the map. It called by the observer notifier
+ // and it overrides the erase() member function of the observer base.
virtual void erase(const Key& key) {
int id = Parent::notifier()->id(key);
@@ -278,8 +280,8 @@
}
- /// \brief Erase more keys from the map.
- ///
- /// Erase more keys from the map. It called by the observer notifier
- /// and it overrides the erase() member function of the observer base.
+ // \brief Erase more keys from the map.
+ //
+ // Erase more keys from the map. It called by the observer notifier
+ // and it overrides the erase() member function of the observer base.
virtual void erase(const std::vector& keys) {
for (int i = 0; i < int(keys.size()); ++i) {
@@ -289,8 +291,8 @@
}
- /// \brief Buildes the map.
- ///
- /// It buildes the map. It called by the observer notifier
- /// and it overrides the build() member function of the observer base.
+ // \brief Buildes the map.
+ //
+ // It buildes the map. It called by the observer notifier
+ // and it overrides the build() member function of the observer base.
virtual void build() {
Notifier* nf = Parent::notifier();
@@ -303,8 +305,8 @@
}
- /// \brief Clear the map.
- ///
- /// It erase all items from the map. It called by the observer notifier
- /// and it overrides the clear() member function of the observer base.
+ // \brief Clear the map.
+ //
+ // It erase all items from the map. It called by the observer notifier
+ // and it overrides the clear() member function of the observer base.
virtual void clear() {
Notifier* nf = Parent::notifier();
Index: lemon/bits/base_extender.h
===================================================================
--- lemon/bits/base_extender.h (revision 220)
+++ lemon/bits/base_extender.h (revision 318)
@@ -29,12 +29,12 @@
#include
-///\ingroup digraphbits
-///\file
-///\brief Extenders for the digraph types
+//\ingroup digraphbits
+//\file
+//\brief Extenders for the digraph types
namespace lemon {
- /// \ingroup digraphbits
- ///
- /// \brief BaseDigraph to BaseGraph extender
+ // \ingroup digraphbits
+ //
+ // \brief BaseDigraph to BaseGraph extender
template
class UndirDigraphExtender : public Base {
@@ -60,5 +60,5 @@
Arc() {}
- /// Invalid arc constructor
+ // Invalid arc constructor
Arc(Invalid i) : Edge(i), forward(true) {}
@@ -75,36 +75,36 @@
};
-
-
- using Parent::source;
-
- /// Source of the given Arc.
+ // First node of the edge
+ Node u(const Edge &e) const {
+ return Parent::source(e);
+ }
+
+ // Source of the given arc
Node source(const Arc &e) const {
return e.forward ? Parent::source(e) : Parent::target(e);
}
- using Parent::target;
-
- /// Target of the given Arc.
+ // Second node of the edge
+ Node v(const Edge &e) const {
+ return Parent::target(e);
+ }
+
+ // Target of the given arc
Node target(const Arc &e) const {
return e.forward ? Parent::target(e) : Parent::source(e);
}
- /// \brief Directed arc from an edge.
- ///
- /// Returns a directed arc corresponding to the specified Edge.
- /// If the given bool is true the given edge and the
- /// returned arc have the same source node.
- static Arc direct(const Edge &ue, bool d) {
- return Arc(ue, d);
- }
-
- /// Returns whether the given directed arc is same orientation as the
- /// corresponding edge.
- ///
- /// \todo reference to the corresponding point of the undirected digraph
- /// concept. "What does the direction of an edge mean?"
- static bool direction(const Arc &e) { return e.forward; }
-
+ // \brief Directed arc from an edge.
+ //
+ // Returns a directed arc corresponding to the specified edge.
+ // If the given bool is true, the first node of the given edge and
+ // the source node of the returned arc are the same.
+ static Arc direct(const Edge &e, bool d) {
+ return Arc(e, d);
+ }
+
+ // Returns whether the given directed arc has the same orientation
+ // as the corresponding edge.
+ static bool direction(const Arc &a) { return a.forward; }
using Parent::first;
@@ -229,5 +229,4 @@
return Parent::maxArcId();
}
-
int arcNum() const {
@@ -300,10 +299,10 @@
Red() {}
Red(const Node& node) : Node(node) {
- LEMON_ASSERT(Parent::red(node) || node == INVALID,
- typename Parent::NodeSetError());
+ LEMON_DEBUG(Parent::red(node) || node == INVALID,
+ typename Parent::NodeSetError());
}
Red& operator=(const Node& node) {
- LEMON_ASSERT(Parent::red(node) || node == INVALID,
- typename Parent::NodeSetError());
+ LEMON_DEBUG(Parent::red(node) || node == INVALID,
+ typename Parent::NodeSetError());
Node::operator=(node);
return *this;
@@ -332,10 +331,10 @@
Blue() {}
Blue(const Node& node) : Node(node) {
- LEMON_ASSERT(Parent::blue(node) || node == INVALID,
- typename Parent::NodeSetError());
+ LEMON_DEBUG(Parent::blue(node) || node == INVALID,
+ typename Parent::NodeSetError());
}
Blue& operator=(const Node& node) {
- LEMON_ASSERT(Parent::blue(node) || node == INVALID,
- typename Parent::NodeSetError());
+ LEMON_DEBUG(Parent::blue(node) || node == INVALID,
+ typename Parent::NodeSetError());
Node::operator=(node);
return *this;
Index: lemon/bits/bezier.h
===================================================================
--- lemon/bits/bezier.h (revision 209)
+++ lemon/bits/bezier.h (revision 318)
@@ -20,9 +20,9 @@
#define LEMON_BEZIER_H
-///\ingroup misc
-///\file
-///\brief Classes to compute with Bezier curves.
-///
-///Up to now this file is used internally by \ref graph_to_eps.h
+//\ingroup misc
+//\file
+//\brief Classes to compute with Bezier curves.
+//
+//Up to now this file is used internally by \ref graph_to_eps.h
#include
Index: lemon/bits/default_map.h
===================================================================
--- lemon/bits/default_map.h (revision 209)
+++ lemon/bits/default_map.h (revision 318)
@@ -20,12 +20,11 @@
#define LEMON_BITS_DEFAULT_MAP_H
-
#include
#include
//#include
-///\ingroup graphbits
-///\file
-///\brief Graph maps that construct and destruct their elements dynamically.
+//\ingroup graphbits
+//\file
+//\brief Graph maps that construct and destruct their elements dynamically.
namespace lemon {
@@ -150,5 +149,5 @@
// #endif
- /// \e
+ // DefaultMap class
template
class DefaultMap
Index: lemon/bits/enable_if.h
===================================================================
--- lemon/bits/enable_if.h (revision 220)
+++ lemon/bits/enable_if.h (revision 318)
@@ -36,27 +36,27 @@
#define LEMON_BITS_ENABLE_IF_H
-///\file
-///\brief Miscellaneous basic utilities
+//\file
+//\brief Miscellaneous basic utilities
namespace lemon
{
- /// Basic type for defining "tags". A "YES" condition for \c enable_if.
+ // Basic type for defining "tags". A "YES" condition for \c enable_if.
- /// Basic type for defining "tags". A "YES" condition for \c enable_if.
- ///
- ///\sa False
+ // Basic type for defining "tags". A "YES" condition for \c enable_if.
+ //
+ //\sa False
struct True {
- ///\e
+ //\e
static const bool value = true;
};
- /// Basic type for defining "tags". A "NO" condition for \c enable_if.
+ // Basic type for defining "tags". A "NO" condition for \c enable_if.
- /// Basic type for defining "tags". A "NO" condition for \c enable_if.
- ///
- ///\sa True
+ // Basic type for defining "tags". A "NO" condition for \c enable_if.
+ //
+ //\sa True
struct False {
- ///\e
+ //\e
static const bool value = false;
};
Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h (revision 220)
+++ lemon/bits/graph_extender.h (revision 318)
@@ -28,12 +28,12 @@
#include
-///\ingroup graphbits
-///\file
-///\brief Extenders for the digraph types
+//\ingroup graphbits
+//\file
+//\brief Extenders for the digraph types
namespace lemon {
- /// \ingroup graphbits
- ///
- /// \brief Extender for the Digraphs
+ // \ingroup graphbits
+ //
+ // \brief Extender for the Digraphs
template
class DigraphExtender : public Base {
@@ -187,28 +187,28 @@
};
- /// \brief Base node of the iterator
- ///
- /// Returns the base node (i.e. the source in this case) of the iterator
+ // \brief Base node of the iterator
+ //
+ // Returns the base node (i.e. the source in this case) of the iterator
Node baseNode(const OutArcIt &arc) const {
return Parent::source(arc);
}
- /// \brief Running node of the iterator
- ///
- /// Returns the running node (i.e. the target in this case) of the
- /// iterator
+ // \brief Running node of the iterator
+ //
+ // Returns the running node (i.e. the target in this case) of the
+ // iterator
Node runningNode(const OutArcIt &arc) const {
return Parent::target(arc);
}
- /// \brief Base node of the iterator
- ///
- /// Returns the base node (i.e. the target in this case) of the iterator
+ // \brief Base node of the iterator
+ //
+ // Returns the base node (i.e. the target in this case) of the iterator
Node baseNode(const InArcIt &arc) const {
return Parent::target(arc);
}
- /// \brief Running node of the iterator
- ///
- /// Returns the running node (i.e. the source in this case) of the
- /// iterator
+ // \brief Running node of the iterator
+ //
+ // Returns the running node (i.e. the source in this case) of the
+ // iterator
Node runningNode(const InArcIt &arc) const {
return Parent::source(arc);
@@ -228,4 +228,5 @@
: Parent(digraph, value) {}
+ private:
NodeMap& operator=(const NodeMap& cmap) {
return operator=(cmap);
@@ -252,4 +253,5 @@
: Parent(digraph, value) {}
+ private:
ArcMap& operator=(const ArcMap& cmap) {
return operator=(cmap);
@@ -324,7 +326,7 @@
};
- /// \ingroup _graphbits
- ///
- /// \brief Extender for the Graphs
+ // \ingroup _graphbits
+ //
+ // \brief Extender for the Graphs
template
class GraphExtender : public Base {
@@ -554,41 +556,41 @@
};
- /// \brief Base node of the iterator
- ///
- /// Returns the base node (ie. the source in this case) of the iterator
+ // \brief Base node of the iterator
+ //
+ // Returns the base node (ie. the source in this case) of the iterator
Node baseNode(const OutArcIt &arc) const {
return Parent::source(static_cast(arc));
}
- /// \brief Running node of the iterator
- ///
- /// Returns the running node (ie. the target in this case) of the
- /// iterator
+ // \brief Running node of the iterator
+ //
+ // Returns the running node (ie. the target in this case) of the
+ // iterator
Node runningNode(const OutArcIt &arc) const {
return Parent::target(static_cast(arc));
}
- /// \brief Base node of the iterator
- ///
- /// Returns the base node (ie. the target in this case) of the iterator
+ // \brief Base node of the iterator
+ //
+ // Returns the base node (ie. the target in this case) of the iterator
Node baseNode(const InArcIt &arc) const {
return Parent::target(static_cast(arc));
}
- /// \brief Running node of the iterator
- ///
- /// Returns the running node (ie. the source in this case) of the
- /// iterator
+ // \brief Running node of the iterator
+ //
+ // Returns the running node (ie. the source in this case) of the
+ // iterator
Node runningNode(const InArcIt &arc) const {
return Parent::source(static_cast(arc));
}
- /// Base node of the iterator
- ///
- /// Returns the base node of the iterator
+ // Base node of the iterator
+ //
+ // Returns the base node of the iterator
Node baseNode(const IncEdgeIt &edge) const {
return edge._direction ? u(edge) : v(edge);
}
- /// Running node of the iterator
- ///
- /// Returns the running node of the iterator
+ // Running node of the iterator
+ //
+ // Returns the running node of the iterator
Node runningNode(const IncEdgeIt &edge) const {
return edge._direction ? v(edge) : u(edge);
@@ -609,4 +611,5 @@
: Parent(graph, value) {}
+ private:
NodeMap& operator=(const NodeMap& cmap) {
return operator=(cmap);
@@ -633,4 +636,5 @@
: Parent(graph, value) {}
+ private:
ArcMap& operator=(const ArcMap& cmap) {
return operator=(cmap);
@@ -658,4 +662,5 @@
: Parent(graph, value) {}
+ private:
EdgeMap& operator=(const EdgeMap& cmap) {
return operator=(cmap);
Index: lemon/bits/map_extender.h
===================================================================
--- lemon/bits/map_extender.h (revision 209)
+++ lemon/bits/map_extender.h (revision 318)
@@ -27,12 +27,12 @@
#include
-///\file
-///\brief Extenders for iterable maps.
+//\file
+//\brief Extenders for iterable maps.
namespace lemon {
- /// \ingroup graphbits
- ///
- /// \brief Extender for maps
+ // \ingroup graphbits
+ //
+ // \brief Extender for maps
template
class MapExtender : public _Map {
@@ -63,4 +63,5 @@
: Parent(graph, value) {}
+ private:
MapExtender& operator=(const MapExtender& cmap) {
return operator=(cmap);
@@ -73,4 +74,5 @@
}
+ public:
class MapIt : public Item {
public:
@@ -170,7 +172,7 @@
};
- /// \ingroup graphbits
- ///
- /// \brief Extender for maps which use a subset of the items.
+ // \ingroup graphbits
+ //
+ // \brief Extender for maps which use a subset of the items.
template
class SubMapExtender : public _Map {
@@ -201,4 +203,5 @@
: Parent(_graph, _value), graph(_graph) {}
+ private:
SubMapExtender& operator=(const SubMapExtender& cmap) {
return operator=(cmap);
@@ -215,4 +218,5 @@
}
+ public:
class MapIt : public Item {
public:
Index: lemon/bits/traits.h
===================================================================
--- lemon/bits/traits.h (revision 220)
+++ lemon/bits/traits.h (revision 318)
@@ -20,7 +20,7 @@
#define LEMON_BITS_TRAITS_H
-///\file
-///\brief Traits for graphs and maps
-///
+//\file
+//\brief Traits for graphs and maps
+//
#include
Index: lemon/bits/vector_map.h
===================================================================
--- lemon/bits/vector_map.h (revision 220)
+++ lemon/bits/vector_map.h (revision 318)
@@ -29,22 +29,21 @@
#include
-///\ingroup graphbits
-///
-///\file
-///\brief Vector based graph maps.
+//\ingroup graphbits
+//
+//\file
+//\brief Vector based graph maps.
namespace lemon {
- /// \ingroup graphbits
- ///
- /// \brief Graph map based on the std::vector storage.
- ///
- /// The VectorMap template class is graph map structure what
- /// automatically updates the map when a key is added to or erased from
- /// the map. This map type uses the std::vector to store the values.
- ///
- /// \tparam _Notifier The AlterationNotifier that will notify this map.
- /// \tparam _Item The item type of the graph items.
- /// \tparam _Value The value type of the map.
- /// \todo Fix the doc: there is _Graph parameter instead of _Notifier.
+ // \ingroup graphbits
+ //
+ // \brief Graph map based on the std::vector storage.
+ //
+ // The VectorMap template class is graph map structure what
+ // automatically updates the map when a key is added to or erased from
+ // the map. This map type uses the std::vector to store the values.
+ //
+ // \tparam _Graph The graph this map is attached to.
+ // \tparam _Item The item type of the graph items.
+ // \tparam _Value The value type of the map.
template
class VectorMap
@@ -52,39 +51,39 @@
private:
- /// The container type of the map.
+ // The container type of the map.
typedef std::vector<_Value> Container;
public:
- /// The graph type of the map.
+ // The graph type of the map.
typedef _Graph Graph;
- /// The item type of the map.
+ // The item type of the map.
typedef _Item Item;
- /// The reference map tag.
+ // The reference map tag.
typedef True ReferenceMapTag;
- /// The key type of the map.
+ // The key type of the map.
typedef _Item Key;
- /// The value type of the map.
+ // The value type of the map.
typedef _Value Value;
- /// The notifier type.
+ // The notifier type.
typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
- /// The map type.
+ // The map type.
typedef VectorMap Map;
- /// The base class of the map.
+ // The base class of the map.
typedef typename Notifier::ObserverBase Parent;
- /// The reference type of the map;
+ // The reference type of the map;
typedef typename Container::reference Reference;
- /// The const reference type of the map;
+ // The const reference type of the map;
typedef typename Container::const_reference ConstReference;
- /// \brief Constructor to attach the new map into the notifier.
- ///
- /// It constructs a map and attachs it into the notifier.
- /// It adds all the items of the graph to the map.
+ // \brief Constructor to attach the new map into the notifier.
+ //
+ // It constructs a map and attachs it into the notifier.
+ // It adds all the items of the graph to the map.
VectorMap(const Graph& graph) {
Parent::attach(graph.notifier(Item()));
@@ -92,8 +91,8 @@
}
- /// \brief Constructor uses given value to initialize the map.
- ///
- /// It constructs a map uses a given value to initialize the map.
- /// It adds all the items of the graph to the map.
+ // \brief Constructor uses given value to initialize the map.
+ //
+ // It constructs a map uses a given value to initialize the map.
+ // It adds all the items of the graph to the map.
VectorMap(const Graph& graph, const Value& value) {
Parent::attach(graph.notifier(Item()));
@@ -101,7 +100,8 @@
}
- /// \brief Copy constructor
- ///
- /// Copy constructor.
+ private:
+ // \brief Copy constructor
+ //
+ // Copy constructor.
VectorMap(const VectorMap& _copy) : Parent() {
if (_copy.attached()) {
@@ -111,11 +111,11 @@
}
- /// \brief Assign operator.
- ///
- /// This operator assigns for each item in the map the
- /// value mapped to the same item in the copied map.
- /// The parameter map should be indiced with the same
- /// itemset because this assign operator does not change
- /// the container of the map.
+ // \brief Assign operator.
+ //
+ // This operator assigns for each item in the map the
+ // value mapped to the same item in the copied map.
+ // The parameter map should be indiced with the same
+ // itemset because this assign operator does not change
+ // the container of the map.
VectorMap& operator=(const VectorMap& cmap) {
return operator=(cmap);
@@ -123,10 +123,10 @@
- /// \brief Template assign operator.
- ///
- /// The given parameter should be conform to the ReadMap
- /// concecpt and could be indiced by the current item set of
- /// the NodeMap. In this case the value for each item
- /// is assigned by the value of the given ReadMap.
+ // \brief Template assign operator.
+ //
+ // The given parameter should be conform to the ReadMap
+ // concecpt and could be indiced by the current item set of
+ // the NodeMap. In this case the value for each item
+ // is assigned by the value of the given ReadMap.
template
VectorMap& operator=(const CMap& cmap) {
@@ -142,16 +142,16 @@
public:
- /// \brief The subcript operator.
- ///
- /// The subscript operator. The map can be subscripted by the
- /// actual items of the graph.
+ // \brief The subcript operator.
+ //
+ // The subscript operator. The map can be subscripted by the
+ // actual items of the graph.
Reference operator[](const Key& key) {
return container[Parent::notifier()->id(key)];
}
- /// \brief The const subcript operator.
- ///
- /// The const subscript operator. The map can be subscripted by the
- /// actual items of the graph.
+ // \brief The const subcript operator.
+ //
+ // The const subscript operator. The map can be subscripted by the
+ // actual items of the graph.
ConstReference operator[](const Key& key) const {
return container[Parent::notifier()->id(key)];
@@ -159,7 +159,7 @@
- /// \brief The setter function of the map.
- ///
- /// It the same as operator[](key) = value expression.
+ // \brief The setter function of the map.
+ //
+ // It the same as operator[](key) = value expression.
void set(const Key& key, const Value& value) {
(*this)[key] = value;
@@ -168,8 +168,8 @@
protected:
- /// \brief Adds a new key to the map.
- ///
- /// It adds a new key to the map. It called by the observer notifier
- /// and it overrides the add() member function of the observer base.
+ // \brief Adds a new key to the map.
+ //
+ // It adds a new key to the map. It called by the observer notifier
+ // and it overrides the add() member function of the observer base.
virtual void add(const Key& key) {
int id = Parent::notifier()->id(key);
@@ -179,8 +179,8 @@
}
- /// \brief Adds more new keys to the map.
- ///
- /// It adds more new keys to the map. It called by the observer notifier
- /// and it overrides the add() member function of the observer base.
+ // \brief Adds more new keys to the map.
+ //
+ // It adds more new keys to the map. It called by the observer notifier
+ // and it overrides the add() member function of the observer base.
virtual void add(const std::vector& keys) {
int max = container.size() - 1;
@@ -194,16 +194,16 @@
}
- /// \brief Erase a key from the map.
- ///
- /// Erase a key from the map. It called by the observer notifier
- /// and it overrides the erase() member function of the observer base.
+ // \brief Erase a key from the map.
+ //
+ // Erase a key from the map. It called by the observer notifier
+ // and it overrides the erase() member function of the observer base.
virtual void erase(const Key& key) {
container[Parent::notifier()->id(key)] = Value();
}
- /// \brief Erase more keys from the map.
- ///
- /// Erase more keys from the map. It called by the observer notifier
- /// and it overrides the erase() member function of the observer base.
+ // \brief Erase more keys from the map.
+ //
+ // Erase more keys from the map. It called by the observer notifier
+ // and it overrides the erase() member function of the observer base.
virtual void erase(const std::vector& keys) {
for (int i = 0; i < int(keys.size()); ++i) {
@@ -212,8 +212,8 @@
}
- /// \brief Buildes the map.
- ///
- /// It buildes the map. It called by the observer notifier
- /// and it overrides the build() member function of the observer base.
+ // \brief Buildes the map.
+ //
+ // It buildes the map. It called by the observer notifier
+ // and it overrides the build() member function of the observer base.
virtual void build() {
int size = Parent::notifier()->maxId() + 1;
@@ -222,8 +222,8 @@
}
- /// \brief Clear the map.
- ///
- /// It erase all items from the map. It called by the observer notifier
- /// and it overrides the clear() member function of the observer base.
+ // \brief Clear the map.
+ //
+ // It erase all items from the map. It called by the observer notifier
+ // and it overrides the clear() member function of the observer base.
virtual void clear() {
container.clear();
Index: lemon/color.h
===================================================================
--- lemon/color.h (revision 209)
+++ lemon/color.h (revision 317)
@@ -93,5 +93,5 @@
extern const Color DARK_CYAN;
- ///Map ints to different \ref Color "Color"s
+ ///Map ints to different Colors
///This map assigns one of the predefined \ref Color "Color"s to
Index: lemon/concept_check.h
===================================================================
--- lemon/concept_check.h (revision 209)
+++ lemon/concept_check.h (revision 285)
@@ -17,26 +17,10 @@
*/
-// This file contains a modified version of the concept checking
-// utility from BOOST.
-// See the appropriate copyright notice below.
-
-// (C) Copyright Jeremy Siek 2000.
-// Distributed under the Boost Software License, Version 1.0. (See
-// accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-//
-// Revision History:
-// 05 May 2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
-// 02 April 2001: Removed limits header altogether. (Jeremy Siek)
-// 01 April 2001: Modified to use new header. (JMaddock)
-//
-
-// See http://www.boost.org/libs/concept_check for documentation.
+// The contents of this file was inspired by the concept checking
+// utility of the BOOST library (http://www.boost.org).
///\file
///\brief Basic utilities for concept checking.
///
-///\todo Are we still using BOOST concept checking utility?
-///Is the BOOST copyright notice necessary?
#ifndef LEMON_CONCEPT_CHECK_H
Index: lemon/concepts/digraph.h
===================================================================
--- lemon/concepts/digraph.h (revision 220)
+++ lemon/concepts/digraph.h (revision 263)
@@ -435,4 +435,5 @@
NodeMap(const Digraph&, T) { }
+ private:
///Copy constructor
NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
@@ -457,4 +458,5 @@
///\e
ArcMap(const Digraph&, T) { }
+ private:
///Copy constructor
ArcMap(const ArcMap& em) : ReadWriteMap(em) { }
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h (revision 220)
+++ lemon/concepts/graph.h (revision 263)
@@ -513,4 +513,5 @@
NodeMap(const Graph&, T) { }
+ private:
///Copy constructor
NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
@@ -536,4 +537,5 @@
///\e
ArcMap(const Graph&, T) { }
+ private:
///Copy constructor
ArcMap(const ArcMap& em) : ReadWriteMap(em) { }
@@ -559,4 +561,5 @@
///\e
EdgeMap(const Graph&, T) { }
+ private:
///Copy constructor
EdgeMap(const EdgeMap& em) : ReadWriteMap(em) {}
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h (revision 220)
+++ lemon/concepts/graph_components.h (revision 317)
@@ -983,5 +983,5 @@
///
/// This class describes the common interface of the graph maps
- /// (NodeMap, ArcMap), that is \ref maps-page "maps" which can be used to
+ /// (NodeMap, ArcMap), that is maps that can be used to
/// associate data to graph descriptors (nodes or arcs).
template
@@ -1006,4 +1006,6 @@
/// Construct a new map for the graph and initalise the values.
GraphMap(const Graph&, const Value&) {}
+
+ private:
/// \brief Copy constructor.
///
@@ -1022,4 +1024,5 @@
}
+ public:
template
struct Constraints {
@@ -1031,11 +1034,12 @@
_Map a2(g,t);
// Copy constructor.
- _Map b(c);
-
- ReadMap cmap;
- b = cmap;
-
+ // _Map b(c);
+
+ // ReadMap cmap;
+ // b = cmap;
+
+ ignore_unused_variable_warning(a);
ignore_unused_variable_warning(a2);
- ignore_unused_variable_warning(b);
+ // ignore_unused_variable_warning(b);
}
@@ -1083,4 +1087,5 @@
: Parent(digraph, value) {}
+ private:
/// \brief Copy constructor.
///
@@ -1120,4 +1125,5 @@
: Parent(digraph, value) {}
+ private:
/// \brief Copy constructor.
///
@@ -1216,4 +1222,5 @@
: Parent(graph, value) {}
+ private:
/// \brief Copy constructor.
///
Index: lemon/concepts/heap.h
===================================================================
--- lemon/concepts/heap.h (revision 220)
+++ lemon/concepts/heap.h (revision 290)
@@ -130,5 +130,4 @@
/// Otherwise it inserts the given item with the given priority.
///
- /// It may throw an \ref UnderflowPriorityException.
/// \param i The item.
/// \param p The priority.
Index: lemon/concepts/maps.h
===================================================================
--- lemon/concepts/maps.h (revision 220)
+++ lemon/concepts/maps.h (revision 318)
@@ -23,5 +23,5 @@
#include
-///\ingroup concept
+///\ingroup map_concepts
///\file
///\brief The concept of maps.
@@ -31,5 +31,5 @@
namespace concepts {
- /// \addtogroup concept
+ /// \addtogroup map_concepts
/// @{
Index: lemon/concepts/path.h
===================================================================
--- lemon/concepts/path.h (revision 220)
+++ lemon/concepts/path.h (revision 281)
@@ -21,5 +21,4 @@
///\brief Classes for representing paths in digraphs.
///
-///\todo Iterators have obsolete style
#ifndef LEMON_CONCEPT_PATH_H
@@ -67,5 +66,8 @@
/// \brief Template assigment
template
- Path& operator=(const CPath& cpath) {}
+ Path& operator=(const CPath& cpath) {
+ ignore_unused_variable_warning(cpath);
+ return *this;
+ }
/// Length of the path ie. the number of arcs in the path.
@@ -78,5 +80,5 @@
void clear() {}
- /// \brief Lemon style iterator for path arcs
+ /// \brief LEMON style iterator for path arcs
///
/// This class is used to iterate on the arcs of the paths.
@@ -201,5 +203,5 @@
/// If we would like to give back a real path from these
/// algorithms then we should create a temporarly path object. In
- /// Lemon such algorithms gives back a path dumper what can
+ /// LEMON such algorithms gives back a path dumper what can
/// assigned to a real path and the dumpers can be implemented as
/// an adaptor class to the predecessor map.
@@ -233,5 +235,5 @@
typedef False RevPathTag;
- /// \brief Lemon style iterator for path arcs
+ /// \brief LEMON style iterator for path arcs
///
/// This class is used to iterate on the arcs of the paths.
@@ -260,5 +262,5 @@
};
- /// \brief Lemon style iterator for path arcs
+ /// \brief LEMON style iterator for path arcs
///
/// This class is used to iterate on the arcs of the paths in
Index: lemon/core.h
===================================================================
--- lemon/core.h (revision 220)
+++ lemon/core.h (revision 327)
@@ -25,7 +25,12 @@
#include
#include
+#include
///\file
///\brief LEMON core utilities.
+///
+///This header file contains core utilities for LEMON.
+///It is automatically included by all graph types, therefore it usually
+///do not have to be included directly.
namespace lemon {
@@ -55,8 +60,8 @@
/// @{
- ///Creates convenience typedefs for the digraph types and iterators
-
- ///This \c \#define creates convenience typedefs for the following types
- ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
+ ///Create convenience typedefs for the digraph types and iterators
+
+ ///This \c \#define creates convenient type definitions for the following
+ ///types of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
@@ -79,5 +84,5 @@
typedef Digraph::ArcMap DoubleArcMap
- ///Creates convenience typedefs for the digraph types and iterators
+ ///Create convenience typedefs for the digraph types and iterators
///\see DIGRAPH_TYPEDEFS
@@ -99,7 +104,7 @@
typedef typename Digraph::template ArcMap DoubleArcMap
- ///Creates convenience typedefs for the graph types and iterators
-
- ///This \c \#define creates the same convenience typedefs as defined
+ ///Create convenience typedefs for the graph types and iterators
+
+ ///This \c \#define creates the same convenient type definitions as defined
///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
@@ -107,5 +112,5 @@
///
///\note If the graph type is a dependent type, ie. the graph type depend
- ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
+ ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
///macro.
#define GRAPH_TYPEDEFS(Graph) \
@@ -118,5 +123,5 @@
typedef Graph::EdgeMap DoubleEdgeMap
- ///Creates convenience typedefs for the graph types and iterators
+ ///Create convenience typedefs for the graph types and iterators
///\see GRAPH_TYPEDEFS
@@ -133,8 +138,8 @@
typedef typename Graph::template EdgeMap DoubleEdgeMap
- /// \brief Function to count the items in the graph.
- ///
- /// This function counts the items (nodes, arcs etc) in the graph.
- /// The complexity of the function is O(n) because
+ /// \brief Function to count the items in a graph.
+ ///
+ /// This function counts the items (nodes, arcs etc.) in a graph.
+ /// The complexity of the function is linear because
/// it iterates on all of the items.
template
@@ -173,9 +178,9 @@
///
/// This function counts the nodes in the graph.
- /// The complexity of the function is O(n) but for some
- /// graph structures it is specialized to run in O(1).
- ///
- /// If the graph contains a \e nodeNum() member function and a
- /// \e NodeNumTag tag then this function calls directly the member
+ /// The complexity of the function is O(n), but for some
+ /// graph structures it is specialized to run in O(1).
+ ///
+ /// \note If the graph contains a \c nodeNum() member function and a
+ /// \c NodeNumTag tag then this function calls directly the member
/// function to query the cardinality of the node set.
template
@@ -209,9 +214,9 @@
///
/// This function counts the arcs in the graph.
- /// The complexity of the function is O(e) but for some
- /// graph structures it is specialized to run in O(1).
- ///
- /// If the graph contains a \e arcNum() member function and a
- /// \e EdgeNumTag tag then this function calls directly the member
+ /// The complexity of the function is O(m), but for some
+ /// graph structures it is specialized to run in O(1).
+ ///
+ /// \note If the graph contains a \c arcNum() member function and a
+ /// \c ArcNumTag tag then this function calls directly the member
/// function to query the cardinality of the arc set.
template
@@ -221,4 +226,5 @@
// Edge counting:
+
namespace _core_bits {
@@ -244,9 +250,9 @@
///
/// This function counts the edges in the graph.
- /// The complexity of the function is O(m) but for some
- /// graph structures it is specialized to run in O(1).
- ///
- /// If the graph contains a \e edgeNum() member function and a
- /// \e EdgeNumTag tag then this function calls directly the member
+ /// The complexity of the function is O(m), but for some
+ /// graph structures it is specialized to run in O(1).
+ ///
+ /// \note If the graph contains a \c edgeNum() member function and a
+ /// \c EdgeNumTag tag then this function calls directly the member
/// function to query the cardinality of the edge set.
template
@@ -269,8 +275,8 @@
///
/// This function counts the number of the out-arcs from node \c n
- /// in the graph.
+ /// in the graph \c g.
template
- inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
- return countNodeDegree(_g, _n);
+ inline int countOutArcs(const Graph& g, const typename Graph::Node& n) {
+ return countNodeDegree(g, n);
}
@@ -278,8 +284,8 @@
///
/// This function counts the number of the in-arcs to node \c n
- /// in the graph.
+ /// in the graph \c g.
template
- inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
- return countNodeDegree(_g, _n);
+ inline int countInArcs(const Graph& g, const typename Graph::Node& n) {
+ return countNodeDegree(g, n);
}
@@ -287,8 +293,8 @@
///
/// This function counts the number of the inc-edges to node \c n
- /// in the graph.
+ /// in the undirected graph \c g.
template
- inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
- return countNodeDegree(_g, _n);
+ inline int countIncEdges(const Graph& g, const typename Graph::Node& n) {
+ return countNodeDegree(g, n);
}
@@ -304,10 +310,10 @@
template
+ typename FromMap, typename ToMap>
class MapCopy : public MapCopyBase {
public:
- MapCopy(ToMap& tmap, const FromMap& map)
- : _tmap(tmap), _map(map) {}
+ MapCopy(const FromMap& map, ToMap& tmap)
+ : _map(map), _tmap(tmap) {}
virtual void copy(const Digraph& digraph, const RefMap& refMap) {
@@ -319,6 +325,6 @@
private:
+ const FromMap& _map;
ToMap& _tmap;
- const FromMap& _map;
};
@@ -327,5 +333,5 @@
public:
- ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
+ ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
virtual void copy(const Digraph&, const RefMap& refMap) {
@@ -334,6 +340,6 @@
private:
+ Item _item;
It& _it;
- Item _item;
};
@@ -376,5 +382,5 @@
struct DigraphCopySelector {
template
- static void copy(Digraph &to, const From& from,
+ static void copy(const From& from, Digraph &to,
NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
for (typename From::NodeIt it(from); it != INVALID; ++it) {
@@ -394,5 +400,5 @@
{
template
- static void copy(Digraph &to, const From& from,
+ static void copy(const From& from, Digraph &to,
NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
to.build(from, nodeRefMap, arcRefMap);
@@ -403,5 +409,5 @@
struct GraphCopySelector {
template
- static void copy(Graph &to, const From& from,
+ static void copy(const From& from, Graph &to,
NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
for (typename From::NodeIt it(from); it != INVALID; ++it) {
@@ -421,5 +427,5 @@
{
template
- static void copy(Graph &to, const From& from,
+ static void copy(const From& from, Graph &to,
NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
to.build(from, nodeRefMap, edgeRefMap);
@@ -432,37 +438,37 @@
///
/// Class to copy a digraph to another digraph (duplicate a digraph). The
- /// simplest way of using it is through the \c copyDigraph() function.
- ///
- /// This class not just make a copy of a graph, but it can create
+ /// simplest way of using it is through the \c digraphCopy() function.
+ ///
+ /// This class not only make a copy of a digraph, but it can create
/// references and cross references between the nodes and arcs of
- /// the two graphs, it can copy maps for use with the newly created
- /// graph and copy nodes and arcs.
- ///
- /// To make a copy from a graph, first an instance of DigraphCopy
- /// should be created, then the data belongs to the graph should
+ /// the two digraphs, and it can copy maps to use with the newly created
+ /// digraph.
+ ///
+ /// To make a copy from a digraph, first an instance of DigraphCopy
+ /// should be created, then the data belongs to the digraph should
/// assigned to copy. In the end, the \c run() member should be
/// called.
///
- /// The next code copies a graph with several data:
+ /// The next code copies a digraph with several data:
///\code
- /// DigraphCopy dc(new_graph, orig_graph);
- /// // create a reference for the nodes
+ /// DigraphCopy cg(orig_graph, new_graph);
+ /// // Create references for the nodes
/// OrigGraph::NodeMap nr(orig_graph);
- /// dc.nodeRef(nr);
- /// // create a cross reference (inverse) for the arcs
+ /// cg.nodeRef(nr);
+ /// // Create cross references (inverse) for the arcs
/// NewGraph::ArcMap acr(new_graph);
- /// dc.arcCrossRef(acr);
- /// // copy an arc map
+ /// cg.arcCrossRef(acr);
+ /// // Copy an arc map
/// OrigGraph::ArcMap oamap(orig_graph);
/// NewGraph::ArcMap namap(new_graph);
- /// dc.arcMap(namap, oamap);
- /// // copy a node
+ /// cg.arcMap(oamap, namap);
+ /// // Copy a node
/// OrigGraph::Node on;
/// NewGraph::Node nn;
- /// dc.node(nn, on);
- /// // Executions of copy
- /// dc.run();
+ /// cg.node(on, nn);
+ /// // Execute copying
+ /// cg.run();
///\endcode
- template
+ template
class DigraphCopy {
private:
@@ -479,18 +485,16 @@
typedef typename From::template ArcMap ArcRefMap;
-
public:
-
- /// \brief Constructor for the DigraphCopy.
- ///
- /// It copies the content of the \c _from digraph into the
- /// \c _to digraph.
- DigraphCopy(To& to, const From& from)
+ /// \brief Constructor of DigraphCopy.
+ ///
+ /// Constructor of DigraphCopy for copying the content of the
+ /// \c from digraph into the \c to digraph.
+ DigraphCopy(const From& from, To& to)
: _from(from), _to(to) {}
- /// \brief Destructor of the DigraphCopy
- ///
- /// Destructor of the DigraphCopy
+ /// \brief Destructor of DigraphCopy
+ ///
+ /// Destructor of DigraphCopy.
~DigraphCopy() {
for (int i = 0; i < int(_node_maps.size()); ++i) {
@@ -503,10 +507,10 @@
}
- /// \brief Copies the node references into the given map.
- ///
- /// Copies the node references into the given map. The parameter
- /// should be a map, which key type is the Node type of the source
- /// graph, while the value type is the Node type of the
- /// destination graph.
+ /// \brief Copy the node references into the given map.
+ ///
+ /// This function copies the node references into the given map.
+ /// The parameter should be a map, whose key type is the Node type of
+ /// the source digraph, while the value type is the Node type of the
+ /// destination digraph.
template
DigraphCopy& nodeRef(NodeRef& map) {
@@ -516,10 +520,10 @@
}
- /// \brief Copies the node cross references into the given map.
- ///
- /// Copies the node cross references (reverse references) into
- /// the given map. The parameter should be a map, which key type
- /// is the Node type of the destination graph, while the value type is
- /// the Node type of the source graph.
+ /// \brief Copy the node cross references into the given map.
+ ///
+ /// This function copies the node cross references (reverse references)
+ /// into the given map. The parameter should be a map, whose key type
+ /// is the Node type of the destination digraph, while the value type is
+ /// the Node type of the source digraph.
template
DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
@@ -529,13 +533,15 @@
}
- /// \brief Make copy of the given map.
- ///
- /// Makes copy of the given map for the newly created digraph.
- /// The new map's key type is the destination graph's node type,
- /// and the copied map's key type is the source graph's node type.
- template
- DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
+ /// \brief Make a copy of the given node map.
+ ///
+ /// This function makes a copy of the given node map for the newly
+ /// created digraph.
+ /// The key type of the new map \c tmap should be the Node type of the
+ /// destination digraph, and the key type of the original map \c map
+ /// should be the Node type of the source digraph.
+ template
+ DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
_node_maps.push_back(new _core_bits::MapCopy(tmap, map));
+ NodeRefMap, FromMap, ToMap>(map, tmap));
return *this;
}
@@ -543,14 +549,17 @@
/// \brief Make a copy of the given node.
///
- /// Make a copy of the given node.
- DigraphCopy& node(TNode& tnode, const Node& snode) {
+ /// This function makes a copy of the given node.
+ DigraphCopy& node(const Node& node, TNode& tnode) {
_node_maps.push_back(new _core_bits::ItemCopy(tnode, snode));
- return *this;
- }
-
- /// \brief Copies the arc references into the given map.
- ///
- /// Copies the arc references into the given map.
+ NodeRefMap, TNode>(node, tnode));
+ return *this;
+ }
+
+ /// \brief Copy the arc references into the given map.
+ ///
+ /// This function copies the arc references into the given map.
+ /// The parameter should be a map, whose key type is the Arc type of
+ /// the source digraph, while the value type is the Arc type of the
+ /// destination digraph.
template
DigraphCopy& arcRef(ArcRef& map) {
@@ -560,8 +569,10 @@
}
- /// \brief Copies the arc cross references into the given map.
- ///
- /// Copies the arc cross references (reverse references) into
- /// the given map.
+ /// \brief Copy the arc cross references into the given map.
+ ///
+ /// This function copies the arc cross references (reverse references)
+ /// into the given map. The parameter should be a map, whose key type
+ /// is the Arc type of the destination digraph, while the value type is
+ /// the Arc type of the source digraph.
template
DigraphCopy& arcCrossRef(ArcCrossRef& map) {
@@ -571,14 +582,15 @@
}
- /// \brief Make copy of the given map.
- ///
- /// Makes copy of the given map for the newly created digraph.
- /// The new map's key type is the to digraph's arc type,
- /// and the copied map's key type is the from digraph's arc
- /// type.
- template
- DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
+ /// \brief Make a copy of the given arc map.
+ ///
+ /// This function makes a copy of the given arc map for the newly
+ /// created digraph.
+ /// The key type of the new map \c tmap should be the Arc type of the
+ /// destination digraph, and the key type of the original map \c map
+ /// should be the Arc type of the source digraph.
+ template
+ DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
_arc_maps.push_back(new _core_bits::MapCopy(tmap, map));
+ ArcRefMap, FromMap, ToMap>(map, tmap));
return *this;
}
@@ -586,19 +598,20 @@
/// \brief Make a copy of the given arc.
///
- /// Make a copy of the given arc.
- DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
+ /// This function makes a copy of the given arc.
+ DigraphCopy& arc(const Arc& arc, TArc& tarc) {
_arc_maps.push_back(new _core_bits::ItemCopy(tarc, sarc));
- return *this;
- }
-
- /// \brief Executes the copies.
- ///
- /// Executes the copies.
+ ArcRefMap, TArc>(arc, tarc));
+ return *this;
+ }
+
+ /// \brief Execute copying.
+ ///
+ /// This function executes the copying of the digraph along with the
+ /// copying of the assigned data.
void run() {
NodeRefMap nodeRefMap(_from);
ArcRefMap arcRefMap(_from);
_core_bits::DigraphCopySelector::
- copy(_to, _from, nodeRefMap, arcRefMap);
+ copy(_from, _to, nodeRefMap, arcRefMap);
for (int i = 0; i < int(_node_maps.size()); ++i) {
_node_maps[i]->copy(_from, nodeRefMap);
@@ -611,13 +624,12 @@
protected:
-
const From& _from;
To& _to;
std::vector<_core_bits::MapCopyBase* >
- _node_maps;
+ _node_maps;
std::vector<_core_bits::MapCopyBase* >
- _arc_maps;
+ _arc_maps;
};
@@ -625,20 +637,20 @@
/// \brief Copy a digraph to another digraph.
///
- /// Copy a digraph to another digraph. The complete usage of the
- /// function is detailed in the DigraphCopy class, but a short
- /// example shows a basic work:
+ /// This function copies a digraph to another digraph.
+ /// The complete usage of it is detailed in the DigraphCopy class, but
+ /// a short example shows a basic work:
///\code
- /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
+ /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
///\endcode
///
/// After the copy the \c nr map will contain the mapping from the
/// nodes of the \c from digraph to the nodes of the \c to digraph and
- /// \c ecr will contain the mapping from the arcs of the \c to digraph
+ /// \c acr will contain the mapping from the arcs of the \c to digraph
/// to the arcs of the \c from digraph.
///
/// \see DigraphCopy
- template
- DigraphCopy copyDigraph(To& to, const From& from) {
- return DigraphCopy(to, from);
+ template
+ DigraphCopy digraphCopy(const From& from, To& to) {
+ return DigraphCopy