LEMON/LEMON-main Changeset - r799:6be1f9bd2ac0

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r799:6be1f9bd2ac0

« 796:9cc6e9
« 798:58c330

834:207ba6 »
800:28c7ad »

r799:6be1f9bd2ac0

Wed, 09 Dec 2009 11:14:06

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge #62

0 67 10

merge default

3 files changed:

doc/references.bib

301

CMakeLists.txt

Makefile.am

configure.ac

doc/CMakeLists.txt

doc/Doxyfile.in

doc/Makefile.am

doc/groups.dox

133

doc/mainpage.dox

doc/min_cost_flow.dox

lemon/Makefile.am

lemon/adaptors.h

lemon/bellman_ford.h

lemon/bfs.h

lemon/bits/graph_extender.h

lemon/bits/map_extender.h

lemon/cbc.cc

lemon/cbc.h

lemon/circulation.h

lemon/clp.cc

lemon/clp.h

lemon/concepts/digraph.h

172

171

lemon/concepts/graph.h

344

324

Changeset was too big and was cut off... Show full diff

↑ Collapse diff ↑

doc/references.bib

Show inline comments

 		%%%%% Defining LEMON %%%%%
 		@misc{lemon,
 		  key =          {LEMON},
 		  title =        {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
 		                  {O}ptimization in {N}etworks},
 		  howpublished = {\url{http://lemon.cs.elte.hu/}},
 		  year =         2009
+		}
 		@misc{egres,
 		  key =          {EGRES},
 		  title =        {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on
 		                  {C}ombinatorial {O}ptimization},
 		  url =          {http://www.cs.elte.hu/egres/}
+		}
 		@misc{coinor,
 		  key =          {COIN-OR},
 		  title =        {{COIN-OR} -- {C}omputational {I}nfrastructure for
 		                  {O}perations {R}esearch},
 		  url =          {http://www.coin-or.org/}
+		}
 		%%%%% Other libraries %%%%%%
 		@misc{boost,
 		  key =          {Boost},
 		  title =        {{B}oost {C++} {L}ibraries},
 		  url =          {http://www.boost.org/}
+		}
 		@book{bglbook,
 		  author =       {Jeremy G. Siek and Lee-Quan Lee and Andrew
 		                  Lumsdaine},
 		  title =        {The Boost Graph Library: User Guide and Reference
 		                  Manual},
 		  publisher =    {Addison-Wesley},
 		  year =         2002
+		}
 		@misc{leda,
 		  key =          {LEDA},
 		  title =        {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and
 		                  {A}lgorithms},
 		  url =          {http://www.algorithmic-solutions.com/}
+		}
 		@book{ledabook,
 		  author =       {Kurt Mehlhorn and Stefan N{\"a}her},
 		  title =        {{LEDA}: {A} platform for combinatorial and geometric
 		                  computing},
 		  isbn =         {0-521-56329-1},
 		  publisher =    {Cambridge University Press},
 		  address =      {New York, NY, USA},
 		  year =         1999
+		}
 		%%%%% Tools that LEMON depends on %%%%%
 		@misc{cmake,
 		  key =          {CMake},
 		  title =        {{CMake} -- {C}ross {P}latform {M}ake},
 		  url =          {http://www.cmake.org/}
+		}
 		@misc{doxygen,
 		  key =          {Doxygen},
 		  title =        {{Doxygen} -- {S}ource code documentation generator
 		                  tool},
 		  url =          {http://www.doxygen.org/}
+		}
 		%%%%% LP/MIP libraries %%%%%
 		@misc{glpk,
 		  key =          {GLPK},
 		  title =        {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it},
 		  url =          {http://www.gnu.org/software/glpk/}
+		}
 		@misc{clp,
 		  key =          {Clp},
 		  title =        {{Clp} -- {Coin-Or} {L}inear {P}rogramming},
 		  url =          {http://projects.coin-or.org/Clp/}
+		}
 		@misc{cbc,
 		  key =          {Cbc},
 		  title =        {{Cbc} -- {Coin-Or} {B}ranch and {C}ut},
 		  url =          {http://projects.coin-or.org/Cbc/}
+		}
 		@misc{cplex,
 		  key =          {CPLEX},
 		  title =        {{ILOG} {CPLEX}},
 		  url =          {http://www.ilog.com/}
+		}
 		@misc{soplex,
 		  key =          {SoPlex},
 		  title =        {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented
 		                  {S}implex},
 		  url =          {http://soplex.zib.de/}
+		}
 		%%%%% General books %%%%%
 		@book{amo93networkflows,
 		  author =       {Ravindra K. Ahuja and Thomas L. Magnanti and James
 		                  B. Orlin},
 		  title =        {Network Flows: Theory, Algorithms, and Applications},
 		  publisher =    {Prentice-Hall, Inc.},
 		  year =         1993,
 		  month =        feb,
 		  isbn =         {978-0136175490}
+		}
 		@book{schrijver03combinatorial,
 		  author =       {Alexander Schrijver},
 		  title =        {Combinatorial Optimization: Polyhedra and Efficiency},
 		  publisher =    {Springer-Verlag},
 		  year =         2003,
 		  isbn =         {978-3540443896}
+		}
 		@book{clrs01algorithms,
 		  author =       {Thomas H. Cormen and Charles E. Leiserson and Ronald
 		                  L. Rivest and Clifford Stein},
 		  title =        {Introduction to Algorithms},
 		  publisher =    {The MIT Press},
 		  year =         2001,
 		  edition =      {2nd}
+		}
 		@book{stroustrup00cpp,
 		  author =       {Bjarne Stroustrup},
 		  title =        {The C++ Programming Language},
 		  edition =      {3rd},
 		  publisher =    {Addison-Wesley Professional},
 		  isbn =         0201700735,
 		  month =        {February},
 		  year =         2000
+		}
 		%%%%% Maximum flow algorithms %%%%%
 		@article{edmondskarp72theoretical,
 		  author =       {Jack Edmonds and Richard M. Karp},
 		  title =        {Theoretical improvements in algorithmic efficiency
 		                  for network flow problems},
 		  journal =      {Journal of the ACM},
 		  year =         1972,
 		  volume =       19,
 		  number =       2,
 		  pages =        {248-264}
+		}
 		@article{goldberg88newapproach,
 		  author =       {Andrew V. Goldberg and Robert E. Tarjan},
 		  title =        {A new approach to the maximum flow problem},
 		  journal =      {Journal of the ACM},
 		  year =         1988,
 		  volume =       35,
 		  number =       4,
 		  pages =        {921-940}
+		}
 		@article{dinic70algorithm,
 		  author =       {E. A. Dinic},
 		  title =        {Algorithm for solution of a problem of maximum flow
 		                  in a network with power estimation},
 		  journal =      {Soviet Math. Doklady},
 		  year =         1970,
 		  volume =       11,
 		  pages =        {1277-1280}
+		}
 		@article{goldberg08partial,
 		  author =       {Andrew V. Goldberg},
 		  title =        {The Partial Augment-Relabel Algorithm for the
 		                  Maximum Flow Problem},
 		  journal =      {16th Annual European Symposium on Algorithms},
 		  year =         2008,
 		  pages =        {466-477}
+		}
 		@article{sleator83dynamic,
 		  author =       {Daniel D. Sleator and Robert E. Tarjan},
 		  title =        {A data structure for dynamic trees},
 		  journal =      {Journal of Computer and System Sciences},
 		  year =         1983,
 		  volume =       26,
 		  number =       3,
 		  pages =        {362-391}
+		}
 		%%%%% Minimum mean cycle algorithms %%%%%
 		@article{karp78characterization,
 		  author =       {Richard M. Karp},
 		  title =        {A characterization of the minimum cycle mean in a
 		                  digraph},
 		  journal =      {Discrete Math.},
 		  year =         1978,
 		  volume =       23,
 		  pages =        {309-311}
+		}
 		@article{dasdan98minmeancycle,
 		  author =       {Ali Dasdan and Rajesh K. Gupta},
 		  title =        {Faster Maximum and Minimum Mean Cycle Alogrithms for
 		                  System Performance Analysis},
 		  journal =      {IEEE Transactions on Computer-Aided Design of
 		                  Integrated Circuits and Systems},
 		  year =         1998,
 		  volume =       17,
 		  number =       10,
 		  pages =        {889-899}
+		}
 		%%%%% Minimum cost flow algorithms %%%%%
 		@article{klein67primal,
 		  author =       {Morton Klein},
 		  title =        {A primal method for minimal cost flows with
 		                  applications to the assignment and transportation
 		                  problems},
 		  journal =      {Management Science},
 		  year =         1967,
 		  volume =       14,
 		  pages =        {205-220}
+		}
 		@article{goldberg89cyclecanceling,
 		  author =       {Andrew V. Goldberg and Robert E. Tarjan},
 		  title =        {Finding minimum-cost circulations by canceling
 		                  negative cycles},
 		  journal =      {Journal of the ACM},
 		  year =         1989,
 		  volume =       36,
 		  number =       4,
 		  pages =        {873-886}
+		}
 		@article{goldberg90approximation,
 		  author =       {Andrew V. Goldberg and Robert E. Tarjan},
 		  title =        {Finding Minimum-Cost Circulations by Successive
 		                  Approximation},
 		  journal =      {Mathematics of Operations Research},
 		  year =         1990,
 		  volume =       15,
 		  number =       3,
 		  pages =        {430-466}
+		}
 		@article{goldberg97efficient,
 		  author =       {Andrew V. Goldberg},
 		  title =        {An Efficient Implementation of a Scaling
 		                  Minimum-Cost Flow Algorithm},
 		  journal =      {Journal of Algorithms},
 		  year =         1997,
 		  volume =       22,
 		  number =       1,
 		  pages =        {1-29}
+		}
 		@article{bunnagel98efficient,
 		  author =       {Ursula B{\"u}nnagel and Bernhard Korte and Jens
 		                  Vygen},
 		  title =        {Efficient implementation of the {G}oldberg-{T}arjan
 		                  minimum-cost flow algorithm},
 		  journal =      {Optimization Methods and Software},
 		  year =         1998,
 		  volume =       10,
 		  pages =        {157-174}
+		}
 		@book{dantzig63linearprog,
 		  author =       {George B. Dantzig},
 		  title =        {Linear Programming and Extensions},
 		  publisher =    {Princeton University Press},
 		  year =         1963
+		}
 		@mastersthesis{kellyoneill91netsimplex,
 		  author =       {Damian J. Kelly and Garrett M. O'Neill},
 		  title =        {The Minimum Cost Flow Problem and The Network
 		                  Simplex Method},
 		  school =       {University College},
 		  address =      {Dublin, Ireland},
 		  year =         1991,
 		  month =        sep,
+		}

CMakeLists.txt

Show inline comments

 		CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
 		SET(PROJECT_NAME "LEMON")
 		PROJECT(${PROJECT_NAME})
 		IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
 		  INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
 		ELSEIF(DEFINED ENV{LEMON_VERSION})
 		  SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
 		ELSE()
 		  EXECUTE_PROCESS(
 		    COMMAND hg id -i
 		    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
 		    OUTPUT_VARIABLE HG_REVISION
 		    ERROR_QUIET
 		    OUTPUT_STRIP_TRAILING_WHITESPACE
+		  )
 		  IF(HG_REVISION STREQUAL "")
 		    SET(HG_REVISION "hg-tip")
 		  ENDIF()
 		  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
 		ENDIF()
 		SET(PROJECT_VERSION ${LEMON_VERSION})
 		SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
 		FIND_PACKAGE(Doxygen)
 		FIND_PACKAGE(Ghostscript)
 		FIND_PACKAGE(GLPK 4.33)
 		FIND_PACKAGE(CPLEX)
 		FIND_PACKAGE(COIN)
 		INCLUDE(CheckTypeSize)
 		CHECK_TYPE_SIZE("long long" LONG_LONG)
 		SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
 		INCLUDE(FindPythonInterp)
 		ENABLE_TESTING()
 		ADD_SUBDIRECTORY(lemon)
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		  ADD_SUBDIRECTORY(demo)
 		  ADD_SUBDIRECTORY(tools)
 		  ADD_SUBDIRECTORY(doc)
 		  ADD_SUBDIRECTORY(test)
 		ENDIF()
 		CONFIGURE_FILE(
 		  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
 		  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		  @ONLY
+		)
 		IF(UNIX)
 		  INSTALL(
 		    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		    DESTINATION share/lemon/cmake
+		  )
 		ELSEIF(WIN32)
 		  INSTALL(
 		    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
 		    DESTINATION cmake
+		  )
 		ENDIF()
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
 		  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
 		  SET(CPACK_PACKAGE_VENDOR "EGRES")
 		  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
 		    "LEMON - Library for Efficient Modeling and Optimization in Networks")
 		  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_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}")
 		  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
 		  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
 		  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
 		  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")

Makefile.am

Show inline comments

 		ACLOCAL_AMFLAGS = -I m4
 		AM_CXXFLAGS = $(WARNINGCXXFLAGS)
 		AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
 		LDADD = $(top_builddir)/lemon/libemon.la
 		EXTRA_DIST = \
 			AUTHORS \
 			LICENSE \
 			m4/lx_check_cplex.m4 \
 			m4/lx_check_glpk.m4 \
 			m4/lx_check_soplex.m4 \
 			m4/lx_check_coin.m4 \
 			CMakeLists.txt \
 			cmake/FindGhostscript.cmake \
 			cmake/FindCPLEX.cmake \
 			cmake/FindGLPK.cmake \
 			cmake/FindCOIN.cmake \
 			cmake/LEMONConfig.cmake.in \
 			cmake/version.cmake.in \
 			cmake/version.cmake \
 			cmake/nsis/lemon.ico \
 			cmake/nsis/uninstall.ico
 		pkgconfigdir = $(libdir)/pkgconfig
 		lemondir = $(pkgincludedir)
 		bitsdir = $(lemondir)/bits
 		conceptdir = $(lemondir)/concepts
 		pkgconfig_DATA =
 		lib_LTLIBRARIES =
 		lemon_HEADERS =
 		bits_HEADERS =
 		concept_HEADERS =
 		noinst_HEADERS =
 		noinst_PROGRAMS =
 		bin_PROGRAMS =
 		check_PROGRAMS =
 		dist_bin_SCRIPTS =
 		TESTS =
 		XFAIL_TESTS =
 		include lemon/Makefile.am
 		include test/Makefile.am
 		include doc/Makefile.am
 		include tools/Makefile.am
 		include scripts/Makefile.am
 		DIST_SUBDIRS = demo
 		demo:
 			$(MAKE) $(AM_MAKEFLAGS) -C demo
 		MRPROPERFILES = \
 			aclocal.m4 \
 			config.h.in \
 			config.h.in~ \
 			configure \
 			Makefile.in \
 			build-aux/config.guess \
 			build-aux/config.sub \
 			build-aux/depcomp \
 			build-aux/install-sh \
 			build-aux/ltmain.sh \
 			build-aux/missing \
 			doc/doxygen.log
 		mrproper:
 			$(MAKE) $(AM_MAKEFLAGS) maintainer-clean
 			-rm -f $(MRPROPERFILES)
 		dist-bz2: dist
 			zcat $(PACKAGE)-$(VERSION).tar.gz | \
 			bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
 		distcheck-bz2: distcheck
 			zcat $(PACKAGE)-$(VERSION).tar.gz | \
 			bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
 		.PHONY: demo mrproper dist-bz2 distcheck-bz2

configure.ac

Show inline comments

 		dnl Process this file with autoconf to produce a configure script.
 		dnl Version information.
 		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 2> /dev/null]))])
 		m4_define([lemon_version], [ifelse(lemon_version_number(),
 		                           [],
 		                           [ifelse(lemon_hg_revision(),
 		                           [],
 		                           [hg-tip],
 		                           [lemon_hg_path().lemon_hg_revision()])],
 		                           [lemon_version_number()])])
 		AC_PREREQ([2.59])
 		AC_INIT([LEMON], [lemon_version()], [lemon-user@lemon.cs.elte.hu], [lemon])
 		AC_CONFIG_AUX_DIR([build-aux])
 		AC_CONFIG_MACRO_DIR([m4])
 		AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
 		AC_CONFIG_SRCDIR([lemon/list_graph.h])
 		AC_CONFIG_HEADERS([config.h lemon/config.h])
 		AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string])
 		dnl Do compilation tests using the C++ compiler.
 		AC_LANG([C++])
 		dnl Check the existence of long long type.
 		AC_CHECK_TYPE(long long, [long_long_found=yes], [long_long_found=no])
 		if test x"$long_long_found" = x"yes"; then
 		  AC_DEFINE([LEMON_HAVE_LONG_LONG], [1], [Define to 1 if you have long long.])
 		fi
 		dnl Checks for programs.
 		AC_PROG_CXX
 		AC_PROG_CXXCPP
 		AC_PROG_INSTALL
 		AC_DISABLE_SHARED
 		AC_PROG_LIBTOOL
 		AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
 		AC_CHECK_PROG([python_found],[python],[yes],[no])
 		AC_CHECK_PROG([gs_found],[gs],[yes],[no])
 		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 "$GXX" = yes -a "$ICC" = no; then
 		  WARNINGCXXFLAGS="-Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
 		fi
 		AC_SUBST([WARNINGCXXFLAGS])
 		dnl Checks for libraries.
 		LX_CHECK_GLPK
 		LX_CHECK_CPLEX
 		LX_CHECK_SOPLEX
 		LX_CHECK_COIN
 		AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
 		AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
 		dnl Disable/enable building the binary tools.
 		AC_ARG_ENABLE([tools],
 		AS_HELP_STRING([--enable-tools], [build additional tools @<:@default@:>@])
 		AS_HELP_STRING([--disable-tools], [do not build additional tools]),
 		              [], [enable_tools=yes])
 		AC_MSG_CHECKING([whether to build the additional tools])
 		if test x"$enable_tools" != x"no"; then
 		  AC_MSG_RESULT([yes])
 		else
 		  AC_MSG_RESULT([no])
 		fi
 		AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
 		dnl Support for running test cases using valgrind.
 		use_valgrind=no
 		AC_ARG_ENABLE([valgrind],
 		AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]),
 		              [use_valgrind=yes])
 		if [[ "$use_valgrind" = "yes" ]]; then
 		  AC_CHECK_PROG(HAVE_VALGRIND, valgrind, yes, no)
 		  if [[ "$HAVE_VALGRIND" = "no" ]]; then
 		    AC_MSG_ERROR([Valgrind not found in PATH.])
 		  fi
 		fi
 		AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"])
 		dnl Checks for header files.
 		AC_CHECK_HEADERS(limits.h sys/time.h sys/times.h unistd.h)
 		dnl Checks for typedefs, structures, and compiler characteristics.
 		AC_C_CONST
 		AC_C_INLINE
 		AC_TYPE_SIZE_T
 		AC_HEADER_TIME
 		AC_STRUCT_TM
 		dnl Checks for library functions.
 		AC_HEADER_STDC
 		AC_CHECK_FUNCS(gettimeofday times ctime_r)
 		dnl Add dependencies on files generated by configure.
 		AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
 		  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
 		AC_CONFIG_FILES([
 		Makefile
 		demo/Makefile
 		cmake/version.cmake
 		doc/Doxyfile
 		lemon/lemon.pc
 		])
 		AC_OUTPUT
 		echo
 		echo '****************************** SUMMARY ******************************'
 		echo
 		echo Package version............... : $PACKAGE-$VERSION
 		echo
 		echo C++ compiler.................. : $CXX
 		echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
 		echo
 		echo Compiler supports long long... : $long_long_found
 		echo
 		echo GLPK support.................. : $lx_glpk_found
 		echo CPLEX support................. : $lx_cplex_found
 		echo SOPLEX support................ : $lx_soplex_found
 		echo CLP support................... : $lx_clp_found
 		echo CBC support................... : $lx_cbc_found
 		echo
 		echo Build additional tools........ : $enable_tools
 		echo Use valgrind for tests........ : $use_valgrind
 		echo
 		echo The packace will be installed in
 		echo -n '  '
 		echo $prefix.
 		echo
 		echo '*********************************************************************'
 		echo
 		echo Configure complete, now type \'make\' and then \'make install\'.
 		echo

doc/CMakeLists.txt

Show inline comments

 		SET(PACKAGE_NAME ${PROJECT_NAME})
 		SET(PACKAGE_VERSION ${PROJECT_VERSION})
 		SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
 		SET(abs_top_builddir ${PROJECT_BINARY_DIR})
 		CONFIGURE_FILE(
 		  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
 		  ${PROJECT_BINARY_DIR}/doc/Doxyfile
 		  @ONLY
+		)
 		IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
+		IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
 		  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
 		  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
 		  ADD_CUSTOM_TARGET(html
 		    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
 		    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
 		    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
 		    COMMAND ${CMAKE_COMMAND} -E remove_directory html
 		    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
 		    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
 		    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+		  )
 		  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
 		  IF(UNIX)
 		    INSTALL(
 		      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
 		      DESTINATION share/doc/lemon/html
 		      COMPONENT html_documentation
+		    )
 		  ELSEIF(WIN32)
 		    INSTALL(
 		      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
 		      DESTINATION doc
 		      COMPONENT html_documentation
+		    )
 		  ENDIF()
 		ENDIF()

doc/Doxyfile.in

Show inline comments

-		# Doxyfile 1.5.7.1
+		# Doxyfile 1.5.9
 		#---------------------------------------------------------------------------
 		# Project related configuration options
 		#---------------------------------------------------------------------------
 		DOXYFILE_ENCODING      = UTF-8
 		PROJECT_NAME           = @PACKAGE_NAME@
 		PROJECT_NUMBER         = @PACKAGE_VERSION@
 		OUTPUT_DIRECTORY       =
 		CREATE_SUBDIRS         = NO
 		OUTPUT_LANGUAGE        = English
 		BRIEF_MEMBER_DESC      = YES
 		REPEAT_BRIEF           = NO
 		ABBREVIATE_BRIEF       =
 		ALWAYS_DETAILED_SEC    = NO
 		INLINE_INHERITED_MEMB  = NO
 		FULL_PATH_NAMES        = YES
 		STRIP_FROM_PATH        = "@abs_top_srcdir@"
 		STRIP_FROM_INC_PATH    = "@abs_top_srcdir@"
 		SHORT_NAMES            = YES
 		JAVADOC_AUTOBRIEF      = NO
 		QT_AUTOBRIEF           = NO
 		MULTILINE_CPP_IS_BRIEF = NO
 		DETAILS_AT_TOP         = YES
 		INHERIT_DOCS           = NO
 		SEPARATE_MEMBER_PAGES  = NO
 		TAB_SIZE               = 8
 		ALIASES                =
 		OPTIMIZE_OUTPUT_FOR_C  = NO
 		OPTIMIZE_OUTPUT_JAVA   = NO
 		OPTIMIZE_FOR_FORTRAN   = NO
 		OPTIMIZE_OUTPUT_VHDL   = NO
 		BUILTIN_STL_SUPPORT    = YES
 		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
 		#---------------------------------------------------------------------------
 		EXTRACT_ALL            = NO
 		EXTRACT_PRIVATE        = YES
 		EXTRACT_STATIC         = YES
 		EXTRACT_LOCAL_CLASSES  = NO
 		EXTRACT_LOCAL_METHODS  = NO
 		EXTRACT_ANON_NSPACES   = NO
 		HIDE_UNDOC_MEMBERS     = YES
 		HIDE_UNDOC_CLASSES     = YES
 		HIDE_FRIEND_COMPOUNDS  = NO
 		HIDE_IN_BODY_DOCS      = NO
 		INTERNAL_DOCS          = NO
 		CASE_SENSE_NAMES       = YES
 		HIDE_SCOPE_NAMES       = YES
 		SHOW_INCLUDE_FILES     = YES
 		INLINE_INFO            = YES
 		SORT_MEMBER_DOCS       = NO
 		SORT_BRIEF_DOCS        = NO
 		SORT_GROUP_NAMES       = NO
 		SORT_BY_SCOPE_NAME     = NO
 		GENERATE_TODOLIST      = YES
 		GENERATE_TESTLIST      = YES
 		GENERATE_BUGLIST       = YES
 		GENERATE_DEPRECATEDLIST= YES
 		ENABLED_SECTIONS       =
 		MAX_INITIALIZER_LINES  = 5
 		SHOW_USED_FILES        = NO
 		SHOW_DIRECTORIES       = YES
 		SHOW_FILES             = YES
 		SHOW_NAMESPACES        = YES
 		FILE_VERSION_FILTER    =
 		LAYOUT_FILE            = DoxygenLayout.xml
 		#---------------------------------------------------------------------------
 		# configuration options related to warning and progress messages
 		#---------------------------------------------------------------------------
 		QUIET                  = NO
 		WARNINGS               = YES
 		WARN_IF_UNDOCUMENTED   = YES
 		WARN_IF_DOC_ERROR      = YES
 		WARN_NO_PARAMDOC       = NO
 		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"
+		                         "@abs_top_srcdir@/test/test_tools.h" \
 		                         "@abs_top_builddir@/doc/references.dox"
 		INPUT_ENCODING         = UTF-8
 		FILE_PATTERNS          = *.h \
 		                         *.cc \
 		                         *.dox
 		RECURSIVE              = NO
 		EXCLUDE                =
 		EXCLUDE_SYMLINKS       = NO
 		EXCLUDE_PATTERNS       =
 		EXCLUDE_SYMBOLS        =
 		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"
 		INPUT_FILTER           =
 		FILTER_PATTERNS        =
 		FILTER_SOURCE_FILES    = NO
 		#---------------------------------------------------------------------------
 		# configuration options related to source browsing
 		#---------------------------------------------------------------------------
 		SOURCE_BROWSER         = NO
 		INLINE_SOURCES         = NO
 		STRIP_CODE_COMMENTS    = YES
 		REFERENCED_BY_RELATION = NO
 		REFERENCES_RELATION    = NO
 		REFERENCES_LINK_SOURCE = YES
 		USE_HTAGS              = NO
 		VERBATIM_HEADERS       = NO
 		#---------------------------------------------------------------------------
 		# configuration options related to the alphabetical class index
 		#---------------------------------------------------------------------------
 		ALPHABETICAL_INDEX     = YES
 		COLS_IN_ALPHA_INDEX    = 2
 		IGNORE_PREFIX          =
 		#---------------------------------------------------------------------------
 		# configuration options related to the HTML output
 		#---------------------------------------------------------------------------
 		GENERATE_HTML          = YES
 		HTML_OUTPUT            = html
 		HTML_FILE_EXTENSION    = .html
 		HTML_HEADER            =
 		HTML_FOOTER            =
 		HTML_STYLESHEET        =
 		HTML_ALIGN_MEMBERS     = YES
 		HTML_DYNAMIC_SECTIONS  = NO
 		GENERATE_DOCSET        = NO
@@ -178,89 +178,89 @@
 		#---------------------------------------------------------------------------
 		# configuration options related to the RTF output
 		#---------------------------------------------------------------------------
 		GENERATE_RTF           = NO
 		RTF_OUTPUT             = rtf
 		COMPACT_RTF            = NO
 		RTF_HYPERLINKS         = NO
 		RTF_STYLESHEET_FILE    =
 		RTF_EXTENSIONS_FILE    =
 		#---------------------------------------------------------------------------
 		# configuration options related to the man page output
 		#---------------------------------------------------------------------------
 		GENERATE_MAN           = NO
 		MAN_OUTPUT             = man
 		MAN_EXTENSION          = .3
 		MAN_LINKS              = NO
 		#---------------------------------------------------------------------------
 		# configuration options related to the XML output
 		#---------------------------------------------------------------------------
 		GENERATE_XML           = NO
 		XML_OUTPUT             = xml
 		XML_SCHEMA             =
 		XML_DTD                =
 		XML_PROGRAMLISTING     = YES
 		#---------------------------------------------------------------------------
 		# configuration options for the AutoGen Definitions output
 		#---------------------------------------------------------------------------
 		GENERATE_AUTOGEN_DEF   = NO
 		#---------------------------------------------------------------------------
 		# configuration options related to the Perl module output
 		#---------------------------------------------------------------------------
 		GENERATE_PERLMOD       = NO
 		PERLMOD_LATEX          = NO
 		PERLMOD_PRETTY         = YES
 		PERLMOD_MAKEVAR_PREFIX =
 		#---------------------------------------------------------------------------
 		# Configuration options related to the preprocessor
 		#---------------------------------------------------------------------------
 		ENABLE_PREPROCESSING   = YES
 		MACRO_EXPANSION        = NO
 		EXPAND_ONLY_PREDEF     = NO
 		SEARCH_INCLUDES        = YES
 		INCLUDE_PATH           =
 		INCLUDE_FILE_PATTERNS  =
 		PREDEFINED             = DOXYGEN
 		EXPAND_AS_DEFINED      =
 		SKIP_FUNCTION_MACROS   = YES
 		#---------------------------------------------------------------------------
-		# Configuration::additions related to external references
+		# Options related to the search engine
 		#---------------------------------------------------------------------------
 		TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
 		GENERATE_TAGFILE       = html/lemon.tag
 		ALLEXTERNALS           = NO
 		EXTERNAL_GROUPS        = NO
 		PERL_PATH              = /usr/bin/perl
 		#---------------------------------------------------------------------------
 		# Configuration options related to the dot tool
 		#---------------------------------------------------------------------------
 		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
 		GROUP_GRAPHS           = NO
 		UML_LOOK               = NO
 		TEMPLATE_RELATIONS     = NO
 		INCLUDE_GRAPH          = NO
 		INCLUDED_BY_GRAPH      = NO
 		CALL_GRAPH             = NO
 		CALLER_GRAPH           = NO
 		GRAPHICAL_HIERARCHY    = NO
 		DIRECTORY_GRAPH        = NO
 		DOT_IMAGE_FORMAT       = png
 		DOT_PATH               =
 		DOTFILE_DIRS           =
 		DOT_GRAPH_MAX_NODES    = 50
 		MAX_DOT_GRAPH_DEPTH    = 0
 		DOT_TRANSPARENT        = NO
 		DOT_MULTI_TARGETS      = NO
 		GENERATE_LEGEND        = YES
 		DOT_CLEANUP            = YES
 		#---------------------------------------------------------------------------
 		# Configuration::additions related to the search engine
 		#---------------------------------------------------------------------------
 		SEARCHENGINE           = NO

doc/Makefile.am

Show inline comments

@@ -21,89 +21,101 @@
 			nodeshape_2.eps \
 			nodeshape_3.eps \
 			nodeshape_4.eps
 		DOC_EPS_IMAGES27 = \
 			bipartite_matching.eps \
 			bipartite_partitions.eps \
 			connected_components.eps \
 			edge_biconnected_components.eps \
 			node_biconnected_components.eps \
 			strongly_connected_components.eps
 		DOC_EPS_IMAGES = \
 			$(DOC_EPS_IMAGES18) \
 			$(DOC_EPS_IMAGES27)
 		DOC_PNG_IMAGES = \
 			$(DOC_EPS_IMAGES:%.eps=doc/gen-images/%.png)
 		EXTRA_DIST += $(DOC_EPS_IMAGES:%=doc/images/%)
 		doc/html:
 			$(MAKE) $(AM_MAKEFLAGS) html
 		GS_COMMAND=gs -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4
 		$(DOC_EPS_IMAGES18:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
 			-mkdir doc/gen-images
 			if test ${gs_found} = yes; then \
 			  $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \
 			else \
 			  echo; \
 			  echo "Ghostscript not found."; \
 			  echo; \
 			  exit 1; \
 			fi
 		$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
 			-mkdir doc/gen-images
 			if test ${gs_found} = yes; then \
 			  $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \
 			else \
 			  echo; \
 			  echo "Ghostscript not found."; \
 			  echo; \
 			  exit 1; \
 			fi
-		html-local: $(DOC_PNG_IMAGES)
+		references.dox: doc/references.bib
 			if test ${python_found} = yes; then \
 			  cd doc; \
 			  python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
 			  cd ..; \
 			else \
 			  echo; \
 			  echo "Python not found."; \
 			  echo; \
 			  exit 1; \
 			fi
 		html-local: $(DOC_PNG_IMAGES) references.dox
 			if test ${doxygen_found} = yes; then \
 			  cd doc; \
 			  doxygen Doxyfile; \
 			  cd ..; \
 			else \
 			  echo; \
 			  echo "Doxygen not found."; \
 			  echo; \
 			  exit 1; \
 			fi
 		clean-local:
 			-rm -rf doc/html
 			-rm -f doc/doxygen.log
 			-rm -f $(DOC_PNG_IMAGES)
 			-rm -rf doc/gen-images
 		update-external-tags:
 			wget -O doc/libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag && \
 			mv doc/libstdc++.tag.tmp doc/libstdc++.tag || \
 			rm doc/libstdc++.tag.tmp
 		install-html-local: doc/html
 			@$(NORMAL_INSTALL)
 			$(mkinstalldirs) $(DESTDIR)$(htmldir)/html
 			for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
 			  f="`echo $$p | sed -e 's|^.*/||'`"; \
 			  echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
 			  $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
 			done
 		uninstall-local:
 			@$(NORMAL_UNINSTALL)
 			for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
 			  f="`echo $$p | sed -e 's|^.*/||'`"; \
 			  echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
 			  rm -f $(DESTDIR)$(htmldir)/html/$$f; \
 			done
 		.PHONY: update-external-tags

doc/groups.dox

Show inline comments

@@ -235,459 +235,531 @@
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
 		\sa \ref concepts::Path "Path concept"
 		*/
 		/**
 		@defgroup heaps Heap Structures
 		@ingroup datas
 		\brief %Heap structures implemented in LEMON.
 		This group contains the heap structures implemented in LEMON.
 		LEMON provides several heap classes. They are efficient implementations
 		of the abstract data type \e priority \e queue. They store items with
 		specified values called \e priorities in such a way that finding and
 		removing the item with minimum priority are efficient.
 		The basic operations are adding and erasing items, changing the priority
 		of an item, etc.
 		Heaps are crucial in several algorithms, such as Dijkstra and Prim.
 		The heap implementations have the same interface, thus any of them can be
 		used easily in such algorithms.
 		\sa \ref concepts::Heap "Heap concept"
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group contains some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
 		*/
 		/**
 		@defgroup geomdat Geometric Data Structures
 		@ingroup auxdat
 		\brief Geometric data structures implemented in LEMON.
 		This group contains geometric data structures implemented in LEMON.
 		 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
 		   vector with the usual operations.
 		 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
 		   rectangular bounding box of a set of \ref lemon::dim2::Point
 		   "dim2::Point"'s.
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup auxdat
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group contains the several algorithms
 		implemented in LEMON.
 		This group contains the several algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
 		This group contains the common graph search algorithms, namely
-		\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
 		\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
 		\ref clrs01algorithms.
 		*/
 		/**
 		@defgroup shortest_path Shortest Path Algorithms
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
-		This group contains the algorithms for finding shortest paths in digraphs.
 		This group contains the algorithms for finding shortest paths in digraphs
 		\ref clrs01algorithms.
 		 - \ref Dijkstra algorithm for finding shortest paths from a source node
 		   when all arc lengths are non-negative.
 		 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
 		   from a source node when arc lenghts can be either positive or negative,
 		   but the digraph should not contain directed cycles with negative total
 		   length.
 		 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
 		   for solving the \e all-pairs \e shortest \e paths \e problem when arc
 		   lenghts can be either positive or negative, but the digraph should
 		   not contain directed cycles with negative total length.
 		 - \ref Suurballe A successive shortest path algorithm for finding
 		   arc-disjoint paths between two nodes having minimum total length.
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost spanning trees and arborescences.
 		This group contains the algorithms for finding minimum cost spanning
 		trees and arborescences \ref clrs01algorithms.
 		*/
 		/**
 		@defgroup max_flow Maximum Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding maximum flows.
 		This group contains the algorithms for finding maximum flows and
 		feasible circulations.
+		feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
 		The \e maximum \e flow \e problem is to find a flow of maximum value between
 		a single source and a single target. Formally, there is a \f$G=(V,A)\f$
 		digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
 		\f$s, t \in V\f$ source and target nodes.
 		A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
 		following optimization problem.
 		\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
 		\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
 		    \quad \forall u\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 		LEMON contains several algorithms for solving maximum flow problems:
 		- \ref EdmondsKarp Edmonds-Karp algorithm.
 		- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
 		- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
 		- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
 		- \ref EdmondsKarp Edmonds-Karp algorithm
 		  \ref edmondskarp72theoretical.
 		- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
 		  \ref goldberg88newapproach.
 		- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
 		  \ref dinic70algorithm, \ref sleator83dynamic.
 		- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
 		  \ref goldberg88newapproach, \ref sleator83dynamic.
-		In most cases the \ref Preflow "Preflow" algorithm provides the
 		In most cases the \ref Preflow algorithm provides the
 		fastest method for computing a maximum flow. All implementations
 		also provide functions to query the minimum cut, which is the dual
 		problem of maximum flow.
 		\ref Circulation is a preflow push-relabel algorithm implemented directly
 		for finding feasible circulations, which is a somewhat different problem,
 		but it is strongly related to maximum flow.
 		For more information, see \ref Circulation.
 		*/
 		/**
 		@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost flows and circulations.
 		This group contains the algorithms for finding minimum cost flows and
 		circulations. For more information about this problem and its dual
 		solution see \ref min_cost_flow "Minimum Cost Flow Problem".
 		circulations \ref amo93networkflows. For more information about this
 		problem and its dual solution, see \ref min_cost_flow
 		"Minimum Cost Flow Problem".
 		LEMON contains several algorithms for this problem.
 		 - \ref NetworkSimplex Primal Network Simplex algorithm with various
 		   pivot strategies.
+		   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
 		 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
-		   cost scaling.
+		   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
 		   \ref bunnagel98efficient.
 		 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
 		   capacity scaling.
 		 - \ref CancelAndTighten The Cancel and Tighten algorithm.
-		 - \ref CycleCanceling Cycle-Canceling algorithms.
+		   capacity scaling \ref edmondskarp72theoretical.
 		 - \ref CancelAndTighten The Cancel and Tighten algorithm
 		   \ref goldberg89cyclecanceling.
 		 - \ref CycleCanceling Cycle-Canceling algorithms
 		   \ref klein67primal, \ref goldberg89cyclecanceling.
 		In general NetworkSimplex is the most efficient implementation,
 		but in special cases other algorithms could be faster.
 		For example, if the total supply and/or capacities are rather small,
 		CapacityScaling is usually the fastest algorithm (without effective scaling).
 		*/
 		/**
 		@defgroup min_cut Minimum Cut Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cut in graphs.
 		This group contains the algorithms for finding minimum cut in graphs.
 		The \e minimum \e cut \e problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the nodes with minimum overall capacity on
 		outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
 		\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		cut is the \f$X\f$ solution of the next optimization problem:
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
-		    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
+		    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
 		LEMON contains several algorithms related to minimum cut problems:
 		- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
 		  in directed graphs.
 		- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
 		  calculating minimum cut in undirected graphs.
 		- \ref GomoryHu "Gomory-Hu tree computation" for calculating
 		  all-pairs minimum cut in undirected graphs.
 		If you want to find minimum cut just between two distinict nodes,
 		see the \ref max_flow "maximum flow problem".
 		*/
 		/**
-		@defgroup graph_properties Connectivity and Other Graph Properties
+		@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
 		@ingroup algs
-		\brief Algorithms for discovering the graph properties
+		\brief Algorithms for finding minimum mean cycles.
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		This group contains the algorithms for finding minimum mean cycles
 		\ref clrs01algorithms, \ref amo93networkflows.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
-		*/
+		The \e minimum \e mean \e cycle \e problem is to find a directed cycle
 		of minimum mean length (cost) in a digraph.
 		The mean length of a cycle is the average length of its arcs, i.e. the
 		ratio between the total length of the cycle and the number of arcs on it.
 		/**
 		@defgroup planar Planarity Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This problem has an important connection to \e conservative \e length
 		\e functions, too. A length function on the arcs of a digraph is called
 		conservative if and only if there is no directed cycle of negative total
 		length. For an arbitrary length function, the negative of the minimum
 		cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
 		arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
 		function.
 		This group contains the algorithms for planarity checking,
 		embedding and drawing.
 		LEMON contains three algorithms for solving the minimum mean cycle problem:
 		- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
 		  \ref dasdan98minmeancycle.
 		- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
 		  version of Karp's algorithm \ref dasdan98minmeancycle.
 		- \ref Howard "Howard"'s policy iteration algorithm
 		  \ref dasdan98minmeancycle.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		In practice, the Howard algorithm proved to be by far the most efficient
 		one, though the best known theoretical bound on its running time is
 		exponential.
 		Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
 		O(n<sup>2</sup>+e), but the latter one is typically faster due to the
 		applied early termination scheme.
 		*/
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains the algorithms for calculating
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the edges for which each node has at most one incident
 		edge.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		The matching algorithms implemented in LEMON:
 		- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref PrBipartiteMatching Push-relabel algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref MaxWeightedBipartiteMatching
 		  Successive shortest path algorithm for calculating maximum weighted
 		  matching and maximum weighted bipartite matching in bipartite graphs.
 		- \ref MinCostMaxBipartiteMatching
 		  Successive shortest path algorithm for calculating minimum cost maximum
 		  matching in bipartite graphs.
 		- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum cardinality matching in general graphs.
 		- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum weighted matching in general graphs.
 		- \ref MaxWeightedPerfectMatching
 		  Edmond's blossom shrinking algorithm for calculating maximum weighted
 		  perfect matching in general graphs.
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
-		@defgroup spantree Minimum Spanning Tree Algorithms
+		@defgroup graph_properties Connectivity and Other Graph Properties
 		@ingroup algs
-		\brief Algorithms for finding minimum cost spanning trees and arborescences.
+		\brief Algorithms for discovering the graph properties
 		This group contains the algorithms for finding minimum cost spanning
 		trees and arborescences.
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html connected_components.png
 		\image latex connected_components.eps "Connected components" width=\textwidth
 		*/
 		/**
 		@defgroup planar Planarity Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This group contains the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
 		@defgroup approx Approximation Algorithms
 		@ingroup algs
 		\brief Approximation algorithms.
 		This group contains the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup auxalg Auxiliary Algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
 		This group contains some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
 		@defgroup approx Approximation Algorithms
 		@ingroup algs
 		\brief Approximation algorithms.
 		This group contains the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group contains some general optimization frameworks
 		implemented in LEMON.
 		This group contains 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.
+		\brief LP and MIP solver interfaces for LEMON.
 		This group contains Lp and Mip solver interfaces for LEMON. The
 		various LP solvers could be used in the same manner with this
-		interface.
+		This group contains LP and MIP solver interfaces for LEMON.
 		Various LP solvers could be used in the same manner with this
 		high-level interface.
 		The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
 		\ref cplex, \ref soplex.
 		*/
 		/**
 		@defgroup lp_utils Tools for Lp and Mip Solvers
 		@ingroup lp_group
 		\brief Helper tools to the Lp and Mip solvers.
 		This group adds some helper tools to general optimization framework
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup metah Metaheuristics
 		@ingroup gen_opt_group
 		\brief Metaheuristics for LEMON library.
 		This group contains some metaheuristic optimization tools.
 		*/
 		/**
 		@defgroup utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
 		This group contains some simple basic graph utilities.
 		*/
 		/**
 		@defgroup misc Miscellaneous Tools
 		@ingroup utils
 		\brief Tools for development, debugging and testing.
 		This group contains several useful tools for development,
 		debugging and testing.
 		*/
 		/**
 		@defgroup timecount Time Measuring and Counting
 		@ingroup misc
 		\brief Simple tools for measuring the performance of algorithms.
 		This group contains simple tools for measuring the performance
 		of algorithms.
 		*/
 		/**
 		@defgroup exceptions Exceptions
 		@ingroup utils
 		\brief Exceptions defined in LEMON.
 		This group contains the exceptions defined in LEMON.
 		*/
 		/**
 		@defgroup io_group Input-Output
 		\brief Graph Input-Output methods
 		This group contains the tools for importing and exporting graphs
 		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 Graph Format
 		@ingroup io_group
 		\brief Reading and writing LEMON Graph Format.
 		This group contains methods for reading and writing
 		\ref lgf-format "LEMON Graph Format".
 		*/
 		/**
 		@defgroup eps_io Postscript Exporting
 		@ingroup io_group
 		\brief General \c EPS drawer and graph exporter
 		This group contains general \c EPS drawing methods and special
 		graph exporting tools.
 		*/
 		/**
-		@defgroup dimacs_group DIMACS format
+		@defgroup dimacs_group DIMACS Format
 		@ingroup io_group
 		\brief Read and write files in DIMACS format
 		Tools to read a digraph from or write it to a file in DIMACS format data.
 		*/
 		/**
 		@defgroup nauty_group NAUTY Format
 		@ingroup io_group
 		\brief Read \e Nauty format
 		Tool to read graphs from \e Nauty format data.
 		*/
 		/**
 		@defgroup concept Concepts
 		\brief Skeleton classes and concept checking classes
 		This group contains the data/algorithm skeletons and concept checking
 		classes implemented in LEMON.
 		The purpose of the classes in this group is fourfold.
 		- 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, <tt>typedef</tt>s etc. an
 		  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
 		  the algorithms working on a data structure meeting a certain concept
 		  should compile with these classes. (Though it will not run properly,
 		  of course.) In this way it is easily to check if an algorithm
 		  doesn't use any extra feature of a certain implementation.
 		- The concept descriptor classes also provide a <em>checker class</em>
 		  that makes it possible to check whether a certain implementation of a
 		  concept indeed provides all the required features.
 		- Finally, They can serve as a skeleton of a new implementation of a concept.
 		*/
 		/**
 		@defgroup graph_concepts Graph Structure Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for graph structures
 		This group contains the skeletons and concept checking classes of LEMON's
 		graph structures and helper classes used to implement these.
 		This group contains the skeletons and concept checking classes of
 		graph structures.
 		*/
 		/**
 		@defgroup map_concepts Map Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for maps
 		This group contains the skeletons and concept checking classes of maps.
 		*/
 		/**
 		@defgroup tools Standalone Utility Applications
 		Some utility applications are listed here.
 		The standard compilation procedure (<tt>./configure;make</tt>) will compile
 		them, as well.
 		*/
 		/**
 		\anchor demoprograms
 		@defgroup demos Demo Programs
 		Some demo programs are listed here. Their full source codes can be found in
 		the \c demo subdirectory of the source tree.
 		In order to compile them, use the <tt>make demo</tt> or the
 		<tt>make check</tt> commands.
 		*/
 		/**
 		@defgroup tools Standalone Utility Applications
 		Some utility applications are listed here.
 		The standard compilation procedure (<tt>./configure;make</tt>) will compile
 		them, as well.
 		*/
+		}

doc/mainpage.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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.
+		 *
 		 */
 		/**
 		\mainpage LEMON Documentation
 		\section intro Introduction
 		\subsection whatis What is LEMON
 		LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
 		and <b>O</b>ptimization in <b>N</b>etworks.
 		It is a C++ template
 		library aimed at combinatorial optimization tasks which
 		often involve in working
 		with graphs.
 		<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
 		and <b>O</b>ptimization in <b>N</b>etworks</i>.
 		It is a C++ template library providing efficient implementation of common
 		data structures and algorithms with focus on combinatorial optimization
 		problems in graphs and networks.
 		<b>
 		LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>
 		project.
 		You are free to use it in your commercial or
 		non-commercial applications under very permissive
 		\ref license "license terms".
 		</b>
-		\subsection howtoread How to read the documentation
+		The project is maintained by the
 		<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
 		Combinatorial Optimization</a> \ref egres
 		at the Operations Research Department of the
 		<a href="http://www.elte.hu/">E&ouml;tv&ouml;s Lor&aacute;nd University,
 		Budapest</a>, Hungary.
 		LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
 		initiative \ref coinor.
 		\section howtoread How to Read the Documentation
 		If you would like to get to know the library, see
 		<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
 		If you know what you are looking for, then try to find it under the
 		<a class="el" href="modules.html">Modules</a> 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.
 		*/

doc/min_cost_flow.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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 min_cost_flow Minimum Cost Flow Problem
 		\section mcf_def Definition (GEQ form)
 		The \e minimum \e cost \e flow \e problem is to find a feasible flow of
 		minimum total cost from a set of supply nodes to a set of demand nodes
 		in a network with capacity constraints (lower and upper bounds)
 		and arc costs.
+		and arc costs \ref amo93networkflows.
 		Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
 		\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
 		upper bounds for the flow values on the arcs, for which
 		\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
 		\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
 		on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
 		signed supply values of the nodes.
 		If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		\f$-sup(u)\f$ demand.
 		A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
 		of the following optimization problem.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		zero or negative in order to have a feasible solution (since the sum
 		of the expressions on the left-hand side of the inequalities is zero).
 		It means that the total demand must be greater or equal to the total
 		supply and all the supplies have to be carried out from the supply nodes,
 		but there could be demands that are not satisfied.
 		If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		constraints have to be satisfied with equality, i.e. all demands
 		have to be satisfied and all supplies have to be used.
 		\section mcf_algs Algorithms
 		LEMON contains several algorithms for solving this problem, for more
 		information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
 		A feasible solution for this problem can be found using \ref Circulation.
 		\section mcf_dual Dual Solution
 		The dual solution of the minimum cost flow problem is represented by
 		node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
 		An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
 		if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
 		the following \e complementary \e slackness optimality conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
-		   - \f$\pi(u)<=0\f$;
+		   - \f$\pi(u)\leq 0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
 		\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
 		\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
 		All algorithms provide dual solution (node potentials), as well,
 		if an optimal flow is found.
 		\section mcf_eq Equality Form
 		The above \ref mcf_def "definition" is actually more general than the
 		usual formulation of the minimum cost flow problem, in which strict
 		equalities are required in the supply/demand contraints.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		However if the sum of the supply values is zero, then these two problems
 		are equivalent.
 		The \ref min_cost_flow_algs "algorithms" in LEMON support the general
 		form, so if you need the equality form, you have to ensure this additional
 		contraint manually.
 		\section mcf_leq Opposite Inequalites (LEQ Form)
 		Another possible definition of the minimum cost flow problem is
 		when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
 		instead of the <em>"greater or equal"</em> (GEQ) constraints.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		It means that the total demand must be less or equal to the
 		total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 		positive) and all the demands have to be satisfied, but there
 		could be supplies that are not carried out from the supply
 		nodes.
 		The equality form is also a special case of this form, of course.
 		You could easily transform this case to the \ref mcf_def "GEQ form"
 		of the problem by reversing the direction of the arcs and taking the
 		negative of the supply values (e.g. using \ref ReverseDigraph and
 		\ref NegMap adaptors).
 		However \ref NetworkSimplex algorithm also supports this form directly
 		for the sake of convenience.
 		Note that the optimality conditions for this supply constraint type are
 		slightly differ from the conditions that are discussed for the GEQ form,
 		namely the potentials have to be non-negative instead of non-positive.
 		An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
 		is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
 		node potentials the following conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
-		   - \f$\pi(u)>=0\f$;
+		   - \f$\pi(u)\geq 0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		*/
+		}

lemon/Makefile.am

Show inline comments

@@ -41,102 +41,106 @@
 		lemon_libemon_la_SOURCES += lemon/cplex.cc
 		endif
 		if HAVE_SOPLEX
 		lemon_libemon_la_SOURCES += lemon/soplex.cc
 		endif
 		if HAVE_CLP
 		lemon_libemon_la_SOURCES += lemon/clp.cc
 		endif
 		if HAVE_CBC
 		lemon_libemon_la_SOURCES += lemon/cbc.cc
 		endif
 		lemon_HEADERS += \
 			lemon/adaptors.h \
 			lemon/arg_parser.h \
 			lemon/assert.h \
 			lemon/bellman_ford.h \
 			lemon/bfs.h \
 			lemon/bin_heap.h \
 			lemon/binom_heap.h \
 			lemon/bucket_heap.h \
 			lemon/cbc.h \
 			lemon/circulation.h \
 			lemon/clp.h \
 			lemon/color.h \
 			lemon/concept_check.h \
 			lemon/connectivity.h \
 			lemon/counter.h \
 			lemon/core.h \
 			lemon/cplex.h \
 			lemon/dfs.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
 			lemon/dimacs.h \
 			lemon/edge_set.h \
 			lemon/elevator.h \
 			lemon/error.h \
 			lemon/euler.h \
 			lemon/fib_heap.h \
 			lemon/fourary_heap.h \
 			lemon/full_graph.h \
 			lemon/glpk.h \
 			lemon/gomory_hu.h \
 			lemon/graph_to_eps.h \
 			lemon/grid_graph.h \
 			lemon/hartmann_orlin.h \
 			lemon/howard.h \
 			lemon/hypercube_graph.h \
 			lemon/karp.h \
 			lemon/kary_heap.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
 			lemon/lgf_writer.h \
 			lemon/list_graph.h \
 			lemon/lp.h \
 			lemon/lp_base.h \
 			lemon/lp_skeleton.h \
 			lemon/maps.h \
 			lemon/matching.h \
 			lemon/math.h \
 			lemon/min_cost_arborescence.h \
 			lemon/nauty_reader.h \
 			lemon/network_simplex.h \
 			lemon/pairing_heap.h \
 			lemon/path.h \
 			lemon/planarity.h \
 			lemon/preflow.h \
 			lemon/radix_heap.h \
 			lemon/radix_sort.h \
 			lemon/random.h \
 			lemon/smart_graph.h \
 			lemon/soplex.h \
 			lemon/static_graph.h \
 			lemon/suurballe.h \
 			lemon/time_measure.h \
 			lemon/tolerance.h \
 			lemon/unionfind.h \
 			lemon/bits/windows.h
 		bits_HEADERS += \
 			lemon/bits/alteration_notifier.h \
 			lemon/bits/array_map.h \
 			lemon/bits/bezier.h \
 			lemon/bits/default_map.h \
 			lemon/bits/edge_set_extender.h \
 			lemon/bits/enable_if.h \
 			lemon/bits/graph_adaptor_extender.h \
 			lemon/bits/graph_extender.h \
 			lemon/bits/map_extender.h \
 			lemon/bits/path_dump.h \
 			lemon/bits/solver_bits.h \
 			lemon/bits/traits.h \
 			lemon/bits/variant.h \
 			lemon/bits/vector_map.h
 		concept_HEADERS += \
 			lemon/concepts/digraph.h \
 			lemon/concepts/graph.h \
 			lemon/concepts/graph_components.h \
 			lemon/concepts/heap.h \
 			lemon/concepts/maps.h \
 			lemon/concepts/path.h

lemon/adaptors.h

Show inline comments

@@ -315,96 +315,99 @@
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename DGR>
 		  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
 		    typedef DigraphAdaptorBase<DGR> Parent;
 		  public:
 		    typedef DGR Digraph;
 		  protected:
 		    ReverseDigraphBase() : Parent() { }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
 		    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
 		    void nextIn(Arc& a) const { Parent::nextOut(a); }
 		    void nextOut(Arc& a) const { Parent::nextIn(a); }
 		    Node source(const Arc& a) const { return Parent::target(a); }
 		    Node target(const Arc& a) const { return Parent::source(a); }
 		    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      return Parent::findArc(v, u, prev);
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for reversing the orientation of the arcs in
 		  /// a digraph.
 		  ///
 		  /// ReverseDigraph can be used for reversing the arcs in a digraph.
 		  /// It conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides item counting in the same time as the adapted
 		  /// digraph structure.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  ///
 		  /// \note The \c Node and \c Arc types of this adaptor and the adapted
 		  /// digraph are convertible to each other.
 		  template<typename DGR>
 		#ifdef DOXYGEN
 		  class ReverseDigraph {
 		#else
 		  class ReverseDigraph :
 		    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
 		#endif
 		    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		  protected:
 		    ReverseDigraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a reverse digraph adaptor for the given digraph.
 		    explicit ReverseDigraph(DGR& digraph) {
 		      Parent::initialize(digraph);
+		    }
 		  };
 		  /// \brief Returns a read-only ReverseDigraph adaptor
 		  ///
 		  /// This function just returns a read-only \ref ReverseDigraph adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates ReverseDigraph
 		  template<typename DGR>
 		  ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
 		    return ReverseDigraph<const DGR>(digraph);
+		  }
 		  template <typename DGR, typename NF, typename AF, bool ch = true>
 		  class SubDigraphBase : public DigraphAdaptorBase<DGR> {
 		    typedef DigraphAdaptorBase<DGR> Parent;
 		  public:
 		    typedef DGR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef AF ArcFilterMap;
@@ -674,96 +677,98 @@
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding nodes and arcs in a digraph
 		  ///
 		  /// SubDigraph can be used for hiding nodes and arcs in a digraph.
 		  /// A \c bool node map and a \c bool arc map must be specified, which
 		  /// define the filters for nodes and arcs.
 		  /// Only the nodes and arcs with \c true filter value are
 		  /// shown in the subdigraph. The arcs that are incident to hidden
 		  /// nodes are also filtered out.
 		  /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time counting for nodes and arcs.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam NF The type of the node filter map.
 		  /// It must be a \c bool (or convertible) node map of the
 		  /// adapted digraph. The default type is
 		  /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".
 		  /// \tparam AF The type of the arc filter map.
 		  /// It must be \c bool (or convertible) arc map of the
 		  /// adapted digraph. The default type is
 		  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
 		  ///
 		  /// \note The \c Node and \c Arc types of this adaptor and the adapted
 		  /// digraph are convertible to each other.
 		  ///
 		  /// \see FilterNodes
 		  /// \see FilterArcs
 		#ifdef DOXYGEN
 		  template<typename DGR, typename NF, typename AF>
 		  class SubDigraph {
 		#else
 		  template<typename DGR,
 		           typename NF = typename DGR::template NodeMap<bool>,
 		           typename AF = typename DGR::template ArcMap<bool> >
 		  class SubDigraph :
 		    public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {
 		#endif
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		    /// The type of the node filter map.
 		    typedef NF NodeFilterMap;
 		    /// The type of the arc filter map.
 		    typedef AF ArcFilterMap;
 		    typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >
 		      Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    SubDigraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subdigraph for the given digraph with the
@@ -1269,96 +1274,98 @@
 		    template <typename V>
 		    class EdgeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 			LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding nodes and edges in an undirected
 		  /// graph.
 		  ///
 		  /// SubGraph can be used for hiding nodes and edges in a graph.
 		  /// A \c bool node map and a \c bool edge map must be specified, which
 		  /// define the filters for nodes and edges.
 		  /// Only the nodes and edges with \c true filter value are
 		  /// shown in the subgraph. The edges that are incident to hidden
 		  /// nodes are also filtered out.
 		  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
 		  ///
 		  /// The adapted graph can also be modified through this adaptor
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time counting for nodes, edges and arcs.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam NF The type of the node filter map.
 		  /// It must be a \c bool (or convertible) node map of the
 		  /// adapted graph. The default type is
 		  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
 		  /// \tparam EF The type of the edge filter map.
 		  /// It must be a \c bool (or convertible) edge map of the
 		  /// adapted graph. The default type is
 		  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
 		  ///
 		  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
 		  /// adapted graph are convertible to each other.
 		  ///
 		  /// \see FilterNodes
 		  /// \see FilterEdges
 		#ifdef DOXYGEN
 		  template<typename GR, typename NF, typename EF>
 		  class SubGraph {
 		#else
 		  template<typename GR,
 		           typename NF = typename GR::template NodeMap<bool>,
 		           typename EF = typename GR::template EdgeMap<bool> >
 		  class SubGraph :
 		    public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {
 		#endif
 		  public:
 		    /// The type of the adapted graph.
 		    typedef GR Graph;
 		    /// The type of the node filter map.
 		    typedef NF NodeFilterMap;
 		    /// The type of the edge filter map.
 		    typedef EF EdgeFilterMap;
 		    typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> >
 		      Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    SubGraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given graph with the given node
@@ -1426,96 +1433,98 @@
 		  /// This function just returns a read-only \ref SubGraph adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates SubGraph
 		  template<typename GR, typename NF, typename EF>
 		  SubGraph<const GR, NF, EF>
 		  subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {
 		    return SubGraph<const GR, NF, EF>
 		      (graph, node_filter, edge_filter);
+		  }
 		  template<typename GR, typename NF, typename EF>
 		  SubGraph<const GR, const NF, EF>
 		  subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {
 		    return SubGraph<const GR, const NF, EF>
 		      (graph, node_filter, edge_filter);
+		  }
 		  template<typename GR, typename NF, typename EF>
 		  SubGraph<const GR, NF, const EF>
 		  subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {
 		    return SubGraph<const GR, NF, const EF>
 		      (graph, node_filter, edge_filter);
+		  }
 		  template<typename GR, typename NF, typename EF>
 		  SubGraph<const GR, const NF, const EF>
 		  subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {
 		    return SubGraph<const GR, const NF, const EF>
 		      (graph, node_filter, edge_filter);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding nodes in a digraph or a graph.
 		  ///
 		  /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
 		  /// graph. A \c bool node map must be specified, which defines the filter
 		  /// for the nodes. Only the nodes with \c true filter value and the
 		  /// arcs/edges incident to nodes both with \c true filter value are shown
 		  /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
 		  /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
 		  /// depending on the \c GR template parameter.
 		  ///
 		  /// The adapted (di)graph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs/edges, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time item counting.
 		  ///
 		  /// \tparam GR The type of the adapted digraph or graph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept
 		  /// or the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam NF The type of the node filter map.
 		  /// It must be a \c bool (or convertible) node map of the
 		  /// adapted (di)graph. The default type is
 		  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
 		  ///
 		  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
 		  /// adapted (di)graph are convertible to each other.
 		#ifdef DOXYGEN
 		  template<typename GR, typename NF>
 		  class FilterNodes {
 		#else
 		  template<typename GR,
 		           typename NF = typename GR::template NodeMap<bool>,
 		           typename Enable = void>
 		  class FilterNodes :
 		    public DigraphAdaptorExtender<
 		      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
 		                     true> > {
 		#endif
 		    typedef DigraphAdaptorExtender<
 		      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
 		                     true> > Parent;
 		  public:
 		    typedef GR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
 		    FilterNodes() : const_true_map() {}
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given digraph or graph with the
 		    /// given node filter map.
 		    FilterNodes(GR& graph, NF& node_filter)
 		      : Parent(), const_true_map()
+		    {
@@ -1574,96 +1583,98 @@
 		    FilterNodes() : const_true_map() {}
 		  public:
 		    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
 		      Parent(), const_true_map() {
 		      Parent::initialize(graph, node_filter, const_true_map);
+		    }
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    void disable(const Node& n) const { Parent::status(n, false); }
 		    void enable(const Node& n) const { Parent::status(n, true); }
 		  };
 		  /// \brief Returns a read-only FilterNodes adaptor
 		  ///
 		  /// This function just returns a read-only \ref FilterNodes adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates FilterNodes
 		  template<typename GR, typename NF>
 		  FilterNodes<const GR, NF>
 		  filterNodes(const GR& graph, NF& node_filter) {
 		    return FilterNodes<const GR, NF>(graph, node_filter);
+		  }
 		  template<typename GR, typename NF>
 		  FilterNodes<const GR, const NF>
 		  filterNodes(const GR& graph, const NF& node_filter) {
 		    return FilterNodes<const GR, const NF>(graph, node_filter);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding arcs in a digraph.
 		  ///
 		  /// FilterArcs adaptor can be used for hiding arcs in a digraph.
 		  /// A \c bool arc map must be specified, which defines the filter for
 		  /// the arcs. Only the arcs with \c true filter value are shown in the
 		  /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
 		  /// "Digraph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time counting for nodes and arcs.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam AF The type of the arc filter map.
 		  /// It must be a \c bool (or convertible) arc map of the
 		  /// adapted digraph. The default type is
 		  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
 		  ///
 		  /// \note The \c Node and \c Arc types of this adaptor and the adapted
 		  /// digraph are convertible to each other.
 		#ifdef DOXYGEN
 		  template<typename DGR,
 		           typename AF>
 		  class FilterArcs {
 		#else
 		  template<typename DGR,
 		           typename AF = typename DGR::template ArcMap<bool> >
 		  class FilterArcs :
 		    public DigraphAdaptorExtender<
 		      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
 		                     AF, false> > {
 		#endif
 		    typedef DigraphAdaptorExtender<
 		      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
 		                     AF, false> > Parent;
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		    /// The type of the arc filter map.
 		    typedef AF ArcFilterMap;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
 		    FilterArcs() : const_true_map() {}
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subdigraph for the given digraph with the given arc
 		    /// filter map.
 		    FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
 		      : Parent(), const_true_map() {
@@ -1684,96 +1695,98 @@
 		    bool status(const Arc& a) const { return Parent::status(a); }
 		    /// \brief Disables the given arc
 		    ///
 		    /// This function disables the given arc in the subdigraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(a, false)".
 		    void disable(const Arc& a) const { Parent::status(a, false); }
 		    /// \brief Enables the given arc
 		    ///
 		    /// This function enables the given arc in the subdigraph.
 		    /// It is the same as \ref status() "status(a, true)".
 		    void enable(const Arc& a) const { Parent::status(a, true); }
 		  };
 		  /// \brief Returns a read-only FilterArcs adaptor
 		  ///
 		  /// This function just returns a read-only \ref FilterArcs adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates FilterArcs
 		  template<typename DGR, typename AF>
 		  FilterArcs<const DGR, AF>
 		  filterArcs(const DGR& digraph, AF& arc_filter) {
 		    return FilterArcs<const DGR, AF>(digraph, arc_filter);
+		  }
 		  template<typename DGR, typename AF>
 		  FilterArcs<const DGR, const AF>
 		  filterArcs(const DGR& digraph, const AF& arc_filter) {
 		    return FilterArcs<const DGR, const AF>(digraph, arc_filter);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding edges in a graph.
 		  ///
 		  /// FilterEdges adaptor can be used for hiding edges in a graph.
 		  /// A \c bool edge map must be specified, which defines the filter for
 		  /// the edges. Only the edges with \c true filter value are shown in the
 		  /// subgraph. This adaptor conforms to the \ref concepts::Graph
 		  /// "Graph" concept.
 		  ///
 		  /// The adapted graph can also be modified through this adaptor
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time counting for nodes, edges and arcs.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam EF The type of the edge filter map.
 		  /// It must be a \c bool (or convertible) edge map of the
 		  /// adapted graph. The default type is
 		  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
 		  ///
 		  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
 		  /// adapted graph are convertible to each other.
 		#ifdef DOXYGEN
 		  template<typename GR,
 		           typename EF>
 		  class FilterEdges {
 		#else
 		  template<typename GR,
 		           typename EF = typename GR::template EdgeMap<bool> >
 		  class FilterEdges :
 		    public GraphAdaptorExtender<
 		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
 		                   EF, false> > {
 		#endif
 		    typedef GraphAdaptorExtender<
 		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
 		                   EF, false> > Parent;
 		  public:
 		    /// The type of the adapted graph.
 		    typedef GR Graph;
 		    /// The type of the edge filter map.
 		    typedef EF EdgeFilterMap;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
 		    FilterEdges() : const_true_map(true) {
 		      Parent::setNodeFilterMap(const_true_map);
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given graph with the given edge
 		    /// filter map.
@@ -2187,96 +2200,99 @@
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
 		    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
 		    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
 		    typedef EdgeNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
 		  protected:
 		    UndirectorBase() : _digraph(0) {}
 		    DGR* _digraph;
 		    void initialize(DGR& digraph) {
 		      _digraph = &digraph;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for viewing a digraph as an undirected graph.
 		  ///
 		  /// Undirector adaptor can be used for viewing a digraph as an undirected
 		  /// graph. All arcs of the underlying digraph are showed in the
 		  /// adaptor as an edge (and also as a pair of arcs, of course).
 		  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides item counting in the same time as the adapted
 		  /// digraph structure.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  ///
 		  /// \note The \c Node type of this adaptor and the adapted digraph are
 		  /// convertible to each other, moreover the \c Edge type of the adaptor
 		  /// and the \c Arc type of the adapted digraph are also convertible to
 		  /// each other.
 		  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
 		  /// of the adapted digraph.)
 		  template<typename DGR>
 		#ifdef DOXYGEN
 		  class Undirector {
 		#else
 		  class Undirector :
 		    public GraphAdaptorExtender<UndirectorBase<DGR> > {
 		#endif
 		    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		  protected:
 		    Undirector() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates an undirected graph from the given digraph.
 		    Undirector(DGR& digraph) {
 		      initialize(digraph);
+		    }
 		    /// \brief Arc map combined from two original arc maps
 		    ///
 		    /// This map adaptor class adapts two arc maps of the underlying
 		    /// digraph to get an arc map of the undirected graph.
 		    /// Its value type is inherited from the first arc map type (\c FW).
 		    /// \tparam FW The type of the "foward" arc map.
 		    /// \tparam BK The type of the "backward" arc map.
 		    template <typename FW, typename BK>
 		    class CombinedArcMap {
 		    public:
 		      /// The key type of the map
 		      typedef typename Parent::Arc Key;
 		      /// The value type of the map
 		      typedef typename FW::Value Value;
@@ -2490,96 +2506,99 @@
 		    public:
 		      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
 		        : Parent(*adapter._graph) { }
 		      ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
 		        : Parent(*adapter._graph, value) { }
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  protected:
 		    Graph* _graph;
 		    DM* _direction;
 		    void initialize(GR& graph, DM& direction) {
 		      _graph = &graph;
 		      _direction = &direction;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for orienting the edges of a graph to get a digraph
 		  ///
 		  /// Orienter adaptor can be used for orienting the edges of a graph to
 		  /// get a digraph. A \c bool edge map of the underlying graph must be
 		  /// specified, which define the direction of the arcs in the adaptor.
 		  /// The arcs can be easily reversed by the \c reverseArc() member function
 		  /// of the adaptor.
 		  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// The adapted graph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides item counting in the same time as the adapted
 		  /// graph structure.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam DM The type of the direction map.
 		  /// It must be a \c bool (or convertible) edge map of the
 		  /// adapted graph. The default type is
 		  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
 		  ///
 		  /// \note The \c Node type of this adaptor and the adapted graph are
 		  /// convertible to each other, moreover the \c Arc type of the adaptor
 		  /// and the \c Edge type of the adapted graph are also convertible to
 		  /// each other.
 		#ifdef DOXYGEN
 		  template<typename GR,
 		           typename DM>
 		  class Orienter {
 		#else
 		  template<typename GR,
 		           typename DM = typename GR::template EdgeMap<bool> >
 		  class Orienter :
 		    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
 		#endif
 		    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
 		  public:
 		    /// The type of the adapted graph.
 		    typedef GR Graph;
 		    /// The type of the direction edge map.
 		    typedef DM DirectionMap;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    Orienter() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the adaptor.
 		    Orienter(GR& graph, DM& direction) {
 		      Parent::initialize(graph, direction);
+		    }
 		    /// \brief Reverses the given arc
 		    ///
 		    /// This function reverses the given arc.
 		    /// It is done by simply negate the assigned value of \c a
@@ -2633,96 +2652,98 @@
 		    };
 		    template<typename DGR,typename CM, typename FM, typename TL>
 		    class ResBackwardFilter {
 		    public:
 		      typedef typename DGR::Arc Key;
 		      typedef bool Value;
 		    private:
 		      const CM* _capacity;
 		      const FM* _flow;
 		      TL _tolerance;
 		    public:
 		      ResBackwardFilter(const CM& capacity, const FM& flow,
 		                        const TL& tolerance = TL())
 		        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
 		      bool operator[](const typename DGR::Arc& a) const {
 		        return _tolerance.positive((*_flow)[a]);
+		      }
 		    };
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for composing the residual digraph for directed
 		  /// flow and circulation problems.
 		  ///
 		  /// ResidualDigraph can be used for composing the \e residual digraph
 		  /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
 		  /// be a directed graph and let \f$ F \f$ be a number type.
 		  /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
 		  /// This adaptor implements a digraph structure with node set \f$ V \f$
 		  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
 		  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
 		  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
 		  /// called residual digraph.
 		  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
 		  /// multiplicities are counted, i.e. the adaptor has exactly
 		  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
 		  /// arcs).
 		  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// This class provides only linear time counting for nodes and arcs.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It is implicitly \c const.
 		  /// \tparam CM The type of the capacity map.
 		  /// It must be an arc map of some numerical type, which defines
 		  /// the capacities in the flow problem. It is implicitly \c const.
 		  /// The default type is
 		  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam FM The type of the flow map.
 		  /// It must be an arc map of some numerical type, which defines
 		  /// the flow values in the flow problem. The default type is \c CM.
 		  /// \tparam TL The tolerance type for handling inexact computation.
 		  /// The default tolerance type depends on the value type of the
 		  /// capacity map.
 		  ///
 		  /// \note This adaptor is implemented using Undirector and FilterArcs
 		  /// adaptors.
 		  ///
 		  /// \note The \c Node type of this adaptor and the adapted digraph are
 		  /// convertible to each other, moreover the \c Arc type of the adaptor
 		  /// is convertible to the \c Arc type of the adapted digraph.
 		#ifdef DOXYGEN
 		  template<typename DGR, typename CM, typename FM, typename TL>
 		  class ResidualDigraph
 		#else
 		  template<typename DGR,
 		           typename CM = typename DGR::template ArcMap<int>,
 		           typename FM = CM,
 		           typename TL = Tolerance<typename CM::Value> >
 		  class ResidualDigraph
 		    : public SubDigraph<
 		        Undirector<const DGR>,
 		        ConstMap<typename DGR::Node, Const<bool, true> >,
 		        typename Undirector<const DGR>::template CombinedArcMap<
 		          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
 		          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
 		#endif
+		  {
 		  public:
 		    /// The type of the underlying digraph.
 		    typedef DGR Digraph;
 		    /// The type of the capacity map.
 		    typedef CM CapacityMap;
 		    /// The type of the flow map.
 		    typedef FM FlowMap;
 		    /// The tolerance type.
 		    typedef TL Tolerance;
@@ -3280,96 +3301,99 @@
 		      ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  protected:
 		    SplitNodesBase() : _digraph(0) {}
 		    DGR* _digraph;
 		    void initialize(Digraph& digraph) {
 		      _digraph = &digraph;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for splitting the nodes of a digraph.
 		  ///
 		  /// SplitNodes adaptor can be used for splitting each node into an
 		  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
 		  /// replaces each node \f$ u \f$ in the digraph with two nodes,
 		  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
 		  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
 		  /// new target of the arc will be \f$ u_{in} \f$ and similarly the
 		  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
 		  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
 		  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
 		  ///
 		  /// The aim of this class is running an algorithm with respect to node
 		  /// costs or capacities if the algorithm considers only arc costs or
 		  /// capacities directly.
 		  /// In this case you can use \c SplitNodes adaptor, and set the node
 		  /// costs/capacities of the original digraph to the \e bind \e arcs
 		  /// in the adaptor.
 		  ///
 		  /// This class provides item counting in the same time as the adapted
 		  /// digraph structure.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It is implicitly \c const.
 		  ///
 		  /// \note The \c Node type of this adaptor is converible to the \c Node
 		  /// type of the adapted digraph.
 		  template <typename DGR>
 		#ifdef DOXYGEN
 		  class SplitNodes {
 		#else
 		  class SplitNodes
 		    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
 		#endif
 		    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
 		  public:
 		    typedef DGR Digraph;
 		    typedef typename DGR::Node DigraphNode;
 		    typedef typename DGR::Arc DigraphArc;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the adaptor.
 		    SplitNodes(const DGR& g) {
 		      Parent::initialize(g);
+		    }
 		    /// \brief Returns \c true if the given node is an in-node.
 		    ///
 		    /// Returns \c true if the given node is an in-node.
 		    static bool inNode(const Node& n) {
 		      return Parent::inNode(n);
+		    }
 		    /// \brief Returns \c true if the given node is an out-node.
 		    ///
 		    /// Returns \c true if the given node is an out-node.
 		    static bool outNode(const Node& n) {
 		      return Parent::outNode(n);
+		    }
 		    /// \brief Returns \c true if the given arc is an original arc.
 		    ///
 		    /// Returns \c true if the given arc is one of the arcs in the

lemon/bellman_ford.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_BELLMAN_FORD_H
 		#define LEMON_BELLMAN_FORD_H
 		/// \ingroup shortest_path
 		/// \file
 		/// \brief Bellman-Ford algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		#include <limits>
 		namespace lemon {
 		  /// \brief Default OperationTraits for the BellmanFord algorithm class.
 		  ///
 		  /// This operation traits class defines all computational operations
 		  /// and constants that are used in the Bellman-Ford algorithm.
 		  /// The default implementation is based on the \c numeric_limits class.
 		  /// If the numeric type does not have infinity value, then the maximum
 		  /// value is used as extremal infinity value.
 		  template <
 		    typename V,
 		    bool has_inf = std::numeric_limits<V>::has_infinity>
 		  struct BellmanFordDefaultOperationTraits {
 		    /// \e
 		    typedef V Value;
 		    /// \brief Gives back the zero value of the type.
 		    static Value zero() {
 		      return static_cast<Value>(0);
+		    }
 		    /// \brief Gives back the positive infinity value of the type.
 		    static Value infinity() {
 		      return std::numeric_limits<Value>::infinity();
+		    }
 		    /// \brief Gives back the sum of the given two elements.
 		    static Value plus(const Value& left, const Value& right) {
 		      return left + right;
+		    }
 		    /// \brief Gives back \c true only if the first value is less than
 		    /// the second.
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  template <typename V>
 		  struct BellmanFordDefaultOperationTraits<V, false> {
 		    typedef V Value;
 		    static Value zero() {
 		      return static_cast<Value>(0);
+		    }
@@ -254,97 +255,97 @@
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c PredMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c PredMap type.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap
 		      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
 		      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph&) {
 		        LEMON_ASSERT(false, "DistMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c DistMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c DistMap type.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap
 		      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
 		      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetOperationTraitsTraits : public Traits {
 		      typedef T OperationTraits;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c OperationTraits type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c OperationTraits type.
 		    /// For more information see \ref BellmanFordDefaultOperationTraits.
+		    /// For more information, see \ref BellmanFordDefaultOperationTraits.
 		    template <class T>
 		    struct SetOperationTraits
 		      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
 		      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
 		      Create;
 		    };
 		    ///@}
 		  protected:
 		    BellmanFord() {}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param length The length map used by the algorithm.
 		    BellmanFord(const Digraph& g, const LengthMap& length) :
 		      _gr(&g), _length(&length),
 		      _pred(0), _local_pred(false),
 		      _dist(0), _local_dist(false), _mask(0) {}
 		    ///Destructor.
 		    ~BellmanFord() {
 		      if(_local_pred) delete _pred;
 		      if(_local_dist) delete _dist;
 		      if(_mask) delete _mask;
+		    }
 		    /// \brief Sets the length map.
 		    ///
 		    /// Sets the length map.
 		    /// \return <tt>(*this)</tt>
 		    BellmanFord &lengthMap(const LengthMap &map) {
 		      _length = &map;
 		      return *this;
+		    }
 		    /// \brief 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()
 		    /// or \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
@@ -672,155 +673,155 @@
 		        return static_cast<Node>(*this) < static_cast<Node>(it);
+		      }
 		    private:
 		      const BellmanFord* _algorithm;
 		      int _index;
 		    };
 		    /// \name Query Functions
 		    /// The result of the Bellman-Ford algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either \ref run() or \ref init() should be called before using them.
 		    ///@{
 		    /// \brief The shortest path to the given node.
 		    ///
 		    /// Gives back the shortest path to the given node from the root(s).
 		    ///
 		    /// \warning \c t should be reached from the root(s).
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Path path(Node t) const
+		    {
 		      return Path(*_gr, *_pred, t);
+		    }
 		    /// \brief The distance of the given node from the root(s).
 		    ///
 		    /// Returns the distance of the given node from the root(s).
 		    ///
 		    /// \warning If node \c v is not reached from the root(s), then
 		    /// the return value of this function is undefined.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Value dist(Node v) const { return (*_dist)[v]; }
 		    /// \brief Returns the 'previous arc' of the shortest path tree for
 		    /// the given node.
 		    ///
 		    /// This function returns the 'previous arc' of the shortest path
 		    /// tree for node \c v, i.e. it returns the last arc of a
 		    /// shortest path from a root to \c v. It is \c INVALID if \c v
 		    /// is not reached 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() and \predMap().
+		    /// tree used in \ref predNode() and \ref predMap().
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v]; }
 		    /// \brief Returns the 'previous node' of the shortest path tree for
 		    /// the given node.
 		    ///
 		    /// This function returns the 'previous node' of the shortest path
 		    /// tree for node \c v, i.e. it returns the last but one node of
 		    /// a shortest path from a root to \c v. It is \c INVALID if \c v
 		    /// is not reached 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() and \predMap().
+		    /// tree used in \ref predArc() and \ref predMap().
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Node predNode(Node v) const {
 		      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
+		    }
 		    /// \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;}
 		    /// \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 (forest).
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const PredMap &predMap() const { return *_pred; }
 		    /// \brief Checks if a node is reached from the root(s).
 		    ///
 		    /// Returns \c true if \c v is reached from the root(s).
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    bool reached(Node v) const {
 		      return (*_dist)[v] != OperationTraits::infinity();
+		    }
 		    /// \brief Gives back a negative cycle.
 		    ///
 		    /// This function gives back a directed cycle with negative total
 		    /// length if the algorithm has already found one.
 		    /// Otherwise it gives back an empty path.
 		    lemon::Path<Digraph> negativeCycle() {
+		    lemon::Path<Digraph> negativeCycle() const {
 		      typename Digraph::template NodeMap<int> state(*_gr, -1);
 		      lemon::Path<Digraph> cycle;
 		      for (int i = 0; i < int(_process.size()); ++i) {
 		        if (state[_process[i]] != -1) continue;
 		        for (Node v = _process[i]; (*_pred)[v] != INVALID;
 		             v = _gr->source((*_pred)[v])) {
 		          if (state[v] == i) {
 		            cycle.addFront((*_pred)[v]);
 		            for (Node u = _gr->source((*_pred)[v]); u != v;
 		                 u = _gr->source((*_pred)[u])) {
 		              cycle.addFront((*_pred)[u]);
+		            }
 		            return cycle;
+		          }
 		          else if (state[v] >= 0) {
 		            break;
+		          }
 		          state[v] = i;
+		        }
+		      }
 		      return cycle;
+		    }
 		    ///@}
 		  };
 		  /// \brief Default traits class of bellmanFord() function.
 		  ///
 		  /// Default traits class of bellmanFord() function.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  template <typename GR, typename LEN>
 		  struct BellmanFordWizardDefaultTraits {
 		    /// The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc lengths.
 		    ///
 		    /// The type of the map that stores the arc lengths.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths.
 		    typedef typename LEN::Value Value;
 		    /// \brief Operation traits for Bellman-Ford algorithm.
 		    ///
 		    /// It defines the used operations and the infinity value for the

lemon/bfs.h

Show inline comments

@@ -2,146 +2,147 @@
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_BFS_H
 		#define LEMON_BFS_H
 		///\ingroup search
 		///\file
 		///\brief BFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///Default traits class of Bfs class.
 		  ///Default traits class of Bfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \c PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref 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.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \c ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    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::ReadWriteMap "ReadWriteMap" concept.
+		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \c 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 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.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \c 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 Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%BFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %BFS algorithm.
 		  ///
 		  ///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 type is \ref ListDigraph.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=BfsDefaultTraits<GR> >
 		#endif
 		  class Bfs {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\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 distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
@@ -180,157 +181,157 @@
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Bfs() {}
 		  public:
 		    typedef Bfs Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 		      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "DistMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
-		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
 		    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ProcessedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap :
 		      public Bfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
 		    ///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),
 		      _reached(NULL), local_reached(false),
 		      _processed(NULL), local_processed(false)
 		    { }
 		    ///Destructor.
 		    ~Bfs()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_reached) delete _reached;
 		      if(local_processed) delete _processed;
+		    }
@@ -368,98 +369,98 @@
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		    ///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(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &processedMap(ProcessedMap &m)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
+		      }
 		      _processed = &m;
 		      return *this;
+		    }
 		    ///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(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Bfs &distMap(DistMap &m)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;
+		    }
 		  public:
 		    ///\name Execution Control
 		    ///The simplest way to execute the BFS algorithm is to use one of the
 		    ///member functions called \ref run(Node) "run()".\n
 		    ///If you need more control on the execution, first you have to call
 		    ///\ref init(), then you can add several source nodes with
 		    ///If you need better control on the execution, you have to call
 		    ///\ref init() first, then you can add several source nodes with
 		    ///\ref addSource(). Finally the actual path computation can be
 		    ///performed with one of the \ref start() functions.
 		    ///@{
 		    ///\brief Initializes the internal data structures.
 		    ///
 		    ///Initializes the internal data structures.
 		    void init()
+		    {
 		      create_maps();
 		      _queue.resize(countNodes(*G));
 		      _queue_head=_queue_tail=0;
 		      _curr_dist=1;
 		      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 		        _pred->set(u,INVALID);
 		        _reached->set(u,false);
 		        _processed->set(u,false);
+		      }
+		    }
 		    ///Adds a new source node.
 		    ///Adds a new source node to the set of nodes to be processed.
 		    ///
 		    void addSource(Node s)
+		    {
 		      if(!(*_reached)[s])
+		        {
 		          _reached->set(s,true);
 		          _pred->set(s,INVALID);
 		          _dist->set(s,0);
 		          _queue[_queue_head++]=s;
 		          _queue_next_dist=_queue_head;
+		        }
+		    }
 		    ///Processes the next node.
 		    ///Processes the next node.
 		    ///
 		    ///\return The processed node.
 		    ///
 		    ///\pre The queue must not be empty.
 		    Node processNextNode()
+		    {
 		      if(_queue_tail==_queue_next_dist) {
 		        _curr_dist++;
@@ -655,522 +656,514 @@
 		      return rnode;
+		    }
 		    ///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 <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  b.addSource(s);
 		    ///  b.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///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, <tt>b.run(s,t)</tt> 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);
+		    }
 		    ///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).
 		    ///This method runs the %BFS algorithm in order to visit all nodes
 		    ///in the digraph.
 		    ///
 		    ///\note <tt>b.run(s)</tt> 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();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The results of the BFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref run(Node) "run()" or \ref start() should be called
 		    ///before using them.
 		    ///@{
-		    ///The shortest path to a node.
+		    ///The shortest path to the given node.
-		    ///Returns the shortest path to a node.
+		    ///Returns the shortest path to the given node from the root(s).
 		    ///
 		    ///\warning \c t should be reached from the root(s).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///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).
+		    ///The distance of the given node from the root(s).
-		    ///Returns the distance of a node from the root(s).
+		    ///Returns the distance of the given node from the root(s).
 		    ///
 		    ///\warning If node \c v is not reached from the root(s), then
 		    ///the return value of this function is undefined.
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///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.
 		    ///\brief Returns the 'previous arc' of the shortest path tree for
 		    ///the given 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 a root to \c v. It is \c INVALID if \c v
 		    ///is not reached 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().
+		    ///tree used in \ref predNode() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///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.
 		    ///\brief Returns the 'previous node' of the shortest path tree for
 		    ///the given 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 a root to \c v. It is \c INVALID
+		    ///of a shortest path from a root to \c v. It is \c INVALID
 		    ///if \c v is not reached 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().
+		    ///tree used in \ref predArc() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->source((*_pred)[v]); }
 		    ///\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(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\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.
+		    ///arcs, which form the shortest path tree (forest).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
-		    ///Checks if a node is reached from the root(s).
+		    ///Checks if the given node is reached from the root(s).
 		    ///Returns \c true if \c v is reached from the root(s).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///Default traits class of bfs() function.
 		  ///Default traits class of bfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsWizardDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a 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);
+		    }
 		    ///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.
 		    ///By default it is a NullMap.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
 		    ///This function instantiates a ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    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::ReadWriteMap "ReadWriteMap" concept.
+		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a ReachedMap.
 		    ///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.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a DistMap.
 		    ///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);
+		    }
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
-		    ///It must meet the \ref concepts::Path "Path" concept.
+		    ///It must conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by BfsWizard
 		  /// To make it easier to use Bfs algorithm
 		  /// we have created a wizard class.
 		  /// This \ref BfsWizard class needs default traits,
 		  /// as well as the \ref Bfs class.
 		  /// The \ref BfsWizardBase is a class to be the default traits of the
 		  /// \ref BfsWizard class.
 		  /// Default traits class used by BfsWizard.
 		  /// \tparam GR The type of the digraph.
 		  template<class GR>
 		  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
+		  {
 		    typedef BfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the shortest path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    int *_di;
 		    public:
 		    /// Constructor.
-		    /// This constructor does not require parameters, therefore it initiates
 		    /// This constructor does not require parameters, it initiates
 		    /// all of the attributes to \c 0.
 		    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// 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<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
 		  /// 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(Node) "run()" method, it uses the
 		  /// functions and features of the plain \ref Bfs.
 		  ///
 		  /// This class should only be used through the \ref bfs() function,
 		  /// which makes it easier to use the algorithm.
 		  template<class TR>
 		  class BfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///\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() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param g The digraph the algorithm runs on.
 		    BfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
 		    BfsWizard(const TR &b) : TR(b) {}
 		    ~BfsWizard() {}
 		    ///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<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(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<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      alg.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(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.
 		    ///This method runs BFS algorithm in order to visit all nodes
 		    ///in the digraph.
 		    void run()
+		    {
 		      run(INVALID);
+		    }
 		    template<class T>
 		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting PredMap object.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the predecessor map.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for setting PredMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting ReachedMap object.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the reached map.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting ReachedMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are reached.
 		    template<class T>
 		    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    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.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the distance map.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting DistMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the distances of the nodes calculated
 		    ///by the algorithm.
 		    template<class T>
 		    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetDistMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting ProcessedMap object.
 		    ///\brief \ref named-func-param "Named parameter" for setting
 		    ///the processed map.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting ProcessedMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are processed.
 		    template<class T>
 		    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetPathBase : public Base {
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    ///\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<class T>
 		    BfsWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetPathBase<T> >(*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<int*>(&d);
 		      return *this;
+		    }
 		  };
 		  ///Function-type interface for BFS algorithm.
 		  /// \ingroup search
 		  ///Function-type interface for BFS algorithm.
 		  ///
 		  ///This function also has several \ref named-func-param "named parameters",
 		  ///they are declared as the members of class \ref BfsWizard.
 		  ///The following examples show how to use these parameters.
 		  ///\code
 		  ///  // Compute shortest path from node s to each node
 		  ///  bfs(g).predMap(preds).distMap(dists).run(s);
@@ -1219,97 +1212,97 @@
 		    /// \brief Called when an arc is examined but its target node is
 		    /// already discovered.
 		    ///
 		    /// This function is called when an arc is examined but its target node is
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		  };
 		#else
 		  template <typename GR>
 		  struct BfsVisitor {
 		    typedef GR Digraph;
 		    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 examine(const Arc&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 		        Arc arc;
 		        Node node;
 		        visitor.start(node);
 		        visitor.reach(node);
 		        visitor.process(node);
 		        visitor.discover(arc);
 		        visitor.examine(arc);
+		      }
 		      _Visitor& visitor;
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of BfsVisit class.
 		  ///
 		  /// Default traits class of BfsVisit class.
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  template<class GR>
 		  struct BfsVisitDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief 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::ReadWriteMap "ReadWriteMap" concept.
+		    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a ReachedMap.
 		    ///
 		    /// This function instantiates a ReachedMap.
 		    /// \param digraph is the digraph, to which
 		    /// we would like to define the ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &digraph) {
 		      return new ReachedMap(digraph);
+		    }
 		  };
 		  /// \ingroup search
 		  ///
 		  /// \brief BFS algorithm class with visitor interface.
 		  ///
 		  /// This class provides an efficient implementation of the BFS algorithm
 		  /// with visitor interface.
 		  ///
 		  /// The BfsVisit class provides an alternative interface to the Bfs
 		  /// class. It works with callback mechanism, the BfsVisit object calls
 		  /// the member functions of the \c Visitor class on every BFS event.
 		  ///
 		  /// 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 GR The type of the digraph the algorithm runs on.
 		  /// The default type is \ref ListDigraph.
 		  /// The value of GR is not used directly by \ref BfsVisit,
 		  /// it is only passed to \ref BfsVisitDefaultTraits.
 		  /// \tparam VS The Visitor type that is used by the algorithm.
 		  /// \ref BfsVisitor "BfsVisitor<GR>" 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 TR Traits class to set various data types used by the
 		  /// algorithm. The default traits class is
 		  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
 		  /// See \ref BfsVisitDefaultTraits for the documentation of
 		  /// a BFS visit traits class.
 		#ifdef DOXYGEN
 		  template <typename GR, typename VS, typename TR>
 		#else
 		  template <typename GR = ListDigraph,
 		            typename VS = BfsVisitor<GR>,
 		            typename TR = BfsVisitDefaultTraits<GR> >
@@ -1380,98 +1373,98 @@
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public BfsVisit< Digraph, Visitor,
 		                                            SetReachedMapTraits<T> > {
 		      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \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),
 		        _reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ~BfsVisit() {
 		      if(local_reached) delete _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(Node) "run()"
 		    /// or \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt> (*this) </tt>
 		    BfsVisit &reachedMap(ReachedMap &m) {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached = false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  public:
 		    /// \name Execution Control
 		    /// The simplest way to execute the BFS algorithm is to use one of the
 		    /// member functions called \ref run(Node) "run()".\n
 		    /// If you need more control on the execution, first you have to call
 		    /// \ref init(), then you can add several source nodes with
 		    /// If you need better control on the execution, you have to call
 		    /// \ref init() first, then you can add several source nodes with
 		    /// \ref addSource(). Finally the actual path computation can be
 		    /// performed with one of the \ref start() functions.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    void init() {
 		      create_maps();
 		      _list.resize(countNodes(*_digraph));
 		      _list_front = _list_back = -1;
 		      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
 		        _reached->set(u, false);
+		      }
+		    }
 		    /// \brief Adds a new source node.
 		    ///
 		    /// Adds a new source node to the set of nodes to be processed.
 		    void addSource(Node s) {
 		      if(!(*_reached)[s]) {
 		          _reached->set(s,true);
 		          _visitor->start(s);
 		          _visitor->reach(s);
 		          _list[++_list_back] = s;
+		        }
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    Node processNextNode() {
 		      Node n = _list[++_list_front];
 		      _visitor->process(n);
 		      Arc e;
 		      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
 		        Node m = _digraph->target(e);
 		        if (!(*_reached)[m]) {
 		          _visitor->discover(e);
 		          _visitor->reach(m);
 		          _reached->set(m, true);
 		          _list[++_list_back] = m;
 		        } else {
@@ -1653,100 +1646,96 @@
 		      return rnode;
+		    }
 		    /// \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 <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///   b.init();
 		    ///   b.addSource(s);
 		    ///   b.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    /// \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, <tt>b.run(s,t)</tt> 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 shortest path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree (forest),
 		    /// - the distance of each node from the root(s).
 		    /// This method runs the %BFS algorithm in order to visit all nodes
 		    /// in the digraph.
 		    ///
 		    /// \note <tt>b.run(s)</tt> 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 it(*_digraph); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    /// \name Query Functions
 		    /// The results of the BFS algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either \ref run(Node) "run()" or \ref start() should be called
 		    /// before using them.
 		    ///@{
-		    /// \brief Checks if a node is reached from the root(s).
+		    /// \brief Checks if the given node is reached from the root(s).
 		    ///
 		    /// Returns \c true if \c v is reached from the root(s).
 		    ///
 		    /// \pre Either \ref run(Node) "run()" or \ref init()
 		    /// must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif

lemon/bits/graph_extender.h

Show inline comments

@@ -11,101 +11,101 @@
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_BITS_GRAPH_EXTENDER_H
 		#define LEMON_BITS_GRAPH_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/bits/map_extender.h>
 		#include <lemon/bits/default_map.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		//\ingroup graphbits
 		//\file
 		//\brief Extenders for the graph types
 		namespace lemon {
 		  // \ingroup graphbits
 		  //
 		  // \brief Extender for the digraph implementations
 		  template <typename Base>
 		  class DigraphExtender : public Base {
 		    typedef Base Parent;
 		  public:
 		    typedef DigraphExtender Digraph;
 		    // Base extensions
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
-		    Node fromId(int id, Node) const {
+		    static Node fromId(int id, Node) {
 		      return Parent::nodeFromId(id);
+		    }
-		    Arc fromId(int id, Arc) const {
+		    static Arc fromId(int id, Arc) {
 		      return Parent::arcFromId(id);
+		    }
 		    Node oppositeNode(const Node &node, const Arc &arc) const {
 		      if (node == Parent::source(arc))
 		        return Parent::target(arc);
 		      else if(node == Parent::target(arc))
 		        return Parent::source(arc);
 		      else
 		        return INVALID;
+		    }
 		    // Alterable extension
 		    typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
 		    typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
 		  protected:
 		    mutable NodeNotifier node_notifier;
 		    mutable ArcNotifier arc_notifier;
 		  public:
 		    NodeNotifier& notifier(Node) const {
 		      return node_notifier;
+		    }
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    class NodeIt : public Node {
 		      const Digraph* _digraph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
 		        _digraph->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Digraph& digraph, const Node& node)
 		        : Node(node), _digraph(&digraph) {}
@@ -310,105 +310,105 @@
 		    void erase(const Arc& arc) {
 		      notifier(Arc()).erase(arc);
 		      Parent::erase(arc);
+		    }
 		    DigraphExtender() {
 		      node_notifier.setContainer(*this);
 		      arc_notifier.setContainer(*this);
+		    }
 		    ~DigraphExtender() {
 		      arc_notifier.clear();
 		      node_notifier.clear();
+		    }
 		  };
 		  // \ingroup _graphbits
 		  //
 		  // \brief Extender for the Graphs
 		  template <typename Base>
 		  class GraphExtender : public Base {
 		    typedef Base Parent;
 		  public:
 		    typedef GraphExtender Graph;
 		    typedef True UndirectedTag;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    // Graph extension
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    int maxId(Edge) const {
 		      return Parent::maxEdgeId();
+		    }
-		    Node fromId(int id, Node) const {
+		    static Node fromId(int id, Node) {
 		      return Parent::nodeFromId(id);
+		    }
-		    Arc fromId(int id, Arc) const {
+		    static Arc fromId(int id, Arc) {
 		      return Parent::arcFromId(id);
+		    }
-		    Edge fromId(int id, Edge) const {
+		    static Edge fromId(int id, Edge) {
 		      return Parent::edgeFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Edge &e) const {
 		      if( n == Parent::u(e))
 		        return Parent::v(e);
 		      else if( n == Parent::v(e))
 		        return Parent::u(e);
 		      else
 		        return INVALID;
+		    }
 		    Arc oppositeArc(const Arc &arc) const {
 		      return Parent::direct(arc, !Parent::direction(arc));
+		    }
 		    using Parent::direct;
 		    Arc direct(const Edge &edge, const Node &node) const {
 		      return Parent::direct(edge, Parent::u(edge) == node);
+		    }
 		    // Alterable extension
 		    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
 		    typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
 		    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
 		  protected:
 		    mutable NodeNotifier node_notifier;
 		    mutable ArcNotifier arc_notifier;
 		    mutable EdgeNotifier edge_notifier;
 		  public:
 		    NodeNotifier& notifier(Node) const {
 		      return node_notifier;
+		    }
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    EdgeNotifier& notifier(Edge) const {
 		      return edge_notifier;
+		    }

lemon/bits/map_extender.h

Show inline comments

@@ -4,96 +4,98 @@
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_BITS_MAP_EXTENDER_H
 		#define LEMON_BITS_MAP_EXTENDER_H
 		#include <iterator>
 		#include <lemon/bits/traits.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		//\file
 		//\brief Extenders for iterable maps.
 		namespace lemon {
 		  // \ingroup graphbits
 		  //
 		  // \brief Extender for maps
 		  template <typename _Map>
 		  class MapExtender : public _Map {
 		    typedef _Map Parent;
 		    typedef typename Parent::GraphType GraphType;
 		  public:
 		    typedef MapExtender Map;
 		    typedef typename Parent::Key Item;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    typedef typename Parent::Reference Reference;
 		    typedef typename Parent::ConstReference ConstReference;
 		    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
 		    class MapIt;
 		    class ConstMapIt;
 		    friend class MapIt;
 		    friend class ConstMapIt;
 		  public:
 		    MapExtender(const GraphType& graph)
 		      : Parent(graph) {}
 		    MapExtender(const GraphType& graph, const Value& value)
 		      : Parent(graph, value) {}
 		  private:
 		    MapExtender& operator=(const MapExtender& cmap) {
 		      return operator=<MapExtender>(cmap);
+		    }
 		    template <typename CMap>
 		    MapExtender& operator=(const CMap& cmap) {
 		      Parent::operator=(cmap);
 		      return *this;
+		    }
 		  public:
 		    class MapIt : public Item {
 		      typedef Item Parent;
 		    public:
 		      typedef typename Map::Value Value;
 		      MapIt() {}
 		      MapIt(Invalid i) : Parent(i) { }
 		      explicit MapIt(Map& _map) : map(_map) {
 		        map.notifier()->first(*this);
+		      }
 		      MapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      MapIt& operator++() {
 		        map.notifier()->next(*this);
 		        return *this;
+		      }
@@ -146,96 +148,98 @@
 		      const Map& map;
 		    };
 		    class ItemIt : public Item {
 		      typedef Item Parent;
 		    public:
 		      ItemIt() {}
 		      ItemIt(Invalid i) : Parent(i) { }
 		      explicit ItemIt(Map& _map) : map(_map) {
 		        map.notifier()->first(*this);
+		      }
 		      ItemIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ItemIt& operator++() {
 		        map.notifier()->next(*this);
 		        return *this;
+		      }
 		    protected:
 		      const Map& map;
 		    };
 		  };
 		  // \ingroup graphbits
 		  //
 		  // \brief Extender for maps which use a subset of the items.
 		  template <typename _Graph, typename _Map>
 		  class SubMapExtender : public _Map {
 		    typedef _Map Parent;
 		    typedef _Graph GraphType;
 		  public:
 		    typedef SubMapExtender Map;
 		    typedef typename Parent::Key Item;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    typedef typename Parent::Reference Reference;
 		    typedef typename Parent::ConstReference ConstReference;
 		    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
 		    class MapIt;
 		    class ConstMapIt;
 		    friend class MapIt;
 		    friend class ConstMapIt;
 		  public:
 		    SubMapExtender(const GraphType& _graph)
 		      : Parent(_graph), graph(_graph) {}
 		    SubMapExtender(const GraphType& _graph, const Value& _value)
 		      : Parent(_graph, _value), graph(_graph) {}
 		  private:
 		    SubMapExtender& operator=(const SubMapExtender& cmap) {
 		      return operator=<MapExtender>(cmap);
+		    }
 		    template <typename CMap>
 		    SubMapExtender& operator=(const CMap& cmap) {
 		      checkConcept<concepts::ReadMap<Key, Value>, CMap>();
 		      Item it;
 		      for (graph.first(it); it != INVALID; graph.next(it)) {
 		        Parent::set(it, cmap[it]);
+		      }
 		      return *this;
+		    }
 		  public:
 		    class MapIt : public Item {
 		      typedef Item Parent;
 		    public:
 		      typedef typename Map::Value Value;
 		      MapIt() {}
 		      MapIt(Invalid i) : Parent(i) { }
 		      explicit MapIt(Map& _map) : map(_map) {
 		        map.graph.first(*this);
+		      }
 		      MapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      MapIt& operator++() {

lemon/cbc.cc

Show inline comments

@@ -49,96 +49,108 @@
#include "coin/CbcHeuristic.hpp"

namespace lemon {

  CbcMip::CbcMip() {
    _prob = new CoinModel();
    _prob->setProblemName("LEMON");
    _osi_solver = 0;
    _cbc_model = 0;
    messageLevel(MESSAGE_NOTHING);
  }

  CbcMip::CbcMip(const CbcMip& other) {
    _prob = new CoinModel(*other._prob);
    _prob->setProblemName("LEMON");
    _osi_solver = 0;
    _cbc_model = 0;
    messageLevel(MESSAGE_NOTHING);
  }

  CbcMip::~CbcMip() {
    delete _prob;
    if (_osi_solver) delete _osi_solver;
    if (_cbc_model) delete _cbc_model;
  }

  const char* CbcMip::_solverName() const { return "CbcMip"; }

  int CbcMip::_addCol() {
    _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0, 0, false);
    return _prob->numberColumns() - 1;
  }

  CbcMip* CbcMip::newSolver() const {
    CbcMip* newlp = new CbcMip;
    return newlp;
  }

  CbcMip* CbcMip::cloneSolver() const {
    CbcMip* copylp = new CbcMip(*this);
    return copylp;
  }

  int CbcMip::_addRow() {
    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
    return _prob->numberRows() - 1;
  }

  int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
    std::vector<int> indexes;
    std::vector<Value> values;

    for(ExprIterator it = b; it != e; ++it) {
      indexes.push_back(it->first);
      values.push_back(it->second);
    }

    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    return _prob->numberRows() - 1;
  }

  void CbcMip::_eraseCol(int i) {
    _prob->deleteColumn(i);
  }

  void CbcMip::_eraseRow(int i) {
    _prob->deleteRow(i);
  }

  void CbcMip::_eraseColId(int i) {
    cols.eraseIndex(i);
  }

  void CbcMip::_eraseRowId(int i) {
    rows.eraseIndex(i);
  }

  void CbcMip::_getColName(int c, std::string& name) const {
    name = _prob->getColumnName(c);
  }

  void CbcMip::_setColName(int c, const std::string& name) {
    _prob->setColumnName(c, name.c_str());
  }

  int CbcMip::_colByName(const std::string& name) const {
    return _prob->column(name.c_str());
  }

  void CbcMip::_getRowName(int r, std::string& name) const {
    name = _prob->getRowName(r);
  }

  void CbcMip::_setRowName(int r, const std::string& name) {
    _prob->setRowName(r, name.c_str());
  }

  int CbcMip::_rowByName(const std::string& name) const {
    return _prob->row(name.c_str());
  }

  void CbcMip::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
    for (ExprIterator it = b; it != e; ++it) {
      _prob->setElement(i, it->first, it->second);
    }
  }

  void CbcMip::_getRowCoeffs(int ix, InsertIterator b) const {

lemon/cbc.h

Show inline comments

@@ -17,96 +17,97 @@
 		 */
 		// -*- C++ -*-
 		#ifndef LEMON_CBC_H
 		#define LEMON_CBC_H
 		///\file
 		///\brief Header of the LEMON-CBC mip solver interface.
 		///\ingroup lp_group
 		#include <lemon/lp_base.h>
 		class CoinModel;
 		class OsiSolverInterface;
 		class CbcModel;
 		namespace lemon {
 		  /// \brief Interface for the CBC MIP solver
 		  ///
 		  /// This class implements an interface for the CBC MIP solver.
 		  ///\ingroup lp_group
 		  class CbcMip : public MipSolver {
 		  protected:
 		    CoinModel *_prob;
 		    OsiSolverInterface *_osi_solver;
 		    CbcModel *_cbc_model;
 		  public:
 		    /// \e
 		    CbcMip();
 		    /// \e
 		    CbcMip(const CbcMip&);
 		    /// \e
 		    ~CbcMip();
 		    /// \e
 		    virtual CbcMip* newSolver() const;
 		    /// \e
 		    virtual CbcMip* cloneSolver() const;
 		  protected:
 		    virtual const char* _solverName() const;
 		    virtual int _addCol();
 		    virtual int _addRow();
 		    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 		    virtual void _eraseCol(int i);
 		    virtual void _eraseRow(int i);
 		    virtual void _eraseColId(int i);
 		    virtual void _eraseRowId(int i);
 		    virtual void _getColName(int col, std::string& name) const;
 		    virtual void _setColName(int col, const std::string& name);
 		    virtual int _colByName(const std::string& name) const;
 		    virtual void _getRowName(int row, std::string& name) const;
 		    virtual void _setRowName(int row, const std::string& name);
 		    virtual int _rowByName(const std::string& name) const;
 		    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getRowCoeffs(int i, InsertIterator b) const;
 		    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getColCoeffs(int i, InsertIterator b) const;
 		    virtual void _setCoeff(int row, int col, Value value);
 		    virtual Value _getCoeff(int row, int col) const;
 		    virtual void _setColLowerBound(int i, Value value);
 		    virtual Value _getColLowerBound(int i) const;
 		    virtual void _setColUpperBound(int i, Value value);
 		    virtual Value _getColUpperBound(int i) const;
 		    virtual void _setRowLowerBound(int i, Value value);
 		    virtual Value _getRowLowerBound(int i) const;
 		    virtual void _setRowUpperBound(int i, Value value);
 		    virtual Value _getRowUpperBound(int i) const;
 		    virtual void _setObjCoeffs(ExprIterator b, ExprIterator e);
 		    virtual void _getObjCoeffs(InsertIterator b) const;
 		    virtual void _setObjCoeff(int i, Value obj_coef);
 		    virtual Value _getObjCoeff(int i) const;
 		    virtual void _setSense(Sense sense);
 		    virtual Sense _getSense() const;
 		    virtual ColTypes _getColType(int col) const;
 		    virtual void _setColType(int col, ColTypes col_type);
 		    virtual SolveExitStatus _solve();
 		    virtual ProblemType _getType() const;

lemon/circulation.h

Show inline comments

@@ -27,114 +27,121 @@
 		///\file
 		///\brief Push-relabel algorithm for finding a feasible circulation.
 		///
 		namespace lemon {
 		  /// \brief Default traits class of Circulation class.
 		  ///
 		  /// Default traits class of Circulation class.
 		  ///
 		  /// \tparam GR Type of the digraph the algorithm runs on.
 		  /// \tparam LM The type of the lower bound map.
 		  /// \tparam UM The type of the upper bound (capacity) map.
 		  /// \tparam SM The type of the supply map.
 		  template <typename GR, typename LM,
 		            typename UM, typename SM>
 		  struct CirculationDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the lower bound map.
 		    ///
 		    /// The type of the map that stores the lower bounds on the arcs.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LM LowerMap;
 		    /// \brief The type of the upper bound (capacity) map.
 		    ///
 		    /// The type of the map that stores the upper bounds (capacities)
 		    /// on the arcs.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef UM UpperMap;
 		    /// \brief The type of supply map.
 		    ///
 		    /// The type of the map that stores the signed supply values of the
 		    /// nodes.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef SM SupplyMap;
 		    /// \brief The type of the flow and supply values.
 		    typedef typename SupplyMap::Value Value;
 		    /// \brief The type of the map that stores the flow values.
 		    ///
 		    /// The type of the map that stores the flow values.
 		    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
 		    /// concept.
 		#ifdef DOXYGEN
 		    typedef GR::ArcMap<Value> FlowMap;
 		#else
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		#endif
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the flow map.
 		    static FlowMap* createFlowMap(const Digraph& digraph) {
 		      return new FlowMap(digraph);
+		    }
 		    /// \brief The elevator type used by the algorithm.
 		    ///
 		    /// The elevator type used by the algorithm.
 		    ///
 		    /// \sa Elevator
 		    /// \sa LinkedElevator
 		    /// \sa Elevator, LinkedElevator
 		#ifdef DOXYGEN
 		    typedef lemon::Elevator<GR, GR::Node> Elevator;
 		#else
 		    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
 		#endif
 		    /// \brief Instantiates an Elevator.
 		    ///
 		    /// This function instantiates an \ref Elevator.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
 		    ///
 		    /// The tolerance used by the algorithm to handle inexact computation.
 		    typedef lemon::Tolerance<Value> Tolerance;
 		  };
 		  /**
 		     \brief Push-relabel algorithm for the network circulation problem.
 		     \ingroup max_flow
 		     This class implements a push-relabel algorithm for the \e network
 		     \e circulation problem.
 		     It is to find a feasible circulation when lower and upper bounds
 		     are given for the flow values on the arcs and lower bounds are
 		     given for the difference between the outgoing and incoming flow
 		     at the nodes.
 		     The exact formulation of this problem is the following.
 		     Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$
 		     \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and
 		     upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$
 		     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
 		     denotes the signed supply values of the nodes.
 		     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		     \f$-sup(u)\f$ demand.
 		     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
 		     solution of the following problem.
 		     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
 		     \geq sup(u) \quad \forall u\in V, \f]
 		     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
 		     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		     zero or negative in order to have a feasible solution (since the sum
 		     of the expressions on the left-hand side of the inequalities is zero).
@@ -254,97 +261,97 @@
 		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                           SetFlowMapTraits<T> > {
 		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                          SetFlowMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph&, int) {
 		        LEMON_ASSERT(false, "Elevator is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type. If this named parameter is used, then an external
 		    /// elevator object must be passed to the algorithm using the
 		    /// \ref elevator(Elevator&) "elevator()" function before calling
 		    /// \ref run() or \ref init().
 		    /// \sa SetStandardElevator
 		    template <typename T>
 		    struct SetElevator
 		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                           SetElevatorTraits<T> > {
 		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                          SetElevatorTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetStandardElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph& digraph, int max_level) {
 		        return new Elevator(digraph, max_level);
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type with automatic allocation
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type with automatic allocation.
 		    /// The Elevator should have standard constructor interface to be
 		    /// able to automatically created by the algorithm (i.e. the
 		    /// digraph and the maximum level should be passed to it).
 		    /// However an external elevator object could also be passed to the
+		    /// However, an external elevator object could also be passed to the
 		    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
 		    /// before calling \ref run() or \ref init().
 		    /// \sa SetElevator
 		    template <typename T>
 		    struct SetStandardElevator
 		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                       SetStandardElevatorTraits<T> > {
 		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                      SetStandardElevatorTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Circulation() {}
 		  public:
 		    /// Constructor.
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    /// \param lower The lower bounds for the flow values on the arcs.
 		    /// \param upper The upper bounds (capacities) for the flow values
 		    /// on the arcs.
 		    /// \param supply The signed supply values of the nodes.
 		    Circulation(const Digraph &graph, const LowerMap &lower,
 		                const UpperMap &upper, const SupplyMap &supply)
 		      : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
 		        _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
 		        _excess(NULL) {}
 		    /// Destructor.
 		    ~Circulation() {
 		      destroyStructures();
+		    }
 		  private:
 		    bool checkBoundMaps() {
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        if (_tol.less((*_up)[e], (*_lo)[e])) return false;
+		      }
 		      return true;
+		    }
@@ -424,98 +431,98 @@
+		    }
 		    /// \brief Sets the elevator used by algorithm.
 		    ///
 		    /// Sets the elevator used by algorithm.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated elevator,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& elevator(Elevator& elevator) {
 		      if (_local_level) {
 		        delete _level;
 		        _local_level = false;
+		      }
 		      _level = &elevator;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the elevator.
 		    ///
 		    /// Returns a const reference to the elevator.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const Elevator& elevator() const {
 		      return *_level;
+		    }
 		    /// \brief Sets the tolerance used by the algorithm.
 		    ///
 		    /// Sets the tolerance object used by the algorithm.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& tolerance(const Tolerance& tolerance) {
 		      _tol = tolerance;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the tolerance.
 		    ///
 		    /// Returns a const reference to the tolerance object used by
 		    /// the algorithm.
 		    const Tolerance& tolerance() const {
 		      return _tol;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to call \ref run().\n
 		    /// If you need more control on the initial solution or the execution,
 		    /// first you have to call one of the \ref init() functions, then
 		    /// If you need better control on the initial solution or the execution,
 		    /// you have to call one of the \ref init() functions first, then
 		    /// the \ref start() function.
 		    ///@{
 		    /// Initializes the internal data structures.
 		    /// Initializes the internal data structures and sets all flow values
 		    /// to the lower bound.
 		    void init()
+		    {
 		      LEMON_DEBUG(checkBoundMaps(),
 		        "Upper bounds must be greater or equal to the lower bounds");
 		      createStructures();
 		      for(NodeIt n(_g);n!=INVALID;++n) {
 		        (*_excess)[n] = (*_supply)[n];
+		      }
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        _flow->set(e, (*_lo)[e]);
 		        (*_excess)[_g.target(e)] += (*_flow)[e];
 		        (*_excess)[_g.source(e)] -= (*_flow)[e];
+		      }
 		      // global relabeling tested, but in general case it provides
 		      // worse performance for random digraphs
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    /// Initializes the internal data structures using a greedy approach.
 		    /// Initializes the internal data structures using a greedy approach
 		    /// to construct the initial solution.
 		    void greedyInit()
+		    {
 		      LEMON_DEBUG(checkBoundMaps(),
 		        "Upper bounds must be greater or equal to the lower bounds");
 		      createStructures();
 		      for(NodeIt n(_g);n!=INVALID;++n) {

lemon/clp.cc

Show inline comments

@@ -33,96 +33,109 @@
    cols = other.cols;
    _init_temporals();
    messageLevel(MESSAGE_NOTHING);
  }

  ClpLp::~ClpLp() {
    delete _prob;
    _clear_temporals();
  }

  void ClpLp::_init_temporals() {
    _primal_ray = 0;
    _dual_ray = 0;
  }

  void ClpLp::_clear_temporals() {
    if (_primal_ray) {
      delete[] _primal_ray;
      _primal_ray = 0;
    }
    if (_dual_ray) {
      delete[] _dual_ray;
      _dual_ray = 0;
    }
  }

  ClpLp* ClpLp::newSolver() const {
    ClpLp* newlp = new ClpLp;
    return newlp;
  }

  ClpLp* ClpLp::cloneSolver() const {
    ClpLp* copylp = new ClpLp(*this);
    return copylp;
  }

  const char* ClpLp::_solverName() const { return "ClpLp"; }

  int ClpLp::_addCol() {
    _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0);
    return _prob->numberColumns() - 1;
  }

  int ClpLp::_addRow() {
    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
    return _prob->numberRows() - 1;
  }

  int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
    std::vector<int> indexes;
    std::vector<Value> values;

    for(ExprIterator it = b; it != e; ++it) {
      indexes.push_back(it->first);
      values.push_back(it->second);
    }

    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    return _prob->numberRows() - 1;
  }


  void ClpLp::_eraseCol(int c) {
    _col_names_ref.erase(_prob->getColumnName(c));
    _prob->deleteColumns(1, &c);
  }

  void ClpLp::_eraseRow(int r) {
    _row_names_ref.erase(_prob->getRowName(r));
    _prob->deleteRows(1, &r);
  }

  void ClpLp::_eraseColId(int i) {
    cols.eraseIndex(i);
    cols.shiftIndices(i);
  }

  void ClpLp::_eraseRowId(int i) {
    rows.eraseIndex(i);
    rows.shiftIndices(i);
  }

  void ClpLp::_getColName(int c, std::string& name) const {
    name = _prob->getColumnName(c);
  }

  void ClpLp::_setColName(int c, const std::string& name) {
    _prob->setColumnName(c, const_cast<std::string&>(name));
    _col_names_ref[name] = c;
  }

  int ClpLp::_colByName(const std::string& name) const {
    std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
    return it != _col_names_ref.end() ? it->second : -1;
  }

  void ClpLp::_getRowName(int r, std::string& name) const {
    name = _prob->getRowName(r);
  }

  void ClpLp::_setRowName(int r, const std::string& name) {
    _prob->setRowName(r, const_cast<std::string&>(name));
    _row_names_ref[name] = r;
  }

  int ClpLp::_rowByName(const std::string& name) const {
    std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
    return it != _row_names_ref.end() ? it->second : -1;
  }

lemon/clp.h

Show inline comments

@@ -30,96 +30,97 @@
 		class ClpSimplex;
 		namespace lemon {
 		  /// \ingroup lp_group
 		  ///
 		  /// \brief Interface for the CLP solver
 		  ///
 		  /// This class implements an interface for the Clp LP solver.  The
 		  /// Clp library is an object oriented lp solver library developed at
 		  /// the IBM. The CLP is part of the COIN-OR package and it can be
 		  /// used with Common Public License.
 		  class ClpLp : public LpSolver {
 		  protected:
 		    ClpSimplex* _prob;
 		    std::map<std::string, int> _col_names_ref;
 		    std::map<std::string, int> _row_names_ref;
 		  public:
 		    /// \e
 		    ClpLp();
 		    /// \e
 		    ClpLp(const ClpLp&);
 		    /// \e
 		    ~ClpLp();
 		    /// \e
 		    virtual ClpLp* newSolver() const;
 		    /// \e
 		    virtual ClpLp* cloneSolver() const;
 		  protected:
 		    mutable double* _primal_ray;
 		    mutable double* _dual_ray;
 		    void _init_temporals();
 		    void _clear_temporals();
 		  protected:
 		    virtual const char* _solverName() const;
 		    virtual int _addCol();
 		    virtual int _addRow();
 		    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 		    virtual void _eraseCol(int i);
 		    virtual void _eraseRow(int i);
 		    virtual void _eraseColId(int i);
 		    virtual void _eraseRowId(int i);
 		    virtual void _getColName(int col, std::string& name) const;
 		    virtual void _setColName(int col, const std::string& name);
 		    virtual int _colByName(const std::string& name) const;
 		    virtual void _getRowName(int row, std::string& name) const;
 		    virtual void _setRowName(int row, const std::string& name);
 		    virtual int _rowByName(const std::string& name) const;
 		    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getRowCoeffs(int i, InsertIterator b) const;
 		    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getColCoeffs(int i, InsertIterator b) const;
 		    virtual void _setCoeff(int row, int col, Value value);
 		    virtual Value _getCoeff(int row, int col) const;
 		    virtual void _setColLowerBound(int i, Value value);
 		    virtual Value _getColLowerBound(int i) const;
 		    virtual void _setColUpperBound(int i, Value value);
 		    virtual Value _getColUpperBound(int i) const;
 		    virtual void _setRowLowerBound(int i, Value value);
 		    virtual Value _getRowLowerBound(int i) const;
 		    virtual void _setRowUpperBound(int i, Value value);
 		    virtual Value _getRowUpperBound(int i) const;
 		    virtual void _setObjCoeffs(ExprIterator, ExprIterator);
 		    virtual void _getObjCoeffs(InsertIterator) const;
 		    virtual void _setObjCoeff(int i, Value obj_coef);
 		    virtual Value _getObjCoeff(int i) const;
 		    virtual void _setSense(Sense sense);
 		    virtual Sense _getSense() const;
 		    virtual SolveExitStatus _solve();
 		    virtual Value _getPrimal(int i) const;
 		    virtual Value _getDual(int i) const;

lemon/concepts/digraph.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_CONCEPTS_DIGRAPH_H
 		#define LEMON_CONCEPTS_DIGRAPH_H
 		///\ingroup graph_concepts
 		///\file
 		///\brief The concept of directed graphs.
 		#include <lemon/core.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/graph_components.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \ingroup graph_concepts
 		    ///
 		    /// \brief Class describing the concept of directed graphs.
 		    ///
 		    /// This class describes the \ref concept "concept" of the
 		    /// immutable directed digraphs.
 		    /// This class describes the common interface of all directed
 		    /// graphs (digraphs).
 		    ///
 		    /// Note that actual digraph implementation like @ref ListDigraph or
 		    /// @ref SmartDigraph may have several additional functionality.
 		    /// Like all concept classes, it only provides an interface
 		    /// without any sensible implementation. So any general algorithm for
 		    /// directed graphs should compile with this class, but it will not
 		    /// run properly, of course.
 		    /// An actual digraph implementation like \ref ListDigraph or
 		    /// \ref SmartDigraph may have additional functionality.
 		    ///
-		    /// \sa concept
+		    /// \sa Graph
 		    class Digraph {
 		    private:
-		      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
+		      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
 		      Digraph(const Digraph &) {}
 		      /// \brief Assignment of a digraph to another one is \e not allowed.
 		      /// Use DigraphCopy instead.
 		      void operator=(const Digraph &) {}
 		      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
 		      ///
 		      Digraph(const Digraph &) {};
 		      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
-		      ///\e not allowed. Use DigraphCopy() instead.
+		    public:
 		      /// Default constructor.
 		      Digraph() { }
 		      ///Assignment of \ref Digraph "Digraph"s to another ones are
 		      ///\e not allowed.  Use DigraphCopy() instead.
 		      void operator=(const Digraph &) {}
 		    public:
 		      ///\e
 		      /// Defalult constructor.
 		      /// Defalult constructor.
 		      ///
 		      Digraph() { }
-		      /// Class for identifying a node of the digraph
+		      /// The node type of the digraph
 		      /// This class identifies a node of the digraph. It also serves
 		      /// as a base class of the node iterators,
-		      /// thus they will convert to this type.
 		      /// thus they convert to this type.
 		      class Node {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the object to an undefined value.
 		        Node() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Node(const Node&) { }
 		        /// Invalid constructor \& conversion.
+		        /// %Invalid constructor \& conversion.
-		        /// This constructor initializes the iterator to be invalid.
+		        /// Initializes the object to be invalid.
 		        /// \sa Invalid for more details.
 		        Node(Invalid) { }
 		        /// Equality operator
 		        /// Equality operator.
 		        ///
 		        /// Two iterators are equal if and only if they point to the
-		        /// same object or both are invalid.
+		        /// same object or both are \c INVALID.
 		        bool operator==(Node) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Node n)
 		        ///
 		        /// Inequality operator.
 		        bool operator!=(Node) const { return true; }
 		        /// Artificial ordering operator.
 		        /// To allow the use of digraph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        /// Artificial ordering operator.
 		        ///
 		        /// \note This operator only have to define some strict ordering of
 		        /// the items; this order has nothing to do with the iteration
-		        /// ordering of the items.
+		        /// \note This operator only has to define some strict ordering of
 		        /// the nodes; this order has nothing to do with the iteration
 		        /// ordering of the nodes.
 		        bool operator<(Node) const { return false; }
 		      };
-		      /// This iterator goes through each node.
+		      /// Iterator class for the nodes.
 		      /// This iterator goes through each node.
 		      /// Its usage is quite simple, for example you can count the number
-		      /// of nodes in digraph \c g of type \c Digraph like this:
+		      /// This iterator goes through each node of the digraph.
 		      /// Its usage is quite simple, for example, you can count the number
 		      /// of nodes in a digraph \c g of type \c %Digraph like this:
 		      ///\code
 		      /// int count=0;
 		      /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
 		      ///\endcode
 		      class NodeIt : public Node {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        NodeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        NodeIt(const NodeIt& n) : Node(n) { }
 		        /// Invalid constructor \& conversion.
+		        /// %Invalid constructor \& conversion.
-		        /// Initialize the iterator to be invalid.
+		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        NodeIt(Invalid) { }
 		        /// Sets the iterator to the first node.
-		        /// Sets the iterator to the first node of \c g.
+		        /// Sets the iterator to the first node of the given digraph.
 		        ///
 		        NodeIt(const Digraph&) { }
 		        /// Node -> NodeIt conversion.
 		        explicit NodeIt(const Digraph&) { }
 		        /// Sets the iterator to the given node.
 		        /// Sets the iterator to the node of \c the digraph pointed by
 		        /// the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        /// Sets the iterator to the given node of the given digraph.
 		        ///
 		        NodeIt(const Digraph&, const Node&) { }
 		        /// Next node.
 		        /// Assign the iterator to the next node.
 		        ///
 		        NodeIt& operator++() { return *this; }
 		      };
-		      /// Class for identifying an arc of the digraph
+		      /// The arc type of the digraph
 		      /// This class identifies an arc of the digraph. It also serves
 		      /// as a base class of the arc iterators,
 		      /// thus they will convert to this type.
 		      class Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the object to an undefined value.
 		        Arc() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Arc(const Arc&) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        /// Initializes the object to be invalid.
 		        /// \sa Invalid for more details.
 		        Arc(Invalid) { }
 		        /// Equality operator
 		        /// Equality operator.
 		        ///
 		        /// Two iterators are equal if and only if they point to the
-		        /// same object or both are invalid.
+		        /// same object or both are \c INVALID.
 		        bool operator==(Arc) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Arc n)
 		        ///
 		        /// Inequality operator.
 		        bool operator!=(Arc) const { return true; }
 		        /// Artificial ordering operator.
 		        /// To allow the use of digraph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        /// Artificial ordering operator.
 		        ///
 		        /// \note This operator only have to define some strict ordering of
 		        /// the items; this order has nothing to do with the iteration
-		        /// ordering of the items.
+		        /// \note This operator only has to define some strict ordering of
 		        /// the arcs; this order has nothing to do with the iteration
 		        /// ordering of the arcs.
 		        bool operator<(Arc) const { return false; }
 		      };
-		      /// This iterator goes trough the outgoing arcs of a node.
+		      /// Iterator class for the outgoing arcs of a node.
 		      /// This iterator goes trough the \e outgoing arcs of a certain node
 		      /// of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in digraph \c g of type \c Digraph as follows.
+		      /// in a digraph \c g of type \c %Digraph as follows.
 		      ///\code
 		      /// int count=0;
-		      /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
+		      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class OutArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        OutArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        OutArcIt(const OutArcIt& e) : Arc(e) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
-		        /// Initialize the iterator to be invalid.
+		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        OutArcIt(Invalid) { }
 		        /// Sets the iterator to the first outgoing arc.
 		        /// Sets the iterator to the first outgoing arc of the given node.
 		        ///
 		        OutArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first outgoing arc.
 		        OutArcIt(const Digraph&, const Node&) { }
 		        /// Sets the iterator to the given arc.
 		        /// This constructor sets the iterator to the first outgoing arc of
 		        /// the node.
 		        OutArcIt(const Digraph&, const Node&) { }
 		        /// Arc -> OutArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        /// Sets the iterator to the given arc of the given digraph.
 		        ///
 		        OutArcIt(const Digraph&, const Arc&) { }
 		        ///Next outgoing arc
+		        /// Next outgoing arc
 		        /// Assign the iterator to the next
 		        /// outgoing arc of the corresponding node.
 		        OutArcIt& operator++() { return *this; }
 		      };
-		      /// This iterator goes trough the incoming arcs of a node.
+		      /// Iterator class for the incoming arcs of a node.
 		      /// This iterator goes trough the \e incoming arcs of a certain node
 		      /// of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of outgoing arcs of a node \c n
-		      /// in digraph \c g of type \c Digraph as follows.
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of incoming arcs of a node \c n
 		      /// in a digraph \c g of type \c %Digraph as follows.
 		      ///\code
 		      /// int count=0;
-		      /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
+		      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class InArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        InArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        InArcIt(const InArcIt& e) : Arc(e) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
-		        /// Initialize the iterator to be invalid.
+		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        InArcIt(Invalid) { }
 		        /// Sets the iterator to the first incoming arc.
 		        /// Sets the iterator to the first incoming arc of the given node.
 		        ///
 		        InArcIt(Invalid) { }
 		        /// This constructor sets the iterator to first incoming arc.
 		        InArcIt(const Digraph&, const Node&) { }
 		        /// Sets the iterator to the given arc.
 		        /// This constructor set the iterator to the first incoming arc of
 		        /// the node.
 		        InArcIt(const Digraph&, const Node&) { }
 		        /// Arc -> InArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        /// Sets the iterator to the given arc of the given digraph.
 		        ///
 		        InArcIt(const Digraph&, const Arc&) { }
 		        /// Next incoming arc
 		        /// Assign the iterator to the next inarc of the corresponding node.
 		        ///
 		        /// Assign the iterator to the next
 		        /// incoming arc of the corresponding node.
 		        InArcIt& operator++() { return *this; }
 		      };
 		      /// This iterator goes through each arc.
 		      /// This iterator goes through each arc of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
-		      /// of arcs in a digraph \c g of type \c Digraph as follows:
+		      /// Iterator class for the arcs.
 		      /// This iterator goes through each arc of the digraph.
 		      /// Its usage is quite simple, for example, you can count the number
 		      /// of arcs in a digraph \c g of type \c %Digraph as follows:
 		      ///\code
 		      /// int count=0;
-		      /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
+		      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class ArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        ArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        ArcIt(const ArcIt& e) : Arc(e) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
-		        /// Initialize the iterator to be invalid.
+		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        ArcIt(Invalid) { }
 		        /// Sets the iterator to the first arc.
 		        /// Sets the iterator to the first arc of the given digraph.
 		        ///
 		        ArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first arc.
 		        explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
 		        /// Sets the iterator to the given arc.
 		        /// This constructor sets the iterator to the first arc of \c g.
 		        ///@param g the digraph
 		        ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
 		        /// Arc -> ArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        /// Sets the iterator to the given arc of the given digraph.
 		        ///
 		        ArcIt(const Digraph&, const Arc&) { }
 		        ///Next arc
+		        /// Next arc
 		        /// Assign the iterator to the next arc.
 		        ///
 		        ArcIt& operator++() { return *this; }
 		      };
 		      ///Gives back the target node of an arc.
-		      ///Gives back the target node of an arc.
+		      /// \brief The source node of the arc.
 		      ///
 		      Node target(Arc) const { return INVALID; }
 		      ///Gives back the source node of an arc.
 		      ///Gives back the source node of an arc.
 		      ///
+		      /// Returns the source node of the given arc.
 		      Node source(Arc) const { return INVALID; }
-		      /// \brief Returns the ID of the node.
+		      /// \brief The target node of the arc.
 		      ///
 		      /// Returns the target node of the given arc.
 		      Node target(Arc) const { return INVALID; }
 		      /// \brief The ID of the node.
 		      ///
 		      /// Returns the ID of the given node.
 		      int id(Node) const { return -1; }
-		      /// \brief Returns the ID of the arc.
+		      /// \brief The ID of the arc.
 		      ///
 		      /// Returns the ID of the given arc.
 		      int id(Arc) const { return -1; }
-		      /// \brief Returns the node with the given ID.
+		      /// \brief The node with the given ID.
 		      ///
-		      /// \pre The argument should be a valid node ID in the graph.
+		      /// Returns the node with the given ID.
 		      /// \pre The argument should be a valid node ID in the digraph.
 		      Node nodeFromId(int) const { return INVALID; }
-		      /// \brief Returns the arc with the given ID.
+		      /// \brief The arc with the given ID.
 		      ///
-		      /// \pre The argument should be a valid arc ID in the graph.
+		      /// Returns the arc with the given ID.
 		      /// \pre The argument should be a valid arc ID in the digraph.
 		      Arc arcFromId(int) const { return INVALID; }
-		      /// \brief Returns an upper bound on the node IDs.
+		      /// \brief An upper bound on the node IDs.
 		      ///
 		      /// Returns an upper bound on the node IDs.
 		      int maxNodeId() const { return -1; }
-		      /// \brief Returns an upper bound on the arc IDs.
+		      /// \brief An upper bound on the arc IDs.
 		      ///
 		      /// Returns an upper bound on the arc IDs.
 		      int maxArcId() const { return -1; }
 		      void first(Node&) const {}
 		      void next(Node&) const {}
 		      void first(Arc&) const {}
 		      void next(Arc&) const {}
 		      void firstIn(Arc&, const Node&) const {}
 		      void nextIn(Arc&) const {}
 		      void firstOut(Arc&, const Node&) const {}
 		      void nextOut(Arc&) const {}
 		      // The second parameter is dummy.
 		      Node fromId(int, Node) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Arc fromId(int, Arc) const { return INVALID; }
 		      // Dummy parameter.
 		      int maxId(Node) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Arc) const { return -1; }
 		      /// \brief The opposite node on the arc.
 		      ///
 		      /// Returns the opposite node on the given arc.
 		      Node oppositeNode(Node, Arc) const { return INVALID; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Gives back the base node of the iterator.
 		      /// It is always the target of the pointed arc.
-		      Node baseNode(const InArcIt&) const { return INVALID; }
+		      /// Returns the base node of the given outgoing arc iterator
 		      /// (i.e. the source node of the corresponding arc).
 		      Node baseNode(OutArcIt) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Gives back the running node of the iterator.
 		      /// It is always the source of the pointed arc.
-		      Node runningNode(const InArcIt&) const { return INVALID; }
+		      /// Returns the running node of the given outgoing arc iterator
 		      /// (i.e. the target node of the corresponding arc).
 		      Node runningNode(OutArcIt) const { return INVALID; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Gives back the base node of the iterator.
 		      /// It is always the source of the pointed arc.
-		      Node baseNode(const OutArcIt&) const { return INVALID; }
+		      /// Returns the base node of the given incomming arc iterator
 		      /// (i.e. the target node of the corresponding arc).
 		      Node baseNode(InArcIt) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Gives back the running node of the iterator.
 		      /// It is always the target of the pointed arc.
-		      Node runningNode(const OutArcIt&) const { return INVALID; }
+		      /// Returns the running node of the given incomming arc iterator
 		      /// (i.e. the source node of the corresponding arc).
 		      Node runningNode(InArcIt) const { return INVALID; }
-		      /// \brief The opposite node on the given arc.
+		      /// \brief Standard graph map type for the nodes.
 		      ///
 		      /// Gives back the opposite node on the given arc.
 		      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
 		      /// \brief Reference map of the nodes to type \c T.
 		      ///
 		      /// Reference map of the nodes to type \c T.
 		      /// Standard graph map type for the nodes.
 		      /// It conforms to the ReferenceMap concept.
 		      template<class T>
 		      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
 		      public:
 		        ///\e
 		        NodeMap(const Digraph&) { }
-		        ///\e
+		        /// Constructor
 		        explicit NodeMap(const Digraph&) { }
 		        /// Constructor with given initial value
 		        NodeMap(const Digraph&, T) { }
 		      private:
 		        ///Copy constructor
 		        NodeMap(const NodeMap& nm) :
 		          ReferenceMap<Node, T, T&, const T&>(nm) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, CMap>();
 		          return *this;
+		        }
 		      };
-		      /// \brief Reference map of the arcs to type \c T.
+		      /// \brief Standard graph map type for the arcs.
 		      ///
-		      /// Reference map of the arcs to type \c T.
+		      /// Standard graph map type for the arcs.
 		      /// It conforms to the ReferenceMap concept.
 		      template<class T>
 		      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
 		      public:
 		        ///\e
 		        ArcMap(const Digraph&) { }
-		        ///\e
+		        /// Constructor
 		        explicit ArcMap(const Digraph&) { }
 		        /// Constructor with given initial value
 		        ArcMap(const Digraph&, T) { }
 		      private:
 		        ///Copy constructor
 		        ArcMap(const ArcMap& em) :
 		          ReferenceMap<Arc, T, T&, const T&>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<BaseDigraphComponent, _Digraph>();
 		          checkConcept<IterableDigraphComponent<>, _Digraph>();
 		          checkConcept<IDableDigraphComponent<>, _Digraph>();
 		          checkConcept<MappableDigraphComponent<>, _Digraph>();
+		        }
 		      };
 		    };
 		  } //namespace concepts
 		} //namespace lemon
 		#endif

lemon/concepts/graph.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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.
+		 *
 		 */
 		///\ingroup graph_concepts
 		///\file
-		///\brief The concept of Undirected Graphs.
+		///\brief The concept of undirected graphs.
 		#ifndef LEMON_CONCEPTS_GRAPH_H
 		#define LEMON_CONCEPTS_GRAPH_H
 		#include <lemon/concepts/graph_components.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/core.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \ingroup graph_concepts
 		    ///
-		    /// \brief Class describing the concept of Undirected Graphs.
+		    /// \brief Class describing the concept of undirected graphs.
 		    ///
 		    /// This class describes the common interface of all Undirected
 		    /// Graphs.
 		    /// This class describes the common interface of all undirected
 		    /// graphs.
 		    ///
 		    /// As all concept describing classes it provides only interface
 		    /// without any sensible implementation. So any algorithm for
-		    /// undirected graph should compile with this class, but it will not
+		    /// Like all concept classes, it only provides an interface
 		    /// without any sensible implementation. So any general algorithm for
 		    /// undirected graphs should compile with this class, but it will not
 		    /// run properly, of course.
 		    /// An actual graph implementation like \ref ListGraph or
 		    /// \ref SmartGraph may have additional functionality.
 		    ///
 		    /// The LEMON undirected graphs also fulfill the concept of
 		    /// directed graphs (\ref lemon::concepts::Digraph "Digraph
 		    /// Concept"). Each edges can be seen as two opposite
 		    /// directed arc and consequently the undirected graph can be
 		    /// seen as the direceted graph of these directed arcs. The
 		    /// Graph has the Edge inner class for the edges and
 		    /// the Arc type for the directed arcs. The Arc type is
 		    /// convertible to Edge or inherited from it so from a directed
-		    /// arc we can get the represented edge.
+		    /// The undirected graphs also fulfill the concept of \ref Digraph
 		    /// "directed graphs", since each edge can also be regarded as two
 		    /// oppositely directed arcs.
 		    /// Undirected graphs provide an Edge type for the undirected edges and
 		    /// an Arc type for the directed arcs. The Arc type is convertible to
 		    /// Edge or inherited from it, i.e. the corresponding edge can be
 		    /// obtained from an arc.
 		    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
 		    /// and ArcMap classes can be used for the arcs (just like in digraphs).
 		    /// Both InArcIt and OutArcIt iterates on the same edges but with
 		    /// opposite direction. IncEdgeIt also iterates on the same edges
 		    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
 		    /// only to Edge.
 		    ///
 		    /// In the sense of the LEMON each edge has a default
 		    /// direction (it should be in every computer implementation,
 		    /// because the order of edge's nodes defines an
 		    /// orientation). With the default orientation we can define that
 		    /// the directed arc is forward or backward directed. With the \c
 		    /// direction() and \c direct() function we can get the direction
-		    /// of the directed arc and we can direct an edge.
+		    /// In LEMON, each undirected edge has an inherent orientation.
 		    /// Thus it can defined if an arc is forward or backward oriented in
 		    /// an undirected graph with respect to this default oriantation of
 		    /// the represented edge.
 		    /// With the direction() and direct() functions the direction
 		    /// of an arc can be obtained and set, respectively.
 		    ///
 		    /// The EdgeIt is an iterator for the edges. We can use
 		    /// the EdgeMap to map values for the edges. The InArcIt and
 		    /// OutArcIt iterates on the same edges but with opposite
 		    /// direction. The IncEdgeIt iterates also on the same edges
 		    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
 		    /// to Edge.
 		    /// Only nodes and edges can be added to or removed from an undirected
 		    /// graph and the corresponding arcs are added or removed automatically.
 		    ///
 		    /// \sa Digraph
 		    class Graph {
 		    private:
 		      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
 		      Graph(const Graph&) {}
 		      /// \brief Assignment of a graph to another one is \e not allowed.
 		      /// Use DigraphCopy instead.
 		      void operator=(const Graph&) {}
 		    public:
 		      /// \brief The undirected graph should be tagged by the
 		      /// UndirectedTag.
 		      /// Default constructor.
 		      Graph() {}
 		      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
 		      ///
 		      /// The undirected graph should be tagged by the UndirectedTag. This
 		      /// tag helps the enable_if technics to make compile time
 		      /// Undirected graphs should be tagged with \c UndirectedTag.
 		      ///
 		      /// This tag helps the \c enable_if technics to make compile time
 		      /// specializations for undirected graphs.
 		      typedef True UndirectedTag;
 		      /// \brief The base type of node iterators,
 		      /// or in other words, the trivial node iterator.
 		      ///
 		      /// This is the base type of each node iterator,
 		      /// thus each kind of node iterator converts to this.
 		      /// More precisely each kind of node iterator should be inherited
-		      /// from the trivial node iterator.
+		      /// The node type of the graph
 		      /// This class identifies a node of the graph. It also serves
 		      /// as a base class of the node iterators,
 		      /// thus they convert to this type.
 		      class Node {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the object to an undefined value.
 		        Node() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Node(const Node&) { }
 		        /// Invalid constructor \& conversion.
+		        /// %Invalid constructor \& conversion.
-		        /// This constructor initializes the iterator to be invalid.
+		        /// Initializes the object to be invalid.
 		        /// \sa Invalid for more details.
 		        Node(Invalid) { }
 		        /// Equality operator
 		        /// Equality operator.
 		        ///
 		        /// Two iterators are equal if and only if they point to the
-		        /// same object or both are invalid.
+		        /// same object or both are \c INVALID.
 		        bool operator==(Node) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Node n)
 		        ///
 		        /// Inequality operator.
 		        bool operator!=(Node) const { return true; }
 		        /// Artificial ordering operator.
 		        /// To allow the use of graph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        /// Artificial ordering operator.
 		        ///
-		        /// \note This operator only have to define some strict ordering of
+		        /// \note This operator only has to define some strict ordering of
 		        /// the items; this order has nothing to do with the iteration
 		        /// ordering of the items.
 		        bool operator<(Node) const { return false; }
 		      };
-		      /// This iterator goes through each node.
+		      /// Iterator class for the nodes.
 		      /// This iterator goes through each node.
 		      /// Its usage is quite simple, for example you can count the number
-		      /// of nodes in graph \c g of type \c Graph like this:
+		      /// This iterator goes through each node of the graph.
 		      /// Its usage is quite simple, for example, you can count the number
 		      /// of nodes in a graph \c g of type \c %Graph like this:
 		      ///\code
 		      /// int count=0;
 		      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
 		      ///\endcode
 		      class NodeIt : public Node {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        NodeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        NodeIt(const NodeIt& n) : Node(n) { }
 		        /// Invalid constructor \& conversion.
+		        /// %Invalid constructor \& conversion.
-		        /// Initialize the iterator to be invalid.
+		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        NodeIt(Invalid) { }
 		        /// Sets the iterator to the first node.
-		        /// Sets the iterator to the first node of \c g.
+		        /// Sets the iterator to the first node of the given digraph.
 		        ///
 		        NodeIt(const Graph&) { }
 		        /// Node -> NodeIt conversion.
 		        explicit NodeIt(const Graph&) { }
 		        /// Sets the iterator to the given node.
 		        /// Sets the iterator to the node of \c the graph pointed by
 		        /// the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        /// Sets the iterator to the given node of the given digraph.
 		        ///
 		        NodeIt(const Graph&, const Node&) { }
 		        /// Next node.
 		        /// Assign the iterator to the next node.
 		        ///
 		        NodeIt& operator++() { return *this; }
 		      };
-		      /// The base type of the edge iterators.
+		      /// The edge type of the graph
 		      /// The base type of the edge iterators.
 		      ///
 		      /// This class identifies an edge of the graph. It also serves
 		      /// as a base class of the edge iterators,
 		      /// thus they will convert to this type.
 		      class Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the object to an undefined value.
 		        Edge() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Edge(const Edge&) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        /// Initializes the object to be invalid.
 		        /// \sa Invalid for more details.
 		        Edge(Invalid) { }
 		        /// Equality operator
 		        /// Equality operator.
 		        ///
 		        /// Two iterators are equal if and only if they point to the
-		        /// same object or both are invalid.
+		        /// same object or both are \c INVALID.
 		        bool operator==(Edge) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Edge n)
 		        ///
 		        /// Inequality operator.
 		        bool operator!=(Edge) const { return true; }
 		        /// Artificial ordering operator.
 		        /// To allow the use of graph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        /// Artificial ordering operator.
 		        ///
 		        /// \note This operator only have to define some strict ordering of
 		        /// the items; this order has nothing to do with the iteration
-		        /// ordering of the items.
+		        /// \note This operator only has to define some strict ordering of
 		        /// the edges; this order has nothing to do with the iteration
 		        /// ordering of the edges.
 		        bool operator<(Edge) const { return false; }
 		      };
-		      /// This iterator goes through each edge.
+		      /// Iterator class for the edges.
 		      /// This iterator goes through each edge of a graph.
 		      /// Its usage is quite simple, for example you can count the number
-		      /// of edges in a graph \c g of type \c Graph as follows:
+		      /// This iterator goes through each edge of the graph.
 		      /// Its usage is quite simple, for example, you can count the number
 		      /// of edges in a graph \c g of type \c %Graph as follows:
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class EdgeIt : public Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        EdgeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        EdgeIt(const EdgeIt& e) : Edge(e) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
-		        /// Initialize the iterator to be invalid.
+		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        EdgeIt(Invalid) { }
 		        /// Sets the iterator to the first edge.
 		        /// Sets the iterator to the first edge of the given graph.
 		        ///
 		        EdgeIt(Invalid) { }
 		        /// This constructor sets the iterator to the first edge.
 		        explicit EdgeIt(const Graph&) { }
 		        /// Sets the iterator to the given edge.
 		        /// This constructor sets the iterator to the first edge.
 		        EdgeIt(const Graph&) { }
 		        /// Edge -> EdgeIt conversion
 		        /// Sets the iterator to the value of the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the edge-set, the iteration order is the
 		        /// same.
 		        /// Sets the iterator to the given edge of the given graph.
 		        ///
 		        EdgeIt(const Graph&, const Edge&) { }
 		        /// Next edge
 		        /// Assign the iterator to the next edge.
 		        ///
 		        EdgeIt& operator++() { return *this; }
 		      };
 		      /// \brief This iterator goes trough the incident undirected
 		      /// arcs of a node.
 		      ///
 		      /// This iterator goes trough the incident edges
 		      /// of a certain node of a graph. You should assume that the
 		      /// loop arcs will be iterated twice.
 		      ///
 		      /// Its usage is quite simple, for example you can compute the
 		      /// degree (i.e. count the number of incident arcs of a node \c n
 		      /// in graph \c g of type \c Graph as follows.
 		      /// Iterator class for the incident edges of a node.
 		      /// This iterator goes trough the incident undirected edges
 		      /// of a certain node of a graph.
 		      /// Its usage is quite simple, for example, you can compute the
 		      /// degree (i.e. the number of incident edges) of a node \c n
 		      /// in a graph \c g of type \c %Graph as follows.
 		      ///
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      ///
 		      /// \warning Loop edges will be iterated twice.
 		      class IncEdgeIt : public Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        IncEdgeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
-		        /// Initialize the iterator to be invalid.
+		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        IncEdgeIt(Invalid) { }
 		        /// Sets the iterator to the first incident edge.
 		        /// Sets the iterator to the first incident edge of the given node.
 		        ///
 		        IncEdgeIt(Invalid) { }
 		        /// This constructor sets the iterator to first incident arc.
 		        IncEdgeIt(const Graph&, const Node&) { }
 		        /// Sets the iterator to the given edge.
 		        /// This constructor set the iterator to the first incident arc of
 		        /// the node.
 		        IncEdgeIt(const Graph&, const Node&) { }
 		        /// Edge -> IncEdgeIt conversion
 		        /// Sets the iterator to the given edge of the given graph.
 		        ///
 		        IncEdgeIt(const Graph&, const Edge&) { }
 		        /// Next incident edge
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        IncEdgeIt(const Graph&, const Edge&) { }
 		        /// Next incident arc
-		        /// Assign the iterator to the next incident arc
+		        /// Assign the iterator to the next incident edge
 		        /// of the corresponding node.
 		        IncEdgeIt& operator++() { return *this; }
 		      };
-		      /// The directed arc type.
+		      /// The arc type of the graph
 		      /// The directed arc type. It can be converted to the
 		      /// edge or it should be inherited from the undirected
-		      /// edge.
+		      /// This class identifies a directed arc of the graph. It also serves
 		      /// as a base class of the arc iterators,
 		      /// thus they will convert to this type.
 		      class Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the object to an undefined value.
 		        Arc() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Arc(const Arc&) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        /// Initializes the object to be invalid.
 		        /// \sa Invalid for more details.
 		        Arc(Invalid) { }
 		        /// Equality operator
 		        /// Equality operator.
 		        ///
 		        /// Two iterators are equal if and only if they point to the
-		        /// same object or both are invalid.
+		        /// same object or both are \c INVALID.
 		        bool operator==(Arc) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Arc n)
 		        ///
 		        /// Inequality operator.
 		        bool operator!=(Arc) const { return true; }
 		        /// Artificial ordering operator.
 		        /// To allow the use of graph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        /// Artificial ordering operator.
 		        ///
 		        /// \note This operator only have to define some strict ordering of
 		        /// the items; this order has nothing to do with the iteration
-		        /// ordering of the items.
+		        /// \note This operator only has to define some strict ordering of
 		        /// the arcs; this order has nothing to do with the iteration
 		        /// ordering of the arcs.
 		        bool operator<(Arc) const { return false; }
 		        /// Converison to Edge
+		        /// Converison to \c Edge
 		        /// Converison to \c Edge.
 		        ///
 		        operator Edge() const { return Edge(); }
 		      };
 		      /// This iterator goes through each directed arc.
 		      /// This iterator goes through each arc of a graph.
 		      /// Its usage is quite simple, for example you can count the number
-		      /// of arcs in a graph \c g of type \c Graph as follows:
+		      /// Iterator class for the arcs.
 		      /// This iterator goes through each directed arc of the graph.
 		      /// Its usage is quite simple, for example, you can count the number
 		      /// of arcs in a graph \c g of type \c %Graph as follows:
 		      ///\code
 		      /// int count=0;
-		      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
+		      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class ArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        ArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        ArcIt(const ArcIt& e) : Arc(e) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
-		        /// Initialize the iterator to be invalid.
+		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        ArcIt(Invalid) { }
 		        /// Sets the iterator to the first arc.
 		        /// Sets the iterator to the first arc of the given graph.
 		        ///
 		        ArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first arc.
 		        explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
 		        /// Sets the iterator to the given arc.
 		        /// This constructor sets the iterator to the first arc of \c g.
 		        ///@param g the graph
 		        ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
 		        /// Arc -> ArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        /// Sets the iterator to the given arc of the given graph.
 		        ///
 		        ArcIt(const Graph&, const Arc&) { }
 		        ///Next arc
+		        /// Next arc
 		        /// Assign the iterator to the next arc.
 		        ///
 		        ArcIt& operator++() { return *this; }
 		      };
-		      /// This iterator goes trough the outgoing directed arcs of a node.
+		      /// Iterator class for the outgoing arcs of a node.
 		      /// This iterator goes trough the \e outgoing arcs of a certain node
 		      /// of a graph.
-		      /// Its usage is quite simple, for example you can count the number
+		      /// This iterator goes trough the \e outgoing directed arcs of a
 		      /// certain node of a graph.
 		      /// Its usage is quite simple, for example, you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in graph \c g of type \c Graph as follows.
+		      /// in a graph \c g of type \c %Graph as follows.
 		      ///\code
 		      /// int count=0;
-		      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
+		      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class OutArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        OutArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        OutArcIt(const OutArcIt& e) : Arc(e) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
-		        /// Initialize the iterator to be invalid.
+		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        OutArcIt(Invalid) { }
 		        /// Sets the iterator to the first outgoing arc.
 		        /// Sets the iterator to the first outgoing arc of the given node.
 		        ///
 		        OutArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first outgoing arc.
 		        /// This constructor sets the iterator to the first outgoing arc of
 		        /// the node.
 		        ///@param n the node
 		        ///@param g the graph
 		        OutArcIt(const Graph& n, const Node& g) {
 		          ignore_unused_variable_warning(n);
 		          ignore_unused_variable_warning(g);
+		        }
-		        /// Arc -> OutArcIt conversion
+		        /// Sets the iterator to the given arc.
 		        /// Sets the iterator to the value of the trivial iterator.
 		        /// This feature necessitates that each time we
-		        /// iterate the arc-set, the iteration order is the same.
+		        /// Sets the iterator to the given arc of the given graph.
 		        ///
 		        OutArcIt(const Graph&, const Arc&) { }
 		        ///Next outgoing arc
+		        /// Next outgoing arc
 		        /// Assign the iterator to the next
 		        /// outgoing arc of the corresponding node.
 		        OutArcIt& operator++() { return *this; }
 		      };
-		      /// This iterator goes trough the incoming directed arcs of a node.
+		      /// Iterator class for the incoming arcs of a node.
 		      /// This iterator goes trough the \e incoming arcs of a certain node
 		      /// of a graph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of outgoing arcs of a node \c n
-		      /// in graph \c g of type \c Graph as follows.
+		      /// This iterator goes trough the \e incoming directed arcs of a
 		      /// certain node of a graph.
 		      /// Its usage is quite simple, for example, you can count the number
 		      /// of incoming arcs of a node \c n
 		      /// in a graph \c g of type \c %Graph as follows.
 		      ///\code
 		      /// int count=0;
-		      /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
+		      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class InArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        InArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        InArcIt(const InArcIt& e) : Arc(e) { }
-		        /// Initialize the iterator to be invalid.
+		        /// %Invalid constructor \& conversion.
-		        /// Initialize the iterator to be invalid.
+		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        InArcIt(Invalid) { }
 		        /// Sets the iterator to the first incoming arc.
 		        /// Sets the iterator to the first incoming arc of the given node.
 		        ///
 		        InArcIt(Invalid) { }
 		        /// This constructor sets the iterator to first incoming arc.
 		        /// This constructor set the iterator to the first incoming arc of
 		        /// the node.
 		        ///@param n the node
 		        ///@param g the graph
 		        InArcIt(const Graph& g, const Node& n) {
 		          ignore_unused_variable_warning(n);
 		          ignore_unused_variable_warning(g);
+		        }
-		        /// Arc -> InArcIt conversion
+		        /// Sets the iterator to the given arc.
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
-		        /// iterate the arc-set, the iteration order is the same.
+		        /// Sets the iterator to the given arc of the given graph.
 		        ///
 		        InArcIt(const Graph&, const Arc&) { }
 		        /// Next incoming arc
 		        /// Assign the iterator to the next inarc of the corresponding node.
 		        ///
 		        /// Assign the iterator to the next
 		        /// incoming arc of the corresponding node.
 		        InArcIt& operator++() { return *this; }
 		      };
-		      /// \brief Reference map of the nodes to type \c T.
+		      /// \brief Standard graph map type for the nodes.
 		      ///
-		      /// Reference map of the nodes to type \c T.
+		      /// Standard graph map type for the nodes.
 		      /// It conforms to the ReferenceMap concept.
 		      template<class T>
 		      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
+		      {
 		      public:
 		        ///\e
 		        NodeMap(const Graph&) { }
-		        ///\e
+		        /// Constructor
 		        explicit NodeMap(const Graph&) { }
 		        /// Constructor with given initial value
 		        NodeMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
 		        NodeMap(const NodeMap& nm) :
 		          ReferenceMap<Node, T, T&, const T&>(nm) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, CMap>();
 		          return *this;
+		        }
 		      };
-		      /// \brief Reference map of the arcs to type \c T.
+		      /// \brief Standard graph map type for the arcs.
 		      ///
-		      /// Reference map of the arcs to type \c T.
+		      /// Standard graph map type for the arcs.
 		      /// It conforms to the ReferenceMap concept.
 		      template<class T>
 		      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
+		      {
 		      public:
 		        ///\e
 		        ArcMap(const Graph&) { }
-		        ///\e
+		        /// Constructor
 		        explicit ArcMap(const Graph&) { }
 		        /// Constructor with given initial value
 		        ArcMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
 		        ArcMap(const ArcMap& em) :
 		          ReferenceMap<Arc, T, T&, const T&>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// Reference map of the edges to type \c T.
-		      /// Reference map of the edges to type \c T.
+		      /// \brief Standard graph map type for the edges.
 		      ///
 		      /// Standard graph map type for the edges.
 		      /// It conforms to the ReferenceMap concept.
 		      template<class T>
 		      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
+		      {
 		      public:
 		        ///\e
 		        EdgeMap(const Graph&) { }
-		        ///\e
+		        /// Constructor
 		        explicit EdgeMap(const Graph&) { }
 		        /// Constructor with given initial value
 		        EdgeMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
 		        EdgeMap(const EdgeMap& em) :
 		          ReferenceMap<Edge, T, T&, const T&>(em) {}
 		        ///Assignment operator
 		        template <typename CMap>
 		        EdgeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Edge, T>, CMap>();
 		          return *this;
+		        }
 		      };
-		      /// \brief Direct the given edge.
+		      /// \brief The first node of the edge.
 		      ///
 		      /// Direct the given edge. The returned arc source
 		      /// will be the given node.
 		      Arc direct(const Edge&, const Node&) const {
 		        return INVALID;
+		      }
-		      /// \brief Direct the given edge.
+		      /// Returns the first node of the given edge.
 		      ///
 		      /// Direct the given edge. The returned arc
 		      /// represents the given edge and the direction comes
 		      /// from the bool parameter. The source of the edge and
 		      /// the directed arc is the same when the given bool is true.
 		      Arc direct(const Edge&, bool) const {
 		        return INVALID;
+		      }
 		      /// \brief Returns true if the arc has default orientation.
 		      ///
 		      /// Returns whether the given directed arc is same orientation as
 		      /// the corresponding edge's default orientation.
 		      bool direction(Arc) const { return true; }
 		      /// \brief Returns the opposite directed arc.
 		      ///
 		      /// Returns the opposite directed arc.
 		      Arc oppositeArc(Arc) const { return INVALID; }
 		      /// \brief Opposite node on an arc
 		      ///
 		      /// \return The opposite of the given node on the given edge.
 		      Node oppositeNode(Node, Edge) const { return INVALID; }
 		      /// \brief First node of the edge.
 		      ///
 		      /// \return The first node of the given edge.
 		      ///
 		      /// Naturally edges don't have direction and thus
 		      /// don't have source and target node. However we use \c u() and \c v()
 		      /// methods to query the two nodes of the arc. The direction of the
 		      /// arc which arises this way is called the inherent direction of the
 		      /// edge, and is used to define the "default" direction
 		      /// of the directed versions of the arcs.
 		      /// Edges don't have source and target nodes, however, methods
 		      /// u() and v() are used to query the two end-nodes of an edge.
 		      /// The orientation of an edge that arises this way is called
 		      /// the inherent direction, it is used to define the default
 		      /// direction for the corresponding arcs.
 		      /// \sa v()
 		      /// \sa direction()
 		      Node u(Edge) const { return INVALID; }
-		      /// \brief Second node of the edge.
+		      /// \brief The second node of the edge.
 		      ///
-		      /// \return The second node of the given edge.
+		      /// Returns the second node of the given edge.
 		      ///
 		      /// Naturally edges don't have direction and thus
 		      /// don't have source and target node. However we use \c u() and \c v()
 		      /// methods to query the two nodes of the arc. The direction of the
 		      /// arc which arises this way is called the inherent direction of the
 		      /// edge, and is used to define the "default" direction
 		      /// of the directed versions of the arcs.
 		      /// Edges don't have source and target nodes, however, methods
 		      /// u() and v() are used to query the two end-nodes of an edge.
 		      /// The orientation of an edge that arises this way is called
 		      /// the inherent direction, it is used to define the default
 		      /// direction for the corresponding arcs.
 		      /// \sa u()
 		      /// \sa direction()
 		      Node v(Edge) const { return INVALID; }
-		      /// \brief Source node of the directed arc.
+		      /// \brief The source node of the arc.
 		      ///
 		      /// Returns the source node of the given arc.
 		      Node source(Arc) const { return INVALID; }
-		      /// \brief Target node of the directed arc.
+		      /// \brief The target node of the arc.
 		      ///
 		      /// Returns the target node of the given arc.
 		      Node target(Arc) const { return INVALID; }
-		      /// \brief Returns the id of the node.
+		      /// \brief The ID of the node.
 		      ///
 		      /// Returns the ID of the given node.
 		      int id(Node) const { return -1; }
-		      /// \brief Returns the id of the edge.
+		      /// \brief The ID of the edge.
 		      ///
 		      /// Returns the ID of the given edge.
 		      int id(Edge) const { return -1; }
-		      /// \brief Returns the id of the arc.
+		      /// \brief The ID of the arc.
 		      ///
 		      /// Returns the ID of the given arc.
 		      int id(Arc) const { return -1; }
-		      /// \brief Returns the node with the given id.
+		      /// \brief The node with the given ID.
 		      ///
-		      /// \pre The argument should be a valid node id in the graph.
+		      /// Returns the node with the given ID.
 		      /// \pre The argument should be a valid node ID in the graph.
 		      Node nodeFromId(int) const { return INVALID; }
-		      /// \brief Returns the edge with the given id.
+		      /// \brief The edge with the given ID.
 		      ///
-		      /// \pre The argument should be a valid edge id in the graph.
+		      /// Returns the edge with the given ID.
 		      /// \pre The argument should be a valid edge ID in the graph.
 		      Edge edgeFromId(int) const { return INVALID; }
-		      /// \brief Returns the arc with the given id.
+		      /// \brief The arc with the given ID.
 		      ///
-		      /// \pre The argument should be a valid arc id in the graph.
+		      /// Returns the arc with the given ID.
 		      /// \pre The argument should be a valid arc ID in the graph.
 		      Arc arcFromId(int) const { return INVALID; }
-		      /// \brief Returns an upper bound on the node IDs.
+		      /// \brief An upper bound on the node IDs.
 		      ///
 		      /// Returns an upper bound on the node IDs.
 		      int maxNodeId() const { return -1; }
-		      /// \brief Returns an upper bound on the edge IDs.
+		      /// \brief An upper bound on the edge IDs.
 		      ///
 		      /// Returns an upper bound on the edge IDs.
 		      int maxEdgeId() const { return -1; }
-		      /// \brief Returns an upper bound on the arc IDs.
+		      /// \brief An upper bound on the arc IDs.
 		      ///
 		      /// Returns an upper bound on the arc IDs.
 		      int maxArcId() const { return -1; }
 		      /// \brief The direction of the arc.
 		      ///
 		      /// Returns \c true if the direction of the given arc is the same as
 		      /// the inherent orientation of the represented edge.
 		      bool direction(Arc) const { return true; }
 		      /// \brief Direct the edge.
 		      ///
 		      /// Direct the given edge. The returned arc
 		      /// represents the given edge and its direction comes
 		      /// from the bool parameter. If it is \c true, then the direction
 		      /// of the arc is the same as the inherent orientation of the edge.
 		      Arc direct(Edge, bool) const {
 		        return INVALID;
+		      }
 		      /// \brief Direct the edge.
 		      ///
 		      /// Direct the given edge. The returned arc represents the given
 		      /// edge and its source node is the given node.
 		      Arc direct(Edge, Node) const {
 		        return INVALID;
+		      }
 		      /// \brief The oppositely directed arc.
 		      ///
 		      /// Returns the oppositely directed arc representing the same edge.
 		      Arc oppositeArc(Arc) const { return INVALID; }
 		      /// \brief The opposite node on the edge.
 		      ///
 		      /// Returns the opposite node on the given edge.
 		      Node oppositeNode(Node, Edge) const { return INVALID; }
 		      void first(Node&) const {}
 		      void next(Node&) const {}
 		      void first(Edge&) const {}
 		      void next(Edge&) const {}
 		      void first(Arc&) const {}
 		      void next(Arc&) const {}
 		      void firstOut(Arc&, Node) const {}
 		      void nextOut(Arc&) const {}
 		      void firstIn(Arc&, Node) const {}
 		      void nextIn(Arc&) const {}
 		      void firstInc(Edge &, bool &, const Node &) const {}
 		      void nextInc(Edge &, bool &) const {}
 		      // The second parameter is dummy.
 		      Node fromId(int, Node) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Edge fromId(int, Edge) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Arc fromId(int, Arc) const { return INVALID; }
 		      // Dummy parameter.
 		      int maxId(Node) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Edge) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Arc) const { return -1; }
-		      /// \brief Base node of the iterator
+		      /// \brief The base node of the iterator.
 		      ///
 		      /// Returns the base node (the source in this case) of the iterator
 		      Node baseNode(OutArcIt e) const {
 		        return source(e);
+		      }
-		      /// \brief Running node of the iterator
+		      /// Returns the base node of the given incident edge iterator.
 		      Node baseNode(IncEdgeIt) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Returns the running node (the target in this case) of the
 		      /// iterator
 		      Node runningNode(OutArcIt e) const {
 		        return target(e);
+		      }
+		      /// Returns the running node of the given incident edge iterator.
 		      Node runningNode(IncEdgeIt) const { return INVALID; }
-		      /// \brief Base node of the iterator
+		      /// \brief The base node of the iterator.
 		      ///
 		      /// Returns the base node (the target in this case) of the iterator
 		      Node baseNode(InArcIt e) const {
 		        return target(e);
+		      }
-		      /// \brief Running node of the iterator
+		      /// Returns the base node of the given outgoing arc iterator
 		      /// (i.e. the source node of the corresponding arc).
 		      Node baseNode(OutArcIt) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Returns the running node (the source in this case) of the
 		      /// iterator
 		      Node runningNode(InArcIt e) const {
 		        return source(e);
+		      }
+		      /// Returns the running node of the given outgoing arc iterator
 		      /// (i.e. the target node of the corresponding arc).
 		      Node runningNode(OutArcIt) const { return INVALID; }
-		      /// \brief Base node of the iterator
+		      /// \brief The base node of the iterator.
 		      ///
 		      /// Returns the base node of the iterator
 		      Node baseNode(IncEdgeIt) const {
 		        return INVALID;
+		      }
 		      /// Returns the base node of the given incomming arc iterator
 		      /// (i.e. the target node of the corresponding arc).
 		      Node baseNode(InArcIt) const { return INVALID; }
-		      /// \brief Running node of the iterator
+		      /// \brief The running node of the iterator.
 		      ///
 		      /// Returns the running node of the iterator
 		      Node runningNode(IncEdgeIt) const {
 		        return INVALID;
+		      }
 		      /// Returns the running node of the given incomming arc iterator
 		      /// (i.e. the source node of the corresponding arc).
 		      Node runningNode(InArcIt) const { return INVALID; }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<BaseGraphComponent, _Graph>();
 		          checkConcept<IterableGraphComponent<>, _Graph>();
 		          checkConcept<IDableGraphComponent<>, _Graph>();
 		          checkConcept<MappableGraphComponent<>, _Graph>();
+		        }
 		      };
 		    };
+		  }
+		}
 		#endif

Changeset was too big and was cut off... Show full diff

0 comments (0 inline)

RhodeCode

Login to your account

Changeset was too big and was cut off... Show full diff

Changeset was too big and was cut off... Show full diff

...	...	@@ -49,96 +49,108 @@
49	49	#include "coin/CbcHeuristic.hpp"
50	50
51	51	namespace lemon {
52	52
53	53	CbcMip::CbcMip() {
54	54	_prob = new CoinModel();
55	55	_prob->setProblemName("LEMON");
56	56	_osi_solver = 0;
57	57	_cbc_model = 0;
58	58	messageLevel(MESSAGE_NOTHING);
59	59	}
60	60
61	61	CbcMip::CbcMip(const CbcMip& other) {
62	62	_prob = new CoinModel(*other._prob);
63	63	_prob->setProblemName("LEMON");
64	64	_osi_solver = 0;
65	65	_cbc_model = 0;
66	66	messageLevel(MESSAGE_NOTHING);
67	67	}
68	68
69	69	CbcMip::~CbcMip() {
70	70	delete _prob;
71	71	if (_osi_solver) delete _osi_solver;
72	72	if (_cbc_model) delete _cbc_model;
73	73	}
74	74
75	75	const char* CbcMip::_solverName() const { return "CbcMip"; }
76	76
77	77	int CbcMip::_addCol() {
78	78	_prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0, 0, false);
79	79	return _prob->numberColumns() - 1;
80	80	}
81	81
82	82	CbcMip* CbcMip::newSolver() const {
83	83	CbcMip* newlp = new CbcMip;
84	84	return newlp;
85	85	}
86	86
87	87	CbcMip* CbcMip::cloneSolver() const {
88	88	CbcMip* copylp = new CbcMip(*this);
89	89	return copylp;
90	90	}
91	91
92	92	int CbcMip::_addRow() {
93	93	_prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
94	94	return _prob->numberRows() - 1;
95	95	}
96	96
	97	int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
	98	std::vector<int> indexes;
	99	std::vector<Value> values;
	100
	101	for(ExprIterator it = b; it != e; ++it) {
	102	indexes.push_back(it->first);
	103	values.push_back(it->second);
	104	}
	105
	106	_prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
	107	return _prob->numberRows() - 1;
	108	}
97	109
98	110	void CbcMip::_eraseCol(int i) {
99	111	_prob->deleteColumn(i);
100	112	}
101	113
102	114	void CbcMip::_eraseRow(int i) {
103	115	_prob->deleteRow(i);
104	116	}
105	117
106	118	void CbcMip::_eraseColId(int i) {
107	119	cols.eraseIndex(i);
108	120	}
109	121
110	122	void CbcMip::_eraseRowId(int i) {
111	123	rows.eraseIndex(i);
112	124	}
113	125
114	126	void CbcMip::_getColName(int c, std::string& name) const {
115	127	name = _prob->getColumnName(c);
116	128	}
117	129
118	130	void CbcMip::_setColName(int c, const std::string& name) {
119	131	_prob->setColumnName(c, name.c_str());
120	132	}
121	133
122	134	int CbcMip::_colByName(const std::string& name) const {
123	135	return _prob->column(name.c_str());
124	136	}
125	137
126	138	void CbcMip::_getRowName(int r, std::string& name) const {
127	139	name = _prob->getRowName(r);
128	140	}
129	141
130	142	void CbcMip::_setRowName(int r, const std::string& name) {
131	143	_prob->setRowName(r, name.c_str());
132	144	}
133	145
134	146	int CbcMip::_rowByName(const std::string& name) const {
135	147	return _prob->row(name.c_str());
136	148	}
137	149
138	150	void CbcMip::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
139	151	for (ExprIterator it = b; it != e; ++it) {
140	152	_prob->setElement(i, it->first, it->second);
141	153	}
142	154	}
143	155
144	156	void CbcMip::_getRowCoeffs(int ix, InsertIterator b) const {

...	...	@@ -33,96 +33,109 @@
33	33	cols = other.cols;
34	34	_init_temporals();
35	35	messageLevel(MESSAGE_NOTHING);
36	36	}
37	37
38	38	ClpLp::~ClpLp() {
39	39	delete _prob;
40	40	_clear_temporals();
41	41	}
42	42
43	43	void ClpLp::_init_temporals() {
44	44	_primal_ray = 0;
45	45	_dual_ray = 0;
46	46	}
47	47
48	48	void ClpLp::_clear_temporals() {
49	49	if (_primal_ray) {
50	50	delete[] _primal_ray;
51	51	_primal_ray = 0;
52	52	}
53	53	if (_dual_ray) {
54	54	delete[] _dual_ray;
55	55	_dual_ray = 0;
56	56	}
57	57	}
58	58
59	59	ClpLp* ClpLp::newSolver() const {
60	60	ClpLp* newlp = new ClpLp;
61	61	return newlp;
62	62	}
63	63
64	64	ClpLp* ClpLp::cloneSolver() const {
65	65	ClpLp* copylp = new ClpLp(*this);
66	66	return copylp;
67	67	}
68	68
69	69	const char* ClpLp::_solverName() const { return "ClpLp"; }
70	70
71	71	int ClpLp::_addCol() {
72	72	_prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0);
73	73	return _prob->numberColumns() - 1;
74	74	}
75	75
76	76	int ClpLp::_addRow() {
77	77	_prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
78	78	return _prob->numberRows() - 1;
79	79	}
80	80
	81	int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
	82	std::vector<int> indexes;
	83	std::vector<Value> values;
	84
	85	for(ExprIterator it = b; it != e; ++it) {
	86	indexes.push_back(it->first);
	87	values.push_back(it->second);
	88	}
	89
	90	_prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
	91	return _prob->numberRows() - 1;
	92	}
	93
81	94
82	95	void ClpLp::_eraseCol(int c) {
83	96	_col_names_ref.erase(_prob->getColumnName(c));
84	97	_prob->deleteColumns(1, &c);
85	98	}
86	99
87	100	void ClpLp::_eraseRow(int r) {
88	101	_row_names_ref.erase(_prob->getRowName(r));
89	102	_prob->deleteRows(1, &r);
90	103	}
91	104
92	105	void ClpLp::_eraseColId(int i) {
93	106	cols.eraseIndex(i);
94	107	cols.shiftIndices(i);
95	108	}
96	109
97	110	void ClpLp::_eraseRowId(int i) {
98	111	rows.eraseIndex(i);
99	112	rows.shiftIndices(i);
100	113	}
101	114
102	115	void ClpLp::_getColName(int c, std::string& name) const {
103	116	name = _prob->getColumnName(c);
104	117	}
105	118
106	119	void ClpLp::_setColName(int c, const std::string& name) {
107	120	_prob->setColumnName(c, const_cast<std::string&>(name));
108	121	_col_names_ref[name] = c;
109	122	}
110	123
111	124	int ClpLp::_colByName(const std::string& name) const {
112	125	std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
113	126	return it != _col_names_ref.end() ? it->second : -1;
114	127	}
115	128
116	129	void ClpLp::_getRowName(int r, std::string& name) const {
117	130	name = _prob->getRowName(r);
118	131	}
119	132
120	133	void ClpLp::_setRowName(int r, const std::string& name) {
121	134	_prob->setRowName(r, const_cast<std::string&>(name));
122	135	_row_names_ref[name] = r;
123	136	}
124	137
125	138	int ClpLp::_rowByName(const std::string& name) const {
126	139	std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
127	140	return it != _row_names_ref.end() ? it->second : -1;
128	141	}