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

@@ -152,24 +152,46 @@
 		   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

@@ -5,48 +5,49 @@
 		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

@@ -7,48 +7,49 @@
 			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; \

lemon/bellman_ford.h

Show inline comments

@@ -150,48 +150,53 @@
 		  /// 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;
@@ -912,48 +917,51 @@
 		    /// 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.

lemon/bfs.h

Show inline comments

@@ -100,48 +100,53 @@
 		    ///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;
@@ -936,48 +941,51 @@
 		    /// 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.
@@ -1274,53 +1282,53 @@
 		  /// \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:

lemon/capacity_scaling.h

Show inline comments

@@ -56,51 +56,56 @@
 		    /// 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;

lemon/circulation.h

Show inline comments

@@ -152,48 +152,53 @@
 		     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;

lemon/cost_scaling.h

Show inline comments

@@ -83,82 +83,86 @@
 		  };
 		  /// \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.

lemon/dfs.h

Show inline comments

@@ -100,48 +100,53 @@
 		    ///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;
@@ -866,48 +871,51 @@
 		    /// 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.
@@ -1216,53 +1224,53 @@
 		  /// \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:

lemon/dijkstra.h

Show inline comments

@@ -171,48 +171,53 @@
 		  ///
 		  ///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;
@@ -1071,48 +1076,51 @@
 		                           _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() {}

lemon/hartmann_orlin.h

Show inline comments

@@ -85,71 +85,75 @@
 		#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;

lemon/howard.h

Show inline comments

@@ -85,71 +85,75 @@
 		#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;

lemon/karp.h

Show inline comments

@@ -83,71 +83,75 @@
 		#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;

lemon/min_cost_arborescence.h

Show inline comments

@@ -91,59 +91,60 @@
 		  };
 		  /// \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);

lemon/planarity.h

Show inline comments

@@ -497,72 +497,73 @@
 		        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;
@@ -570,64 +571,68 @@
 		    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);
@@ -678,72 +683,74 @@
 		            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];
@@ -2038,71 +2045,74 @@
 		              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];
+		        }
@@ -2345,241 +2355,246 @@
 		      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);
+		          }
+		        }
+		      }
@@ -2639,99 +2654,102 @@
 		    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

@@ -98,48 +98,53 @@
 		  /// \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.

0 comments (0 inline)

RhodeCode

Login to your account