LEMON/LEMON-main Changeset - r831:cc9e0c15d747

Repositories » LEMON » LEMON-main

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

Changeset - r831:cc9e0c15d747

« 829:7762ca
« 830:75c97c

842:c2ff0a »
833:d2bc45 »

r831:cc9e0c15d747

Fri, 12 Feb 2010 22:24:26

[Not Reviewed]

0 comments (0 inline)

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

Merge

0 16 1

merge default

2 files changed with 389 insertions and 102 deletions:

doc/images/planar.eps

181

INSTALL

doc/CMakeLists.txt

doc/Makefile.am

lemon/bellman_ford.h

lemon/bfs.h

lemon/capacity_scaling.h

lemon/circulation.h

lemon/cost_scaling.h

lemon/dfs.h

lemon/dijkstra.h

lemon/hartmann_orlin.h

lemon/howard.h

lemon/karp.h

lemon/min_cost_arborescence.h

lemon/planarity.h

lemon/preflow.h

↑ Collapse diff ↑

doc/images/planar.eps

Show inline comments

 		%!PS-Adobe-2.0 EPSF-2.0
 		%%Creator: LEMON, graphToEps()
 		%%CreationDate: Fri Oct 19 18:32:32 2007
 		%%BoundingBox: 0 0 596 842
 		%%DocumentPaperSizes: a4
 		%%EndComments
 		/lb { setlinewidth setrgbcolor newpath moveto
 2 roll 1 index 1 index curveto stroke } bind def
 		/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
 		/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
 		/sq { newpath 2 index 1 index add 2 index 2 index add moveto
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 index 1 index add 2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/di { newpath 2 index 1 index add 2 index moveto
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 index             2 index 2 index sub lineto
 		      closepath pop pop pop} bind def
 		/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
 		     setrgbcolor 1.1 div c fill
 		   } bind def
 		/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
 		     setrgbcolor 1.1 div sq fill
 		   } bind def
 		/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
 		     setrgbcolor 1.1 div di fill
 		   } bind def
 		/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
 		  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
 		  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
 index 5 index 5 index c fill
 		  setrgbcolor 1.1 div c fill
 		  } bind def
 		/nmale {
 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
 		  newpath 5 index 5 index moveto
 index 4 index 1 mul 1.5 mul add
 index 5 index 3 sqrt 1.5 mul mul add
 index 1 index lineto
 index 1 index 7 index sub moveto
 index 1 index lineto
 		  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
 		  stroke
 index 5 index 5 index c fill
 		  setrgbcolor 1.1 div c fill
 		  } bind def
 		/arrl 1 def
 		/arrw 0.3 def
 		/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
 		/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
 		       /w exch def /len exch def
 		       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
 		       len w sub arrl sub dx dy lrl
 		       arrw dy dx neg lrl
 		       dx arrl w add mul dy w 2 div arrw add mul sub
 		       dy arrl w add mul dx w 2 div arrw add mul add rlineto
 		       dx arrl w add mul neg dy w 2 div arrw add mul sub
 		       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
 		       arrw dy dx neg lrl
 		       len w sub arrl sub neg dx dy lrl
 		       closepath fill } bind def
 		/cshow { 2 index 2 index moveto dup stringwidth pop
 		         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
 		gsave
 138.307 translate
 .7843 dup scale
 rotate
 .608112 -43.6081 translate
 		%Edges:
 		gsave
 31 9.5 30.5 10 30 0 0 0 0.091217 lb
 31 5.5 34.5 2 38 0 0 0 0.091217 lb
 31 25.5 16 42 1 0 0 0 0.091217 lb
 40 23 20.5 43 1 0 0 0 0.091217 lb
 40 22.5 20.5 42 1 0 0 0 0.091217 lb
 40 2.5 40.5 2 41 0 0 0 0.091217 lb
 25 10.5 24.5 8 24 0 0 0 0.091217 lb
 25 12 27 11 29 0 0 0 0.091217 lb
 4 2.5 3 2 2 0 0 0 0.091217 lb
 4 4.5 3 6 2 0 0 0 0.091217 lb
 25 7 24.5 8 24 0 0 0 0.091217 lb
 25 6 24.5 6 24 0 0 0 0.091217 lb
 2 33.5 2 33 2 0 0 0 0.091217 lb
 2 35 2 36 2 0 0 0 0.091217 lb
 8 16 9 26 10 0 0 0 0.091217 lb
 8 6 10.5 6 13 0 0 0 0.091217 lb
 8 6 7.5 6 7 0 0 0 0.091217 lb
 10 27.5 8.5 29 7 0 0 0 0.091217 lb
 10 27.5 9 29 8 0 0 0 0.091217 lb
 30 10.5 29.5 11 29 0 0 0 0.091217 lb
 24 7 23.5 6 23 0 0 0 0.091217 lb
 24 8 24.5 8 25 0 0 0 0.091217 lb
 2 32.5 2 32 2 0 0 0 0.091217 lb
 7 17.5 7 6 7 0 0 0 0.091217 lb
 2 1.5 22 1 42 0 0 0 0.091217 lb
 2 3.5 2 5 2 0 0 0 0.091217 lb
 15 13.5 14.5 6 14 0 0 0 0.091217 lb
 15 21 15.5 21 16 0 0 0 0.091217 lb
 42 0.5 42.5 0 43 0 0 0 0.091217 lb
 42 1.5 41.5 2 41 0 0 0 0.091217 lb
 15 6 15.5 6 16 0 0 0 0.091217 lb
 15 6 14.5 6 14 0 0 0 0.091217 lb
 1 22 0.5 1 0 0 0 0 0.091217 lb
 2 18.5 2 6 2 0 0 0 0.091217 lb
 2 31.5 2 32 2 0 0 0 0.091217 lb
 24 6 23.5 6 23 0 0 0 0.091217 lb
 16 6 16.5 6 17 0 0 0 0.091217 lb
 23 6 20 6 17 0 0 0 0.091217 lb
 2 5.5 2 5 2 0 0 0 0.091217 lb
 2 6 4.5 6 7 0 0 0 0.091217 lb
 43 0.5 21.5 1 0 0 0 0 0.091217 lb
 1 19.5 1.5 38 2 0 0 0 0.091217 lb
 1 1 0.5 1 0 0 0 0 0.091217 lb
 38 5.5 31.5 9 25 0 0 0 0.091217 lb
 13 15.5 13 6 13 0 0 0 0.091217 lb
 13 15.5 13.5 6 14 0 0 0 0.091217 lb
 25 8.5 25 9 25 0 0 0 0.091217 lb
 29 24.5 15.5 38 2 0 0 0 0.091217 lb
 17 11.5 18 17 19 0 0 0 0.091217 lb
 23 26.5 12.5 37 2 0 0 0 0.091217 lb
 23 18.5 19.5 21 16 0 0 0 0.091217 lb
 2 36.5 2 37 2 0 0 0 0.091217 lb
 2 32.5 5 29 8 0 0 0 0.091217 lb
 13 6 13.5 6 14 0 0 0 0.091217 lb
 2 37.5 2 38 2 0 0 0 0.091217 lb
 16 19 17.5 17 19 0 0 0 0.091217 lb
 		grestore
 		%Nodes:
 		gsave
 8 0.304556 1 1 1 nc
 41 0.304556 1 1 1 nc
 7 0.304556 1 1 1 nc
 2 0.304556 1 1 1 nc
 19 0.304556 1 1 1 nc
 16 0.304556 1 1 1 nc
 0 0.304556 1 1 1 nc
 25 0.304556 1 1 1 nc
 14 0.304556 1 1 1 nc
 1 0.304556 1 1 1 nc
 2 0.304556 1 1 1 nc
 2 0.304556 1 1 1 nc
 13 0.304556 1 1 1 nc
 2 0.304556 1 1 1 nc
 23 0.304556 1 1 1 nc
 17 0.304556 1 1 1 nc
 29 0.304556 1 1 1 nc
 25 0.304556 1 1 1 nc
 2 0.304556 1 1 1 nc
 13 0.304556 1 1 1 nc
 38 0.304556 1 1 1 nc
 1 0.304556 1 1 1 nc
 43 0.304556 1 1 1 nc
 2 0.304556 1 1 1 nc
 23 0.304556 1 1 1 nc
 16 0.304556 1 1 1 nc
 24 0.304556 1 1 1 nc
 2 0.304556 1 1 1 nc
 1 0.304556 1 1 1 nc
 15 0.304556 1 1 1 nc
 42 0.304556 1 1 1 nc
 15 0.304556 1 1 1 nc
 2 0.304556 1 1 1 nc
 7 0.304556 1 1 1 nc
 2 0.304556 1 1 1 nc
 24 0.304556 1 1 1 nc
 30 0.304556 1 1 1 nc
 10 0.304556 1 1 1 nc
 8 0.304556 1 1 1 nc
 2 0.304556 1 1 1 nc
 25 0.304556 1 1 1 nc
 4 0.304556 1 1 1 nc
 25 0.304556 1 1 1 nc
 40 0.304556 1 1 1 nc
 31 0.304556 1 1 1 nc
 		grestore
 		grestore
 		showpage

INSTALL

Show inline comments

@@ -80,96 +80,118 @@
 		   Build the programs in the tools subdirectory (default).
 		--disable-tools
 		   Do not build the programs in the tools subdirectory.
 		--with-glpk[=PREFIX]
 		   Enable GLPK support (default). You should specify the prefix too if
 		   you installed GLPK to some non-standard location (e.g. your home
 		   directory). If it is not found, GLPK support will be disabled.
 		--with-glpk-includedir=DIR
 		   The directory where the GLPK header files are located. This is only
 		   useful when the GLPK headers and libraries are not under the same
 		   prefix (which is unlikely).
 		--with-glpk-libdir=DIR
 		   The directory where the GLPK libraries are located. This is only
 		   useful when the GLPK headers and libraries are not under the same
 		   prefix (which is unlikely).
 		--without-glpk
 		   Disable GLPK support.
 		--with-cplex[=PREFIX]
 		   Enable CPLEX support (default). You should specify the prefix too
 		   if you installed CPLEX to some non-standard location
 		   (e.g. /opt/ilog/cplex75). If it is not found, CPLEX support will be
 		   disabled.
 		--with-cplex-includedir=DIR
 		   The directory where the CPLEX header files are located. This is
 		   only useful when the CPLEX headers and libraries are not under the
 		   same prefix (e.g.  /usr/local/cplex/cplex75/include).
 		--with-cplex-libdir=DIR
 		   The directory where the CPLEX libraries are located. This is only
 		   useful when the CPLEX headers and libraries are not under the same
 		   prefix (e.g.
 		   /usr/local/cplex/cplex75/lib/i86_linux2_glibc2.2_gcc3.0/static_pic_mt).
 		--without-cplex
 		   Disable CPLEX support.
 		--with-soplex[=PREFIX]
 		   Enable SoPlex support (default). You should specify the prefix too if
 		   you installed SoPlex to some non-standard location (e.g. your home
 		   directory). If it is not found, SoPlex support will be disabled.
 		--with-soplex-includedir=DIR
 		   The directory where the SoPlex header files are located. This is only
 		   useful when the SoPlex headers and libraries are not under the same
 		   prefix (which is unlikely).
 		--with-soplex-libdir=DIR
 		   The directory where the SoPlex libraries are located. This is only
 		   useful when the SoPlex headers and libraries are not under the same
 		   prefix (which is unlikely).
 		--without-soplex
 		   Disable SoPlex support.
 		--with-coin[=PREFIX]
 		   Enable support for COIN-OR solvers (CLP and CBC). You should
 		   specify the prefix too. (by default, COIN-OR tools install
 		   themselves to the source code directory). This command enables the
 		   solvers that are actually found.
 		--with-coin-includedir=DIR
 		   The directory where the COIN-OR header files are located. This is
 		   only useful when the COIN-OR headers and libraries are not under
 		   the same prefix (which is unlikely).
 		--with-coin-libdir=DIR
 		   The directory where the COIN-OR libraries are located. This is only
 		   useful when the COIN-OR headers and libraries are not under the
 		   same prefix (which is unlikely).
 		--without-coin
 		   Disable COIN-OR support.
 		Makefile Variables
 		==================
 		Some Makefile variables are reserved by the GNU Coding Standards for
 		the use of the "user" - the person building the package. For instance,
 		CXX and CXXFLAGS are such variables, and have the same meaning as
 		explained in the previous section. These variables can be set on the
 		command line when invoking `make' like this:
 		`make [VARIABLE=VALUE]...'
 		WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
 		to hold several compiler flags related to warnings. Its default value
 		can be overridden when invoking `make'. For example to disable all
 		warning flags use `make WARNINGCXXFLAGS='.
 		In order to turn off a single flag from the default set of warning
 		flags, you can use the CXXFLAGS variable, since this is passed after
 		WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
 		used by default when g++ is detected) you can use
 		`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.

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 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/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.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/Makefile.am

Show inline comments

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

lemon/bellman_ford.h

Show inline comments

@@ -78,192 +78,197 @@
 		    static Value plus(const Value& left, const Value& right) {
 		      if (left == infinity() || right == infinity()) return infinity();
 		      return left + right;
+		    }
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  /// \brief Default traits class of BellmanFord class.
 		  ///
 		  /// Default traits class of BellmanFord class.
 		  /// \param GR The type of the digraph.
 		  /// \param LEN The type of the length map.
 		  template<typename GR, typename LEN>
 		  struct BellmanFordDefaultTraits {
 		    /// The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc lengths.
 		    ///
 		    /// The type of the map that stores the arc lengths.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths.
 		    typedef typename LEN::Value Value;
 		    /// \brief Operation traits for Bellman-Ford algorithm.
 		    ///
 		    /// It defines the used operations and the infinity value for the
 		    /// given \c Value type.
 		    /// \see BellmanFordDefaultOperationTraits
 		    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 		    /// \brief The type of the map that stores the last arcs of the
 		    /// shortest paths.
 		    ///
 		    /// The type of the map that stores the last
 		    /// arcs of the shortest paths.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
 		    /// \brief Instantiates a \c PredMap.
 		    ///
 		    /// This function instantiates a \ref PredMap.
 		    /// \param g is the digraph to which we would like to define the
 		    /// \ref PredMap.
 		    static PredMap *createPredMap(const GR& g) {
 		      return new PredMap(g);
+		    }
 		    /// \brief The type of the map that stores the distances of the nodes.
 		    ///
 		    /// The type of the map that stores the distances of the nodes.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
 		    /// \brief Instantiates a \c DistMap.
 		    ///
 		    /// This function instantiates a \ref DistMap.
 		    /// \param g is the digraph to which we would like to define the
 		    /// \ref DistMap.
 		    static DistMap *createDistMap(const GR& g) {
 		      return new DistMap(g);
+		    }
 		  };
 		  /// \brief %BellmanFord algorithm class.
 		  ///
 		  /// \ingroup shortest_path
 		  /// This class provides an efficient implementation of the Bellman-Ford
 		  /// algorithm. The maximum time complexity of the algorithm is
 		  /// <tt>O(ne)</tt>.
 		  ///
 		  /// The Bellman-Ford algorithm solves the single-source shortest path
 		  /// problem when the arcs can have negative lengths, but the digraph
 		  /// should not contain directed cycles with negative total length.
 		  /// If all arc costs are non-negative, consider to use the Dijkstra
 		  /// algorithm instead, since it is more efficient.
 		  ///
 		  /// The arc lengths are passed to the algorithm using a
 		  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
 		  /// kind of length. The type of the length values is determined by the
 		  /// \ref concepts::ReadMap::Value "Value" type of the length map.
 		  ///
 		  /// There is also a \ref bellmanFord() "function-type interface" for the
 		  /// Bellman-Ford 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.
 		  /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
 		  /// the lengths of the arcs. The default map type is
 		  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref BellmanFordDefaultTraits
 		  /// "BellmanFordDefaultTraits<GR, LEN>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename LEN=typename GR::template ArcMap<int>,
 		            typename TR=BellmanFordDefaultTraits<GR,LEN> >
 		#endif
 		  class BellmanFord {
 		  public:
 		    ///The type of the underlying digraph.
 		    typedef typename TR::Digraph Digraph;
 		    /// \brief The type of the arc lengths.
 		    typedef typename TR::LengthMap::Value Value;
 		    /// \brief The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    /// \brief The type of the map that stores the last
 		    /// 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;
 		    /// The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///\brief The \ref BellmanFordDefaultOperationTraits
 		    /// "operation traits class" of the algorithm.
 		    typedef typename TR::OperationTraits OperationTraits;
 		    ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    // Pointer to the underlying digraph.
 		    const Digraph *_gr;
 		    // Pointer to the length map
 		    const LengthMap *_length;
 		    // Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    // Indicates if _pred is locally allocated (true) or not.
 		    bool _local_pred;
 		    // Pointer to the map of distances.
 		    DistMap *_dist;
 		    // Indicates if _dist is locally allocated (true) or not.
 		    bool _local_dist;
 		    typedef typename Digraph::template NodeMap<bool> MaskMap;
 		    MaskMap *_mask;
 		    std::vector<Node> _process;
 		    // Creates the maps if necessary.
 		    void create_maps() {
 		      if(!_pred) {
 			_local_pred = true;
 			_pred = Traits::createPredMap(*_gr);
+		      }
 		      if(!_dist) {
 			_local_dist = true;
 			_dist = Traits::createDistMap(*_gr);
+		      }
 		      if(!_mask) {
 		        _mask = new MaskMap(*_gr);
+		      }
+		    }
 		  public :
 		    typedef BellmanFord Create;
 		    /// \name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph&) {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c PredMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c PredMap type.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap
@@ -840,192 +845,195 @@
 		    ///
 		    /// The type of the map that stores the last arcs of the shortest paths.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
 		    /// \brief Instantiates a \c PredMap.
 		    ///
 		    /// This function instantiates a \ref PredMap.
 		    /// \param g is the digraph to which we would like to define the
 		    /// \ref PredMap.
 		    static PredMap *createPredMap(const GR &g) {
 		      return new PredMap(g);
+		    }
 		    /// \brief The type of the map that stores the distances of the nodes.
 		    ///
 		    /// The type of the map that stores the distances of the nodes.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<Value> DistMap;
 		    /// \brief Instantiates a \c DistMap.
 		    ///
 		    /// This function instantiates a \ref DistMap.
 		    /// \param g is the digraph to which we would like to define the
 		    /// \ref DistMap.
 		    static DistMap *createDistMap(const GR &g) {
 		      return new DistMap(g);
+		    }
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
 		    ///It must meet the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \brief Default traits class used by BellmanFordWizard.
 		  ///
 		  /// Default traits class used by BellmanFordWizard.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  template <typename GR, typename LEN>
 		  class BellmanFordWizardBase
 		    : public BellmanFordWizardDefaultTraits<GR, LEN> {
 		    typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
 		  protected:
 		    // Type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    // Pointer to the underlying digraph.
 		    void *_graph;
 		    // Pointer to the length map
 		    void *_length;
 		    // 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.
 		    void *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, it initiates
 		    /// all of the attributes to default values \c 0.
 		    BellmanFordWizardBase() :
 		      _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires two parameters,
 		    /// others are initiated to \c 0.
 		    /// \param gr The digraph the algorithm runs on.
 		    /// \param len The length map.
 		    BellmanFordWizardBase(const GR& gr,
 					  const LEN& len) :
 		      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
 		      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
 		      _pred(0), _dist(0), _path(0), _di(0) {}
 		  };
 		  /// \brief Auxiliary class for the function-type interface of the
 		  /// \ref BellmanFord "Bellman-Ford" algorithm.
 		  ///
 		  /// This auxiliary class is created to implement the
 		  /// \ref bellmanFord() "function-type interface" of the
 		  /// \ref BellmanFord "Bellman-Ford" algorithm.
 		  /// It does not have own \ref run() method, it uses the
 		  /// functions and features of the plain \ref BellmanFord.
 		  ///
 		  /// This class should only be used through the \ref bellmanFord()
 		  /// function, which makes it easier to use the algorithm.
 		  ///
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm.
 		  template<class TR>
 		  class BellmanFordWizard : public TR {
 		    typedef TR Base;
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt ArcIt;
 		    typedef typename TR::LengthMap LengthMap;
 		    typedef typename LengthMap::Value Value;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    BellmanFordWizard() : TR() {}
 		    /// \brief Constructor that requires parameters.
 		    ///
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param gr The digraph the algorithm runs on.
 		    /// \param len The length map.
 		    BellmanFordWizard(const Digraph& gr, const LengthMap& len)
 		      : TR(gr, len) {}
 		    /// \brief Copy constructor
 		    BellmanFordWizard(const TR &b) : TR(b) {}
 		    ~BellmanFordWizard() {}
 		    /// \brief Runs the Bellman-Ford algorithm from the given source node.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the given source
 		    /// node in order to compute the shortest path to each node.
 		    void run(Node s) {
 		      BellmanFord<Digraph,LengthMap,TR>
 			bf(*reinterpret_cast<const Digraph*>(Base::_graph),
 		           *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      bf.run(s);
+		    }
 		    /// \brief Runs the Bellman-Ford algorithm to find the shortest path
 		    /// between \c s and \c t.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from node \c s
 		    /// in order to compute the shortest path to node \c t.
 		    /// Actually, it computes the shortest path to each node, but using
 		    /// this function you can retrieve the distance and the shortest path
 		    /// for a single target node easier.
 		    ///
 		    /// \return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t) {
 		      BellmanFord<Digraph,LengthMap,TR>
 		        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
 		           *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      bf.run(s);
 		      if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
 		      if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
 		      return bf.reached(t);
+		    }
 		    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-templ-param "Named parameter" for setting
 		    /// the predecessor map.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BellmanFordWizard<SetPredMapBase<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-templ-param "Named parameter" for setting

lemon/bfs.h

Show inline comments

@@ -28,192 +28,197 @@
 		#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 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 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 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 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.
 		  ///\tparam TR The traits class that defines various types used by the
 		  ///algorithm. By default, it is \ref BfsDefaultTraits
 		  ///"BfsDefaultTraits<GR>".
 		  ///In most cases, this parameter should not be set directly,
 		  ///consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=BfsDefaultTraits<GR> >
 		#endif
 		  class Bfs {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::Node> _queue;
 		    int _queue_head,_queue_tail,_queue_next_dist;
 		    int _curr_dist;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Bfs() {}
 		  public:
 		    typedef Bfs Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
@@ -864,192 +869,195 @@
 		      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 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 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 conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by BfsWizard
 		  /// 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, 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.
 		  ///
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm.
 		  template<class TR>
 		  class BfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    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;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::ReachedMap ReachedMap;
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    BfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param g The digraph the algorithm runs on.
 		    BfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
 		    BfsWizard(const TR &b) : TR(b) {}
 		    ~BfsWizard() {}
 		    ///Runs BFS algorithm from the given source node.
 		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    void run(Node s)
+		    {
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if (s!=INVALID)
 		        alg.run(s);
 		      else
 		        alg.run();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)
+		    {
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      alg.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
 		      if (Base::_di)
 		        *Base::_di = alg.dist(t);
 		      return alg.reached(t);
+		    }
 		    ///Runs BFS algorithm to visit all nodes in the digraph.
 		    ///This method runs BFS algorithm in order to 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; };
@@ -1202,197 +1210,197 @@
 		    void reach(const Node& node) {}
 		    /// \brief Called when a node is processed.
 		    ///
 		    /// This function is called when a node is processed.
 		    void process(const Node& node) {}
 		    /// \brief Called when an arc reaches a new node.
 		    ///
 		    /// This function is called when the BFS finds an arc whose target node
 		    /// is not reached yet.
 		    void discover(const Arc& arc) {}
 		    /// \brief Called when an arc is examined but its target node is
 		    /// already discovered.
 		    ///
 		    /// This function is called when an arc is examined but its target node is
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		  };
 		#else
 		  template <typename GR>
 		  struct BfsVisitor {
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    void start(const Node&) {}
 		    void reach(const Node&) {}
 		    void process(const Node&) {}
 		    void discover(const Arc&) {}
 		    void examine(const Arc&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 		        Arc arc;
 		        Node node;
 		        visitor.start(node);
 		        visitor.reach(node);
 		        visitor.process(node);
 		        visitor.discover(arc);
 		        visitor.examine(arc);
+		      }
 		      _Visitor& visitor;
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of BfsVisit class.
 		  ///
 		  /// Default traits class of BfsVisit class.
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  template<class GR>
 		  struct BfsVisitDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that indicates which nodes are reached.
 		    ///
 		    /// The type of the map that indicates which nodes are reached.
 		    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a ReachedMap.
 		    ///
 		    /// This function instantiates a ReachedMap.
 		    /// \param digraph is the digraph, to which
 		    /// we would like to define the ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &digraph) {
 		      return new ReachedMap(digraph);
+		    }
 		  };
 		  /// \ingroup search
 		  ///
 		  /// \brief BFS algorithm class with visitor interface.
 		  ///
 		  /// This class provides an efficient implementation of the BFS algorithm
 		  /// with visitor interface.
 		  ///
 		  /// The BfsVisit class provides an alternative interface to the Bfs
 		  /// class. It works with callback mechanism, the BfsVisit object calls
 		  /// the member functions of the \c Visitor class on every BFS event.
 		  ///
 		  /// This interface of the BFS algorithm should be used in special cases
 		  /// when extra actions have to be performed in connection with certain
 		  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
 		  /// instead.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// The default type is \ref ListDigraph.
 		  /// The value of GR is not used directly by \ref BfsVisit,
 		  /// it is only passed to \ref BfsVisitDefaultTraits.
 		  /// \tparam VS The Visitor type that is used by the algorithm.
 		  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
 		  /// does not observe the BFS events. If you want to observe the BFS
 		  /// events, you should implement your own visitor class.
 		  /// \tparam TR Traits class to set various data types used by the
 		  /// algorithm. The default traits class is
 		  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
 		  /// See \ref BfsVisitDefaultTraits for the documentation of
-		  /// a BFS visit traits class.
+		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref BfsVisitDefaultTraits
 		  /// "BfsVisitDefaultTraits<GR>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename VS, typename TR>
 		#else
 		  template <typename GR = ListDigraph,
 		            typename VS = BfsVisitor<GR>,
 		            typename TR = BfsVisitDefaultTraits<GR> >
 		#endif
 		  class BfsVisit {
 		  public:
 		    ///The traits class.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The visitor type used by the algorithm.
 		    typedef VS Visitor;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename Traits::ReachedMap ReachedMap;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *_digraph;
 		    //Pointer to the visitor object.
 		    Visitor *_visitor;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Node> _list;
 		    int _list_front, _list_back;
 		    //Creates the maps if necessary.
 		    void create_maps() {
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*_digraph);
+		      }
+		    }
 		  protected:
 		    BfsVisit() {}
 		  public:
 		    typedef BfsVisit Create;
 		    /// \name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public BfsVisit< Digraph, Visitor,
 		                                            SetReachedMapTraits<T> > {
 		      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param visitor The visitor object of the algorithm.
 		    BfsVisit(const Digraph& digraph, Visitor& visitor)
 		      : _digraph(&digraph), _visitor(&visitor),
 		        _reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ~BfsVisit() {
 		      if(local_reached) delete _reached;
+		    }

lemon/capacity_scaling.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_CAPACITY_SCALING_H
 		#define LEMON_CAPACITY_SCALING_H
 		/// \ingroup min_cost_flow_algs
 		///
 		/// \file
 		/// \brief Capacity Scaling algorithm for finding a minimum cost flow.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/bin_heap.h>
 		namespace lemon {
 		  /// \brief Default traits class of CapacityScaling algorithm.
 		  ///
 		  /// Default traits class of CapacityScaling algorithm.
 		  /// \tparam GR Digraph type.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values. By default it is \c int.
 		  /// \tparam C The number type used for costs and potentials.
 		  /// By default it is the same as \c V.
 		  template <typename GR, typename V = int, typename C = V>
 		  struct CapacityScalingDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef V Value;
 		    /// The type of the arc costs
 		    typedef C Cost;
 		    /// \brief The type of the heap used for internal Dijkstra computations.
 		    ///
 		    /// The type of the heap used for internal Dijkstra computations.
 		    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
 		    /// its priority type must be \c Cost and its cross reference type
 		    /// must be \ref RangeMap "RangeMap<int>".
 		    typedef BinHeap<Cost, RangeMap<int> > Heap;
 		  };
 		  /// \addtogroup min_cost_flow_algs
 		  /// @{
 		  /// \brief Implementation of the Capacity Scaling algorithm for
 		  /// finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref CapacityScaling implements the capacity scaling version
 		  /// of the successive shortest path algorithm for finding a
 		  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
 		  /// \ref edmondskarp72theoretical. It is an efficient dual
 		  /// solution method.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
 		  /// specified, then default values will be used.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default it is \c int.
+		  /// and supply values in the algorithm. By default, it is \c int.
 		  /// \tparam C The number type used for costs and potentials in the
 		  /// algorithm. By default it is the same as \c V.
+		  /// algorithm. By default, it is the same as \c V.
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
 		  /// "CapacityScalingDefaultTraits<GR, V, C>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		  ///
 		  /// \warning Both number types must be signed and all input data must
 		  /// be integer.
 		  /// \warning This algorithm does not support negative costs for such
 		  /// arcs that have infinite upper bound.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V, typename C, typename TR>
 		#else
 		  template < typename GR, typename V = int, typename C = V,
 		             typename TR = CapacityScalingDefaultTraits<GR, V, C> >
 		#endif
 		  class CapacityScaling
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef typename TR::Value Value;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
 		    /// The type of the heap used for internal Dijkstra computations
 		    typedef typename TR::Heap Heap;
 		    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost and infinite
 		      /// upper bound. It means that the objective function is unbounded
 		      /// on that arc, however, note that it could actually be bounded
 		      /// over the feasible flows, but this algroithm cannot handle
 		      /// these cases.
 		      UNBOUNDED
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<char> BoolVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _res_arc_num;
 		    int _root;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_idf;
 		    IntArcMap _arc_idb;
 		    IntVector _first_out;
 		    BoolVector _forward;
 		    IntVector _source;
 		    IntVector _target;
 		    IntVector _reverse;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    CostVector _cost;
 		    ValueVector _supply;
 		    ValueVector _res_cap;
 		    CostVector _pi;
 		    ValueVector _excess;
 		    IntVector _excess_nodes;
 		    IntVector _deficit_nodes;
 		    Value _delta;
 		    int _factor;
 		    IntVector _pred;

lemon/circulation.h

Show inline comments

@@ -80,192 +80,197 @@
 		    /// \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, LinkedElevator
 		#ifdef DOXYGEN
 		    typedef lemon::Elevator<GR, GR::Node> Elevator;
 		#else
 		    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
 		#endif
 		    /// \brief Instantiates an Elevator.
 		    ///
 		    /// This function instantiates an \ref Elevator.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
 		    ///
 		    /// The tolerance used by the algorithm to handle inexact computation.
 		    typedef lemon::Tolerance<Value> Tolerance;
 		  };
 		  /**
 		     \brief Push-relabel algorithm for the network circulation problem.
 		     \ingroup max_flow
 		     This class implements a push-relabel algorithm for the \e network
 		     \e circulation problem.
 		     It is to find a feasible circulation when lower and upper bounds
 		     are given for the flow values on the arcs and lower bounds are
 		     given for the difference between the outgoing and incoming flow
 		     at the nodes.
 		     The exact formulation of this problem is the following.
 		     Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$
 		     \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and
 		     upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$
 		     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
 		     denotes the signed supply values of the nodes.
 		     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		     \f$-sup(u)\f$ demand.
 		     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
 		     solution of the following problem.
 		     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
 		     \geq sup(u) \quad \forall u\in V, \f]
 		     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
 		     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		     zero or negative in order to have a feasible solution (since the sum
 		     of the expressions on the left-hand side of the inequalities is zero).
 		     It means that the total demand must be greater or equal to the total
 		     supply and all the supplies have to be carried out from the supply nodes,
 		     but there could be demands that are not satisfied.
 		     If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		     constraints have to be satisfied with equality, i.e. all demands
 		     have to be satisfied and all supplies have to be used.
 		     If you need the opposite inequalities in the supply/demand constraints
 		     (i.e. the total demand is less than the total supply and all the demands
 		     have to be satisfied while there could be supplies that are not used),
 		     then you could easily transform the problem to the above form by reversing
 		     the direction of the arcs and taking the negative of the supply values
 		     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
 		     This algorithm either calculates a feasible circulation, or provides
 		     a \ref barrier() "barrier", which prooves that a feasible soultion
 		     cannot exist.
 		     Note that this algorithm also provides a feasible solution for the
 		     \ref min_cost_flow "minimum cost flow problem".
 		     \tparam GR The type of the digraph the algorithm runs on.
 		     \tparam LM The type of the lower bound map. The default
 		     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		     \tparam UM The type of the upper bound (capacity) map.
 		     The default map type is \c LM.
 		     \tparam SM The type of the supply map. The default map type is
 		     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
 		     \tparam TR The traits class that defines various types used by the
 		     algorithm. By default, it is \ref CirculationDefaultTraits
 		     "CirculationDefaultTraits<GR, LM, UM, SM>".
 		     In most cases, this parameter should not be set directly,
 		     consider to use the named template parameters instead.
 		  */
 		#ifdef DOXYGEN
 		template< typename GR,
 		          typename LM,
 		          typename UM,
 		          typename SM,
 		          typename TR >
 		#else
 		template< typename GR,
 		          typename LM = typename GR::template ArcMap<int>,
 		          typename UM = LM,
 		          typename SM = typename GR::template NodeMap<typename UM::Value>,
 		          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
 		#endif
 		  class Circulation {
 		  public:
 		    ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The type of the flow and supply values.
 		    typedef typename Traits::Value Value;
 		    ///The type of the lower bound map.
 		    typedef typename Traits::LowerMap LowerMap;
 		    ///The type of the upper bound (capacity) map.
 		    typedef typename Traits::UpperMap UpperMap;
 		    ///The type of the supply map.
 		    typedef typename Traits::SupplyMap SupplyMap;
 		    ///The type of the flow map.
 		    typedef typename Traits::FlowMap FlowMap;
 		    ///The type of the elevator.
 		    typedef typename Traits::Elevator Elevator;
 		    ///The type of the tolerance.
 		    typedef typename Traits::Tolerance Tolerance;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph &_g;
 		    int _node_num;
 		    const LowerMap *_lo;
 		    const UpperMap *_up;
 		    const SupplyMap *_supply;
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tol;
 		    int _el;
 		  public:
 		    typedef Circulation Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		      static FlowMap *createFlowMap(const Digraph&) {
 		        LEMON_ASSERT(false, "FlowMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// FlowMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting FlowMap
 		    /// type.
 		    template <typename T>
 		    struct SetFlowMap
 		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                           SetFlowMapTraits<T> > {
 		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                          SetFlowMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph&, int) {
 		        LEMON_ASSERT(false, "Elevator is not initialized");

lemon/cost_scaling.h

Show inline comments

@@ -11,226 +11,230 @@
 		 * 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_COST_SCALING_H
 		#define LEMON_COST_SCALING_H
 		/// \ingroup min_cost_flow_algs
 		/// \file
 		/// \brief Cost scaling algorithm for finding a minimum cost flow.
 		#include <vector>
 		#include <deque>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/math.h>
 		#include <lemon/static_graph.h>
 		#include <lemon/circulation.h>
 		#include <lemon/bellman_ford.h>
 		namespace lemon {
 		  /// \brief Default traits class of CostScaling algorithm.
 		  ///
 		  /// Default traits class of CostScaling algorithm.
 		  /// \tparam GR Digraph type.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values. By default it is \c int.
 		  /// \tparam C The number type used for costs and potentials.
 		  /// By default it is the same as \c V.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V = int, typename C = V>
 		#else
 		  template < typename GR, typename V = int, typename C = V,
 		             bool integer = std::numeric_limits<C>::is_integer >
 		#endif
 		  struct CostScalingDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef V Value;
 		    /// The type of the arc costs
 		    typedef C Cost;
 		    /// \brief The large cost type used for internal computations
 		    ///
 		    /// The large cost type used for internal computations.
 		    /// It is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Cost must be convertible to \c LargeCost.
 		    typedef double LargeCost;
 		  };
 		  // Default traits class for integer cost types
 		  template <typename GR, typename V, typename C>
 		  struct CostScalingDefaultTraits<GR, V, C, true>
+		  {
 		    typedef GR Digraph;
 		    typedef V Value;
 		    typedef C Cost;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeCost;
 		#else
 		    typedef long LargeCost;
 		#endif
 		  };
 		  /// \addtogroup min_cost_flow_algs
 		  /// @{
 		  /// \brief Implementation of the Cost Scaling algorithm for
 		  /// finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref CostScaling implements a cost scaling algorithm that performs
 		  /// push/augment and relabel operations for finding a \ref min_cost_flow
 		  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
 		  /// \ref goldberg97efficient, \ref bunnagel98efficient.
 		  /// It is a highly efficient primal-dual solution method, which
 		  /// can be viewed as the generalization of the \ref Preflow
 		  /// "preflow push-relabel" algorithm for the maximum flow problem.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
 		  /// specified, then default values will be used.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default it is \c int.
+		  /// and supply values in the algorithm. By default, it is \c int.
 		  /// \tparam C The number type used for costs and potentials in the
 		  /// algorithm. By default it is the same as \c V.
+		  /// algorithm. By default, it is the same as \c V.
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref CostScalingDefaultTraits
 		  /// "CostScalingDefaultTraits<GR, V, C>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		  ///
 		  /// \warning Both number types must be signed and all input data must
 		  /// be integer.
 		  /// \warning This algorithm does not support negative costs for such
 		  /// arcs that have infinite upper bound.
 		  ///
 		  /// \note %CostScaling provides three different internal methods,
 		  /// from which the most efficient one is used by default.
 		  /// For more information, see \ref Method.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V, typename C, typename TR>
 		#else
 		  template < typename GR, typename V = int, typename C = V,
 		             typename TR = CostScalingDefaultTraits<GR, V, C> >
 		#endif
 		  class CostScaling
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef typename TR::Value Value;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
 		    /// \brief The large cost type
 		    ///
 		    /// The large cost type used for internal computations.
 		    /// Using the \ref CostScalingDefaultTraits "default traits class",
 		    /// it is \c long \c long if the \c Cost type is integer,
 		    /// By default, it is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeCost LargeCost;
 		    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost and infinite
 		      /// upper bound. It means that the objective function is unbounded
 		      /// on that arc, however, note that it could actually be bounded
 		      /// over the feasible flows, but this algroithm cannot handle
 		      /// these cases.
 		      UNBOUNDED
 		    };
 		    /// \brief Constants for selecting the internal method.
 		    ///
 		    /// Enum type containing constants for selecting the internal method
 		    /// for the \ref run() function.
 		    ///
 		    /// \ref CostScaling provides three internal methods that differ mainly
 		    /// in their base operations, which are used in conjunction with the
 		    /// relabel operation.
 		    /// By default, the so called \ref PARTIAL_AUGMENT
 		    /// "Partial Augment-Relabel" method is used, which proved to be
 		    /// the most efficient and the most robust on various test inputs.
 		    /// However, the other methods can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum Method {
 		      /// Local push operations are used, i.e. flow is moved only on one
 		      /// admissible arc at once.
 		      PUSH,
 		      /// Augment operations are used, i.e. flow is moved on admissible
 		      /// paths from a node with excess to a node with deficit.
 		      AUGMENT,
 		      /// Partial augment operations are used, i.e. flow is moved on
 		      /// admissible paths started from a node with excess, but the
 		      /// lengths of these paths are limited. This method can be viewed
 		      /// as a combined version of the previous two operations.
 		      PARTIAL_AUGMENT
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<char> BoolVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<LargeCost> LargeCostVector;
 		  private:
 		    template <typename KT, typename VT>
 		    class StaticVectorMap {
 		    public:
 		      typedef KT Key;
 		      typedef VT Value;
 		      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
 		      const Value& operator[](const Key& key) const {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      Value& operator[](const Key& key) {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      void set(const Key& key, const Value& val) {
 		        _v[StaticDigraph::id(key)] = val;
+		      }
 		    private:
 		      std::vector<Value>& _v;
 		    };
 		    typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
 		    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
 		  private:
 		    // Data related to the underlying digraph

lemon/dfs.h

Show inline comments

@@ -28,192 +28,197 @@
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///Default traits class of Dfs class.
 		  ///Default traits class of Dfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsDefaultTraits
+		  {
 		    ///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 %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///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 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 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 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);
+		    }
 		  };
 		  ///%DFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %DFS algorithm.
 		  ///
 		  ///There is also a \ref dfs() "function-type interface" for the DFS
 		  ///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.
 		  ///\tparam TR The traits class that defines various types used by the
 		  ///algorithm. By default, it is \ref DfsDefaultTraits
 		  ///"DfsDefaultTraits<GR>".
 		  ///In most cases, this parameter should not be set directly,
 		  ///consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=DfsDefaultTraits<GR> >
 		#endif
 		  class Dfs {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::OutArcIt> _stack;
 		    int _stack_head;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Dfs() {}
 		  public:
 		    typedef Dfs 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");
@@ -794,192 +799,195 @@
 		      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 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 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 DFS paths.
 		    ///The type of the DFS paths.
 		    ///It must conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by DfsWizard
 		  /// Default traits class used by DfsWizard.
 		  /// \tparam GR The type of the digraph.
 		  template<class GR>
 		  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
+		  {
 		    typedef DfsWizardDefaultTraits<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 DFS 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, it initiates
 		    /// all of the attributes to \c 0.
 		    DfsWizardBase() : _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.
 		    DfsWizardBase(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 DFS algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
 		  /// It does not have own \ref run(Node) "run()" method, it uses the
 		  /// functions and features of the plain \ref Dfs.
 		  ///
 		  /// This class should only be used through the \ref dfs() function,
 		  /// which makes it easier to use the algorithm.
 		  ///
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm.
 		  template<class TR>
 		  class DfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    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;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::ReachedMap ReachedMap;
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    DfsWizard() : 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.
 		    DfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
 		    DfsWizard(const TR &b) : TR(b) {}
 		    ~DfsWizard() {}
 		    ///Runs DFS algorithm from the given source node.
 		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS path to each node.
 		    void run(Node s)
+		    {
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if (s!=INVALID)
 		        alg.run(s);
 		      else
 		        alg.run();
+		    }
 		    ///Finds the DFS path between \c s and \c t.
 		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS 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)
+		    {
 		      Dfs<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 DFS algorithm to visit all nodes in the digraph.
 		    ///This method runs DFS 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; };
@@ -1144,197 +1152,197 @@
 		    ///
 		    /// This function is called when an arc is examined but its target node is
 		    /// already discovered.
 		    void examine(const Arc& arc) {}
 		    /// \brief Called when the DFS steps back from a node.
 		    ///
 		    /// This function is called when the DFS steps back from a node.
 		    void leave(const Node& node) {}
 		    /// \brief Called when the DFS steps back on an arc.
 		    ///
 		    /// This function is called when the DFS steps back on an arc.
 		    void backtrack(const Arc& arc) {}
 		  };
 		#else
 		  template <typename GR>
 		  struct DfsVisitor {
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Node Node;
 		    void start(const Node&) {}
 		    void stop(const Node&) {}
 		    void reach(const Node&) {}
 		    void discover(const Arc&) {}
 		    void examine(const Arc&) {}
 		    void leave(const Node&) {}
 		    void backtrack(const Arc&) {}
 		    template <typename _Visitor>
 		    struct Constraints {
 		      void constraints() {
 		        Arc arc;
 		        Node node;
 		        visitor.start(node);
 		        visitor.stop(arc);
 		        visitor.reach(node);
 		        visitor.discover(arc);
 		        visitor.examine(arc);
 		        visitor.leave(node);
 		        visitor.backtrack(arc);
+		      }
 		      _Visitor& visitor;
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of DfsVisit class.
 		  ///
 		  /// Default traits class of DfsVisit class.
 		  /// \tparam _Digraph The type of the digraph the algorithm runs on.
 		  template<class GR>
 		  struct DfsVisitDefaultTraits {
 		    /// \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 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 DFS algorithm class with visitor interface.
 		  ///
 		  /// This class provides an efficient implementation of the DFS algorithm
 		  /// with visitor interface.
 		  ///
 		  /// The DfsVisit class provides an alternative interface to the Dfs
 		  /// class. It works with callback mechanism, the DfsVisit object calls
 		  /// the member functions of the \c Visitor class on every DFS event.
 		  ///
 		  /// This interface of the DFS algorithm should be used in special cases
 		  /// when extra actions have to be performed in connection with certain
 		  /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
 		  /// 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 DfsVisit,
 		  /// it is only passed to \ref DfsVisitDefaultTraits.
 		  /// \tparam VS The Visitor type that is used by the algorithm.
 		  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
 		  /// does not observe the DFS events. If you want to observe the DFS
 		  /// events, you should implement your own visitor class.
 		  /// \tparam TR Traits class to set various data types used by the
 		  /// algorithm. The default traits class is
 		  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
 		  /// See \ref DfsVisitDefaultTraits for the documentation of
-		  /// a DFS visit traits class.
+		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
 		  /// "DfsVisitDefaultTraits<GR>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename VS, typename TR>
 		#else
 		  template <typename GR = ListDigraph,
 		            typename VS = DfsVisitor<GR>,
 		            typename TR = DfsVisitDefaultTraits<GR> >
 		#endif
 		  class DfsVisit {
 		  public:
 		    ///The traits class.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The visitor type used by the algorithm.
 		    typedef VS Visitor;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename Traits::ReachedMap ReachedMap;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *_digraph;
 		    //Pointer to the visitor object.
 		    Visitor *_visitor;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    std::vector<typename Digraph::Arc> _stack;
 		    int _stack_head;
 		    //Creates the maps if necessary.
 		    void create_maps() {
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*_digraph);
+		      }
+		    }
 		  protected:
 		    DfsVisit() {}
 		  public:
 		    typedef DfsVisit Create;
 		    /// \name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// ReachedMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public DfsVisit< Digraph, Visitor,
 		                                            SetReachedMapTraits<T> > {
 		      typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
 		    };
 		    ///@}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param visitor The visitor object of the algorithm.
 		    DfsVisit(const Digraph& digraph, Visitor& visitor)
 		      : _digraph(&digraph), _visitor(&visitor),
 		        _reached(0), local_reached(false) {}
 		    /// \brief Destructor.
 		    ~DfsVisit() {
 		      if(local_reached) delete _reached;
+		    }

lemon/dijkstra.h

Show inline comments

@@ -99,192 +99,197 @@
 		    ///The heap type used by the %Dijkstra algorithm.
 		    ///The heap type used by the Dijkstra algorithm.
 		    ///
 		    ///\sa BinHeap
 		    ///\sa Dijkstra
 		    typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap;
 		    ///Instantiates a \c Heap.
 		    ///This function instantiates a \ref Heap.
 		    static Heap *createHeap(HeapCrossRef& r)
+		    {
 		      return new Heap(r);
+		    }
 		    ///\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 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 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 stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename LEN::Value> 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);
+		    }
 		  };
 		  ///%Dijkstra algorithm class.
 		  /// \ingroup shortest_path
 		  ///This class provides an efficient implementation of the %Dijkstra algorithm.
 		  ///
 		  ///The %Dijkstra algorithm solves the single-source shortest path problem
 		  ///when all arc lengths are non-negative. If there are negative lengths,
 		  ///the BellmanFord algorithm should be used instead.
 		  ///
 		  ///The arc lengths are passed to the algorithm using a
 		  ///\ref concepts::ReadMap "ReadMap",
 		  ///so it is easy to change it to any kind of length.
 		  ///The type of the length is determined by the
 		  ///\ref concepts::ReadMap::Value "Value" of the length map.
 		  ///It is also possible to change the underlying priority heap.
 		  ///
 		  ///There is also a \ref dijkstra() "function-type interface" for the
 		  ///%Dijkstra 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.
 		  ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
 		  ///the lengths of the arcs.
 		  ///It is read once for each arc, so the map may involve in
 		  ///relatively time consuming process to compute the arc lengths if
 		  ///it is necessary. The default map type is \ref
 		  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  ///\tparam TR The traits class that defines various types used by the
 		  ///algorithm. By default, it is \ref DijkstraDefaultTraits
 		  ///"DijkstraDefaultTraits<GR, LEN>".
 		  ///In most cases, this parameter should not be set directly,
 		  ///consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename LEN=typename GR::template ArcMap<int>,
 		            typename TR=DijkstraDefaultTraits<GR,LEN> >
 		#endif
 		  class Dijkstra {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///The type of the arc lengths.
 		    typedef typename TR::Value Value;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The cross reference type used for the current heap.
 		    typedef typename TR::HeapCrossRef HeapCrossRef;
 		    ///The heap type used by the algorithm.
 		    typedef typename TR::Heap Heap;
 		    ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
 		    ///of the algorithm.
 		    typedef typename TR::OperationTraits OperationTraits;
 		    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the length map.
 		    const LengthMap *_length;
 		    //Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    //Pointer to the heap cross references.
 		    HeapCrossRef *_heap_cross_ref;
 		    //Indicates if _heap_cross_ref is locally allocated (true) or not.
 		    bool local_heap_cross_ref;
 		    //Pointer to the heap.
 		    Heap *_heap;
 		    //Indicates if _heap is locally allocated (true) or not.
 		    bool local_heap;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
 		      if (!_heap_cross_ref) {
 		        local_heap_cross_ref = true;
 		        _heap_cross_ref = Traits::createHeapCrossRef(*G);
+		      }
 		      if (!_heap) {
 		        local_heap = true;
 		        _heap = Traits::createHeap(*_heap_cross_ref);
+		      }
+		    }
 		  public:
@@ -999,192 +1004,195 @@
 		    ///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 stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename LEN::Value> 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 conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by DijkstraWizard
 		  /// Default traits class used by DijkstraWizard.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  template<typename GR, typename LEN>
 		  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
+		  {
 		    typedef DijkstraWizardDefaultTraits<GR,LEN> 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 length map.
 		    void *_length;
 		    //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.
 		    void *_di;
 		  public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to \c 0.
 		    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
 		                           _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires two parameters,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param l The length map.
 		    DijkstraWizardBase(const GR &g,const LEN &l) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))),
 		      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
 		  /// It does not have own \ref run(Node) "run()" method, it uses the
 		  /// functions and features of the plain \ref Dijkstra.
 		  ///
 		  /// This class should only be used through the \ref dijkstra() function,
 		  /// which makes it easier to use the algorithm.
 		  ///
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm.
 		  template<class TR>
 		  class DijkstraWizard : public TR
+		  {
 		    typedef TR Base;
 		    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;
 		    typedef typename TR::LengthMap LengthMap;
 		    typedef typename LengthMap::Value Value;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    typedef typename TR::Path Path;
 		    typedef typename TR::Heap Heap;
 		  public:
 		    /// Constructor.
 		    DijkstraWizard() : 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.
 		    /// \param l The length map.
 		    DijkstraWizard(const Digraph &g, const LengthMap &l) :
 		      TR(g,l) {}
 		    ///Copy constructor
 		    DijkstraWizard(const TR &b) : TR(b) {}
 		    ~DijkstraWizard() {}
 		    ///Runs Dijkstra algorithm from the given source node.
 		    ///This method runs %Dijkstra algorithm from the given source node
 		    ///in order to compute the shortest path to each node.
 		    void run(Node s)
+		    {
 		      Dijkstra<Digraph,LengthMap,TR>
 		        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
 		             *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if (Base::_pred)
 		        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_processed)
 		        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      dijk.run(s);
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs the %Dijkstra 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)
+		    {
 		      Dijkstra<Digraph,LengthMap,TR>
 		        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
 		             *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if (Base::_pred)
 		        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_processed)
 		        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      dijk.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
 		      if (Base::_di)
 		        *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
 		      return dijk.reached(t);
+		    }
 		    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-templ-param "Named parameter" for setting
 		    ///the predecessor map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the predecessor arcs of the nodes.
 		    template<class T>

lemon/hartmann_orlin.h

Show inline comments

@@ -13,215 +13,219 @@
 		 * 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_HARTMANN_ORLIN_H
 		#define LEMON_HARTMANN_ORLIN_H
 		/// \ingroup min_mean_cycle
 		///
 		/// \file
 		/// \brief Hartmann-Orlin's algorithm for finding a minimum mean cycle.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
 		  /// \brief Default traits class of HartmannOrlin algorithm.
 		  ///
 		  /// Default traits class of HartmannOrlin algorithm.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		#endif
 		  struct HartmannOrlinDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// \brief The large value type used for internal computations
 		    ///
 		    /// The large value type used for internal computations.
 		    /// It is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// The tolerance type used for internal computations
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addFront() function.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  // Default traits class for integer value types
 		  template <typename GR, typename LEN>
 		  struct HartmannOrlinDefaultTraits<GR, LEN, true>
+		  {
 		    typedef GR Digraph;
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeValue;
 		#else
 		    typedef long LargeValue;
 		#endif
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \addtogroup min_mean_cycle
 		  /// @{
 		  /// \brief Implementation of the Hartmann-Orlin algorithm for finding
 		  /// a minimum mean cycle.
 		  ///
 		  /// This class implements the Hartmann-Orlin algorithm for finding
 		  /// a directed cycle of minimum mean length (cost) in a digraph
 		  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
 		  /// It is an improved version of \ref Karp "Karp"'s original algorithm,
 		  /// it applies an efficient early termination scheme.
 		  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam LEN The type of the length map. The default
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits
 		  /// "HartmannOrlinDefaultTraits<GR, LEN>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = HartmannOrlinDefaultTraits<GR, LEN> >
 		#endif
 		  class HartmannOrlin
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map
 		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename TR::Value Value;
 		    /// \brief The large value type
 		    ///
 		    /// The large value type used for internal computations.
 		    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
 		    /// it is \c long \c long if the \c Value type is integer,
 		    /// By default, it is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeValue LargeValue;
 		    /// The tolerance type
 		    typedef typename TR::Tolerance Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
 		    /// it is \ref lemon::Path "Path<Digraph>".
 		    typedef typename TR::Path Path;
 		    /// The \ref HartmannOrlinDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    // Data sturcture for path data
 		    struct PathData
+		    {
 		      LargeValue dist;
 		      Arc pred;
 		      PathData(LargeValue d, Arc p = INVALID) :
 		        dist(d), pred(p) {}
 		    };
 		    typedef typename Digraph::template NodeMap<std::vector<PathData> >
 		      PathDataNodeMap;
 		  private:
 		    // The digraph the algorithm runs on
 		    const Digraph &_gr;
 		    // The length of the arcs
 		    const LengthMap &_length;
 		    // Data for storing the strongly connected components
 		    int _comp_num;
 		    typename Digraph::template NodeMap<int> _comp;
 		    std::vector<std::vector<Node> > _comp_nodes;
 		    std::vector<Node>* _nodes;
 		    typename Digraph::template NodeMap<std::vector<Arc> > _out_arcs;
 		    // Data for the found cycles
 		    bool _curr_found, _best_found;
 		    LargeValue _curr_length, _best_length;
 		    int _curr_size, _best_size;
 		    Node _curr_node, _best_node;
 		    int _curr_level, _best_level;
 		    Path *_cycle_path;
 		    bool _local_path;
 		    // Node map for storing path data
 		    PathDataNodeMap _data;
 		    // The processed nodes in the last round
 		    std::vector<Node> _process;
 		    Tolerance _tolerance;
 		    // Infinite constant
 		    const LargeValue INF;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeValueTraits : public Traits {
 		      typedef T LargeValue;
 		      typedef lemon::Tolerance<T> Tolerance;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeValue type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
 		    /// type. It is used for internal computations in the algorithm.
 		    template <typename T>
 		    struct SetLargeValue
 		      : public HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > {
 		      typedef HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPathTraits : public Traits {
 		      typedef T Path;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c %Path type.
 		    ///

lemon/howard.h

Show inline comments

@@ -13,215 +13,219 @@
 		 * 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_HOWARD_H
 		#define LEMON_HOWARD_H
 		/// \ingroup min_mean_cycle
 		///
 		/// \file
 		/// \brief Howard's algorithm for finding a minimum mean cycle.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
 		  /// \brief Default traits class of Howard class.
 		  ///
 		  /// Default traits class of Howard class.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		#endif
 		  struct HowardDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// \brief The large value type used for internal computations
 		    ///
 		    /// The large value type used for internal computations.
 		    /// It is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// The tolerance type used for internal computations
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  // Default traits class for integer value types
 		  template <typename GR, typename LEN>
 		  struct HowardDefaultTraits<GR, LEN, true>
+		  {
 		    typedef GR Digraph;
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeValue;
 		#else
 		    typedef long LargeValue;
 		#endif
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \addtogroup min_mean_cycle
 		  /// @{
 		  /// \brief Implementation of Howard's algorithm for finding a minimum
 		  /// mean cycle.
 		  ///
 		  /// This class implements Howard's policy iteration algorithm for finding
 		  /// a directed cycle of minimum mean length (cost) in a digraph
 		  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
 		  /// This class provides the most efficient algorithm for the
 		  /// minimum mean cycle problem, though the best known theoretical
 		  /// bound on its running time is exponential.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam LEN The type of the length map. The default
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref HowardDefaultTraits
 		  /// "HowardDefaultTraits<GR, LEN>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = HowardDefaultTraits<GR, LEN> >
 		#endif
 		  class Howard
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map
 		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename TR::Value Value;
 		    /// \brief The large value type
 		    ///
 		    /// The large value type used for internal computations.
 		    /// Using the \ref HowardDefaultTraits "default traits class",
 		    /// it is \c long \c long if the \c Value type is integer,
 		    /// By default, it is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeValue LargeValue;
 		    /// The tolerance type
 		    typedef typename TR::Tolerance Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// Using the \ref HowardDefaultTraits "default traits class",
 		    /// it is \ref lemon::Path "Path<Digraph>".
 		    typedef typename TR::Path Path;
 		    /// The \ref HowardDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    // The digraph the algorithm runs on
 		    const Digraph &_gr;
 		    // The length of the arcs
 		    const LengthMap &_length;
 		    // Data for the found cycles
 		    bool _curr_found, _best_found;
 		    LargeValue _curr_length, _best_length;
 		    int _curr_size, _best_size;
 		    Node _curr_node, _best_node;
 		    Path *_cycle_path;
 		    bool _local_path;
 		    // Internal data used by the algorithm
 		    typename Digraph::template NodeMap<Arc> _policy;
 		    typename Digraph::template NodeMap<bool> _reached;
 		    typename Digraph::template NodeMap<int> _level;
 		    typename Digraph::template NodeMap<LargeValue> _dist;
 		    // Data for storing the strongly connected components
 		    int _comp_num;
 		    typename Digraph::template NodeMap<int> _comp;
 		    std::vector<std::vector<Node> > _comp_nodes;
 		    std::vector<Node>* _nodes;
 		    typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
 		    // Queue used for BFS search
 		    std::vector<Node> _queue;
 		    int _qfront, _qback;
 		    Tolerance _tolerance;
 		    // Infinite constant
 		    const LargeValue INF;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeValueTraits : public Traits {
 		      typedef T LargeValue;
 		      typedef lemon::Tolerance<T> Tolerance;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeValue type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
 		    /// type. It is used for internal computations in the algorithm.
 		    template <typename T>
 		    struct SetLargeValue
 		      : public Howard<GR, LEN, SetLargeValueTraits<T> > {
 		      typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPathTraits : public Traits {
 		      typedef T Path;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c %Path type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting the \c %Path
 		    /// type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    template <typename T>
 		    struct SetPath
 		      : public Howard<GR, LEN, SetPathTraits<T> > {
 		      typedef Howard<GR, LEN, SetPathTraits<T> > Create;
 		    };

lemon/karp.h

Show inline comments

@@ -11,215 +11,219 @@
 		 * 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_KARP_H
 		#define LEMON_KARP_H
 		/// \ingroup min_mean_cycle
 		///
 		/// \file
 		/// \brief Karp's algorithm for finding a minimum mean cycle.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
 		  /// \brief Default traits class of Karp algorithm.
 		  ///
 		  /// Default traits class of Karp algorithm.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		#endif
 		  struct KarpDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// \brief The large value type used for internal computations
 		    ///
 		    /// The large value type used for internal computations.
 		    /// It is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// The tolerance type used for internal computations
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addFront() function.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  // Default traits class for integer value types
 		  template <typename GR, typename LEN>
 		  struct KarpDefaultTraits<GR, LEN, true>
+		  {
 		    typedef GR Digraph;
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeValue;
 		#else
 		    typedef long LargeValue;
 		#endif
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \addtogroup min_mean_cycle
 		  /// @{
 		  /// \brief Implementation of Karp's algorithm for finding a minimum
 		  /// mean cycle.
 		  ///
 		  /// This class implements Karp's algorithm for finding a directed
 		  /// cycle of minimum mean length (cost) in a digraph
 		  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
 		  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam LEN The type of the length map. The default
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref KarpDefaultTraits
 		  /// "KarpDefaultTraits<GR, LEN>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = KarpDefaultTraits<GR, LEN> >
 		#endif
 		  class Karp
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the length map
 		    typedef typename TR::LengthMap LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename TR::Value Value;
 		    /// \brief The large value type
 		    ///
 		    /// The large value type used for internal computations.
 		    /// Using the \ref KarpDefaultTraits "default traits class",
 		    /// it is \c long \c long if the \c Value type is integer,
 		    /// By default, it is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeValue LargeValue;
 		    /// The tolerance type
 		    typedef typename TR::Tolerance Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// Using the \ref KarpDefaultTraits "default traits class",
 		    /// it is \ref lemon::Path "Path<Digraph>".
 		    typedef typename TR::Path Path;
 		    /// The \ref KarpDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    // Data sturcture for path data
 		    struct PathData
+		    {
 		      LargeValue dist;
 		      Arc pred;
 		      PathData(LargeValue d, Arc p = INVALID) :
 		        dist(d), pred(p) {}
 		    };
 		    typedef typename Digraph::template NodeMap<std::vector<PathData> >
 		      PathDataNodeMap;
 		  private:
 		    // The digraph the algorithm runs on
 		    const Digraph &_gr;
 		    // The length of the arcs
 		    const LengthMap &_length;
 		    // Data for storing the strongly connected components
 		    int _comp_num;
 		    typename Digraph::template NodeMap<int> _comp;
 		    std::vector<std::vector<Node> > _comp_nodes;
 		    std::vector<Node>* _nodes;
 		    typename Digraph::template NodeMap<std::vector<Arc> > _out_arcs;
 		    // Data for the found cycle
 		    LargeValue _cycle_length;
 		    int _cycle_size;
 		    Node _cycle_node;
 		    Path *_cycle_path;
 		    bool _local_path;
 		    // Node map for storing path data
 		    PathDataNodeMap _data;
 		    // The processed nodes in the last round
 		    std::vector<Node> _process;
 		    Tolerance _tolerance;
 		    // Infinite constant
 		    const LargeValue INF;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeValueTraits : public Traits {
 		      typedef T LargeValue;
 		      typedef lemon::Tolerance<T> Tolerance;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeValue type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
 		    /// type. It is used for internal computations in the algorithm.
 		    template <typename T>
 		    struct SetLargeValue
 		      : public Karp<GR, LEN, SetLargeValueTraits<T> > {
 		      typedef Karp<GR, LEN, SetLargeValueTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetPathTraits : public Traits {
 		      typedef T Path;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c %Path type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting the \c %Path
 		    /// type of the found cycles.

lemon/min_cost_arborescence.h

Show inline comments

@@ -19,203 +19,204 @@
 		#ifndef LEMON_MIN_COST_ARBORESCENCE_H
 		#define LEMON_MIN_COST_ARBORESCENCE_H
 		///\ingroup spantree
 		///\file
 		///\brief Minimum Cost Arborescence algorithm.
 		#include <vector>
 		#include <lemon/list_graph.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/assert.h>
 		namespace lemon {
 		  /// \brief Default traits class for MinCostArborescence class.
 		  ///
 		  /// Default traits class for MinCostArborescence class.
 		  /// \param GR Digraph type.
 		  /// \param CM Type of the cost map.
 		  template <class GR, class CM>
 		  struct MinCostArborescenceDefaultTraits{
 		    /// \brief The digraph type the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc costs.
 		    ///
 		    /// The type of the map that stores the arc costs.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef CM CostMap;
 		    /// \brief The value type of the costs.
 		    ///
 		    /// The value type of the costs.
 		    typedef typename CostMap::Value Value;
 		    /// \brief The type of the map that stores which arcs are in the
 		    /// arborescence.
 		    ///
 		    /// The type of the map that stores which arcs are in the
 		    /// arborescence.  It must conform to the \ref concepts::WriteMap
 		    /// "WriteMap" concept, and its value type must be \c bool
 		    /// (or convertible). Initially it will be set to \c false on each
 		    /// arc, then it will be set on each arborescence arc once.
 		    typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
 		    /// \brief Instantiates a \c ArborescenceMap.
 		    ///
 		    /// This function instantiates a \c ArborescenceMap.
 		    /// \param digraph The digraph to which we would like to calculate
 		    /// the \c ArborescenceMap.
 		    static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
 		      return new ArborescenceMap(digraph);
+		    }
 		    /// \brief The type of the \c PredMap
 		    ///
 		    /// The type of the \c PredMap. It must confrom to the
 		    /// \ref concepts::WriteMap "WriteMap" concept, and its value type
 		    /// must be the \c Arc type of the digraph.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    /// \brief Instantiates a \c PredMap.
 		    ///
 		    /// This function instantiates a \c PredMap.
 		    /// \param digraph The digraph to which we would like to define the
 		    /// \c PredMap.
 		    static PredMap *createPredMap(const Digraph &digraph){
 		      return new PredMap(digraph);
+		    }
 		  };
 		  /// \ingroup spantree
 		  ///
 		  /// \brief Minimum Cost Arborescence algorithm class.
 		  ///
 		  /// This class provides an efficient implementation of the
 		  /// Minimum Cost Arborescence algorithm. The arborescence is a tree
 		  /// which is directed from a given source node of the digraph. One or
 		  /// more sources should be given to the algorithm and it will calculate
 		  /// the minimum cost subgraph that is the union of arborescences with the
 		  /// given sources and spans all the nodes which are reachable from the
 		  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
 		  ///
 		  /// The algorithm also provides an optimal dual solution, therefore
 		  /// the optimality of the solution can be checked.
 		  ///
 		  /// \param GR The digraph type the algorithm runs on.
 		  /// \param CM A read-only arc map storing the costs of the
 		  /// arcs. It is read once for each arc, so the map may involve in
 		  /// relatively time consuming process to compute the arc costs if
 		  /// it is necessary. The default map type is \ref
 		  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
 		  /// \param TR Traits class to set various data types used
 		  /// by the algorithm. The default traits class is
-		  /// \ref MinCostArborescenceDefaultTraits
+		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits
 		  /// "MinCostArborescenceDefaultTraits<GR, CM>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifndef DOXYGEN
 		  template <typename GR,
 		            typename CM = typename GR::template ArcMap<int>,
 		            typename TR =
 		              MinCostArborescenceDefaultTraits<GR, CM> >
 		#else
-		  template <typename GR, typename CM, typedef TR>
+		  template <typename GR, typename CM, typename TR>
 		#endif
 		  class MinCostArborescence {
 		  public:
 		    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
 		    /// of the algorithm.
 		    typedef TR Traits;
 		    /// The type of the underlying digraph.
 		    typedef typename Traits::Digraph Digraph;
 		    /// The type of the map that stores the arc costs.
 		    typedef typename Traits::CostMap CostMap;
 		    ///The type of the costs of the arcs.
 		    typedef typename Traits::Value Value;
 		    ///The type of the predecessor map.
 		    typedef typename Traits::PredMap PredMap;
 		    ///The type of the map that stores which arcs are in the arborescence.
 		    typedef typename Traits::ArborescenceMap ArborescenceMap;
 		    typedef MinCostArborescence Create;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    struct CostArc {
 		      Arc arc;
 		      Value value;
 		      CostArc() {}
 		      CostArc(Arc _arc, Value _value) : arc(_arc), value(_value) {}
 		    };
 		    const Digraph *_digraph;
 		    const CostMap *_cost;
 		    PredMap *_pred;
 		    bool local_pred;
 		    ArborescenceMap *_arborescence;
 		    bool local_arborescence;
 		    typedef typename Digraph::template ArcMap<int> ArcOrder;
 		    ArcOrder *_arc_order;
 		    typedef typename Digraph::template NodeMap<int> NodeOrder;
 		    NodeOrder *_node_order;
 		    typedef typename Digraph::template NodeMap<CostArc> CostArcMap;
 		    CostArcMap *_cost_arcs;
 		    struct StackLevel {
 		      std::vector<CostArc> arcs;
 		      int node_level;
 		    };
 		    std::vector<StackLevel> level_stack;
 		    std::vector<Node> queue;
 		    typedef std::vector<typename Digraph::Node> DualNodeList;
 		    DualNodeList _dual_node_list;
 		    struct DualVariable {
 		      int begin, end;
 		      Value value;
 		      DualVariable(int _begin, int _end, Value _value)
 		        : begin(_begin), end(_end), value(_value) {}
 		    };
 		    typedef std::vector<DualVariable> DualVariables;
 		    DualVariables _dual_variables;
 		    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		    HeapCrossRef *_heap_cross_ref;
 		    typedef BinHeap<int, HeapCrossRef> Heap;
 		    Heap *_heap;
 		  protected:
 		    MinCostArborescence() {}
 		  private:
 		    void createStructures() {
 		      if (!_pred) {
 		        local_pred = true;

lemon/planarity.h

Show inline comments

@@ -425,397 +425,404 @@
 		              int rn = merge_roots[node].front();
 		              int xn = node_data[rn].next;
 		              Node xnode = order_list[xn];
 		              int yn = node_data[rn].prev;
 		              Node ynode = order_list[yn];
 		              bool rd;
 		              if (!external(xnode, rorder, child_lists,
 		                            ancestor_map, low_map)) {
 		                rd = true;
 		              } else if (!external(ynode, rorder, child_lists,
 		                                   ancestor_map, low_map)) {
 		                rd = false;
 		              } else if (pertinent(xnode, embed_arc, merge_roots)) {
 		                rd = true;
 		              } else {
 		                rd = false;
+		              }
 		              merge_stack.push_back(std::make_pair(rn, rd));
 		              pn = rn;
 		              n = rd ? xn : yn;
 		            } else if (!external(node, rorder, child_lists,
 		                                 ancestor_map, low_map)) {
 		              int nn = (node_data[n].next != pn ?
 		                        node_data[n].next : node_data[n].prev);
 		              bool nd = n == node_data[nn].prev;
 		              if (nd) node_data[nn].prev = pn;
 		              else node_data[nn].next = pn;
 		              if (n == node_data[pn].prev) node_data[pn].prev = nn;
 		              else node_data[pn].next = nn;
 		              node_data[nn].inverted =
 		                (node_data[nn].prev == node_data[nn].next && nd != rd);
 		              n = nn;
+		            }
 		            else break;
+		          }
 		          if (!merge_stack.empty() || n == rn) {
 		            break;
+		          }
+		        }
+		      }
 		      void initFace(const Node& node, NodeData& node_data,
 		                    const OrderMap& order_map, const OrderList& order_list) {
 		        int n = order_map[node];
 		        int rn = n + order_list.size();
 		        node_data[n].next = node_data[n].prev = rn;
 		        node_data[rn].next = node_data[rn].prev = n;
 		        node_data[n].visited = order_list.size();
 		        node_data[rn].visited = order_list.size();
+		      }
 		      bool external(const Node& node, int rorder,
 		                    ChildLists& child_lists, AncestorMap& ancestor_map,
 		                    LowMap& low_map) {
 		        Node child = child_lists[node].first;
 		        if (child != INVALID) {
 		          if (low_map[child] < rorder) return true;
+		        }
 		        if (ancestor_map[node] < rorder) return true;
 		        return false;
+		      }
 		      bool pertinent(const Node& node, const EmbedArc& embed_arc,
 		                     const MergeRoots& merge_roots) {
 		        return !merge_roots[node].empty() || embed_arc[node];
+		      }
 		    };
+		  }
 		  /// \ingroup planar
 		  ///
 		  /// \brief Planarity checking of an undirected simple graph
 		  ///
 		  /// This function implements the Boyer-Myrvold algorithm for
 		  /// planarity checking of an undirected graph. It is a simplified
+		  /// planarity checking of an undirected simple graph. It is a simplified
 		  /// version of the PlanarEmbedding algorithm class because neither
-		  /// the embedding nor the kuratowski subdivisons are not computed.
+		  /// the embedding nor the Kuratowski subdivisons are computed.
 		  template <typename GR>
 		  bool checkPlanarity(const GR& graph) {
 		    _planarity_bits::PlanarityChecking<GR> pc(graph);
 		    return pc.run();
+		  }
 		  /// \ingroup planar
 		  ///
 		  /// \brief Planar embedding of an undirected simple graph
 		  ///
 		  /// This class implements the Boyer-Myrvold algorithm for planar
 		  /// embedding of an undirected graph. The planar embedding is an
+		  /// embedding of an undirected simple graph. The planar embedding is an
 		  /// ordering of the outgoing edges of the nodes, which is a possible
 		  /// configuration to draw the graph in the plane. If there is not
 		  /// such ordering then the graph contains a \f$ K_5 \f$ (full graph
 		  /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on
-		  /// 3 ANode and 3 BNode) subdivision.
+		  /// such ordering then the graph contains a K<sub>5</sub> (full graph
 		  /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on
 		  /// 3 Red and 3 Blue nodes) subdivision.
 		  ///
 		  /// The current implementation calculates either an embedding or a
 		  /// Kuratowski subdivision. The running time of the algorithm is
 		  /// \f$ O(n) \f$.
 		  /// Kuratowski subdivision. The running time of the algorithm is O(n).
 		  ///
 		  /// \see PlanarDrawing, checkPlanarity()
 		  template <typename Graph>
 		  class PlanarEmbedding {
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    const Graph& _graph;
 		    typename Graph::template ArcMap<Arc> _embedding;
 		    typename Graph::template EdgeMap<bool> _kuratowski;
 		  private:
 		    typedef typename Graph::template NodeMap<Arc> PredMap;
 		    typedef typename Graph::template EdgeMap<bool> TreeMap;
 		    typedef typename Graph::template NodeMap<int> OrderMap;
 		    typedef std::vector<Node> OrderList;
 		    typedef typename Graph::template NodeMap<int> LowMap;
 		    typedef typename Graph::template NodeMap<int> AncestorMap;
 		    typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
 		    typedef std::vector<NodeDataNode> NodeData;
 		    typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
 		    typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
 		    typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
 		    typedef typename Graph::template NodeMap<Arc> EmbedArc;
 		    typedef _planarity_bits::ArcListNode<Graph> ArcListNode;
 		    typedef typename Graph::template ArcMap<ArcListNode> ArcLists;
 		    typedef typename Graph::template NodeMap<bool> FlipMap;
 		    typedef typename Graph::template NodeMap<int> TypeMap;
 		    enum IsolatorNodeType {
 		      HIGHX = 6, LOWX = 7,
 		      HIGHY = 8, LOWY = 9,
 		      ROOT = 10, PERTINENT = 11,
 		      INTERNAL = 12
 		    };
 		  public:
-		    /// \brief The map for store of embedding
+		    /// \brief The map type for storing the embedding
 		    ///
 		    /// The map type for storing the embedding.
 		    /// \see embeddingMap()
 		    typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
 		    /// \brief Constructor
 		    ///
 		    /// \note The graph should be simple, i.e. parallel and loop arc
 		    /// free.
 		    /// Constructor.
 		    /// \pre The graph must be simple, i.e. it should not
 		    /// contain parallel or loop arcs.
 		    PlanarEmbedding(const Graph& graph)
 		      : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
-		    /// \brief Runs the algorithm.
+		    /// \brief Run the algorithm.
 		    ///
 		    /// Runs the algorithm.
 		    /// \param kuratowski If the parameter is false, then the
 		    /// This function runs the algorithm.
 		    /// \param kuratowski If this parameter is set to \c false, then the
 		    /// algorithm does not compute a Kuratowski subdivision.
-		    ///\return %True when the graph is planar.
+		    /// \return \c true if the graph is planar.
 		    bool run(bool kuratowski = true) {
 		      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
 		      PredMap pred_map(_graph, INVALID);
 		      TreeMap tree_map(_graph, false);
 		      OrderMap order_map(_graph, -1);
 		      OrderList order_list;
 		      AncestorMap ancestor_map(_graph, -1);
 		      LowMap low_map(_graph, -1);
 		      Visitor visitor(_graph, pred_map, tree_map,
 		                      order_map, order_list, ancestor_map, low_map);
 		      DfsVisit<Graph, Visitor> visit(_graph, visitor);
 		      visit.run();
 		      ChildLists child_lists(_graph);
 		      createChildLists(tree_map, order_map, low_map, child_lists);
 		      NodeData node_data(2 * order_list.size());
 		      EmbedArc embed_arc(_graph, INVALID);
 		      MergeRoots merge_roots(_graph);
 		      ArcLists arc_lists(_graph);
 		      FlipMap flip_map(_graph, false);
 		      for (int i = order_list.size() - 1; i >= 0; --i) {
 		        Node node = order_list[i];
 		        node_data[i].first = INVALID;
 		        Node source = node;
 		        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && tree_map[e]) {
 		            initFace(target, arc_lists, node_data,
 		                     pred_map, order_map, order_list);
+		          }
+		        }
 		        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && !tree_map[e]) {
 		            embed_arc[target] = e;
 		            walkUp(target, source, i, pred_map, low_map,
 		                   order_map, order_list, node_data, merge_roots);
+		          }
+		        }
 		        for (typename MergeRoots::Value::iterator it =
 		               merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
 		          int rn = *it;
 		          walkDown(rn, i, node_data, arc_lists, flip_map, order_list,
 		                   child_lists, ancestor_map, low_map, embed_arc, merge_roots);
+		        }
 		        merge_roots[node].clear();
 		        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && !tree_map[e]) {
 		            if (embed_arc[target] != INVALID) {
 		              if (kuratowski) {
 		                isolateKuratowski(e, node_data, arc_lists, flip_map,
 		                                  order_map, order_list, pred_map, child_lists,
 		                                  ancestor_map, low_map,
 		                                  embed_arc, merge_roots);
+		              }
 		              return false;
+		            }
+		          }
+		        }
+		      }
 		      for (int i = 0; i < int(order_list.size()); ++i) {
 		        mergeRemainingFaces(order_list[i], node_data, order_list, order_map,
 		                            child_lists, arc_lists);
 		        storeEmbedding(order_list[i], node_data, order_map, pred_map,
 		                       arc_lists, flip_map);
+		      }
 		      return true;
+		    }
-		    /// \brief Gives back the successor of an arc
+		    /// \brief Give back the successor of an arc
 		    ///
-		    /// Gives back the successor of an arc. This function makes
+		    /// This function gives back the successor of an arc. It makes
 		    /// possible to query the cyclic order of the outgoing arcs from
 		    /// a node.
 		    Arc next(const Arc& arc) const {
 		      return _embedding[arc];
+		    }
-		    /// \brief Gives back the calculated embedding map
+		    /// \brief Give back the calculated embedding map
 		    ///
 		    /// The returned map contains the successor of each arc in the
 		    /// graph.
 		    /// This function gives back the calculated embedding map, which
 		    /// contains the successor of each arc in the cyclic order of the
 		    /// outgoing arcs of its source node.
 		    const EmbeddingMap& embeddingMap() const {
 		      return _embedding;
+		    }
 		    /// \brief Gives back true if the undirected arc is in the
 		    /// kuratowski subdivision
 		    /// \brief Give back \c true if the given edge is in the Kuratowski
 		    /// subdivision
 		    ///
 		    /// Gives back true if the undirected arc is in the kuratowski
 		    /// subdivision
 		    /// \note The \c run() had to be called with true value.
 		    bool kuratowski(const Edge& edge) {
 		    /// This function gives back \c true if the given edge is in the found
 		    /// Kuratowski subdivision.
 		    /// \pre The \c run() function must be called with \c true parameter
 		    /// before using this function.
 		    bool kuratowski(const Edge& edge) const {
 		      return _kuratowski[edge];
+		    }
 		  private:
 		    void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
 		                          const LowMap& low_map, ChildLists& child_lists) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        Node source = n;
 		        std::vector<Node> targets;
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && tree_map[e]) {
 		            targets.push_back(target);
+		          }
+		        }
 		        if (targets.size() == 0) {
 		          child_lists[source].first = INVALID;
 		        } else if (targets.size() == 1) {
 		          child_lists[source].first = targets[0];
 		          child_lists[targets[0]].prev = INVALID;
 		          child_lists[targets[0]].next = INVALID;
 		        } else {
 		          radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
 		          for (int i = 1; i < int(targets.size()); ++i) {
 		            child_lists[targets[i]].prev = targets[i - 1];
 		            child_lists[targets[i - 1]].next = targets[i];
+		          }
 		          child_lists[targets.back()].next = INVALID;
 		          child_lists[targets.front()].prev = INVALID;
 		          child_lists[source].first = targets.front();
+		        }
+		      }
+		    }
 		    void walkUp(const Node& node, Node root, int rorder,
 		                const PredMap& pred_map, const LowMap& low_map,
 		                const OrderMap& order_map, const OrderList& order_list,
 		                NodeData& node_data, MergeRoots& merge_roots) {
 		      int na, nb;
 		      bool da, db;
 		      na = nb = order_map[node];
 		      da = true; db = false;
 		      while (true) {
 		        if (node_data[na].visited == rorder) break;
 		        if (node_data[nb].visited == rorder) break;
 		        node_data[na].visited = rorder;
 		        node_data[nb].visited = rorder;
 		        int rn = -1;
 		        if (na >= int(order_list.size())) {
 		          rn = na;
 		        } else if (nb >= int(order_list.size())) {
 		          rn = nb;
+		        }
 		        if (rn == -1) {
 		          int nn;
 		          nn = da ? node_data[na].prev : node_data[na].next;
 		          da = node_data[nn].prev != na;
 		          na = nn;
 		          nn = db ? node_data[nb].prev : node_data[nb].next;
 		          db = node_data[nn].prev != nb;
 		          nb = nn;
 		        } else {
 		          Node rep = order_list[rn - order_list.size()];
 		          Node parent = _graph.source(pred_map[rep]);
 		          if (low_map[rep] < rorder) {
 		            merge_roots[parent].push_back(rn);
 		          } else {
 		            merge_roots[parent].push_front(rn);
+		          }
 		          if (parent != root) {
 		            na = nb = order_map[parent];
 		            da = true; db = false;
 		          } else {
 		            break;
+		          }
+		        }
+		      }
@@ -1966,215 +1973,218 @@
 		        for (typename Graph::OutArcIt e(graph, s); e != INVALID; ++e) {
 		          visited.set(graph.target(e), true);
+		        }
 		        typename Graph::Arc oppe = INVALID;
 		        e = embedding[graph.oppositeArc(mine)];
 		        e = embedding[graph.oppositeArc(e)];
 		        while (graph.target(e) != s) {
 		          if (visited[graph.source(e)]) {
 		            oppe = e;
 		            break;
+		          }
 		          e = embedding[graph.oppositeArc(e)];
+		        }
 		        visited.setAll(false);
 		        if (oppe == INVALID) {
 		          e = embedding[graph.oppositeArc(mine)];
 		          typename Graph::Arc pn = mine, p = e;
 		          e = embedding[graph.oppositeArc(e)];
 		          while (graph.target(e) != s) {
 		            typename Graph::Arc n =
 		              graph.direct(graph.addEdge(s, graph.source(e)), true);
 		            embedding[n] = pn;
 		            embedding[graph.oppositeArc(n)] = e;
 		            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
 		            pn = n;
 		            p = e;
 		            e = embedding[graph.oppositeArc(e)];
+		          }
 		          embedding[graph.oppositeArc(e)] = pn;
 		        } else {
 		          mine = embedding[graph.oppositeArc(mine)];
 		          s = graph.source(mine);
 		          oppe = embedding[graph.oppositeArc(oppe)];
 		          typename Graph::Node t = graph.source(oppe);
 		          typename Graph::Arc ce = graph.direct(graph.addEdge(s, t), true);
 		          embedding[ce] = mine;
 		          embedding[graph.oppositeArc(ce)] = oppe;
 		          typename Graph::Arc pn = ce, p = oppe;
 		          e = embedding[graph.oppositeArc(oppe)];
 		          while (graph.target(e) != s) {
 		            typename Graph::Arc n =
 		              graph.direct(graph.addEdge(s, graph.source(e)), true);
 		            embedding[n] = pn;
 		            embedding[graph.oppositeArc(n)] = e;
 		            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
 		            pn = n;
 		            p = e;
 		            e = embedding[graph.oppositeArc(e)];
+		          }
 		          embedding[graph.oppositeArc(e)] = pn;
 		          pn = graph.oppositeArc(ce), p = mine;
 		          e = embedding[graph.oppositeArc(mine)];
 		          while (graph.target(e) != t) {
 		            typename Graph::Arc n =
 		              graph.direct(graph.addEdge(t, graph.source(e)), true);
 		            embedding[n] = pn;
 		            embedding[graph.oppositeArc(n)] = e;
 		            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
 		            pn = n;
 		            p = e;
 		            e = embedding[graph.oppositeArc(e)];
+		          }
 		          embedding[graph.oppositeArc(e)] = pn;
+		        }
+		      }
+		    }
+		  }
 		  /// \ingroup planar
 		  ///
 		  /// \brief Schnyder's planar drawing algorithm
 		  ///
 		  /// The planar drawing algorithm calculates positions for the nodes
 		  /// in the plane which coordinates satisfy that if the arcs are
 		  /// represented with straight lines then they will not intersect
 		  /// in the plane. These coordinates satisfy that if the edges are
 		  /// represented with straight lines, then they will not intersect
 		  /// each other.
 		  ///
 		  /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
 		  /// i.e. each node will be located in the \c [0,n-2]x[0,n-2] square.
 		  /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,
 		  /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.
 		  /// The time complexity of the algorithm is O(n).
 		  ///
 		  /// \see PlanarEmbedding
 		  template <typename Graph>
 		  class PlanarDrawing {
 		  public:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
-		    /// \brief The point type for store coordinates
+		    /// \brief The point type for storing coordinates
 		    typedef dim2::Point<int> Point;
-		    /// \brief The map type for store coordinates
+		    /// \brief The map type for storing the coordinates of the nodes
 		    typedef typename Graph::template NodeMap<Point> PointMap;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
-		    /// \pre The graph should be simple, i.e. loop and parallel arc free.
+		    /// \pre The graph must be simple, i.e. it should not
 		    /// contain parallel or loop arcs.
 		    PlanarDrawing(const Graph& graph)
 		      : _graph(graph), _point_map(graph) {}
 		  private:
 		    template <typename AuxGraph, typename AuxEmbeddingMap>
 		    void drawing(const AuxGraph& graph,
 		                 const AuxEmbeddingMap& next,
 		                 PointMap& point_map) {
 		      TEMPLATE_GRAPH_TYPEDEFS(AuxGraph);
 		      typename AuxGraph::template ArcMap<Arc> prev(graph);
 		      for (NodeIt n(graph); n != INVALID; ++n) {
 		        Arc e = OutArcIt(graph, n);
 		        Arc p = e, l = e;
 		        e = next[e];
 		        while (e != l) {
 		          prev[e] = p;
 		          p = e;
 		          e = next[e];
+		        }
 		        prev[e] = p;
+		      }
 		      Node anode, bnode, cnode;
+		      {
 		        Arc e = ArcIt(graph);
 		        anode = graph.source(e);
 		        bnode = graph.target(e);
 		        cnode = graph.target(next[graph.oppositeArc(e)]);
+		      }
 		      IterableBoolMap<AuxGraph, Node> proper(graph, false);
 		      typename AuxGraph::template NodeMap<int> conn(graph, -1);
 		      conn[anode] = conn[bnode] = -2;
+		      {
 		        for (OutArcIt e(graph, anode); e != INVALID; ++e) {
 		          Node m = graph.target(e);
 		          if (conn[m] == -1) {
 		            conn[m] = 1;
+		          }
+		        }
 		        conn[cnode] = 2;
 		        for (OutArcIt e(graph, bnode); e != INVALID; ++e) {
 		          Node m = graph.target(e);
 		          if (conn[m] == -1) {
 		            conn[m] = 1;
 		          } else if (conn[m] != -2) {
 		            conn[m] += 1;
 		            Arc pe = graph.oppositeArc(e);
 		            if (conn[graph.target(next[pe])] == -2) {
 		              conn[m] -= 1;
+		            }
 		            if (conn[graph.target(prev[pe])] == -2) {
 		              conn[m] -= 1;
+		            }
 		            proper.set(m, conn[m] == 1);
+		          }
+		        }
+		      }
 		      typename AuxGraph::template ArcMap<int> angle(graph, -1);
 		      while (proper.trueNum() != 0) {
 		        Node n = typename IterableBoolMap<AuxGraph, Node>::TrueIt(proper);
 		        proper.set(n, false);
 		        conn[n] = -2;
 		        for (OutArcIt e(graph, n); e != INVALID; ++e) {
 		          Node m = graph.target(e);
 		          if (conn[m] == -1) {
 		            conn[m] = 1;
 		          } else if (conn[m] != -2) {
 		            conn[m] += 1;
 		            Arc pe = graph.oppositeArc(e);
 		            if (conn[graph.target(next[pe])] == -2) {
 		              conn[m] -= 1;
+		            }
 		            if (conn[graph.target(prev[pe])] == -2) {
 		              conn[m] -= 1;
+		            }
 		            proper.set(m, conn[m] == 1);
+		          }
+		        }
+		        {
 		          Arc e = OutArcIt(graph, n);
@@ -2273,465 +2283,473 @@
 		              processed[m] = true;
 		              m = bpred[m];
+		            }
 		            while (!st.empty()) {
 		              border.push_back(st.back());
 		              st.pop_back();
+		            }
+		          }
+		        }
+		      }
+		      {
 		        typename AuxGraph::template NodeMap<bool> processed(graph, false);
 		        std::vector<Node> st;
 		        for (NodeIt n(graph); n != INVALID; ++n) {
 		          if (!processed[n] && n != anode && n != bnode) {
 		            st.push_back(n);
 		            processed[n] = true;
 		            Node m = cpred[n];
 		            while (m != INVALID && !processed[m]) {
 		              st.push_back(m);
 		              processed[m] = true;
 		              m = cpred[m];
+		            }
 		            while (!st.empty()) {
 		              corder.push_back(st.back());
 		              st.pop_back();
+		            }
+		          }
+		        }
+		      }
 		      typename AuxGraph::template NodeMap<int> atree(graph, 0);
 		      for (int i = aorder.size() - 1; i >= 0; --i) {
 		        Node n = aorder[i];
 		        atree[n] = 1;
 		        for (OutArcIt e(graph, n); e != INVALID; ++e) {
 		          if (apred[graph.target(e)] == n) {
 		            atree[n] += atree[graph.target(e)];
+		          }
+		        }
+		      }
 		      typename AuxGraph::template NodeMap<int> btree(graph, 0);
 		      for (int i = border.size() - 1; i >= 0; --i) {
 		        Node n = border[i];
 		        btree[n] = 1;
 		        for (OutArcIt e(graph, n); e != INVALID; ++e) {
 		          if (bpred[graph.target(e)] == n) {
 		            btree[n] += btree[graph.target(e)];
+		          }
+		        }
+		      }
 		      typename AuxGraph::template NodeMap<int> apath(graph, 0);
 		      apath[bnode] = apath[cnode] = 1;
 		      typename AuxGraph::template NodeMap<int> apath_btree(graph, 0);
 		      apath_btree[bnode] = btree[bnode];
 		      for (int i = 1; i < int(aorder.size()); ++i) {
 		        Node n = aorder[i];
 		        apath[n] = apath[apred[n]] + 1;
 		        apath_btree[n] = btree[n] + apath_btree[apred[n]];
+		      }
 		      typename AuxGraph::template NodeMap<int> bpath_atree(graph, 0);
 		      bpath_atree[anode] = atree[anode];
 		      for (int i = 1; i < int(border.size()); ++i) {
 		        Node n = border[i];
 		        bpath_atree[n] = atree[n] + bpath_atree[bpred[n]];
+		      }
 		      typename AuxGraph::template NodeMap<int> cpath(graph, 0);
 		      cpath[anode] = cpath[bnode] = 1;
 		      typename AuxGraph::template NodeMap<int> cpath_atree(graph, 0);
 		      cpath_atree[anode] = atree[anode];
 		      typename AuxGraph::template NodeMap<int> cpath_btree(graph, 0);
 		      cpath_btree[bnode] = btree[bnode];
 		      for (int i = 1; i < int(corder.size()); ++i) {
 		        Node n = corder[i];
 		        cpath[n] = cpath[cpred[n]] + 1;
 		        cpath_atree[n] = atree[n] + cpath_atree[cpred[n]];
 		        cpath_btree[n] = btree[n] + cpath_btree[cpred[n]];
+		      }
 		      typename AuxGraph::template NodeMap<int> third(graph);
 		      for (NodeIt n(graph); n != INVALID; ++n) {
 		        point_map[n].x =
 		          bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1;
 		        point_map[n].y =
 		          cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1;
+		      }
+		    }
 		  public:
-		    /// \brief Calculates the node positions
+		    /// \brief Calculate the node positions
 		    ///
 		    /// This function calculates the node positions.
 		    /// \return %True if the graph is planar.
 		    /// This function calculates the node positions on the plane.
 		    /// \return \c true if the graph is planar.
 		    bool run() {
 		      PlanarEmbedding<Graph> pe(_graph);
 		      if (!pe.run()) return false;
 		      run(pe);
 		      return true;
+		    }
-		    /// \brief Calculates the node positions according to a
+		    /// \brief Calculate the node positions according to a
 		    /// combinatorical embedding
 		    ///
 		    /// This function calculates the node locations. The \c embedding
 		    /// parameter should contain a valid combinatorical embedding, i.e.
-		    /// a valid cyclic order of the arcs.
+		    /// This function calculates the node positions on the plane.
 		    /// The given \c embedding map should contain a valid combinatorical
 		    /// embedding, i.e. a valid cyclic order of the arcs.
 		    /// It can be computed using PlanarEmbedding.
 		    template <typename EmbeddingMap>
 		    void run(const EmbeddingMap& embedding) {
 		      typedef SmartEdgeSet<Graph> AuxGraph;
 		      if (3 * countNodes(_graph) - 6 == countEdges(_graph)) {
 		        drawing(_graph, embedding, _point_map);
 		        return;
+		      }
 		      AuxGraph aux_graph(_graph);
 		      typename AuxGraph::template ArcMap<typename AuxGraph::Arc>
 		        aux_embedding(aux_graph);
+		      {
 		        typename Graph::template EdgeMap<typename AuxGraph::Edge>
 		          ref(_graph);
 		        for (EdgeIt e(_graph); e != INVALID; ++e) {
 		          ref[e] = aux_graph.addEdge(_graph.u(e), _graph.v(e));
+		        }
 		        for (EdgeIt e(_graph); e != INVALID; ++e) {
 		          Arc ee = embedding[_graph.direct(e, true)];
 		          aux_embedding[aux_graph.direct(ref[e], true)] =
 		            aux_graph.direct(ref[ee], _graph.direction(ee));
 		          ee = embedding[_graph.direct(e, false)];
 		          aux_embedding[aux_graph.direct(ref[e], false)] =
 		            aux_graph.direct(ref[ee], _graph.direction(ee));
+		        }
+		      }
 		      _planarity_bits::makeConnected(aux_graph, aux_embedding);
 		      _planarity_bits::makeBiNodeConnected(aux_graph, aux_embedding);
 		      _planarity_bits::makeMaxPlanar(aux_graph, aux_embedding);
 		      drawing(aux_graph, aux_embedding, _point_map);
+		    }
 		    /// \brief The coordinate of the given node
 		    ///
-		    /// The coordinate of the given node.
+		    /// This function returns the coordinate of the given node.
 		    Point operator[](const Node& node) const {
 		      return _point_map[node];
+		    }
-		    /// \brief Returns the grid embedding in a \e NodeMap.
+		    /// \brief Return the grid embedding in a node map
 		    ///
-		    /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
+		    /// This function returns the grid embedding in a node map of
 		    /// \c dim2::Point<int> coordinates.
 		    const PointMap& coords() const {
 		      return _point_map;
+		    }
 		  private:
 		    const Graph& _graph;
 		    PointMap _point_map;
 		  };
 		  namespace _planarity_bits {
 		    template <typename ColorMap>
 		    class KempeFilter {
 		    public:
 		      typedef typename ColorMap::Key Key;
 		      typedef bool Value;
 		      KempeFilter(const ColorMap& color_map,
 		                  const typename ColorMap::Value& first,
 		                  const typename ColorMap::Value& second)
 		        : _color_map(color_map), _first(first), _second(second) {}
 		      Value operator[](const Key& key) const {
 		        return _color_map[key] == _first || _color_map[key] == _second;
+		      }
 		    private:
 		      const ColorMap& _color_map;
 		      typename ColorMap::Value _first, _second;
 		    };
+		  }
 		  /// \ingroup planar
 		  ///
 		  /// \brief Coloring planar graphs
 		  ///
 		  /// The graph coloring problem is the coloring of the graph nodes
 		  /// that there are not adjacent nodes with the same color. The
 		  /// planar graphs can be always colored with four colors, it is
-		  /// proved by Appel and Haken and their proofs provide a quadratic
+		  /// so that there are no adjacent nodes with the same color. The
 		  /// planar graphs can always be colored with four colors, which is
 		  /// proved by Appel and Haken. Their proofs provide a quadratic
 		  /// time algorithm for four coloring, but it could not be used to
 		  /// implement efficient algorithm. The five and six coloring can be
 		  /// made in linear time, but in this class the five coloring has
 		  /// implement an efficient algorithm. The five and six coloring can be
 		  /// made in linear time, but in this class, the five coloring has
 		  /// quadratic worst case time complexity. The two coloring (if
 		  /// possible) is solvable with a graph search algorithm and it is
 		  /// implemented in \ref bipartitePartitions() function in LEMON. To
 		  /// decide whether the planar graph is three colorable is
 		  /// NP-complete.
 		  /// decide whether a planar graph is three colorable is NP-complete.
 		  ///
 		  /// This class contains member functions for calculate colorings
 		  /// with five and six colors. The six coloring algorithm is a simple
 		  /// greedy coloring on the backward minimum outgoing order of nodes.
 		  /// This order can be computed as in each phase the node with least
 		  /// outgoing arcs to unprocessed nodes is chosen. This order
 		  /// This order can be computed by selecting the node with least
 		  /// outgoing arcs to unprocessed nodes in each phase. This order
 		  /// guarantees that when a node is chosen for coloring it has at
 		  /// most five already colored adjacents. The five coloring algorithm
 		  /// use the same method, but if the greedy approach fails to color
 		  /// with five colors, i.e. the node has five already different
 		  /// colored neighbours, it swaps the colors in one of the connected
 		  /// two colored sets with the Kempe recoloring method.
 		  template <typename Graph>
 		  class PlanarColoring {
 		  public:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
-		    /// \brief The map type for store color indexes
+		    /// \brief The map type for storing color indices
 		    typedef typename Graph::template NodeMap<int> IndexMap;
-		    /// \brief The map type for store colors
+		    /// \brief The map type for storing colors
 		    ///
 		    /// The map type for storing colors.
 		    /// \see Palette, Color
 		    typedef ComposeMap<Palette, IndexMap> ColorMap;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \pre The graph should be simple, i.e. loop and parallel arc free.
 		    /// Constructor.
 		    /// \pre The graph must be simple, i.e. it should not
 		    /// contain parallel or loop arcs.
 		    PlanarColoring(const Graph& graph)
 		      : _graph(graph), _color_map(graph), _palette(0) {
 		      _palette.add(Color(1,0,0));
 		      _palette.add(Color(0,1,0));
 		      _palette.add(Color(0,0,1));
 		      _palette.add(Color(1,1,0));
 		      _palette.add(Color(1,0,1));
 		      _palette.add(Color(0,1,1));
+		    }
-		    /// \brief Returns the \e NodeMap of color indexes
+		    /// \brief Return the node map of color indices
 		    ///
 		    /// Returns the \e NodeMap of color indexes. The values are in the
 		    /// range \c [0..4] or \c [0..5] according to the coloring method.
 		    /// This function returns the node map of color indices. The values are
 		    /// in the range \c [0..4] or \c [0..5] according to the coloring method.
 		    IndexMap colorIndexMap() const {
 		      return _color_map;
+		    }
-		    /// \brief Returns the \e NodeMap of colors
+		    /// \brief Return the node map of colors
 		    ///
 		    /// Returns the \e NodeMap of colors. The values are five or six
 		    /// distinct \ref lemon::Color "colors".
 		    /// This function returns the node map of colors. The values are among
 		    /// five or six distinct \ref lemon::Color "colors".
 		    ColorMap colorMap() const {
 		      return composeMap(_palette, _color_map);
+		    }
-		    /// \brief Returns the color index of the node
+		    /// \brief Return the color index of the node
 		    ///
 		    /// Returns the color index of the node. The values are in the
 		    /// range \c [0..4] or \c [0..5] according to the coloring method.
 		    /// This function returns the color index of the given node. The value is
 		    /// in the range \c [0..4] or \c [0..5] according to the coloring method.
 		    int colorIndex(const Node& node) const {
 		      return _color_map[node];
+		    }
-		    /// \brief Returns the color of the node
+		    /// \brief Return the color of the node
 		    ///
 		    /// Returns the color of the node. The values are five or six
 		    /// distinct \ref lemon::Color "colors".
 		    /// This function returns the color of the given node. The value is among
 		    /// five or six distinct \ref lemon::Color "colors".
 		    Color color(const Node& node) const {
 		      return _palette[_color_map[node]];
+		    }
-		    /// \brief Calculates a coloring with at most six colors
+		    /// \brief Calculate a coloring with at most six colors
 		    ///
 		    /// This function calculates a coloring with at most six colors. The time
 		    /// complexity of this variant is linear in the size of the graph.
 		    /// \return %True when the algorithm could color the graph with six color.
 		    /// If the algorithm fails, then the graph could not be planar.
 		    /// \note This function can return true if the graph is not
 		    /// planar but it can be colored with 6 colors.
 		    /// \return \c true if the algorithm could color the graph with six colors.
 		    /// If the algorithm fails, then the graph is not planar.
 		    /// \note This function can return \c true if the graph is not
 		    /// planar, but it can be colored with at most six colors.
 		    bool runSixColoring() {
 		      typename Graph::template NodeMap<int> heap_index(_graph, -1);
 		      BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _color_map[n] = -2;
 		        heap.push(n, countOutArcs(_graph, n));
+		      }
 		      std::vector<Node> order;
 		      while (!heap.empty()) {
 		        Node n = heap.top();
 		        heap.pop();
 		        _color_map[n] = -1;
 		        order.push_back(n);
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node t = _graph.runningNode(e);
 		          if (_color_map[t] == -2) {
 		            heap.decrease(t, heap[t] - 1);
+		          }
+		        }
+		      }
 		      for (int i = order.size() - 1; i >= 0; --i) {
 		        std::vector<bool> forbidden(6, false);
 		        for (OutArcIt e(_graph, order[i]); e != INVALID; ++e) {
 		          Node t = _graph.runningNode(e);
 		          if (_color_map[t] != -1) {
 		            forbidden[_color_map[t]] = true;
+		          }
+		        }
 		               for (int k = 0; k < 6; ++k) {
 		          if (!forbidden[k]) {
 		            _color_map[order[i]] = k;
 		            break;
+		          }
+		        }
 		        if (_color_map[order[i]] == -1) {
 		          return false;
+		        }
+		      }
 		      return true;
+		    }
 		  private:
 		    bool recolor(const Node& u, const Node& v) {
 		      int ucolor = _color_map[u];
 		      int vcolor = _color_map[v];
 		      typedef _planarity_bits::KempeFilter<IndexMap> KempeFilter;
 		      KempeFilter filter(_color_map, ucolor, vcolor);
 		      typedef FilterNodes<const Graph, const KempeFilter> KempeGraph;
 		      KempeGraph kempe_graph(_graph, filter);
 		      std::vector<Node> comp;
 		      Bfs<KempeGraph> bfs(kempe_graph);
 		      bfs.init();
 		      bfs.addSource(u);
 		      while (!bfs.emptyQueue()) {
 		        Node n = bfs.nextNode();
 		        if (n == v) return false;
 		        comp.push_back(n);
 		        bfs.processNextNode();
+		      }
 		      int scolor = ucolor + vcolor;
 		      for (int i = 0; i < static_cast<int>(comp.size()); ++i) {
 		        _color_map[comp[i]] = scolor - _color_map[comp[i]];
+		      }
 		      return true;
+		    }
 		    template <typename EmbeddingMap>
 		    void kempeRecoloring(const Node& node, const EmbeddingMap& embedding) {
 		      std::vector<Node> nodes;
 		      nodes.reserve(4);
 		      for (Arc e = OutArcIt(_graph, node); e != INVALID; e = embedding[e]) {
 		        Node t = _graph.target(e);
 		        if (_color_map[t] != -1) {
 		          nodes.push_back(t);
 		          if (nodes.size() == 4) break;
+		        }
+		      }
 		      int color = _color_map[nodes[0]];
 		      if (recolor(nodes[0], nodes[2])) {
 		        _color_map[node] = color;
 		      } else {
 		        color = _color_map[nodes[1]];
 		        recolor(nodes[1], nodes[3]);
 		        _color_map[node] = color;
+		      }
+		    }
 		  public:
-		    /// \brief Calculates a coloring with at most five colors
+		    /// \brief Calculate a coloring with at most five colors
 		    ///
 		    /// This function calculates a coloring with at most five
 		    /// colors. The worst case time complexity of this variant is
 		    /// quadratic in the size of the graph.
 		    /// \param embedding This map should contain a valid combinatorical
 		    /// embedding, i.e. a valid cyclic order of the arcs.
 		    /// It can be computed using PlanarEmbedding.
 		    template <typename EmbeddingMap>
 		    void runFiveColoring(const EmbeddingMap& embedding) {
 		      typename Graph::template NodeMap<int> heap_index(_graph, -1);
 		      BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _color_map[n] = -2;
 		        heap.push(n, countOutArcs(_graph, n));
+		      }
 		      std::vector<Node> order;
 		      while (!heap.empty()) {
 		        Node n = heap.top();
 		        heap.pop();
 		        _color_map[n] = -1;
 		        order.push_back(n);
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node t = _graph.runningNode(e);
 		          if (_color_map[t] == -2) {
 		            heap.decrease(t, heap[t] - 1);
+		          }
+		        }
+		      }
 		      for (int i = order.size() - 1; i >= 0; --i) {
 		        std::vector<bool> forbidden(5, false);
 		        for (OutArcIt e(_graph, order[i]); e != INVALID; ++e) {
 		          Node t = _graph.runningNode(e);
 		          if (_color_map[t] != -1) {
 		            forbidden[_color_map[t]] = true;
+		          }
+		        }
 		        for (int k = 0; k < 5; ++k) {
 		          if (!forbidden[k]) {
 		            _color_map[order[i]] = k;
 		            break;
+		          }
+		        }
 		        if (_color_map[order[i]] == -1) {
 		          kempeRecoloring(order[i], embedding);
+		        }
+		      }
+		    }
-		    /// \brief Calculates a coloring with at most five colors
+		    /// \brief Calculate a coloring with at most five colors
 		    ///
 		    /// This function calculates a coloring with at most five
 		    /// colors. The worst case time complexity of this variant is
 		    /// quadratic in the size of the graph.
-		    /// \return %True when the graph is planar.
+		    /// \return \c true if the graph is planar.
 		    bool runFiveColoring() {
 		      PlanarEmbedding<Graph> pe(_graph);
 		      if (!pe.run()) return false;
 		      runFiveColoring(pe.embeddingMap());
 		      return true;
+		    }
 		  private:
 		    const Graph& _graph;
 		    IndexMap _color_map;
 		    Palette _palette;
 		  };
+		}
 		#endif

lemon/preflow.h

Show inline comments

@@ -26,192 +26,197 @@
 		/// \ingroup max_flow
 		/// \brief Implementation of the preflow algorithm.
 		namespace lemon {
 		  /// \brief Default traits class of Preflow class.
 		  ///
 		  /// Default traits class of Preflow class.
 		  /// \tparam GR Digraph type.
 		  /// \tparam CAP Capacity map type.
 		  template <typename GR, typename CAP>
 		  struct PreflowDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc capacities.
 		    ///
 		    /// The type of the map that stores the arc capacities.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef CAP CapacityMap;
 		    /// \brief The type of the flow values.
 		    typedef typename CapacityMap::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 meet 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 Preflow algorithm.
 		    ///
 		    /// The elevator type used by Preflow algorithm.
 		    ///
 		    /// \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;
 		  };
 		  /// \ingroup max_flow
 		  ///
 		  /// \brief %Preflow algorithm class.
 		  ///
 		  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
 		  /// \e push-relabel algorithm producing a \ref max_flow
 		  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
 		  /// \ref amo93networkflows, \ref goldberg88newapproach.
 		  /// The preflow algorithms are the fastest known maximum
 		  /// flow algorithms. The current implementation uses a mixture of the
 		  /// \e "highest label" and the \e "bound decrease" heuristics.
 		  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
 		  ///
 		  /// The algorithm consists of two phases. After the first phase
 		  /// the maximum flow value and the minimum cut is obtained. The
 		  /// second phase constructs a feasible maximum flow on each arc.
 		  ///
 		  /// \warning This implementation cannot handle infinite or very large
 		  /// capacities (e.g. the maximum value of \c CAP::Value).
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam CAP The type of the capacity map. The default map
 		  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref PreflowDefaultTraits
 		  /// "PreflowDefaultTraits<GR, CAP>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename CAP, typename TR>
 		#else
 		  template <typename GR,
 		            typename CAP = typename GR::template ArcMap<int>,
 		            typename TR = PreflowDefaultTraits<GR, CAP> >
 		#endif
 		  class Preflow {
 		  public:
 		    ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The type of the capacity map.
 		    typedef typename Traits::CapacityMap CapacityMap;
 		    ///The type of the flow values.
 		    typedef typename Traits::Value Value;
 		    ///The type of the flow map.
 		    typedef typename Traits::FlowMap FlowMap;
 		    ///The type of the elevator.
 		    typedef typename Traits::Elevator Elevator;
 		    ///The type of the tolerance.
 		    typedef typename Traits::Tolerance Tolerance;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph& _graph;
 		    const CapacityMap* _capacity;
 		    int _node_num;
 		    Node _source, _target;
 		    FlowMap* _flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tolerance;
 		    bool _phase;
 		    void createStructures() {
 		      _node_num = countNodes(_graph);
 		      if (!_flow) {
 		        _flow = Traits::createFlowMap(_graph);
 		        _local_flow = true;
+		      }
 		      if (!_level) {
 		        _level = Traits::createElevator(_graph, _node_num);
 		        _local_level = true;
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_graph);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_local_flow) {
 		        delete _flow;
+		      }
 		      if (_local_level) {
 		        delete _level;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
+		    }
 		  public:
 		    typedef Preflow Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		      static FlowMap *createFlowMap(const Digraph&) {
 		        LEMON_ASSERT(false, "FlowMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };

0 comments (0 inline)

RhodeCode

Login to your account