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

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")
 		  SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
 		    "C++ header files")
 		  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
 		    "DLL and import library")
 		  SET(CPACK_COMPONENT_BIN_DESCRIPTION
 		    "Command line utilities")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
 		    "Doxygen generated documentation")
 		  SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
 		  SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
 		  SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
 		  SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
 		    "Components needed to develop software using LEMON")
 		  SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
 		    "Documentation of LEMON")
 		  SET(CPACK_ALL_INSTALL_TYPES Full Developer)
 		  SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
 		  SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
 		  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
 		  SET(CPACK_GENERATOR "NSIS")
 		  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
 		  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
 		  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
 		  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
 		  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
 		  SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
 		    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
 		    ")
 		  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
 		    !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
 		    Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
 		    ")
 		  INCLUDE(CPack)
 		ENDIF()

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
 		DOCSET_FEEDNAME        = "Doxygen generated docs"
 		DOCSET_BUNDLE_ID       = org.doxygen.Project
 		GENERATE_HTMLHELP      = NO
 		CHM_FILE               =
 		HHC_LOCATION           =
 		GENERATE_CHI           = NO
 		CHM_INDEX_ENCODING     =
 		BINARY_TOC             = NO
 		TOC_EXPAND             = NO
 		GENERATE_QHP           = NO
 		QCH_FILE               =
 		QHP_NAMESPACE          = org.doxygen.Project
 		QHP_VIRTUAL_FOLDER     = doc
 		QHG_LOCATION           =
 		DISABLE_INDEX          = NO
 		ENUM_VALUES_PER_LINE   = 4
 		GENERATE_TREEVIEW      = NO
 		TREEVIEW_WIDTH         = 250
 		FORMULA_FONTSIZE       = 10
 		#---------------------------------------------------------------------------
 		# configuration options related to the LaTeX output
 		#---------------------------------------------------------------------------
 		GENERATE_LATEX         = NO
 		LATEX_OUTPUT           = latex
 		LATEX_CMD_NAME         = latex
 		MAKEINDEX_CMD_NAME     = makeindex
 		COMPACT_LATEX          = YES
 		PAPER_TYPE             = a4wide
 		EXTRA_PACKAGES         = amsmath \
 		                         amssymb
 		LATEX_HEADER           =
 		PDF_HYPERLINKS         = YES
 		USE_PDFLATEX           = YES
 		LATEX_BATCHMODE        = NO
 		LATEX_HIDE_INDICES     = NO
 		#---------------------------------------------------------------------------
 		# 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

 		EXTRA_DIST += \
 			doc/Doxyfile.in \
 			doc/DoxygenLayout.xml \
 			doc/coding_style.dox \
 			doc/dirs.dox \
 			doc/groups.dox \
 			doc/lgf.dox \
 			doc/license.dox \
 			doc/mainpage.dox \
 			doc/migration.dox \
 			doc/min_cost_flow.dox \
 			doc/named-param.dox \
 			doc/namespaces.dox \
 			doc/html \
 			doc/CMakeLists.txt
 		DOC_EPS_IMAGES18 = \
 			grid_graph.eps \
 			nodeshape_0.eps \
 			nodeshape_1.eps \
 			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

@@ -187,507 +187,579 @@
 		      return Color(1.0, 0.5, 1.0);
 		    } else {
 		      return Color(0.0, 0.0, 0.0);
+		    }
+		  }
 		  Digraph::NodeMap<int> degree_map(graph);
 		  graphToEps(graph, "graph.eps")
 		    .coords(coords).scaleToA4().undirected()
 		    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
 		    .run();
 		\endcode
 		The \c functorToMap() function makes an \c int to \c Color map from the
 		\c nodeColor() function. The \c composeMap() compose the \c degree_map
 		and the previously created map. The composed map is a proper function to
 		get the color of each node.
 		The usage with class type algorithms is little bit harder. In this
 		case the function type map adaptors can not be used, because the
 		function map adaptors give back temporary objects.
 		\code
 		  Digraph graph;
 		  typedef Digraph::ArcMap<double> DoubleArcMap;
 		  DoubleArcMap length(graph);
 		  DoubleArcMap speed(graph);
 		  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
 		  TimeMap time(length, speed);
 		  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 		  dijkstra.run(source, target);
 		\endcode
 		We have a length map and a maximum speed map on the arcs of a digraph.
 		The minimum time to pass the arc can be calculated as the division of
 		the two maps which can be done implicitly with the \c DivMap template
 		class. We use the implicit minimum time map as the length map of the
 		\c Dijkstra algorithm.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief %Path structures implemented in LEMON.
 		This group contains the path structures implemented in LEMON.
 		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

 		EXTRA_DIST += \
 			lemon/lemon.pc.in \
 			lemon/CMakeLists.txt \
 			lemon/config.h.cmake
 		pkgconfig_DATA += lemon/lemon.pc
 		lib_LTLIBRARIES += lemon/libemon.la
 		lemon_libemon_la_SOURCES = \
 			lemon/arg_parser.cc \
 			lemon/base.cc \
 			lemon/color.cc \
 			lemon/lp_base.cc \
 			lemon/lp_skeleton.cc \
 			lemon/random.cc \
 			lemon/bits/windows.cc
 		nodist_lemon_HEADERS = lemon/config.h
 		lemon_libemon_la_CXXFLAGS = \
 			$(AM_CXXFLAGS) \
 			$(GLPK_CFLAGS) \
 			$(CPLEX_CFLAGS) \
 			$(SOPLEX_CXXFLAGS) \
 			$(CLP_CXXFLAGS) \
 			$(CBC_CXXFLAGS)
 		lemon_libemon_la_LDFLAGS = \
 			$(GLPK_LIBS) \
 			$(CPLEX_LIBS) \
 			$(SOPLEX_LIBS) \
 			$(CLP_LIBS) \
 			$(CBC_LIBS)
 		if HAVE_GLPK
 		lemon_libemon_la_SOURCES += lemon/glpk.cc
 		endif
 		if HAVE_CPLEX
 		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

@@ -267,192 +267,195 @@
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap : public GR::template ArcMap<V> {
 		      typedef typename GR::template ArcMap<V> Parent;
 		    public:
 		      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
 		        : Parent(*adapter._graph) {}
 		      ArcMap(const GraphAdaptorBase<GR>& 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;
+		      }
 		    };
 		    template <typename V>
 		    class EdgeMap : public GR::template EdgeMap<V> {
 		      typedef typename GR::template EdgeMap<V> Parent;
 		    public:
 		      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
 		        : Parent(*adapter._graph) {}
 		      EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        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;
 		    typedef SubDigraphBase Adaptor;
 		  protected:
 		    NF* _node_filter;
 		    AF* _arc_filter;
 		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
 		      Parent::initialize(digraph);
 		      _node_filter = &node_filter;
 		      _arc_filter = &arc_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
@@ -626,192 +629,194 @@
+		    }
 		    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
 		    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
 		    bool status(const Node& n) const { return (*_node_filter)[n]; }
 		    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
 		    typedef False NodeNumTag;
 		    typedef False ArcNumTag;
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& source, const Node& target,
 		                const Arc& prev = INVALID) const {
 		      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(source, target, prev);
 		      while (arc != INVALID && !(*_arc_filter)[arc]) {
 		        arc = Parent::findArc(source, target, arc);
+		      }
 		      return arc;
+		    }
 		    template <typename V>
 		    class NodeMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    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
 		    /// given node and arc filter maps.
 		    SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
 		      Parent::initialize(digraph, node_filter, arc_filter);
+		    }
 		    /// \brief Sets the status of the given node
 		    ///
 		    /// This function sets the status of the given node.
 		    /// It is done by simply setting the assigned value of \c n
 		    /// to \c v in the node filter map.
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    /// \brief Sets the status of the given arc
 		    ///
 		    /// This function sets the status of the given arc.
 		    /// It is done by simply setting the assigned value of \c a
 		    /// to \c v in the arc filter map.
 		    void status(const Arc& a, bool v) const { Parent::status(a, v); }
 		    /// \brief Returns the status of the given node
 		    ///
 		    /// This function returns the status of the given node.
 		    /// It is \c true if the given node is enabled (i.e. not hidden).
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    /// \brief Returns the status of the given arc
 		    ///
 		    /// This function returns the status of the given arc.
 		    /// It is \c true if the given arc is enabled (i.e. not hidden).
 		    bool status(const Arc& a) const { return Parent::status(a); }
 		    /// \brief Disables the given node
 		    ///
 		    /// This function disables the given node in the subdigraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(n, false)".
 		    void disable(const Node& n) const { Parent::status(n, false); }
 		    /// \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 node
 		    ///
 		    /// This function enables the given node in the subdigraph.
@@ -1221,607 +1226,615 @@
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubGraphBase<GR, NF, EF, 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;
+		      }
 		    };
 		    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
 		    /// and edge filter maps.
 		    SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
 		      initialize(graph, node_filter, edge_filter);
+		    }
 		    /// \brief Sets the status of the given node
 		    ///
 		    /// This function sets the status of the given node.
 		    /// It is done by simply setting the assigned value of \c n
 		    /// to \c v in the node filter map.
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    /// \brief Sets the status of the given edge
 		    ///
 		    /// This function sets the status of the given edge.
 		    /// It is done by simply setting the assigned value of \c e
 		    /// to \c v in the edge filter map.
 		    void status(const Edge& e, bool v) const { Parent::status(e, v); }
 		    /// \brief Returns the status of the given node
 		    ///
 		    /// This function returns the status of the given node.
 		    /// It is \c true if the given node is enabled (i.e. not hidden).
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    /// \brief Returns the status of the given edge
 		    ///
 		    /// This function returns the status of the given edge.
 		    /// It is \c true if the given edge is enabled (i.e. not hidden).
 		    bool status(const Edge& e) const { return Parent::status(e); }
 		    /// \brief Disables the given node
 		    ///
 		    /// This function disables the given node in the subdigraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(n, false)".
 		    void disable(const Node& n) const { Parent::status(n, false); }
 		    /// \brief Disables the given edge
 		    ///
 		    /// This function disables the given edge in the subgraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(e, false)".
 		    void disable(const Edge& e) const { Parent::status(e, false); }
 		    /// \brief Enables the given node
 		    ///
 		    /// This function enables the given node in the subdigraph.
 		    /// It is the same as \ref status() "status(n, true)".
 		    void enable(const Node& n) const { Parent::status(n, true); }
 		    /// \brief Enables the given edge
 		    ///
 		    /// This function enables the given edge in the subgraph.
 		    /// It is the same as \ref status() "status(e, true)".
 		    void enable(const Edge& e) const { Parent::status(e, true); }
 		  };
 		  /// \brief Returns a read-only SubGraph adaptor
 		  ///
 		  /// 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()
+		    {
 		      Parent::initialize(graph, node_filter, const_true_map);
+		    }
 		    /// \brief Sets the status of the given node
 		    ///
 		    /// This function sets the status of the given node.
 		    /// It is done by simply setting the assigned value of \c n
 		    /// to \c v in the node filter map.
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    /// \brief Returns the status of the given node
 		    ///
 		    /// This function returns the status of the given node.
 		    /// It is \c true if the given node is enabled (i.e. not hidden).
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    /// \brief Disables the given node
 		    ///
 		    /// This function disables the given node, so the iteration
 		    /// jumps over it.
 		    /// It is the same as \ref status() "status(n, false)".
 		    void disable(const Node& n) const { Parent::status(n, false); }
 		    /// \brief Enables the given node
 		    ///
 		    /// This function enables the given node.
 		    /// It is the same as \ref status() "status(n, true)".
 		    void enable(const Node& n) const { Parent::status(n, true); }
 		  };
 		  template<typename GR, typename NF>
 		  class FilterNodes<GR, NF,
 		                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
 		    public GraphAdaptorExtender<
 		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		                   true> > {
 		    typedef GraphAdaptorExtender<
 		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		                   true> > Parent;
 		  public:
 		    typedef GR Graph;
 		    typedef NF NodeFilterMap;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
 		    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() {
 		      Parent::initialize(digraph, const_true_map, arc_filter);
+		    }
 		    /// \brief Sets the status of the given arc
 		    ///
 		    /// This function sets the status of the given arc.
 		    /// It is done by simply setting the assigned value of \c a
 		    /// to \c v in the arc filter map.
 		    void status(const Arc& a, bool v) const { Parent::status(a, v); }
 		    /// \brief Returns the status of the given arc
 		    ///
 		    /// This function returns the status of the given arc.
 		    /// It is \c true if the given arc is enabled (i.e. not hidden).
 		    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.
 		    FilterEdges(GR& graph, EF& edge_filter)
 		      : Parent(), const_true_map() {
 		      Parent::initialize(graph, const_true_map, edge_filter);
+		    }
 		    /// \brief Sets the status of the given edge
 		    ///
 		    /// This function sets the status of the given edge.
 		    /// It is done by simply setting the assigned value of \c e
 		    /// to \c v in the edge filter map.
 		    void status(const Edge& e, bool v) const { Parent::status(e, v); }
 		    /// \brief Returns the status of the given edge
 		    ///
 		    /// This function returns the status of the given edge.
 		    /// It is \c true if the given edge is enabled (i.e. not hidden).
 		    bool status(const Edge& e) const { return Parent::status(e); }
 		    /// \brief Disables the given edge
 		    ///
 		    /// This function disables the given edge in the subgraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(e, false)".
 		    void disable(const Edge& e) const { Parent::status(e, false); }
 		    /// \brief Enables the given edge
 		    ///
 		    /// This function enables the given edge in the subgraph.
 		    /// It is the same as \ref status() "status(e, true)".
 		    void enable(const Edge& e) const { Parent::status(e, true); }
 		  };
 		  /// \brief Returns a read-only FilterEdges adaptor
 		  ///
 		  /// This function just returns a read-only \ref FilterEdges adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates FilterEdges
 		  template<typename GR, typename EF>
 		  FilterEdges<const GR, EF>
 		  filterEdges(const GR& graph, EF& edge_filter) {
 		    return FilterEdges<const GR, EF>(graph, edge_filter);
+		  }
 		  template<typename GR, typename EF>
 		  FilterEdges<const GR, const EF>
 		  filterEdges(const GR& graph, const EF& edge_filter) {
 		    return FilterEdges<const GR, const EF>(graph, edge_filter);
@@ -2139,192 +2152,195 @@
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
 		      typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
 		    public:
 		      typedef V Value;
 		      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const UndirectorBase<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;
+		      }
 		    };
 		    template <typename V>
 		    class EdgeMap : public Digraph::template ArcMap<V> {
 		      typedef typename Digraph::template ArcMap<V> Parent;
 		    public:
 		      typedef V Value;
 		      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
 		        : Parent(*adaptor._digraph, value) {}
 		    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;
 		      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<FW>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<FW>::ReturnValue Reference;
 		      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
 		      /// Constructor
 		      CombinedArcMap(FW& forward, BK& backward)
 		        : _forward(&forward), _backward(&backward) {}
 		      /// Sets the value associated with the given key.
 		      void set(const Key& e, const Value& a) {
 		        if (Parent::direction(e)) {
 		          _forward->set(e, a);
 		        } else {
 		          _backward->set(e, a);
+		        }
+		      }
 		      /// Returns the value associated with the given key.
 		      ConstReturnValue operator[](const Key& e) const {
 		        if (Parent::direction(e)) {
 		          return (*_forward)[e];
 		        } else {
 		          return (*_backward)[e];
+		        }
+		      }
 		      /// Returns a reference to the value associated with the given key.
 		      ReturnValue operator[](const Key& e) {
 		        if (Parent::direction(e)) {
 		          return (*_forward)[e];
 		        } else {
 		          return (*_backward)[e];
+		        }
+		      }
 		    protected:
 		      FW* _forward;
 		      BK* _backward;
 		    };
 		    /// \brief Returns a combined arc map
 		    ///
 		    /// This function just returns a combined arc map.
@@ -2442,335 +2458,340 @@
 		    void erase(const Arc& i) { _graph->erase(i); }
 		    void clear() { _graph->clear(); }
 		    int id(const Node& v) const { return _graph->id(v); }
 		    int id(const Arc& e) const { return _graph->id(e); }
 		    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
 		    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
 		    int maxNodeId() const { return _graph->maxNodeId(); }
 		    int maxArcId() const { return _graph->maxEdgeId(); }
 		    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 		    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 		    template <typename V>
 		    class NodeMap : public GR::template NodeMap<V> {
 		      typedef typename GR::template NodeMap<V> Parent;
 		    public:
 		      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
 		        : Parent(*adapter._graph) {}
 		      NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap : public GR::template EdgeMap<V> {
 		      typedef typename Graph::template EdgeMap<V> Parent;
 		    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
 		    /// in the direction map.
 		    void reverseArc(const Arc& a) {
 		      Parent::reverseArc(a);
+		    }
 		  };
 		  /// \brief Returns a read-only Orienter adaptor
 		  ///
 		  /// This function just returns a read-only \ref Orienter adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates Orienter
 		  template<typename GR, typename DM>
 		  Orienter<const GR, DM>
 		  orienter(const GR& graph, DM& direction) {
 		    return Orienter<const GR, DM>(graph, direction);
+		  }
 		  template<typename GR, typename DM>
 		  Orienter<const GR, const DM>
 		  orienter(const GR& graph, const DM& direction) {
 		    return Orienter<const GR, const DM>(graph, direction);
+		  }
 		  namespace _adaptor_bits {
 		    template <typename DGR, typename CM, typename FM, typename TL>
 		    class ResForwardFilter {
 		    public:
 		      typedef typename DGR::Arc Key;
 		      typedef bool Value;
 		    private:
 		      const CM* _capacity;
 		      const FM* _flow;
 		      TL _tolerance;
 		    public:
 		      ResForwardFilter(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((*_capacity)[a] - (*_flow)[a]);
+		      }
 		    };
 		    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;
 		    typedef typename CapacityMap::Value Value;
 		    typedef ResidualDigraph Adaptor;
 		  protected:
 		    typedef Undirector<const Digraph> Undirected;
 		    typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
 		    typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
 		                                            FM, TL> ForwardFilter;
 		    typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
 		                                             FM, TL> BackwardFilter;
 		    typedef typename Undirected::
 		      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
 		    typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
 		    const CapacityMap* _capacity;
 		    FlowMap* _flow;
 		    Undirected _graph;
 		    NodeFilter _node_filter;
 		    ForwardFilter _forward_filter;
 		    BackwardFilter _backward_filter;
 		    ArcFilter _arc_filter;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the residual digraph adaptor. The parameters are the
 		    /// digraph, the capacity map, the flow map, and a tolerance object.
 		    ResidualDigraph(const DGR& digraph, const CM& capacity,
 		                    FM& flow, const TL& tolerance = Tolerance())
 		      : Parent(), _capacity(&capacity), _flow(&flow),
 		        _graph(digraph), _node_filter(),
 		        _forward_filter(capacity, flow, tolerance),
 		        _backward_filter(capacity, flow, tolerance),
 		        _arc_filter(_forward_filter, _backward_filter)
+		    {
 		      Parent::initialize(_graph, _node_filter, _arc_filter);
+		    }
 		    typedef typename Parent::Arc Arc;
@@ -3232,192 +3253,195 @@
 		          return _node_map[static_cast<const DigraphNode&>(key)];
+		        }
+		      }
 		    private:
 		      ArcImpl _arc_map;
 		      NodeImpl _node_map;
 		    };
 		  public:
 		    template <typename V>
 		    class NodeMap
 		      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
 		      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SplitNodesBase<DGR>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
 		      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SplitNodesBase<DGR>& adaptor)
 		        : Parent(adaptor) {}
 		      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
 		    /// original digraph.
 		    static bool origArc(const Arc& a) {
 		      return Parent::origArc(a);
+		    }
 		    /// \brief Returns \c true if the given arc is a bind arc.
 		    ///
 		    /// Returns \c true if the given arc is a bind arc, i.e. it connects
 		    /// an in-node and an out-node.
 		    static bool bindArc(const Arc& a) {
 		      return Parent::bindArc(a);
+		    }
 		    /// \brief Returns the in-node created from the given original node.
 		    ///
 		    /// Returns the in-node created from the given original node.
 		    static Node inNode(const DigraphNode& n) {
 		      return Parent::inNode(n);
+		    }
 		    /// \brief Returns the out-node created from the given original node.
 		    ///
 		    /// Returns the out-node created from the given original node.
 		    static Node outNode(const DigraphNode& n) {
 		      return Parent::outNode(n);
+		    }
 		    /// \brief Returns the bind arc that corresponds to the given
 		    /// original node.
 		    ///
 		    /// Returns the bind arc in the adaptor that corresponds to the given
 		    /// original node, i.e. the arc connecting the in-node and out-node
 		    /// of \c n.
 		    static Arc arc(const DigraphNode& n) {
 		      return Parent::arc(n);
+		    }
 		    /// \brief Returns the arc that corresponds to the given original arc.
 		    ///
 		    /// Returns the arc in the adaptor that corresponds to the given
 		    /// original arc.
 		    static Arc arc(const DigraphArc& a) {
 		      return Parent::arc(a);
+		    }
 		    /// \brief Node map combined from two original node maps
 		    ///
 		    /// This map adaptor class adapts two node maps of the original digraph

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);
+		    }
 		    static Value infinity() {
 		      return std::numeric_limits<Value>::max();
+		    }
 		    static Value plus(const Value& left, const Value& right) {
 		      if (left == infinity() || right == infinity()) return infinity();
 		      return left + right;
+		    }
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  /// \brief Default traits class of BellmanFord class.
 		  ///
 		  /// Default traits class of BellmanFord class.
 		  /// \param GR The type of the digraph.
 		  /// \param LEN The type of the length map.
 		  template<typename GR, typename LEN>
 		  struct BellmanFordDefaultTraits {
 		    /// 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 conform to 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
 		    /// given \c Value type.
 		    /// \see BellmanFordDefaultOperationTraits
 		    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 		    /// \brief The type of the map that stores the last arcs of the
 		    /// shortest paths.
 		    ///
 		    /// The type of the map that stores the last
 		    /// arcs of the shortest paths.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
 		    /// \brief Instantiates a \c PredMap.
 		    ///
@@ -206,193 +207,193 @@
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    // Pointer to the underlying digraph.
 		    const Digraph *_gr;
 		    // Pointer to the length map
 		    const LengthMap *_length;
 		    // Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    // Indicates if _pred is locally allocated (true) or not.
 		    bool _local_pred;
 		    // Pointer to the map of distances.
 		    DistMap *_dist;
 		    // Indicates if _dist is locally allocated (true) or not.
 		    bool _local_dist;
 		    typedef typename Digraph::template NodeMap<bool> MaskMap;
 		    MaskMap *_mask;
 		    std::vector<Node> _process;
 		    // Creates the maps if necessary.
 		    void create_maps() {
 		      if(!_pred) {
 			_local_pred = true;
 			_pred = Traits::createPredMap(*_gr);
+		      }
 		      if(!_dist) {
 			_local_dist = true;
 			_dist = Traits::createDistMap(*_gr);
+		      }
 		      _mask = new MaskMap(*_gr, false);
+		    }
 		  public :
 		    typedef BellmanFord 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 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.
 		    /// \return <tt>(*this)</tt>
 		    BellmanFord &predMap(PredMap &map) {
 		      if(_local_pred) {
 			delete _pred;
 			_local_pred=false;
+		      }
 		      _pred = &map;
 		      return *this;
+		    }
 		    /// \brief 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()
 		    /// or \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    BellmanFord &distMap(DistMap &map) {
 		      if(_local_dist) {
 			delete _dist;
 			_local_dist=false;
+		      }
 		      _dist = &map;
 		      return *this;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the Bellman-Ford algorithm is to use
 		    /// one of the member functions called \ref run().\n
 		    /// 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 \ref start(), \ref checkedStart() or
 		    /// \ref limitedStart().
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures. The optional parameter
 		    /// is the initial distance of each node.
 		    void init(const Value value = OperationTraits::infinity()) {
 		      create_maps();
 		      for (NodeIt it(*_gr); it != INVALID; ++it) {
 			_pred->set(it, INVALID);
 			_dist->set(it, value);
@@ -624,251 +625,251 @@
 		    ///@}
 		    /// \brief LEMON iterator for getting the active nodes.
 		    ///
 		    /// This class provides a common style LEMON iterator that traverses
 		    /// the active nodes of the Bellman-Ford algorithm after the last
 		    /// phase. These nodes should be checked in the next phase to
 		    /// find augmenting arcs outgoing from them.
 		    class ActiveIt {
 		    public:
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor for getting the active nodes of the given BellmanFord
 		      /// instance.
 		      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
+		      {
 		        _index = _algorithm->_process.size() - 1;
+		      }
 		      /// \brief Invalid constructor.
 		      ///
 		      /// Invalid constructor.
 		      ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
 		      /// \brief Conversion to \c Node.
 		      ///
 		      /// Conversion to \c Node.
 		      operator Node() const {
 		        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
+		      }
 		      /// \brief Increment operator.
 		      ///
 		      /// Increment operator.
 		      ActiveIt& operator++() {
 		        --_index;
 		        return *this;
+		      }
 		      bool operator==(const ActiveIt& it) const {
 		        return static_cast<Node>(*this) == static_cast<Node>(it);
+		      }
 		      bool operator!=(const ActiveIt& it) const {
 		        return static_cast<Node>(*this) != static_cast<Node>(it);
+		      }
 		      bool operator<(const ActiveIt& it) const {
 		        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
 		    /// given \c Value type.
 		    /// \see BellmanFordDefaultOperationTraits
 		    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 		    /// \brief The type of the map that stores the last
 		    /// arcs of the shortest paths.
 		    ///
 		    /// The type of the map that stores the last arcs of the shortest paths.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
 		    /// \brief 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 GR &g) {
 		      return new PredMap(g);
+		    }
 		    /// \brief 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 conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<Value> DistMap;
 		    /// \brief 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 GR &g) {
 		      return new DistMap(g);
+		    }
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
 		    ///It must meet the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \brief Default traits class used by BellmanFordWizard.
 		  ///
 		  /// Default traits class used by BellmanFordWizard.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  template <typename GR, typename LEN>

lemon/bfs.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_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;
 		    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::Node> _queue;
 		    int _queue_head,_queue_tail,_queue_next_dist;
 		    int _curr_dist;
 		    //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;
+		    }
 		    ///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(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 &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///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>
 		    Bfs &reachedMap(ReachedMap &m)
+		    {
 		      if(local_reached) {
 		        delete _reached;
 		        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++;
 		        _queue_next_dist=_queue_head;
+		      }
 		      Node n=_queue[_queue_tail++];
 		      _processed->set(n,true);
 		      Node m;
 		      for(OutArcIt e(*G,n);e!=INVALID;++e)
 		        if(!(*_reached)[m=G->target(e)]) {
 		          _queue[_queue_head++]=m;
 		          _reached->set(m,true);
 		          _pred->set(m,e);
 		          _dist->set(m,_curr_dist);
+		        }
 		      return n;
+		    }
 		    ///Processes the next node.
 		    ///Processes the next node and checks if the given target node
 		    ///is reached. If the target node is reachable from the processed
 		    ///node, then the \c reach parameter will be set to \c true.
 		    ///
 		    ///\param target The target node.
 		    ///\retval reach Indicates if the target node is reached.
 		    ///It should be initially \c false.
 		    ///
 		    ///\return The processed node.
 		    ///
 		    ///\pre The queue must not be empty.
 		    Node processNextNode(Node target, bool& reach)
+		    {
 		      if(_queue_tail==_queue_next_dist) {
 		        _curr_dist++;
 		        _queue_next_dist=_queue_head;
+		      }
 		      Node n=_queue[_queue_tail++];
 		      _processed->set(n,true);
 		      Node m;
 		      for(OutArcIt e(*G,n);e!=INVALID;++e)
 		        if(!(*_reached)[m=G->target(e)]) {
 		          _queue[_queue_head++]=m;
 		          _reached->set(m,true);
 		          _pred->set(m,e);
 		          _dist->set(m,_curr_dist);
 		          reach = reach || (target == m);
+		        }
 		      return n;
+		    }
@@ -607,919 +608,911 @@
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  bool reach = false;
 		    ///  while ( !b.emptyQueue() && !reach ) {
 		    ///    b.processNextNode(t, reach);
 		    ///  }
 		    ///\endcode
 		    void start(Node t)
+		    {
 		      bool reach = false;
 		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
 		    ///Executes the algorithm until a condition is met.
 		    ///Executes the algorithm until a condition is met.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s) in
 		    ///order to compute the shortest path to a node \c v with
 		    /// <tt>nm[v]</tt> true, if such a node can be found.
 		    ///
 		    ///\param nm A \c bool (or convertible) node map. The algorithm
 		    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
 		    ///
 		    ///\return The reached node \c v with <tt>nm[v]</tt> true or
 		    ///\c INVALID if no such node was found.
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  Node rnode = INVALID;
 		    ///  while ( !b.emptyQueue() && rnode == INVALID ) {
 		    ///    b.processNextNode(nm, rnode);
 		    ///  }
 		    ///  return rnode;
 		    ///\endcode
 		    template<class NodeBoolMap>
 		    Node start(const NodeBoolMap &nm)
+		    {
 		      Node rnode = INVALID;
 		      while ( !emptyQueue() && rnode == INVALID ) {
 		        processNextNode(nm, rnode);
+		      }
 		      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);
 		  ///
 		  ///  // Compute shortest path from s to t
 		  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
 		  ///to the end of the parameter list.
 		  ///\sa BfsWizard
 		  ///\sa Bfs
 		  template<class GR>
 		  BfsWizard<BfsWizardBase<GR> >
 		  bfs(const GR &digraph)
+		  {
 		    return BfsWizard<BfsWizardBase<GR> >(digraph);
+		  }
 		#ifdef DOXYGEN
 		  /// \brief Visitor class for BFS.
 		  ///
 		  /// This class defines the interface of the BfsVisit events, and
 		  /// it could be the base of a real visitor class.
 		  template <typename GR>
 		  struct BfsVisitor {
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    /// \brief Called for the source node(s) of the BFS.
 		    ///
 		    /// This function is called for the source node(s) of the BFS.
 		    void start(const Node& node) {}
 		    /// \brief Called when a node is reached first time.
 		    ///
 		    /// This function is called when a node is reached first time.
 		    void reach(const Node& node) {}
 		    /// \brief Called when a node is processed.
 		    ///
 		    /// This function is called when a node is processed.
 		    void process(const Node& node) {}
 		    /// \brief Called when an arc reaches a new node.
 		    ///
 		    /// This function is called when the BFS finds an arc whose target node
 		    /// is not reached yet.
 		    void discover(const Arc& arc) {}
 		    /// \brief Called when 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> >
 		#endif
 		  class BfsVisit {
 		  public:
 		    ///The traits class.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The visitor type used by the algorithm.
 		    typedef VS Visitor;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename Traits::ReachedMap ReachedMap;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *_digraph;
 		    //Pointer to the visitor object.
 		    Visitor *_visitor;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Node> _list;
 		    int _list_front, _list_back;
 		    //Creates the maps if necessary.
 		    void create_maps() {
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*_digraph);
+		      }
+		    }
 		  protected:
 		    BfsVisit() {}
 		  public:
 		    typedef BfsVisit Create;
 		    /// \name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
 		    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 {
 		          _visitor->examine(e);
+		        }
+		      }
 		      return n;
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node and checks if the given target node
 		    /// is reached. If the target node is reachable from the processed
 		    /// node, then the \c reach parameter will be set to \c true.
 		    ///
 		    /// \param target The target node.
 		    /// \retval reach Indicates if the target node is reached.
 		    /// It should be initially \c false.
 		    ///
 		    /// \return The processed node.
 		    ///
 		    /// \pre The queue must not be empty.
 		    Node processNextNode(Node target, bool& reach) {
 		      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;
 		          reach = reach || (target == m);
 		        } else {
 		          _visitor->examine(e);
+		        }
+		      }
 		      return n;
+		    }
 		    /// \brief Processes the next node.
 		    ///
 		    /// Processes the next node and checks if at least one of reached
 		    /// nodes has \c true value in the \c nm node map. If one node
 		    /// with \c true value is reachable from the processed node, then the
 		    /// \c rnode parameter will be set to the first of such nodes.
 		    ///
 		    /// \param nm A \c bool (or convertible) node map that indicates the
 		    /// possible targets.
 		    /// \retval rnode The reached target node.
@@ -1605,148 +1598,144 @@
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    ///
 		    /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   bool reach = false;
 		    ///   while ( !b.emptyQueue() && !reach ) {
 		    ///     b.processNextNode(t, reach);
 		    ///   }
 		    /// \endcode
 		    void start(Node t) {
 		      bool reach = false;
 		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
 		    /// \brief Executes the algorithm until a condition is met.
 		    ///
 		    /// Executes the algorithm until a condition is met.
 		    ///
 		    /// This method runs the %BFS algorithm from the root node(s) in
 		    /// order to compute the shortest path to a node \c v with
 		    /// <tt>nm[v]</tt> true, if such a node can be found.
 		    ///
 		    /// \param nm must be a bool (or convertible) node map. The
 		    /// algorithm will stop when it reaches a node \c v with
 		    /// <tt>nm[v]</tt> true.
 		    ///
 		    /// \return The reached node \c v with <tt>nm[v]</tt> true or
 		    /// \c INVALID if no such node was found.
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    ///
 		    /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
 		    /// \code
 		    ///   Node rnode = INVALID;
 		    ///   while ( !b.emptyQueue() && rnode == INVALID ) {
 		    ///     b.processNextNode(nm, rnode);
 		    ///   }
 		    ///   return rnode;
 		    /// \endcode
 		    template <typename NM>
 		    Node start(const NM &nm) {
 		      Node rnode = INVALID;
 		      while ( !emptyQueue() && rnode == INVALID ) {
 		        processNextNode(nm, rnode);
+		      }
 		      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

 		/* -*- 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_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) {}
 		      NodeIt& operator++() {
 		        _digraph->next(*this);
 		        return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Digraph* _digraph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
 		        _digraph->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Digraph& digraph, const Arc& arc) :
 		        Arc(arc), _digraph(&digraph) { }
 		      ArcIt& operator++() {
 		        _digraph->next(*this);
 		        return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Digraph* _digraph;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Digraph& digraph, const Node& node)
 		        : _digraph(&digraph) {
 		        _digraph->firstOut(*this, node);
+		      }
 		      OutArcIt(const Digraph& digraph, const Arc& arc)
 		        : Arc(arc), _digraph(&digraph) {}
 		      OutArcIt& operator++() {
@@ -262,201 +262,201 @@
 		        return *this;
+		      }
 		    };
 		    Node addNode() {
 		      Node node = Parent::addNode();
 		      notifier(Node()).add(node);
 		      return node;
+		    }
 		    Arc addArc(const Node& from, const Node& to) {
 		      Arc arc = Parent::addArc(from, to);
 		      notifier(Arc()).add(arc);
 		      return arc;
+		    }
 		    void clear() {
 		      notifier(Arc()).clear();
 		      notifier(Node()).clear();
 		      Parent::clear();
+		    }
 		    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
 		    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
 		      Parent::build(digraph, nodeRef, arcRef);
 		      notifier(Node()).build();
 		      notifier(Arc()).build();
+		    }
 		    void erase(const Node& node) {
 		      Arc arc;
 		      Parent::firstOut(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstOut(arc, node);
+		      }
 		      Parent::firstIn(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstIn(arc, node);
+		      }
 		      notifier(Node()).erase(node);
 		      Parent::erase(node);
+		    }
 		    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;
+		    }
 		    class NodeIt : public Node {
 		      const Graph* _graph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Graph& graph) : _graph(&graph) {
 		        _graph->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Graph& graph, const Node& node)
 		        : Node(node), _graph(&graph) {}
 		      NodeIt& operator++() {
 		        _graph->next(*this);
 		        return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Graph* _graph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Graph& graph) : _graph(&graph) {
 		        _graph->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Graph& graph, const Arc& arc) :
 		        Arc(arc), _graph(&graph) { }
 		      ArcIt& operator++() {
 		        _graph->next(*this);
 		        return *this;
+		      }
 		    };

lemon/bits/map_extender.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_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;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		      typename MapTraits<Map>::ReturnValue operator*() {
 		        return map[*this];
+		      }
 		      void set(const Value& value) {
 		        map.set(*this, value);
+		      }
 		    protected:
 		      Map& map;
 		    };
 		    class ConstMapIt : public Item {
 		      typedef Item Parent;
 		    public:
 		      typedef typename Map::Value Value;
 		      ConstMapIt() {}
 		      ConstMapIt(Invalid i) : Parent(i) { }
 		      explicit ConstMapIt(Map& _map) : map(_map) {
 		        map.notifier()->first(*this);
+		      }
 		      ConstMapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ConstMapIt& operator++() {
 		        map.notifier()->next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		    protected:
 		      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++() {
 		        map.graph.next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		      typename MapTraits<Map>::ReturnValue operator*() {
 		        return map[*this];
+		      }
 		      void set(const Value& value) {
 		        map.set(*this, value);
+		      }
 		    protected:
 		      Map& map;
 		    };
 		    class ConstMapIt : public Item {
 		      typedef Item Parent;
 		    public:
 		      typedef typename Map::Value Value;
 		      ConstMapIt() {}
 		      ConstMapIt(Invalid i) : Parent(i) { }
 		      explicit ConstMapIt(Map& _map) : map(_map) {
 		        map.graph.first(*this);
+		      }
 		      ConstMapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ConstMapIt& operator++() {
 		        map.graph.next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }

lemon/cbc.cc

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.
 *
 */

///\file
///\brief Implementation of the CBC MIP solver interface.

#include "cbc.h"

#include <coin/CoinModel.hpp>
#include <coin/CbcModel.hpp>
#include <coin/OsiSolverInterface.hpp>

#ifdef COIN_HAS_CLP
#include "coin/OsiClpSolverInterface.hpp"
#endif
#ifdef COIN_HAS_OSL
#include "coin/OsiOslSolverInterface.hpp"
#endif

#include "coin/CbcCutGenerator.hpp"
#include "coin/CbcHeuristicLocal.hpp"
#include "coin/CbcHeuristicGreedy.hpp"
#include "coin/CbcHeuristicFPump.hpp"
#include "coin/CbcHeuristicRINS.hpp"

#include "coin/CglGomory.hpp"
#include "coin/CglProbing.hpp"
#include "coin/CglKnapsackCover.hpp"
#include "coin/CglOddHole.hpp"
#include "coin/CglClique.hpp"
#include "coin/CglFlowCover.hpp"
#include "coin/CglMixedIntegerRounding.hpp"

#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 {
    int length = _prob->numberRows();

    std::vector<int> indices(length);
    std::vector<Value> values(length);

    length = _prob->getRow(ix, &indices[0], &values[0]);

    for (int i = 0; i < length; ++i) {
      *b = std::make_pair(indices[i], values[i]);
      ++b;
    }
  }

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

  void CbcMip::_getColCoeffs(int ix, InsertIterator b) const {
    int length = _prob->numberColumns();

    std::vector<int> indices(length);
    std::vector<Value> values(length);

    length = _prob->getColumn(ix, &indices[0], &values[0]);

    for (int i = 0; i < length; ++i) {
      *b = std::make_pair(indices[i], values[i]);
      ++b;
    }
  }

  void CbcMip::_setCoeff(int ix, int jx, Value value) {
    _prob->setElement(ix, jx, value);
  }

  CbcMip::Value CbcMip::_getCoeff(int ix, int jx) const {
    return _prob->getElement(ix, jx);
  }


  void CbcMip::_setColLowerBound(int i, Value lo) {
    LEMON_ASSERT(lo != INF, "Invalid bound");
    _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
  }

  CbcMip::Value CbcMip::_getColLowerBound(int i) const {

lemon/cbc.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.
+		 *
 		 */
 		// -*- 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;
 		    virtual Value _getSol(int i) const;
 		    virtual Value _getSolValue() const;
 		    virtual void _clear();
 		    virtual void _messageLevel(MessageLevel level);
 		    void _applyMessageLevel();
 		    int _message_level;
 		  };
+		}
 		#endif

lemon/circulation.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_CIRCULATION_H
 		#define LEMON_CIRCULATION_H
 		#include <lemon/tolerance.h>
 		#include <lemon/elevator.h>
 		#include <limits>
 		///\ingroup max_flow
 		///\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).
 		     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.
 		     If you need the opposite inequalities in the supply/demand constraints
 		     (i.e. the total demand is less than the total supply and all the demands
 		     have to be satisfied while there could be supplies that are not used),
 		     then you could easily transform the problem to the above form by reversing
 		     the direction of the arcs and taking the negative of the supply values
 		     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
 		     This algorithm either calculates a feasible circulation, or provides
 		     a \ref barrier() "barrier", which prooves that a feasible soultion
 		     cannot exist.
 		     Note that this algorithm also provides a feasible solution for the
 		     \ref min_cost_flow "minimum cost flow problem".
 		     \tparam GR The type of the digraph the algorithm runs on.
 		     \tparam LM The type of the lower bound map. The default
 		     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		     \tparam UM The type of the upper bound (capacity) map.
 		     The default map type is \c LM.
 		     \tparam SM The type of the supply map. The default map type is
 		     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
 		  */
 		#ifdef DOXYGEN
 		template< typename GR,
 		          typename LM,
 		          typename UM,
 		          typename SM,
 		          typename TR >
 		#else
 		template< typename GR,
 		          typename LM = typename GR::template ArcMap<int>,
 		          typename UM = LM,
 		          typename SM = typename GR::template NodeMap<typename UM::Value>,
 		          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
 		#endif
 		  class Circulation {
 		  public:
 		    ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
@@ -206,364 +213,364 @@
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph &_g;
 		    int _node_num;
 		    const LowerMap *_lo;
 		    const UpperMap *_up;
 		    const SupplyMap *_supply;
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tol;
 		    int _el;
 		  public:
 		    typedef Circulation Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		      static FlowMap *createFlowMap(const Digraph&) {
 		        LEMON_ASSERT(false, "FlowMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// FlowMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting FlowMap
 		    /// type.
 		    template <typename T>
 		    struct SetFlowMap
 		      : 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;
+		    }
 		    void createStructures() {
 		      _node_num = _el = countNodes(_g);
 		      if (!_flow) {
 		        _flow = Traits::createFlowMap(_g);
 		        _local_flow = true;
+		      }
 		      if (!_level) {
 		        _level = Traits::createElevator(_g, _node_num);
 		        _local_level = true;
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_g);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_local_flow) {
 		        delete _flow;
+		      }
 		      if (_local_level) {
 		        delete _level;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
+		    }
 		  public:
 		    /// Sets the lower bound map.
 		    /// Sets the lower bound map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& lowerMap(const LowerMap& map) {
 		      _lo = &map;
 		      return *this;
+		    }
 		    /// Sets the upper bound (capacity) map.
 		    /// Sets the upper bound (capacity) map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& upperMap(const UpperMap& map) {
 		      _up = &map;
 		      return *this;
+		    }
 		    /// Sets the supply map.
 		    /// Sets the supply map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& supplyMap(const SupplyMap& map) {
 		      _supply = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the flow map.
 		    ///
 		    /// Sets the flow map.
 		    /// 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.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& flowMap(FlowMap& map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \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) {
 		        (*_excess)[n] = (*_supply)[n];
+		      }
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {
 		          _flow->set(e, (*_up)[e]);
 		          (*_excess)[_g.target(e)] += (*_up)[e];
 		          (*_excess)[_g.source(e)] -= (*_up)[e];
 		        } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
 		          _flow->set(e, (*_lo)[e]);
 		          (*_excess)[_g.target(e)] += (*_lo)[e];
 		          (*_excess)[_g.source(e)] -= (*_lo)[e];
 		        } else {
 		          Value fc = -(*_excess)[_g.target(e)];
 		          _flow->set(e, fc);
 		          (*_excess)[_g.target(e)] = 0;
 		          (*_excess)[_g.source(e)] -= fc;
+		        }
+		      }
 		      _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);
+		    }
 		    ///Executes the algorithm
 		    ///This function executes the algorithm.
 		    ///
 		    ///\return \c true if a feasible circulation is found.
 		    ///
 		    ///\sa barrier()
 		    ///\sa barrierMap()
 		    bool start()
+		    {
 		      Node act;
 		      Node bact=INVALID;
 		      Node last_activated=INVALID;
 		      while((act=_level->highestActive())!=INVALID) {
 		        int actlevel=(*_level)[act];
 		        int mlevel=_node_num;
 		        Value exc=(*_excess)[act];

lemon/clp.cc

Show inline comments

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <lemon/clp.h>
#include <coin/ClpSimplex.hpp>

namespace lemon {

  ClpLp::ClpLp() {
    _prob = new ClpSimplex();
    _init_temporals();
    messageLevel(MESSAGE_NOTHING);
  }

  ClpLp::ClpLp(const ClpLp& other) {
    _prob = new ClpSimplex(*other._prob);
    rows = other.rows;
    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;
  }


  void ClpLp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
    std::map<int, Value> coeffs;

    int n = _prob->clpMatrix()->getNumCols();

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    for (int i = 0; i < n; ++i) {
      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];

      const int* it = std::lower_bound(indices + begin, indices + end, ix);
      if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
        coeffs[i] = 0.0;
      }
    }

    for (ExprIterator it = b; it != e; ++it) {
      coeffs[it->first] = it->second;
    }

    for (std::map<int, Value>::iterator it = coeffs.begin();
         it != coeffs.end(); ++it) {
      _prob->modifyCoefficient(ix, it->first, it->second);
    }
  }

  void ClpLp::_getRowCoeffs(int ix, InsertIterator b) const {
    int n = _prob->clpMatrix()->getNumCols();

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    for (int i = 0; i < n; ++i) {
      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];

      const int* it = std::lower_bound(indices + begin, indices + end, ix);
      if (it != indices + end && *it == ix) {
        *b = std::make_pair(i, elements[it - indices]);
      }
    }
  }

  void ClpLp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {

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

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	///\file
20	20	///\brief Implementation of the CBC MIP solver interface.
21	21
22	22	#include "cbc.h"
23	23
24	24	#include <coin/CoinModel.hpp>
25	25	#include <coin/CbcModel.hpp>
26	26	#include <coin/OsiSolverInterface.hpp>
27	27
28	28	#ifdef COIN_HAS_CLP
29	29	#include "coin/OsiClpSolverInterface.hpp"
30	30	#endif
31	31	#ifdef COIN_HAS_OSL
32	32	#include "coin/OsiOslSolverInterface.hpp"
33	33	#endif
34	34
35	35	#include "coin/CbcCutGenerator.hpp"
36	36	#include "coin/CbcHeuristicLocal.hpp"
37	37	#include "coin/CbcHeuristicGreedy.hpp"
38	38	#include "coin/CbcHeuristicFPump.hpp"
39	39	#include "coin/CbcHeuristicRINS.hpp"
40	40
41	41	#include "coin/CglGomory.hpp"
42	42	#include "coin/CglProbing.hpp"
43	43	#include "coin/CglKnapsackCover.hpp"
44	44	#include "coin/CglOddHole.hpp"
45	45	#include "coin/CglClique.hpp"
46	46	#include "coin/CglFlowCover.hpp"
47	47	#include "coin/CglMixedIntegerRounding.hpp"
48	48
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 {
145	157	int length = _prob->numberRows();
146	158
147	159	std::vector<int> indices(length);
148	160	std::vector<Value> values(length);
149	161
150	162	length = _prob->getRow(ix, &indices[0], &values[0]);
151	163
152	164	for (int i = 0; i < length; ++i) {
153	165	*b = std::make_pair(indices[i], values[i]);
154	166	++b;
155	167	}
156	168	}
157	169
158	170	void CbcMip::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
159	171	for (ExprIterator it = b; it != e; ++it) {
160	172	_prob->setElement(it->first, ix, it->second);
161	173	}
162	174	}
163	175
164	176	void CbcMip::_getColCoeffs(int ix, InsertIterator b) const {
165	177	int length = _prob->numberColumns();
166	178
167	179	std::vector<int> indices(length);
168	180	std::vector<Value> values(length);
169	181
170	182	length = _prob->getColumn(ix, &indices[0], &values[0]);
171	183
172	184	for (int i = 0; i < length; ++i) {
173	185	*b = std::make_pair(indices[i], values[i]);
174	186	++b;
175	187	}
176	188	}
177	189
178	190	void CbcMip::_setCoeff(int ix, int jx, Value value) {
179	191	_prob->setElement(ix, jx, value);
180	192	}
181	193
182	194	CbcMip::Value CbcMip::_getCoeff(int ix, int jx) const {
183	195	return _prob->getElement(ix, jx);
184	196	}
185	197
186	198
187	199	void CbcMip::_setColLowerBound(int i, Value lo) {
188	200	LEMON_ASSERT(lo != INF, "Invalid bound");
189	201	_prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
190	202	}
191	203
192	204	CbcMip::Value CbcMip::_getColLowerBound(int i) const {

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#include <lemon/clp.h>
20	20	#include <coin/ClpSimplex.hpp>
21	21
22	22	namespace lemon {
23	23
24	24	ClpLp::ClpLp() {
25	25	_prob = new ClpSimplex();
26	26	_init_temporals();
27	27	messageLevel(MESSAGE_NOTHING);
28	28	}
29	29
30	30	ClpLp::ClpLp(const ClpLp& other) {
31	31	_prob = new ClpSimplex(*other._prob);
32	32	rows = other.rows;
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	}
129	142
130	143
131	144	void ClpLp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
132	145	std::map<int, Value> coeffs;
133	146
134	147	int n = _prob->clpMatrix()->getNumCols();
135	148
136	149	const int* indices = _prob->clpMatrix()->getIndices();
137	150	const double* elements = _prob->clpMatrix()->getElements();
138	151
139	152	for (int i = 0; i < n; ++i) {
140	153	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
141	154	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
142	155
143	156	const int* it = std::lower_bound(indices + begin, indices + end, ix);
144	157	if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
145	158	coeffs[i] = 0.0;
146	159	}
147	160	}
148	161
149	162	for (ExprIterator it = b; it != e; ++it) {
150	163	coeffs[it->first] = it->second;
151	164	}
152	165
153	166	for (std::map<int, Value>::iterator it = coeffs.begin();
154	167	it != coeffs.end(); ++it) {
155	168	_prob->modifyCoefficient(ix, it->first, it->second);
156	169	}
157	170	}
158	171
159	172	void ClpLp::_getRowCoeffs(int ix, InsertIterator b) const {
160	173	int n = _prob->clpMatrix()->getNumCols();
161	174
162	175	const int* indices = _prob->clpMatrix()->getIndices();
163	176	const double* elements = _prob->clpMatrix()->getElements();
164	177
165	178	for (int i = 0; i < n; ++i) {
166	179	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
167	180	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
168	181
169	182	const int* it = std::lower_bound(indices + begin, indices + end, ix);
170	183	if (it != indices + end && *it == ix) {
171	184	*b = std::make_pair(i, elements[it - indices]);
172	185	}
173	186	}
174	187	}
175	188
176	189	void ClpLp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {