LEMON/LEMON-main Changeset - r799:6be1f9bd2ac0

Repositories » LEMON » LEMON-main

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

Changeset - r799:6be1f9bd2ac0

« 796:9cc6e9
« 798:58c330

834:207ba6 »
800:28c7ad »

r799:6be1f9bd2ac0

Wed, 09 Dec 2009 11:14:06

[Not Reviewed]

0 comments (0 inline)

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

Merge #62

0 67 10

merge default

3 files changed:

doc/references.bib

301

CMakeLists.txt

Makefile.am

configure.ac

doc/CMakeLists.txt

doc/Doxyfile.in

doc/Makefile.am

doc/groups.dox

133

doc/mainpage.dox

doc/min_cost_flow.dox

lemon/Makefile.am

lemon/adaptors.h

lemon/bellman_ford.h

lemon/bfs.h

lemon/bits/graph_extender.h

lemon/bits/map_extender.h

lemon/cbc.cc

lemon/cbc.h

lemon/circulation.h

lemon/clp.cc

lemon/clp.h

lemon/concepts/digraph.h

172

171

lemon/concepts/graph.h

344

324

lemon/concepts/graph_components.h

lemon/concepts/maps.h

lemon/concepts/path.h

lemon/counter.h

lemon/cplex.cc

lemon/cplex.h

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

@@ -6,64 +6,66 @@
 		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")

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

configure.ac

Show inline comments

@@ -12,128 +12,145 @@
 		                           [],
 		                           [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
@@ -62,65 +61,66 @@
 		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
@@ -194,65 +194,65 @@
 		#---------------------------------------------------------------------------
 		# 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

doc/Makefile.am

Show inline comments

@@ -37,65 +37,77 @@
 		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:

doc/groups.dox

Show inline comments

@@ -251,303 +251,375 @@
 		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.
@@ -579,115 +651,115 @@
 		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
@@ -116,38 +116,38 @@
 		\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

@@ -57,86 +57,90 @@
 			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

@@ -331,64 +331,67 @@
 		    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.
@@ -690,64 +693,66 @@
 		        : 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;
@@ -1285,64 +1290,66 @@
 		    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;
@@ -1442,64 +1449,66 @@
 		  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;
@@ -1590,64 +1599,66 @@
 		  /// \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;
@@ -1700,64 +1711,66 @@
 		  /// \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;
@@ -2203,64 +2216,67 @@
 		    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);
+		    }
@@ -2506,64 +2522,67 @@
 		        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;
@@ -2649,64 +2668,66 @@
 		      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>,
@@ -3296,64 +3317,67 @@
 		    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.

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.
@@ -270,65 +271,65 @@
 		    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;
+		    }
@@ -688,123 +689,123 @@
 		    ///
 		    /// 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>

lemon/bfs.h

Show inline comments

@@ -18,114 +18,115 @@
 		#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:
@@ -196,125 +197,125 @@
 		      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.
@@ -384,66 +385,66 @@
 		      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);
@@ -671,349 +672,336 @@
 		    ///  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)
@@ -1025,136 +1013,141 @@
 		      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);
@@ -1235,65 +1228,65 @@
 		    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,
@@ -1396,66 +1389,66 @@
 		    /// \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.
@@ -1669,84 +1662,80 @@
 		    ///   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

@@ -27,69 +27,69 @@
 		#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;
+		    }
@@ -326,73 +326,73 @@
 		  // \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;

lemon/bits/map_extender.h

Show inline comments

@@ -20,64 +20,66 @@
 		#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;
@@ -162,64 +164,66 @@
 		      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;

lemon/cbc.cc

Show inline comments

@@ -65,64 +65,76 @@
    _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);
  }

lemon/cbc.h

Show inline comments

@@ -33,64 +33,65 @@
 		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);

lemon/circulation.h

Show inline comments

@@ -43,82 +43,89 @@
 		    /// \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
@@ -270,65 +277,65 @@
 		    /// 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),
@@ -440,66 +447,66 @@
 		      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)

lemon/clp.cc

Show inline comments

@@ -49,64 +49,77 @@
    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);

lemon/clp.h

Show inline comments

@@ -46,64 +46,65 @@
 		    std::map<std::string, int> _col_names_ref;
 		    std::map<std::string, int> _row_names_ref;
 		  public:
 		    /// \e
 		    ClpLp();
 		    /// \e
 		    ClpLp(const ClpLp&);
 		    /// \e
 		    ~ClpLp();
 		    /// \e
 		    virtual ClpLp* newSolver() const;
 		    /// \e
 		    virtual ClpLp* cloneSolver() const;
 		  protected:
 		    mutable double* _primal_ray;
 		    mutable double* _dual_ray;
 		    void _init_temporals();
 		    void _clear_temporals();
 		  protected:
 		    virtual const char* _solverName() const;
 		    virtual int _addCol();
 		    virtual int _addRow();
 		    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 		    virtual void _eraseCol(int i);
 		    virtual void _eraseRow(int i);
 		    virtual void _eraseColId(int i);
 		    virtual void _eraseRowId(int i);
 		    virtual void _getColName(int col, std::string& name) const;
 		    virtual void _setColName(int col, const std::string& name);
 		    virtual int _colByName(const std::string& name) const;
 		    virtual void _getRowName(int row, std::string& name) const;
 		    virtual void _setRowName(int row, const std::string& name);
 		    virtual int _rowByName(const std::string& name) const;
 		    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getRowCoeffs(int i, InsertIterator b) const;
 		    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getColCoeffs(int i, InsertIterator b) const;
 		    virtual void _setCoeff(int row, int col, Value value);
 		    virtual Value _getCoeff(int row, int col) const;
 		    virtual void _setColLowerBound(int i, Value value);
 		    virtual Value _getColLowerBound(int i) const;
 		    virtual void _setColUpperBound(int i, Value value);
 		    virtual Value _getColUpperBound(int i) const;
 		    virtual void _setRowLowerBound(int i, Value value);
 		    virtual Value _getRowLowerBound(int i) const;
 		    virtual void _setRowUpperBound(int i, Value value);

lemon/concepts/digraph.h

Show inline comments

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

lemon/concepts/graph.h

Show inline comments

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

lemon/concepts/graph_components.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup graph_concepts
 		///\file
-		///\brief The concept of graph components.
+		///\brief The concepts of graph components.
 		#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 		#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 		#include <lemon/core.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/bits/alteration_notifier.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
 		    ///
 		    /// This class describes the concept of \c Node, \c Arc and \c Edge
 		    /// subtypes of digraph and graph types.
 		    ///
 		    /// \note This class is a template class so that we can use it to
 		    /// create graph skeleton classes. The reason for this is that \c Node
 		    /// and \c Arc (or \c Edge) types should \e not derive from the same
 		    /// base class. For \c Node you should instantiate it with character
 		    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
 		#ifndef DOXYGEN
 		    template <char sel = '0'>
 		#endif
 		    class GraphItem {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
 		      /// \warning The default constructor is not required to set
 		      /// the item to some well-defined value. So you should consider it
@@ -63,65 +63,65 @@
 		      ///
 		      /// Constructor for conversion from \c INVALID.
 		      /// It initializes the item to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphItem(Invalid) {}
 		      /// \brief Assignment operator.
 		      ///
 		      /// Assignment operator for the item.
 		      GraphItem& operator=(const GraphItem&) { return *this; }
 		      /// \brief Assignment operator for INVALID.
 		      ///
 		      /// This operator makes the item invalid.
 		      GraphItem& operator=(Invalid) { return *this; }
 		      /// \brief Equality operator.
 		      ///
 		      /// Equality operator.
 		      bool operator==(const GraphItem&) const { return false; }
 		      /// \brief Inequality operator.
 		      ///
 		      /// Inequality operator.
 		      bool operator!=(const GraphItem&) const { return false; }
 		      /// \brief Ordering operator.
 		      ///
 		      /// This operator defines an ordering of the items.
 		      /// It makes possible to use graph item types as key types in
 		      /// associative containers (e.g. \c std::map).
 		      ///
-		      /// \note This operator only have to define some strict ordering of
+		      /// \note This operator only has to define some strict ordering of
 		      /// the items; this order has nothing to do with the iteration
 		      /// ordering of the items.
 		      bool operator<(const GraphItem&) const { return false; }
 		      template<typename _GraphItem>
 		      struct Constraints {
 		        void constraints() {
 		          _GraphItem i1;
 		          i1=INVALID;
 		          _GraphItem i2 = i1;
 		          _GraphItem i3 = INVALID;
 		          i1 = i2 = i3;
 		          bool b;
 		          b = (ia == ib) && (ia != ib);
 		          b = (ia == INVALID) && (ib != INVALID);
 		          b = (ia < ib);
+		        }
 		        const _GraphItem &ia;
 		        const _GraphItem &ib;
 		      };
 		    };
 		    /// \brief Base skeleton class for directed graphs.
 		    ///
 		    /// This class describes the base interface of directed graph types.
 		    /// All digraph %concepts have to conform to this class.
 		    /// It just provides types for nodes and arcs and functions
 		    /// to get the source and the target nodes of arcs.
 		    class BaseDigraphComponent {

lemon/concepts/maps.h

Show inline comments

@@ -153,64 +153,65 @@
 		    class ReferenceMap : public ReadWriteMap<K,T>
+		    {
 		    public:
 		      /// Tag for reference maps.
 		      typedef True ReferenceMapTag;
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// \brief The value type of the map.
 		      /// (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// The reference type of the map.
 		      typedef R Reference;
 		      /// The const reference type of the map.
 		      typedef CR ConstReference;
 		    public:
 		      /// Returns a reference to the value associated with the given key.
 		      Reference operator[](const Key &) {
 		        return *static_cast<Value *>(0);
+		      }
 		      /// Returns a const reference to the value associated with the given key.
 		      ConstReference operator[](const Key &) const {
 		        return *static_cast<Value *>(0);
+		      }
 		      /// Sets the value associated with the given key.
 		      void set(const Key &k,const Value &t) { operator[](k)=t; }
 		      template<typename _ReferenceMap>
 		      struct Constraints {
-		        void constraints() {
+		        typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
 		        constraints() {
 		          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
 		          ref = m[key];
 		          m[key] = val;
 		          m[key] = ref;
 		          m[key] = cref;
 		          own_ref = m[own_key];
 		          m[own_key] = own_val;
 		          m[own_key] = own_ref;
 		          m[own_key] = own_cref;
 		          m[key] = m[own_key];
 		          m[own_key] = m[key];
+		        }
 		        const Key& key;
 		        Value& val;
 		        Reference ref;
 		        ConstReference cref;
 		        const typename _ReferenceMap::Key& own_key;
 		        typename _ReferenceMap::Value& own_val;
 		        typename _ReferenceMap::Reference own_ref;
 		        typename _ReferenceMap::ConstReference own_cref;
 		        _ReferenceMap& m;
 		      };
 		    };
 		    // @}
 		  } //namespace concepts
 		} //namespace lemon
 		#endif

lemon/concepts/path.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup concept
 		///\file
-		///\brief Classes for representing paths in digraphs.
+		///\brief The concept of paths
 		///
 		#ifndef LEMON_CONCEPTS_PATH_H
 		#define LEMON_CONCEPTS_PATH_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief A skeleton structure for representing directed paths in
 		    /// a digraph.
 		    ///
 		    /// A skeleton structure for representing directed paths in a
 		    /// digraph.
 		    /// In a sense, a path can be treated as a list of arcs.
 		    /// LEMON path types just store this list. As a consequence, they cannot
 		    /// enumerate the nodes on the path directly and a zero length path
 		    /// cannot store its source node.
 		    ///
 		    /// The arcs of a path should be stored in the order of their directions,
 		    /// i.e. the target node of each arc should be the same as the source
 		    /// node of the next arc. This consistency could be checked using
 		    /// \ref checkPath().
 		    /// The source and target nodes of a (consistent) path can be obtained
 		    /// using \ref pathSource() and \ref pathTarget().
 		    ///
 		    /// A path can be constructed from another path of any type using the
 		    /// copy constructor or the assignment operator.
 		    ///
 		    /// \tparam GR The digraph type in which the path is.
 		    ///
 		    /// In a sense, the path can be treated as a list of arcs. The
 		    /// lemon path type stores just this list. As a consequence it
 		    /// cannot enumerate the nodes in the path and the zero length
 		    /// paths cannot store the source.
 		    ///
 		    template <typename GR>
 		    class Path {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef GR Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
 		      class ArcIt;
 		      /// \brief Default constructor
 		      Path() {}
 		      /// \brief Template constructor
+		      /// \brief Template copy constructor
 		      template <typename CPath>
 		      Path(const CPath& cpath) {}
 		      /// \brief Template assigment
+		      /// \brief Template assigment operator
 		      template <typename CPath>
 		      Path& operator=(const CPath& cpath) {
 		        ignore_unused_variable_warning(cpath);
 		        return *this;
+		      }
-		      /// Length of the path ie. the number of arcs in the path.
+		      /// Length of the path, i.e. the number of arcs on the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// Resets the path to an empty path.
 		      void clear() {}
-		      /// \brief LEMON style iterator for path arcs
+		      /// \brief LEMON style iterator for enumerating the arcs of a path.
 		      ///
-		      /// This class is used to iterate on the arcs of the paths.
+		      /// LEMON style iterator class for enumerating the arcs of a path.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
-		        /// Constructor for first arc
+		        /// Sets the iterator to the first arc of the given path
 		        ArcIt(const Path &) {}
 		        /// Conversion to Arc
+		        /// Conversion to \c Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          Path<Digraph> pc;
 		          _Path p, pp(pc);
 		          int l = p.length();
 		          int e = p.empty();
 		          p.clear();
 		          p = pc;
 		          typename _Path::ArcIt id, ii(INVALID), i(p);
 		          ++i;
 		          typename Digraph::Arc ed = i;
 		          e = (i == ii);
 		          e = (i != ii);
@@ -163,145 +172,139 @@
 		      template <typename _Digraph, typename _Path>
 		      struct PathDumperConstraints<
 		        _Digraph, _Path,
 		        typename enable_if<typename _Path::RevPathTag, void>::type
 		      > {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::RevArcIt id, i(p);
 		          ++i;
 		          typename _Digraph::Arc ed = i;
 		          e = (i == INVALID);
 		          e = (i != INVALID);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ed);
+		        }
 		        _Path& p;
 		      };
+		    }
 		    /// \brief A skeleton structure for path dumpers.
 		    ///
 		    /// A skeleton structure for path dumpers. The path dumpers are
 		    /// the generalization of the paths. The path dumpers can
 		    /// enumerate the arcs of the path wheter in forward or in
 		    /// backward order.  In most time these classes are not used
 		    /// directly rather it used to assign a dumped class to a real
-		    /// path type.
+		    /// the generalization of the paths, they can enumerate the arcs
 		    /// of the path either in forward or in backward order.
 		    /// These classes are typically not used directly, they are rather
 		    /// used to be assigned to a real path type.
 		    ///
 		    /// The main purpose of this concept is that the shortest path
 		    /// algorithms can enumerate easily the arcs in reverse order.
 		    /// If we would like to give back a real path from these
 		    /// algorithms then we should create a temporarly path object. In
 		    /// LEMON such algorithms gives back a path dumper what can
-		    /// assigned to a real path and the dumpers can be implemented as
+		    /// algorithms can enumerate the arcs easily in reverse order.
 		    /// In LEMON, such algorithms give back a (reverse) path dumper that
 		    /// can be assigned to a real path. The dumpers can be implemented as
 		    /// an adaptor class to the predecessor map.
 		    ///
 		    /// \tparam GR The digraph type in which the path is.
 		    ///
 		    /// The paths can be constructed from any path type by a
 		    /// template constructor or a template assignment operator.
 		    template <typename GR>
 		    class PathDumper {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef GR Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
-		      /// Length of the path ie. the number of arcs in the path.
+		      /// Length of the path, i.e. the number of arcs on the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// \brief Forward or reverse dumping
 		      ///
 		      /// If the RevPathTag is defined and true then reverse dumping
 		      /// is provided in the path dumper. In this case instead of the
 		      /// ArcIt the RevArcIt iterator should be implemented in the
 		      /// dumper.
 		      /// If this tag is defined to be \c True, then reverse dumping
 		      /// is provided in the path dumper. In this case, \c RevArcIt
 		      /// iterator should be implemented instead of \c ArcIt iterator.
 		      typedef False RevPathTag;
-		      /// \brief LEMON style iterator for path arcs
+		      /// \brief LEMON style iterator for enumerating the arcs of a path.
 		      ///
-		      /// This class is used to iterate on the arcs of the paths.
+		      /// LEMON style iterator class for enumerating the arcs of a path.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
-		        /// Constructor for first arc
+		        /// Sets the iterator to the first arc of the given path
 		        ArcIt(const PathDumper&) {}
 		        /// Conversion to Arc
+		        /// Conversion to \c Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
-		      /// \brief LEMON style iterator for path arcs
+		      /// \brief LEMON style iterator for enumerating the arcs of a path
 		      /// in reverse direction.
 		      ///
 		      /// This class is used to iterate on the arcs of the paths in
 		      /// reverse direction.
 		      /// LEMON style iterator class for enumerating the arcs of a path
 		      /// in reverse direction.
 		      class RevArcIt {
 		      public:
 		        /// Default constructor
 		        RevArcIt() {}
 		        /// Invalid constructor
 		        RevArcIt(Invalid) {}
-		        /// Constructor for first arc
+		        /// Sets the iterator to the last arc of the given path
 		        RevArcIt(const PathDumper &) {}
 		        /// Conversion to Arc
+		        /// Conversion to \c Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        RevArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const RevArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const RevArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const RevArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          function_requires<_path_bits::
 		            PathDumperConstraints<Digraph, _Path> >();
+		        }
 		      };
 		    };
 		    ///@}
+		  }
 		} // namespace lemon
 		#endif

lemon/counter.h

Show inline comments

@@ -183,65 +183,65 @@
 		    /// Constructor.
 		    Counter(const char *title,std::ostream &os=std::cerr)
 		      : _title(title), _os(os), count(0) {}
 		    /// Destructor. Prints the given title and the value of the counter.
 		    ~Counter() {
 		      _os << _title << count <<std::endl;
+		    }
 		    ///\e
 		    Counter &operator++() { count++; return *this;}
 		    ///\e
 		    int operator++(int) { return count++;}
 		    ///\e
 		    Counter &operator--() { count--; return *this;}
 		    ///\e
 		    int operator--(int) { return count--;}
 		    ///\e
 		    Counter &operator+=(int c) { count+=c; return *this;}
 		    ///\e
 		    Counter &operator-=(int c) { count-=c; return *this;}
 		    /// Resets the counter to the given value.
 		    /// Resets the counter to the given value.
 		    /// \note This function does not reset the values of
 		    /// \ref SubCounter "SubCounter"s but it resets \ref NoSubCounter
 		    /// "NoSubCounter"s along with the main counter.
 		    void reset(int c=0) {count=c;}
 		    /// Returns the value of the counter.
 		    operator int() {return count;}
 		  };
 		  /// 'Do nothing' version of Counter.
-		  /// This class can be used in the same way as \ref Counter however it
+		  /// This class can be used in the same way as \ref Counter, but it
 		  /// does not count at all and does not print report on destruction.
 		  ///
 		  /// Replacing a \ref Counter with a \ref NoCounter makes it possible
 		  /// to turn off all counting and reporting (SubCounters should also
 		  /// be replaced with NoSubCounters), so it does not affect the
 		  /// efficiency of the program at all.
 		  ///
 		  /// \sa Counter
 		  class NoCounter
+		  {
 		  public:
 		    typedef _NoSubCounter<NoCounter> SubCounter;
 		    typedef _NoSubCounter<NoCounter> NoSubCounter;
 		    NoCounter() {}
 		    NoCounter(std::string,std::ostream &) {}
 		    NoCounter(const char *,std::ostream &) {}
 		    NoCounter(std::string) {}
 		    NoCounter(const char *) {}
 		    NoCounter &operator++() { return *this; }
 		    int operator++(int) { return 0; }
 		    NoCounter &operator--() { return *this; }
 		    int operator--(int) { return 0; }
 		    NoCounter &operator+=(int) { return *this;}
 		    NoCounter &operator-=(int) { return *this;}
 		    void reset(int) {}
 		    void reset() {}
 		    operator int() {return 0;}
 		  };
 		  ///@}
+		}

lemon/cplex.cc

Show inline comments

@@ -82,64 +82,97 @@
 		    messageLevel(MESSAGE_NOTHING);
+		  }
 		  CplexBase::CplexBase(const CplexBase& cplex)
 		    : LpBase() {
 		    int status;
 		    _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status);
 		    rows = cplex.rows;
 		    cols = cplex.cols;
 		    messageLevel(MESSAGE_NOTHING);
+		  }
 		  CplexBase::~CplexBase() {
 		    CPXfreeprob(cplexEnv(),&_prob);
+		  }
 		  int CplexBase::_addCol() {
 		    int i = CPXgetnumcols(cplexEnv(), _prob);
 		    double lb = -INF, ub = INF;
 		    CPXnewcols(cplexEnv(), _prob, 1, 0, &lb, &ub, 0, 0);
 		    return i;
+		  }
 		  int CplexBase::_addRow() {
 		    int i = CPXgetnumrows(cplexEnv(), _prob);
 		    const double ub = INF;
 		    const char s = 'L';
 		    CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
 		    return i;
+		  }
 		  int CplexBase::_addRow(Value lb, ExprIterator b,
 		                         ExprIterator e, Value ub) {
 		    int i = CPXgetnumrows(cplexEnv(), _prob);
 		    if (lb == -INF) {
 		      const char s = 'L';
 		      CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
 		    } else if (ub == INF) {
 		      const char s = 'G';
 		      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
 		    } else if (lb == ub){
 		      const char s = 'E';
 		      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
 		    } else {
 		      const char s = 'R';
 		      double len = ub - lb;
 		      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
+		    }
 		    std::vector<int> indices;
 		    std::vector<int> rowlist;
 		    std::vector<Value> values;
 		    for(ExprIterator it=b; it!=e; ++it) {
 		      indices.push_back(it->first);
 		      values.push_back(it->second);
 		      rowlist.push_back(i);
+		    }
 		    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
 		                   &rowlist.front(), &indices.front(), &values.front());
 		    return i;
+		  }
 		  void CplexBase::_eraseCol(int i) {
 		    CPXdelcols(cplexEnv(), _prob, i, i);
+		  }
 		  void CplexBase::_eraseRow(int i) {
 		    CPXdelrows(cplexEnv(), _prob, i, i);
+		  }
 		  void CplexBase::_eraseColId(int i) {
 		    cols.eraseIndex(i);
 		    cols.shiftIndices(i);
+		  }
 		  void CplexBase::_eraseRowId(int i) {
 		    rows.eraseIndex(i);
 		    rows.shiftIndices(i);
+		  }
 		  void CplexBase::_getColName(int col, std::string &name) const {
 		    int size;
 		    CPXgetcolname(cplexEnv(), _prob, 0, 0, 0, &size, col, col);
 		    if (size == 0) {
 		      name.clear();
 		      return;
+		    }
 		    size *= -1;
 		    std::vector<char> buf(size);
 		    char *cname;
 		    int tmp;
 		    CPXgetcolname(cplexEnv(), _prob, &cname, &buf.front(), size,
 		                  &tmp, col, col);

lemon/cplex.h

Show inline comments

@@ -64,64 +64,65 @@
 		    CplexEnv();
 		    /// Shallow copy constructor
 		    CplexEnv(const CplexEnv&);
 		    /// Shallow assignement
 		    CplexEnv& operator=(const CplexEnv&);
 		    /// Destructor
 		    virtual ~CplexEnv();
 		  protected:
 		    cpxenv* cplexEnv() { return _env; }
 		    const cpxenv* cplexEnv() const { return _env; }
 		  };
 		  /// \brief Base interface for the CPLEX LP and MIP solver
 		  ///
 		  /// This class implements the common interface of the CPLEX LP and
 		  /// MIP solvers.
 		  /// \ingroup lp_group
 		  class CplexBase : virtual public LpBase {
 		  protected:
 		    CplexEnv _env;
 		    cpxlp* _prob;
 		    CplexBase();
 		    CplexBase(const CplexEnv&);
 		    CplexBase(const CplexBase &);
 		    virtual ~CplexBase();
 		    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;
 		  private:
 		    void _set_row_bounds(int i, Value lb, Value ub);

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

...	...	@@ -65,64 +65,76 @@
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	}

...	...	@@ -49,64 +49,77 @@
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);