LEMON/LEMON-official Changeset - r240:bea328c5a8d3

Repositories » LEMON » LEMON-official

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

Changeset - r240:bea328c5a8d3

« 236:da953e
« 239:7b7e3f

243:32155c »

r240:bea328c5a8d3

Tue, 29 Jul 2008 15:01:30

[Not Reviewed]

0 comments (0 inline)

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

Merge

0 10 0

merge default

1 file changed with 26 insertions and 26 deletions:

CMakeLists.txt

configure.ac

doc/groups.dox

doc/lgf.dox

lemon/bits/alteration_notifier.h

lemon/concepts/path.h

lemon/lgf_reader.h

lemon/lgf_writer.h

lemon/path.h

lemon/unionfind.h

↑ Collapse diff ↑

CMakeLists.txt

Show inline comments

 		CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
 		#EXECUTE_PROCESS(
 		#  COMMAND hg id -i
 		#  OUTPUT_VARIABLE HG_REVISION
 		#  OUTPUT_STRIP_TRAILING_WHITESPACE)
-		SET(PROJECT_NAME "Lemon")
+		SET(PROJECT_NAME "LEMON")
 		SET(PROJECT_VERSION_MAJOR "0")
 		SET(PROJECT_VERSION_MINOR "99")
 		SET(PROJECT_VERSION_PATCH "0")
 		SET(PROJECT_VERSION
 		  "${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")
 		PROJECT(${PROJECT_NAME})
 		SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
 		INCLUDE(FindDoxygen)
 		INCLUDE(FindGhostscript)
 		ENABLE_TESTING()
 		ADD_SUBDIRECTORY(lemon)
 		ADD_SUBDIRECTORY(demo)
 		ADD_SUBDIRECTORY(doc)
 		ADD_SUBDIRECTORY(test)
 		IF(WIN32)
 		  INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico
 		    DESTINATION bin)
 		ENDIF(WIN32)
 		IF(WIN32)
 		  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
 		  SET(CPACK_PACKAGE_VENDOR
 		    "EGRES - Egervary Research Group on Combinatorial Optimization")
 		  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
-		    "Lemon - Library of Efficient Models and Optimization in Networks")
+		    "LEMON - Library of Efficient Models and Optimization in Networks")
 		  SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
 		  SET(CPACK_PACKAGE_VERSION_MAJOR ${PROJECT_VERSION_MAJOR})
 		  SET(CPACK_PACKAGE_VERSION_MINOR ${PROJECT_VERSION_MINOR})
 		  SET(CPACK_PACKAGE_VERSION_PATCH ${PROJECT_VERSION_PATCH})
 		  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
 		  SET(CPACK_PACKAGE_INSTALL_DIRECTORY
 		    "${PROJECT_NAME} ${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}")
 		  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
 		    "${PROJECT_NAME} ${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")
 		  # Variables to generate a component-based installer.
 		  #SET(CPACK_COMPONENTS_ALL headers library html_documentation)
 		  #SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
 		  #SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Static library")
 		  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
 		  #SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
-		  #  "C++ header files for use with the Lemon library")
+		  #  "C++ header files for use with the LEMON library")
 		  #SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
-		  #  "Static library used to build programs with Lemon")
+		  #  "Static library used to build programs with LEMON")
 		  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
 		  #  "Doxygen generated documentation")
 		  #SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
 		  #SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
 		  #SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
 		  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
 		  #SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
-		  #  "Components needed to develop software using Lemon")
+		  #  "Components needed to develop software using LEMON")
 		  #SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
-		  #  "Documentation of Lemon")
+		  #  "Documentation of LEMON")
 		  #SET(CPACK_ALL_INSTALL_TYPES Full Developer)
 		  #SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
 		  #SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
 		  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
 		  SET(CPACK_GENERATOR "NSIS")
 		  SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
 		  SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
 		  #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
 		  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
 		  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
 		  SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
 		  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
 		    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\"
 		    ")
 		  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
 		    !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
 		    Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
 		    ")
 		  INCLUDE(CPack)
 		ENDIF(WIN32)

configure.ac

Show inline comments

 		dnl Process this file with autoconf to produce a configure script.
 		dnl Version information.
 		m4_define([lemon_version_number], [])
 		m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
 		m4_define([lemon_version], [ifelse(lemon_version_number(), [], [lemon_hg_revision()], [lemon_version_number()])])
 		AC_PREREQ([2.59])
-		AC_INIT([Lemon], [lemon_version()], [lemon-user@lemon.cs.elte.hu], [lemon])
+		AC_INIT([LEMON], [lemon_version()], [lemon-user@lemon.cs.elte.hu], [lemon])
 		AC_CONFIG_AUX_DIR([build-aux])
 		AC_CONFIG_MACRO_DIR([m4])
 		AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
 		AC_CONFIG_SRCDIR([lemon/list_graph.h])
 		AC_CONFIG_HEADERS([config.h lemon/config.h])
 		lx_cmdline_cxxflags_set=${CXXFLAGS+set}
 		dnl Checks for programs.
 		AC_PROG_CXX
 		AC_PROG_CXXCPP
 		AC_PROG_INSTALL
 		AC_DISABLE_SHARED
 		AC_PROG_LIBTOOL
 		AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
 		AC_CHECK_PROG([gs_found],[gs],[yes],[no])
 		dnl Set custom compiler flags when using g++.
 		if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then
 		  CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
 		fi
 		dnl Checks for libraries.
 		LX_CHECK_GLPK
 		LX_CHECK_CPLEX
 		LX_CHECK_SOPLEX
 		dnl Disable/enable building the demo programs.
 		AC_ARG_ENABLE([demo],
 		AS_HELP_STRING([--enable-demo], [build the demo programs])
 		AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
 		              [], [enable_demo=no])
 		AC_MSG_CHECKING([whether to build the demo programs])
 		if test x"$enable_demo" != x"no"; then
 		  AC_MSG_RESULT([yes])
 		else
 		  AC_MSG_RESULT([no])
 		fi
 		AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
 		dnl Disable/enable building the binary tools.
 		AC_ARG_ENABLE([tools],
 		AS_HELP_STRING([--enable-tools], [build additional tools @<:@default@:>@])
 		AS_HELP_STRING([--disable-tools], [do not build additional tools]),
 		              [], [enable_tools=yes])
 		AC_MSG_CHECKING([whether to build the additional tools])
 		if test x"$enable_tools" != x"no"; then
 		  AC_MSG_RESULT([yes])
 		else
 		  AC_MSG_RESULT([no])
 		fi
 		AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
 		dnl Disable/enable building the benchmarks.
 		AC_ARG_ENABLE([benchmark],
 		AS_HELP_STRING([--enable-benchmark], [build the benchmarks])
 		AS_HELP_STRING([--disable-benchmark], [do not build the benchmarks @<:@default@:>@]),
 		              [], [enable_benchmark=no])
 		AC_MSG_CHECKING([whether to build the benchmarks])
 		if test x"$enable_benchmark" != x"no"; then
 		  AC_MSG_RESULT([yes])
 		else
 		  AC_MSG_RESULT([no])
 		fi
 		AM_CONDITIONAL([WANT_BENCHMARK], [test x"$enable_benchmark" != x"no"])
 		dnl Checks for header files.
 		AC_CHECK_HEADERS(limits.h sys/time.h sys/times.h unistd.h)
 		dnl Checks for typedefs, structures, and compiler characteristics.
 		AC_C_CONST
 		AC_C_INLINE
 		AC_TYPE_SIZE_T
 		AC_HEADER_TIME
 		AC_STRUCT_TM
 		dnl Checks for library functions.
 		AC_HEADER_STDC
 		AC_CHECK_FUNCS(gettimeofday times ctime_r)
 		dnl Add dependencies on files generated by configure.
 		AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
 		  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in'])
 		AC_CONFIG_FILES([
 		Makefile
 		doc/Doxyfile
 		lemon/lemon.pc
 		])
 		AC_OUTPUT
 		echo
 		echo '****************************** SUMMARY ******************************'
 		echo
 		echo Package version............... : $PACKAGE-$VERSION
 		echo
 		echo C++ compiler.................. : $CXX
 		echo C++ compiles flags............ : $CXXFLAGS
 		echo
 		echo GLPK support.................. : $lx_glpk_found
 		echo CPLEX support................. : $lx_cplex_found
 		echo SOPLEX support................ : $lx_soplex_found
 		echo
 		echo Build benchmarks.............. : $enable_benchmark
 		echo Build demo programs........... : $enable_demo
 		echo Build additional tools........ : $enable_tools
 		echo
 		echo The packace will be installed in
 		echo -n '  '
 		echo $prefix.
 		echo
 		echo '*********************************************************************'
 		echo
 		echo Configure complete, now type \'make\' and then \'make install\'.
 		echo

doc/groups.dox

Show inline comments

@@ -72,492 +72,492 @@
 		@ingroup datas
 		\brief Map structures implemented in LEMON.
 		This group describes the map structures implemented in LEMON.
 		LEMON provides several special purpose maps that e.g. combine
 		new maps from existing ones.
 		*/
 		/**
 		@defgroup graph_maps Graph Maps
 		@ingroup maps
 		\brief Special graph-related maps.
 		This group describes maps that are specifically designed to assign
 		values to the nodes and arcs of graphs.
 		*/
 		/**
 		\defgroup map_adaptors Map Adaptors
 		\ingroup maps
 		\brief Tools to create new maps from existing ones
 		This group describes map adaptors that are used to create "implicit"
 		maps from other maps.
 		Most of them are \ref lemon::concepts::ReadMap "read-only maps".
 		They can make arithmetic and logical operations between one or two maps
 		(negation, shifting, addition, multiplication, logical 'and', 'or',
 		'not' etc.) or e.g. convert a map to another one of different Value type.
 		The typical usage of this classes is passing implicit maps to
 		algorithms.  If a function type algorithm is called then the function
 		type map adaptors can be used comfortable. For example let's see the
 		usage of map adaptors with the \c digraphToEps() function.
 		\code
 		  Color nodeColor(int deg) {
 		    if (deg >= 2) {
 		      return Color(0.5, 0.0, 0.5);
 		    } else if (deg == 1) {
 		      return Color(1.0, 0.5, 1.0);
 		    } else {
 		      return Color(0.0, 0.0, 0.0);
+		    }
+		  }
 		  Digraph::NodeMap<int> degree_map(graph);
 		  digraphToEps(graph, "graph.eps")
 		    .coords(coords).scaleToA4().undirected()
 		    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
 		    .run();
 		\endcode
 		The \c functorToMap() function makes an \c int to \c Color map from the
 		\e nodeColor() function. The \c composeMap() compose the \e degree_map
 		and the previously created map. The composed map is a proper function to
 		get the color of each node.
 		The usage with class type algorithms is little bit harder. In this
 		case the function type map adaptors can not be used, because the
 		function map adaptors give back temporary objects.
 		\code
 		  Digraph graph;
 		  typedef Digraph::ArcMap<double> DoubleArcMap;
 		  DoubleArcMap length(graph);
 		  DoubleArcMap speed(graph);
 		  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
 		  TimeMap time(length, speed);
 		  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 		  dijkstra.run(source, target);
 		\endcode
 		We have a length map and a maximum speed map on the arcs of a digraph.
 		The minimum time to pass the arc can be calculated as the division of
 		the two maps which can be done implicitly with the \c DivMap template
 		class. We use the implicit minimum time map as the length map of the
 		\c Dijkstra algorithm.
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group describes two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief Path structures implemented in LEMON.
 		This group describes the path structures implemented in LEMON.
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
 		\sa lemon::concepts::Path
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group describes some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group describes the several algorithms
 		implemented in LEMON.
 		This group describes the several algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
 		This group describes the common graph search algorithms like
 		Breadth-first search (Bfs) and Depth-first search (Dfs).
 		*/
 		/**
 		@defgroup shortest_path Shortest Path algorithms
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
 		This group describes the algorithms for finding shortest paths in graphs.
 		*/
 		/**
 		@defgroup max_flow Maximum Flow algorithms
 		@ingroup algs
 		\brief Algorithms for finding maximum flows.
 		This group describes the algorithms for finding maximum flows and
 		feasible circulations.
 		The maximum flow problem is to find a flow between a single source and
 		a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
 		directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
 		function and given \f$s, t \in V\f$ source and target node. The
 		maximum flow is the \f$f_a\f$ solution of the next optimization problem:
 		\f[ 0 \le f_a \le c_a \f]
 		\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
 		\qquad \forall u \in V \setminus \{s,t\}\f]
 		\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
 		LEMON contains several algorithms for solving maximum flow problems:
 		- \ref lemon::EdmondsKarp "Edmonds-Karp"
 		- \ref lemon::Preflow "Goldberg's Preflow algorithm"
 		- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
 		- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
 		In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
 		fastest method to compute the maximum flow. All impelementations
 		provides functions to query the minimum cut, which is the dual linear
 		programming problem of the maximum flow.
 		*/
 		/**
 		@defgroup min_cost_flow Minimum Cost Flow algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost flows and circulations.
 		This group describes the algorithms for finding minimum cost flows and
 		circulations.
 		*/
 		/**
 		@defgroup min_cut Minimum Cut algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cut in graphs.
 		This group describes the algorithms for finding minimum cut in graphs.
 		The minimum cut problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the vertices with minimum overall capacity on
 		outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
 		\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		cut is the \f$X\f$ solution of the next optimization problem:
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
 		\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
 		LEMON contains several algorithms related to minimum cut problems:
 		- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
 		  in directed graphs
 		- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
 		  calculate minimum cut in undirected graphs
 		- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
 		  pairs minimum cut in undirected graphs
 		If you want to find minimum cut just between two distinict nodes,
 		please see the \ref max_flow "Maximum Flow page".
 		*/
 		/**
 		@defgroup graph_prop Connectivity and other graph properties
 		@ingroup algs
 		\brief Algorithms for discovering the graph properties
 		This group describes the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		*/
 		/**
 		@defgroup planar Planarity embedding and drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This group describes the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
 		@defgroup matching Matching algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains algorithm objects and functions to calculate
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the arcs which does not shares common endpoints.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be the finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
-		Lemon contains the next algorithms:
+		LEMON contains the next algorithms:
 		- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
 		  augmenting path algorithm for calculate maximum cardinality matching in
 		  bipartite graphs
 		- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
 		  algorithm for calculate maximum cardinality matching in bipartite graphs
 		- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
 		  Successive shortest path algorithm for calculate maximum weighted matching
 		  and maximum weighted bipartite matching in bipartite graph
 		- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
 		  Successive shortest path algorithm for calculate minimum cost maximum
 		  matching in bipartite graph
 		- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
 		  for calculate maximum cardinality matching in general graph
 		- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
 		  shrinking algorithm for calculate maximum weighted matching in general
 		  graph
 		- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
 		  Edmond's blossom shrinking algorithm for calculate maximum weighted
 		  perfect matching in general graph
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree algorithms
 		@ingroup algs
 		\brief Algorithms for finding a minimum cost spanning tree in a graph.
 		This group describes the algorithms for finding a minimum cost spanning
 		tree in a graph
 		*/
 		/**
 		@defgroup auxalg Auxiliary algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
 		This group describes some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
 		@defgroup approx Approximation algorithms
 		\brief Approximation algorithms.
 		This group describes the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group describes some general optimization frameworks
 		implemented in LEMON.
 		This group describes some general optimization frameworks
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup lp_group Lp and Mip solvers
 		@ingroup gen_opt_group
 		\brief Lp and Mip solver interfaces for LEMON.
 		This group describes Lp and Mip solver interfaces for LEMON. The
 		various LP solvers could be used in the same manner with this
 		interface.
 		*/
 		/**
 		@defgroup lp_utils Tools for Lp and Mip solvers
 		@ingroup lp_group
 		\brief Helper tools to the Lp and Mip solvers.
 		This group adds some helper tools to general optimization framework
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup metah Metaheuristics
 		@ingroup gen_opt_group
 		\brief Metaheuristics for LEMON library.
 		This group describes some metaheuristic optimization tools.
 		*/
 		/**
 		@defgroup utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
 		This group describes some simple basic graph utilities.
 		*/
 		/**
 		@defgroup misc Miscellaneous Tools
 		@ingroup utils
 		\brief Tools for development, debugging and testing.
 		This group describes several useful tools for development,
 		debugging and testing.
 		*/
 		/**
 		@defgroup timecount Time measuring and Counting
 		@ingroup misc
 		\brief Simple tools for measuring the performance of algorithms.
 		This group describes simple tools for measuring the performance
 		of algorithms.
 		*/
 		/**
 		@defgroup graphbits Tools for Graph Implementation
 		@ingroup utils
 		\brief Tools to make it easier to create graphs.
 		This group describes the tools that makes it easier to create graphs and
 		the maps that dynamically update with the graph changes.
 		*/
 		/**
 		@defgroup exceptions Exceptions
 		@ingroup utils
 		\brief Exceptions defined in LEMON.
 		This group describes the exceptions defined in LEMON.
 		*/
 		/**
 		@defgroup io_group Input-Output
 		\brief Graph Input-Output methods
 		This group describes the tools for importing and exporting graphs
 		and graph related data. Now it supports the LEMON format, the
 		\c DIMACS format and the encapsulated postscript (EPS) format.
 		*/
 		/**
-		@defgroup lemon_io Lemon Input-Output
+		@defgroup lemon_io LEMON Input-Output
 		@ingroup io_group
-		\brief Reading and writing \ref lgf-format "Lemon Graph Format".
+		\brief Reading and writing \ref lgf-format "LEMON Graph Format".
 		This group describes methods for reading and writing
-		\ref lgf-format "Lemon Graph Format".
+		\ref lgf-format "LEMON Graph Format".
 		*/
 		/**
 		@defgroup eps_io Postscript exporting
 		@ingroup io_group
 		\brief General \c EPS drawer and graph exporter
 		This group describes general \c EPS drawing methods and special
 		graph exporting tools.
 		*/
 		/**
 		@defgroup concept Concepts
 		\brief Skeleton classes and concept checking classes
 		This group describes the data/algorithm skeletons and concept checking
 		classes implemented in LEMON.
 		The purpose of the classes in this group is fourfold.
 		- These classes contain the documentations of the concepts. In order
 		  to avoid document multiplications, an implementation of a concept
 		  simply refers to the corresponding concept class.
 		- These classes declare every functions, <tt>typedef</tt>s etc. an
 		  implementation of the concepts should provide, however completely
 		  without implementations and real data structures behind the
 		  interface. On the other hand they should provide nothing else. All
 		  the algorithms working on a data structure meeting a certain concept
 		  should compile with these classes. (Though it will not run properly,
 		  of course.) In this way it is easily to check if an algorithm
 		  doesn't use any extra feature of a certain implementation.
 		- The concept descriptor classes also provide a <em>checker class</em>
 		  that makes it possible to check whether a certain implementation of a
 		  concept indeed provides all the required features.
 		- Finally, They can serve as a skeleton of a new implementation of a concept.
 		*/
 		/**
 		@defgroup graph_concepts Graph Structure Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for graph structures
 		This group describes the skeletons and concept checking classes of LEMON's
 		graph structures and helper classes used to implement these.
 		*/
 		/* --- Unused group
 		@defgroup experimental Experimental Structures and Algorithms
 		This group describes some Experimental structures and algorithms.
 		The stuff here is subject to change.
 		*/
 		/**
 		\anchor demoprograms
 		@defgroup demos Demo programs
 		Some demo programs are listed here. Their full source codes can be found in
 		the \c demo subdirectory of the source tree.
 		It order to compile them, use <tt>--enable-demo</tt> configure option when
 		build the library.
 		*/
 		/**
 		@defgroup tools Standalone utility applications
 		Some utility applications are listed here.
 		The standard compilation procedure (<tt>./configure;make</tt>) will compile
 		them, as well.
 		*/

doc/lgf.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-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.
+		 *
 		 */
 		namespace lemon {
 		/*!
-		\page lgf-format Lemon Graph Format (LGF)
+		\page lgf-format LEMON Graph Format (LGF)
 		The \e LGF is a <em>column oriented</em>
 		file format for storing graphs and associated data like
 		node and edge maps.
 		Each line with \c '#' first non-whitespace
 		character is considered as a comment line.
 		Otherwise the file consists of sections starting with
 		a header line. The header lines starts with an \c '@' character followed by the
 		type of section. The standard section types are \c \@nodes, \c
 		\@arcs and \c \@edges
 		and \@attributes. Each header line may also have an optional
 		\e name, which can be use to distinguish the sections of the same
 		type.
 		The standard sections are column oriented, each line consists of
 		<em>token</em>s separated by whitespaces. A token can be \e plain or
 		\e quoted. A plain token is just a sequence of non-whitespace characters,
 		while a quoted token is a
 		character sequence surrounded by double quotes, and it can also
 		contain whitespaces and escape sequences.
 		The \c \@nodes section describes a set of nodes and associated
 		maps. The first is a header line, its columns are the names of the
 		maps appearing in the following lines.
 		One of the maps must be called \c
 		"label", which plays special role in the file.
 		The following
 		non-empty lines until the next section describes nodes of the
 		graph. Each line contains the values of the node maps
 		associated to the current node.
 		\code
 		 @nodes
 		 label  coordinates  size    title
 (10,20)      10      "First node"
 (80,80)      8       "Second node"
 (40,10)      10      "Third node"
 		\endcode
 		The \c \@arcs section is very similar to the \c \@nodes section,
 		it again starts with a header line describing the names of the maps,
 		but the \c "label" map is not obligatory here. The following lines
 		describe the arcs. The first two tokens of each line are
 		the source and the target node of the arc, respectively, then come the map
 		values. The source and target tokens must be node labels.
 		\code
 		 @arcs
 		         capacity
 2   16
 3   12
 3   18
 		\endcode
 		The \c \@edges is just a synonym of \c \@arcs. The @arcs section can
 		also store the edge set of an undirected graph. In such case there is
 		a conventional method for store arc maps in the file, if two columns
 		has the same caption with \c '+' and \c '-' prefix, then these columns
 		can be regarded as the values of an arc map.
 		The \c \@attributes section contains key-value pairs, each line
 		consists of two tokens, an attribute name, and then an attribute
 		value. The value of the attribute could be also a label value of a
 		node or an edge, or even an edge label prefixed with \c '+' or \c '-',
 		which regards to the forward or backward directed arc of the
 		corresponding edge.
 		\code
 		 @attributes
 		 source 1
 		 target 3
 		 caption "LEMON test digraph"
 		\endcode
 		The \e LGF can contain extra sections, but there is no restriction on
 		the format of such sections.
 		*/
+		}
 		//  LocalWords:  whitespace whitespaces

lemon/bits/alteration_notifier.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-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_BITS_ALTERATION_NOTIFIER_H
 		#define LEMON_BITS_ALTERATION_NOTIFIER_H
 		#include <vector>
 		#include <list>
 		#include <lemon/core.h>
 		///\ingroup graphbits
 		///\file
 		///\brief Observer notifier for graph alteration observers.
 		namespace lemon {
 		  /// \ingroup graphbits
 		  ///
 		  /// \brief Notifier class to notify observes about alterations in
 		  /// a container.
 		  ///
 		  /// The simple graph's can be refered as two containers, one node container
 		  /// and one edge container. But they are not standard containers they
 		  /// does not store values directly they are just key continars for more
 		  /// value containers which are the node and edge maps.
 		  ///
 		  /// The graph's node and edge sets can be changed as we add or erase
-		  /// nodes and edges in the graph. Lemon would like to handle easily
+		  /// nodes and edges in the graph. LEMON would like to handle easily
 		  /// that the node and edge maps should contain values for all nodes or
 		  /// edges. If we want to check on every indicing if the map contains
 		  /// the current indicing key that cause a drawback in the performance
 		  /// in the library. We use another solution we notify all maps about
 		  /// an alteration in the graph, which cause only drawback on the
 		  /// alteration of the graph.
 		  ///
 		  /// This class provides an interface to the container. The \e first() and \e
 		  /// next() member functions make possible to iterate on the keys of the
 		  /// container. The \e id() function returns an integer id for each key.
 		  /// The \e maxId() function gives back an upper bound of the ids.
 		  ///
 		  /// For the proper functonality of this class, we should notify it
 		  /// about each alteration in the container. The alterations have four type
 		  /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
 		  /// \e erase() signals that only one or few items added or erased to or
 		  /// from the graph. If all items are erased from the graph or from an empty
 		  /// graph a new graph is builded then it can be signaled with the
 		  /// clear() and build() members. Important rule that if we erase items
 		  /// from graph we should first signal the alteration and after that erase
 		  /// them from the container, on the other way on item addition we should
 		  /// first extend the container and just after that signal the alteration.
 		  ///
 		  /// The alteration can be observed with a class inherited from the
 		  /// \e ObserverBase nested class. The signals can be handled with
 		  /// overriding the virtual functions defined in the base class.  The
 		  /// observer base can be attached to the notifier with the
 		  /// \e attach() member and can be detached with detach() function. The
 		  /// alteration handlers should not call any function which signals
 		  /// an other alteration in the same notifier and should not
 		  /// detach any observer from the notifier.
 		  ///
 		  /// Alteration observers try to be exception safe. If an \e add() or
 		  /// a \e clear() function throws an exception then the remaining
 		  /// observeres will not be notified and the fulfilled additions will
 		  /// be rolled back by calling the \e erase() or \e clear()
 		  /// functions. Thence the \e erase() and \e clear() should not throw
 		  /// exception. Actullay, it can be throw only
 		  /// \ref AlterationObserver::ImmediateDetach ImmediateDetach
 		  /// exception which detach the observer from the notifier.
 		  ///
 		  /// There are some place when the alteration observing is not completly
 		  /// reliable. If we want to carry out the node degree in the graph
 		  /// as in the \ref InDegMap and we use the reverseEdge that cause
 		  /// unreliable functionality. Because the alteration observing signals
 		  /// only erasing and adding but not the reversing it will stores bad
 		  /// degrees. The sub graph adaptors cannot signal the alterations because
 		  /// just a setting in the filter map can modify the graph and this cannot
 		  /// be watched in any way.
 		  ///
 		  /// \param _Container The container which is observed.
 		  /// \param _Item The item type which is obserbved.
 		  template <typename _Container, typename _Item>
 		  class AlterationNotifier {
 		  public:
 		    typedef True Notifier;
 		    typedef _Container Container;
 		    typedef _Item Item;
 		    /// \brief Exception which can be called from \e clear() and
 		    /// \e erase().
 		    ///
 		    /// From the \e clear() and \e erase() function only this
 		    /// exception is allowed to throw. The exception immediatly
 		    /// detaches the current observer from the notifier. Because the
 		    /// \e clear() and \e erase() should not throw other exceptions
 		    /// it can be used to invalidate the observer.
 		    struct ImmediateDetach {};
 		    /// \brief ObserverBase is the base class for the observers.
 		    ///
 		    /// ObserverBase is the abstract base class for the observers.
 		    /// It will be notified about an item was inserted into or
 		    /// erased from the graph.
 		    ///
 		    /// The observer interface contains some pure virtual functions
 		    /// to override. The add() and erase() functions are
 		    /// to notify the oberver when one item is added or
 		    /// erased.
 		    ///
 		    /// The build() and clear() members are to notify the observer
 		    /// about the container is built from an empty container or
 		    /// is cleared to an empty container.
 		    class ObserverBase {
 		    protected:
 		      typedef AlterationNotifier Notifier;
 		      friend class AlterationNotifier;
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor for ObserverBase.
 		      ///
 		      ObserverBase() : _notifier(0) {}
 		      /// \brief Constructor which attach the observer into notifier.
 		      ///
 		      /// Constructor which attach the observer into notifier.
 		      ObserverBase(AlterationNotifier& nf) {
 		        attach(nf);
+		      }
 		      /// \brief Constructor which attach the obserever to the same notifier.
 		      ///
 		      /// Constructor which attach the obserever to the same notifier as
 		      /// the other observer is attached to.
 		      ObserverBase(const ObserverBase& copy) {
 		        if (copy.attached()) {
 		          attach(*copy.notifier());
+		        }
+		      }
 		      /// \brief Destructor
 		      virtual ~ObserverBase() {
 		        if (attached()) {
 		          detach();
+		        }
+		      }
 		      /// \brief Attaches the observer into an AlterationNotifier.
 		      ///
 		      /// This member attaches the observer into an AlterationNotifier.
 		      ///
 		      void attach(AlterationNotifier& nf) {
 		        nf.attach(*this);
+		      }
 		      /// \brief Detaches the observer into an AlterationNotifier.
 		      ///
 		      /// This member detaches the observer from an AlterationNotifier.
 		      ///
 		      void detach() {
 		        _notifier->detach(*this);
+		      }
 		      /// \brief Gives back a pointer to the notifier which the map
 		      /// attached into.
 		      ///
 		      /// This function gives back a pointer to the notifier which the map
 		      /// attached into.
 		      ///
 		      Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }
 		      /// Gives back true when the observer is attached into a notifier.
 		      bool attached() const { return _notifier != 0; }
 		    private:
 		      ObserverBase& operator=(const ObserverBase& copy);
 		    protected:
 		      Notifier* _notifier;
 		      typename std::list<ObserverBase*>::iterator _index;
 		      /// \brief The member function to notificate the observer about an
 		      /// item is added to the container.
 		      ///
 		      /// The add() member function notificates the observer about an item
 		      /// is added to the container. It have to be overrided in the
 		      /// subclasses.
 		      virtual void add(const Item&) = 0;
 		      /// \brief The member function to notificate the observer about
 		      /// more item is added to the container.
 		      ///
 		      /// The add() member function notificates the observer about more item
 		      /// is added to the container. It have to be overrided in the
 		      /// subclasses.
 		      virtual void add(const std::vector<Item>& items) = 0;
 		      /// \brief The member function to notificate the observer about an
 		      /// item is erased from the container.
 		      ///
 		      /// The erase() member function notificates the observer about an
 		      /// item is erased from the container. It have to be overrided in
 		      /// the subclasses.
 		      virtual void erase(const Item&) = 0;
 		      /// \brief The member function to notificate the observer about
 		      /// more item is erased from the container.
 		      ///
 		      /// The erase() member function notificates the observer about more item
 		      /// is erased from the container. It have to be overrided in the
 		      /// subclasses.
 		      virtual void erase(const std::vector<Item>& items) = 0;
 		      /// \brief The member function to notificate the observer about the
 		      /// container is built.
 		      ///
 		      /// The build() member function notificates the observer about the
 		      /// container is built from an empty container. It have to be
 		      /// overrided in the subclasses.
 		      virtual void build() = 0;
 		      /// \brief The member function to notificate the observer about all
 		      /// items are erased from the container.
 		      ///
 		      /// The clear() member function notificates the observer about all
 		      /// items are erased from the container. It have to be overrided in
 		      /// the subclasses.
 		      virtual void clear() = 0;
 		    };
 		  protected:
 		    const Container* container;
 		    typedef std::list<ObserverBase*> Observers;
 		    Observers _observers;
 		  public:
 		    /// \brief Default constructor.
 		    ///
 		    /// The default constructor of the AlterationNotifier.
 		    /// It creates an empty notifier.
 		    AlterationNotifier()
 		      : container(0) {}
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor with the observed container parameter.
 		    AlterationNotifier(const Container& _container)
 		      : container(&_container) {}
 		    /// \brief Copy Constructor of the AlterationNotifier.
 		    ///
 		    /// Copy constructor of the AlterationNotifier.
 		    /// It creates only an empty notifier because the copiable
 		    /// notifier's observers have to be registered still into that notifier.
 		    AlterationNotifier(const AlterationNotifier& _notifier)
 		      : container(_notifier.container) {}
 		    /// \brief Destructor.
 		    ///
 		    /// Destructor of the AlterationNotifier.
 		    ///
 		    ~AlterationNotifier() {
 		      typename Observers::iterator it;
 		      for (it = _observers.begin(); it != _observers.end(); ++it) {
 		        (*it)->_notifier = 0;
+		      }
+		    }
 		    /// \brief Sets the container.
 		    ///
 		    /// Sets the container.
 		    void setContainer(const Container& _container) {

lemon/concepts/path.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-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.
+		 *
 		 */
 		///\ingroup concept
 		///\file
 		///\brief Classes for representing paths in digraphs.
 		///
 		///\todo Iterators have obsolete style
 		#ifndef LEMON_CONCEPT_PATH_H
 		#define LEMON_CONCEPT_PATH_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief A skeleton structure for representing directed paths in
 		    /// a digraph.
 		    ///
 		    /// A skeleton structure for representing directed paths in a
 		    /// digraph.
 		    /// \tparam _Digraph The digraph type in which the path is.
 		    ///
 		    /// In a sense, the path can be treated as a list of arcs. The
 		    /// lemon path type stores just this list. As a consequence it
 		    /// cannot enumerate the nodes in the path and the zero length
 		    /// paths cannot store the source.
 		    ///
 		    template <typename _Digraph>
 		    class Path {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef _Digraph Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
 		      class ArcIt;
 		      /// \brief Default constructor
 		      Path() {}
 		      /// \brief Template constructor
 		      template <typename CPath>
 		      Path(const CPath& cpath) {}
 		      /// \brief Template assigment
 		      template <typename CPath>
 		      Path& operator=(const CPath& cpath) {}
 		      /// Length of the path ie. the number of arcs in the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// Resets the path to an empty path.
 		      void clear() {}
-		      /// \brief Lemon style iterator for path arcs
+		      /// \brief LEMON style iterator for path arcs
 		      ///
 		      /// This class is used to iterate on the arcs of the paths.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
 		        /// Constructor for first arc
 		        ArcIt(const Path &) {}
 		        /// Conversion to Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          Path<Digraph> pc;
 		          _Path p, pp(pc);
 		          int l = p.length();
 		          int e = p.empty();
 		          p.clear();
 		          p = pc;
 		          typename _Path::ArcIt id, ii(INVALID), i(p);
 		          ++i;
 		          typename Digraph::Arc ed = i;
 		          e = (i == ii);
 		          e = (i != ii);
 		          e = (i < ii);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(pp);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ii);
 		          ignore_unused_variable_warning(ed);
+		        }
 		      };
 		    };
 		    namespace _path_bits {
 		      template <typename _Digraph, typename _Path, typename RevPathTag = void>
 		      struct PathDumperConstraints {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::ArcIt id, i(p);
 		          ++i;
 		          typename _Digraph::Arc ed = i;
 		          e = (i == INVALID);
 		          e = (i != INVALID);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ed);
+		        }
 		        _Path& p;
 		      };
 		      template <typename _Digraph, typename _Path>
 		      struct PathDumperConstraints<
 		        _Digraph, _Path,
 		        typename enable_if<typename _Path::RevPathTag, void>::type
 		      > {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::RevArcIt id, i(p);
 		          ++i;
 		          typename _Digraph::Arc ed = i;
 		          e = (i == INVALID);
 		          e = (i != INVALID);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ed);
+		        }
 		        _Path& p;
 		      };
+		    }
 		    /// \brief A skeleton structure for path dumpers.
 		    ///
 		    /// A skeleton structure for path dumpers. The path dumpers are
 		    /// the generalization of the paths. The path dumpers can
 		    /// enumerate the arcs of the path wheter in forward or in
 		    /// backward order.  In most time these classes are not used
 		    /// directly rather it used to assign a dumped class to a real
 		    /// path type.
 		    ///
 		    /// The main purpose of this concept is that the shortest path
 		    /// algorithms can enumerate easily the arcs in reverse order.
 		    /// If we would like to give back a real path from these
 		    /// algorithms then we should create a temporarly path object. In
-		    /// Lemon such algorithms gives back a path dumper what can
+		    /// LEMON such algorithms gives back a path dumper what can
 		    /// assigned to a real path and the dumpers can be implemented as
 		    /// an adaptor class to the predecessor map.
 		    /// \tparam _Digraph  The digraph type in which the path is.
 		    ///
 		    /// The paths can be constructed from any path type by a
 		    /// template constructor or a template assignment operator.
 		    ///
 		    template <typename _Digraph>
 		    class PathDumper {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef _Digraph Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
 		      /// Length of the path ie. the number of arcs in the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// \brief Forward or reverse dumping
 		      ///
 		      /// If the RevPathTag is defined and true then reverse dumping
 		      /// is provided in the path dumper. In this case instead of the
 		      /// ArcIt the RevArcIt iterator should be implemented in the
 		      /// dumper.
 		      typedef False RevPathTag;
-		      /// \brief Lemon style iterator for path arcs
+		      /// \brief LEMON style iterator for path arcs
 		      ///
 		      /// This class is used to iterate on the arcs of the paths.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
 		        /// Constructor for first arc
 		        ArcIt(const PathDumper&) {}
 		        /// Conversion to Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
-		      /// \brief Lemon style iterator for path arcs
+		      /// \brief LEMON style iterator for path arcs
 		      ///
 		      /// This class is used to iterate on the arcs of the paths in
 		      /// reverse direction.
 		      class RevArcIt {
 		      public:
 		        /// Default constructor
 		        RevArcIt() {}
 		        /// Invalid constructor
 		        RevArcIt(Invalid) {}
 		        /// Constructor for first arc
 		        RevArcIt(const PathDumper &) {}
 		        /// Conversion to Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        RevArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const RevArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const RevArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const RevArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          function_requires<_path_bits::
 		            PathDumperConstraints<Digraph, _Path> >();
+		        }
 		      };
 		    };
 		    ///@}
+		  }
 		} // namespace lemon
 		#endif // LEMON_CONCEPT_PATH_H

lemon/lgf_reader.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-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.
+		 *
 		 */
 		///\ingroup lemon_io
 		///\file
-		///\brief \ref lgf-format "Lemon Graph Format" reader.
+		///\brief \ref lgf-format "LEMON Graph Format" reader.
 		#ifndef LEMON_LGF_READER_H
 		#define LEMON_LGF_READER_H
 		#include <iostream>
 		#include <fstream>
 		#include <sstream>
 		#include <set>
 		#include <map>
 		#include <lemon/assert.h>
 		#include <lemon/core.h>
 		#include <lemon/lgf_writer.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		namespace lemon {
 		  namespace _reader_bits {
 		    template <typename Value>
 		    struct DefaultConverter {
 		      Value operator()(const std::string& str) {
 		        std::istringstream is(str);
 		        Value value;
 		        is >> value;
 		        char c;
 		        if (is >> std::ws >> c) {
 		          throw DataFormatError("Remaining characters in token");
+		        }
 		        return value;
+		      }
 		    };
 		    template <>
 		    struct DefaultConverter<std::string> {
 		      std::string operator()(const std::string& str) {
 		        return str;
+		      }
 		    };
 		    template <typename _Item>
 		    class MapStorageBase {
 		    public:
 		      typedef _Item Item;
 		    public:
 		      MapStorageBase() {}
 		      virtual ~MapStorageBase() {}
 		      virtual void set(const Item& item, const std::string& value) = 0;
 		    };
 		    template <typename _Item, typename _Map,
 		              typename _Converter = DefaultConverter<typename _Map::Value> >
 		    class MapStorage : public MapStorageBase<_Item> {
 		    public:
 		      typedef _Map Map;
 		      typedef _Converter Converter;
 		      typedef _Item Item;
 		    private:
 		      Map& _map;
 		      Converter _converter;
 		    public:
 		      MapStorage(Map& map, const Converter& converter = Converter())
 		        : _map(map), _converter(converter) {}
 		      virtual ~MapStorage() {}
 		      virtual void set(const Item& item ,const std::string& value) {
 		        _map.set(item, _converter(value));
+		      }
 		    };
 		    template <typename _Graph, bool _dir, typename _Map,
 		              typename _Converter = DefaultConverter<typename _Map::Value> >
 		    class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
 		    public:
 		      typedef _Map Map;
 		      typedef _Converter Converter;
 		      typedef _Graph Graph;
 		      typedef typename Graph::Edge Item;
 		      static const bool dir = _dir;
 		    private:
 		      const Graph& _graph;
 		      Map& _map;
 		      Converter _converter;
 		    public:
 		      GraphArcMapStorage(const Graph& graph, Map& map,
 		                         const Converter& converter = Converter())
 		        : _graph(graph), _map(map), _converter(converter) {}
 		      virtual ~GraphArcMapStorage() {}
 		      virtual void set(const Item& item ,const std::string& value) {
 		        _map.set(_graph.direct(item, dir), _converter(value));
+		      }
 		    };
 		    class ValueStorageBase {
 		    public:
 		      ValueStorageBase() {}
 		      virtual ~ValueStorageBase() {}
 		      virtual void set(const std::string&) = 0;
 		    };
 		    template <typename _Value, typename _Converter = DefaultConverter<_Value> >
 		    class ValueStorage : public ValueStorageBase {
 		    public:
 		      typedef _Value Value;
 		      typedef _Converter Converter;
 		    private:
 		      Value& _value;
 		      Converter _converter;
 		    public:
 		      ValueStorage(Value& value, const Converter& converter = Converter())
 		        : _value(value), _converter(converter) {}
 		      virtual void set(const std::string& value) {
 		        _value = _converter(value);
+		      }
 		    };
 		    template <typename Value>
 		    struct MapLookUpConverter {
 		      const std::map<std::string, Value>& _map;
 		      MapLookUpConverter(const std::map<std::string, Value>& map)
 		        : _map(map) {}
 		      Value operator()(const std::string& str) {
 		        typename std::map<std::string, Value>::const_iterator it =
 		          _map.find(str);
 		        if (it == _map.end()) {
 		          std::ostringstream msg;
 		          msg << "Item not found: " << str;
 		          throw DataFormatError(msg.str().c_str());
+		        }
 		        return it->second;
+		      }
 		    };
 		    template <typename Graph>
 		    struct GraphArcLookUpConverter {
 		      const Graph& _graph;
 		      const std::map<std::string, typename Graph::Edge>& _map;
 		      GraphArcLookUpConverter(const Graph& graph,
 		                              const std::map<std::string,
 		                                             typename Graph::Edge>& map)
 		        : _graph(graph), _map(map) {}
 		      typename Graph::Arc operator()(const std::string& str) {
 		        if (str.empty() || (str[0] != '+' && str[0] != '-')) {
 		          throw DataFormatError("Item must start with '+' or '-'");
+		        }
 		        typename std::map<std::string, typename Graph::Edge>
 		          ::const_iterator it = _map.find(str.substr(1));
 		        if (it == _map.end()) {
 		          throw DataFormatError("Item not found");
+		        }
 		        return _graph.direct(it->second, str[0] == '+');
+		      }
 		    };
 		    inline bool isWhiteSpace(char c) {
 		      return c == ' ' || c == '\t' || c == '\v' ||
 		        c == '\n' || c == '\r' || c == '\f';
+		    }
 		    inline bool isOct(char c) {
 		      return '0' <= c && c <='7';
+		    }
 		    inline int valueOct(char c) {
 		      LEMON_ASSERT(isOct(c), "The character is not octal.");
 		      return c - '0';
+		    }
 		    inline bool isHex(char c) {
 		      return ('0' <= c && c <= '9') ||
 		        ('a' <= c && c <= 'z') ||
 		        ('A' <= c && c <= 'Z');
+		    }
 		    inline int valueHex(char c) {
 		      LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
 		      if ('0' <= c && c <= '9') return c - '0';
 		      if ('a' <= c && c <= 'z') return c - 'a' + 10;
 		      return c - 'A' + 10;
+		    }
 		    inline bool isIdentifierFirstChar(char c) {
 		      return ('a' <= c && c <= 'z') ||
 		        ('A' <= c && c <= 'Z') || c == '_';
+		    }
 		    inline bool isIdentifierChar(char c) {
 		      return isIdentifierFirstChar(c) ||
 		        ('0' <= c && c <= '9');
+		    }
 		    inline char readEscape(std::istream& is) {
 		      char c;
 		      if (!is.get(c))
 		        throw DataFormatError("Escape format error");
 		      switch (c) {
 		      case '\\':
 		        return '\\';
 		      case '\"':
 		        return '\"';
 		      case '\'':
 		        return '\'';
 		      case '\?':
 		        return '\?';
 		      case 'a':
 		        return '\a';
 		      case 'b':
 		        return '\b';
 		      case 'f':
 		        return '\f';
 		      case 'n':
 		        return '\n';
 		      case 'r':
 		        return '\r';
 		      case 't':
 		        return '\t';
 		      case 'v':
 		        return '\v';
 		      case 'x':
+		        {
 		          int code;
 		          if (!is.get(c) || !isHex(c))
 		            throw DataFormatError("Escape format error");
 		          else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
 		          else code = code * 16 + valueHex(c);
 		          return code;
+		        }
 		      default:
+		        {
 		          int code;
 		          if (!isOct(c))
 		            throw DataFormatError("Escape format error");
 		          else if (code = valueOct(c), !is.get(c) || !isOct(c))
@@ -2048,513 +2048,513 @@
 		  /// with two different functions. With the \c sectionLines() function a
 		  /// functor can process the section line-by-line, while with the \c
 		  /// sectionStream() member the section can be read from an input
 		  /// stream.
 		  class SectionReader {
 		  private:
 		    std::istream* _is;
 		    bool local_is;
 		    typedef std::map<std::string, _reader_bits::Section*> Sections;
 		    Sections _sections;
 		    int line_num;
 		    std::istringstream line;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct a section reader, which reads from the given input
 		    /// stream.
 		    SectionReader(std::istream& is)
 		      : _is(&is), local_is(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct a section reader, which reads from the given file.
 		    SectionReader(const std::string& fn)
 		      : _is(new std::ifstream(fn.c_str())), local_is(true) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct a section reader, which reads from the given file.
 		    SectionReader(const char* fn)
 		      : _is(new std::ifstream(fn)), local_is(true) {}
 		    /// \brief Destructor
 		    ~SectionReader() {
 		      for (Sections::iterator it = _sections.begin();
 		           it != _sections.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_is) {
 		        delete _is;
+		      }
+		    }
 		  private:
 		    friend SectionReader sectionReader(std::istream& is);
 		    friend SectionReader sectionReader(const std::string& fn);
 		    friend SectionReader sectionReader(const char* fn);
 		    SectionReader(SectionReader& other)
 		      : _is(other._is), local_is(other.local_is) {
 		      other._is = 0;
 		      other.local_is = false;
 		      _sections.swap(other._sections);
+		    }
 		    SectionReader& operator=(const SectionReader&);
 		  public:
 		    /// \name Section readers
 		    /// @{
 		    /// \brief Add a section processor with line oriented reading
 		    ///
 		    /// The first parameter is the type descriptor of the section, the
 		    /// second is a functor, which takes just one \c std::string
 		    /// parameter. At the reading process, each line of the section
 		    /// will be given to the functor object. However, the empty lines
 		    /// and the comment lines are filtered out, and the leading
 		    /// whitespaces are trimmed from each processed string.
 		    ///
 		    /// For example let's see a section, which contain several
 		    /// integers, which should be inserted into a vector.
 		    ///\code
 		    ///  @numbers
 		    ///  12 45 23
 		    ///  4
 		    ///  23 6
 		    ///\endcode
 		    ///
 		    /// The functor is implemented as a struct:
 		    ///\code
 		    ///  struct NumberSection {
 		    ///    std::vector<int>& _data;
 		    ///    NumberSection(std::vector<int>& data) : _data(data) {}
 		    ///    void operator()(const std::string& line) {
 		    ///      std::istringstream ls(line);
 		    ///      int value;
 		    ///      while (ls >> value) _data.push_back(value);
 		    ///    }
 		    ///  };
 		    ///
 		    ///  // ...
 		    ///
 		    ///  reader.sectionLines("numbers", NumberSection(vec));
 		    ///\endcode
 		    template <typename Functor>
 		    SectionReader& sectionLines(const std::string& type, Functor functor) {
 		      LEMON_ASSERT(!type.empty(), "Type is empty.");
 		      LEMON_ASSERT(_sections.find(type) == _sections.end(),
 		                   "Multiple reading of section.");
 		      _sections.insert(std::make_pair(type,
 		        new _reader_bits::LineSection<Functor>(functor)));
 		      return *this;
+		    }
 		    /// \brief Add a section processor with stream oriented reading
 		    ///
 		    /// The first parameter is the type of the section, the second is
 		    /// a functor, which takes an \c std::istream& and an \c int&
 		    /// parameter, the latter regard to the line number of stream. The
 		    /// functor can read the input while the section go on, and the
 		    /// line number should be modified accordingly.
 		    template <typename Functor>
 		    SectionReader& sectionStream(const std::string& type, Functor functor) {
 		      LEMON_ASSERT(!type.empty(), "Type is empty.");
 		      LEMON_ASSERT(_sections.find(type) == _sections.end(),
 		                   "Multiple reading of section.");
 		      _sections.insert(std::make_pair(type,
 		         new _reader_bits::StreamSection<Functor>(functor)));
 		      return *this;
+		    }
 		    /// @}
 		  private:
 		    bool readLine() {
 		      std::string str;
 		      while(++line_num, std::getline(*_is, str)) {
 		        line.clear(); line.str(str);
 		        char c;
 		        if (line >> std::ws >> c && c != '#') {
 		          line.putback(c);
 		          return true;
+		        }
+		      }
 		      return false;
+		    }
 		    bool readSuccess() {
 		      return static_cast<bool>(*_is);
+		    }
 		    void skipSection() {
 		      char c;
 		      while (readSuccess() && line >> c && c != '@') {
 		        readLine();
+		      }
 		      line.putback(c);
+		    }
 		  public:
 		    /// \name Execution of the reader
 		    /// @{
 		    /// \brief Start the batch processing
 		    ///
 		    /// This function starts the batch processing.
 		    void run() {
 		      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
 		      std::set<std::string> extra_sections;
 		      line_num = 0;
 		      readLine();
 		      skipSection();
 		      while (readSuccess()) {
 		        try {
 		          char c;
 		          std::string section, caption;
 		          line >> c;
 		          _reader_bits::readToken(line, section);
 		          _reader_bits::readToken(line, caption);
 		          if (line >> c)
 		            throw DataFormatError("Extra character on the end of line");
 		          if (extra_sections.find(section) != extra_sections.end()) {
 		            std::ostringstream msg;
 		            msg << "Multiple occurence of section " << section;
 		            throw DataFormatError(msg.str().c_str());
+		          }
 		          Sections::iterator it = _sections.find(section);
 		          if (it != _sections.end()) {
 		            extra_sections.insert(section);
 		            it->second->process(*_is, line_num);
+		          }
 		          readLine();
 		          skipSection();
 		        } catch (DataFormatError& error) {
 		          error.line(line_num);
 		          throw;
+		        }
+		      }
 		      for (Sections::iterator it = _sections.begin();
 		           it != _sections.end(); ++it) {
 		        if (extra_sections.find(it->first) == extra_sections.end()) {
 		          std::ostringstream os;
 		          os << "Cannot find section: " << it->first;
 		          throw DataFormatError(os.str().c_str());
+		        }
+		      }
+		    }
 		    /// @}
 		  };
 		  /// \brief Return a \ref SectionReader class
 		  ///
 		  /// This function just returns a \ref SectionReader class.
 		  /// \relates SectionReader
 		  inline SectionReader sectionReader(std::istream& is) {
 		    SectionReader tmp(is);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref SectionReader class
 		  ///
 		  /// This function just returns a \ref SectionReader class.
 		  /// \relates SectionReader
 		  inline SectionReader sectionReader(const std::string& fn) {
 		    SectionReader tmp(fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref SectionReader class
 		  ///
 		  /// This function just returns a \ref SectionReader class.
 		  /// \relates SectionReader
 		  inline SectionReader sectionReader(const char* fn) {
 		    SectionReader tmp(fn);
 		    return tmp;
+		  }
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief Reader for the contents of the \ref lgf-format "LGF" file
 		  ///
 		  /// This class can be used to read the sections, the map names and
-		  /// the attributes from a file. Usually, the Lemon programs know
+		  /// the attributes from a file. Usually, the LEMON programs know
 		  /// that, which type of graph, which maps and which attributes
 		  /// should be read from a file, but in general tools (like glemon)
 		  /// the contents of an LGF file should be guessed somehow. This class
 		  /// reads the graph and stores the appropriate information for
 		  /// reading the graph.
 		  ///
 		  ///\code
 		  /// LgfContents contents("graph.lgf");
 		  /// contents.run();
 		  ///
 		  /// // Does it contain any node section and arc section?
 		  /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
 		  ///   std::cerr << "Failure, cannot find graph." << std::endl;
 		  ///   return -1;
 		  /// }
 		  /// std::cout << "The name of the default node section: "
 		  ///           << contents.nodeSection(0) << std::endl;
 		  /// std::cout << "The number of the arc maps: "
 		  ///           << contents.arcMaps(0).size() << std::endl;
 		  /// std::cout << "The name of second arc map: "
 		  ///           << contents.arcMaps(0)[1] << std::endl;
 		  ///\endcode
 		  class LgfContents {
 		  private:
 		    std::istream* _is;
 		    bool local_is;
 		    std::vector<std::string> _node_sections;
 		    std::vector<std::string> _edge_sections;
 		    std::vector<std::string> _attribute_sections;
 		    std::vector<std::string> _extra_sections;
 		    std::vector<bool> _arc_sections;
 		    std::vector<std::vector<std::string> > _node_maps;
 		    std::vector<std::vector<std::string> > _edge_maps;
 		    std::vector<std::vector<std::string> > _attributes;
 		    int line_num;
 		    std::istringstream line;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct an \e LGF contents reader, which reads from the given
 		    /// input stream.
 		    LgfContents(std::istream& is)
 		      : _is(&is), local_is(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct an \e LGF contents reader, which reads from the given
 		    /// file.
 		    LgfContents(const std::string& fn)
 		      : _is(new std::ifstream(fn.c_str())), local_is(true) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct an \e LGF contents reader, which reads from the given
 		    /// file.
 		    LgfContents(const char* fn)
 		      : _is(new std::ifstream(fn)), local_is(true) {}
 		    /// \brief Destructor
 		    ~LgfContents() {
 		      if (local_is) delete _is;
+		    }
 		  private:
 		    LgfContents(const LgfContents&);
 		    LgfContents& operator=(const LgfContents&);
 		  public:
 		    /// \name Node sections
 		    /// @{
 		    /// \brief Gives back the number of node sections in the file.
 		    ///
 		    /// Gives back the number of node sections in the file.
 		    int nodeSectionNum() const {
 		      return _node_sections.size();
+		    }
 		    /// \brief Returns the node section name at the given position.
 		    ///
 		    /// Returns the node section name at the given position.
 		    const std::string& nodeSection(int i) const {
 		      return _node_sections[i];
+		    }
 		    /// \brief Gives back the node maps for the given section.
 		    ///
 		    /// Gives back the node maps for the given section.
 		    const std::vector<std::string>& nodeMapNames(int i) const {
 		      return _node_maps[i];
+		    }
 		    /// @}
 		    /// \name Arc/Edge sections
 		    /// @{
 		    /// \brief Gives back the number of arc/edge sections in the file.
 		    ///
 		    /// Gives back the number of arc/edge sections in the file.
 		    /// \note It is synonym of \c edgeSectionNum().
 		    int arcSectionNum() const {
 		      return _edge_sections.size();
+		    }
 		    /// \brief Returns the arc/edge section name at the given position.
 		    ///
 		    /// Returns the arc/edge section name at the given position.
 		    /// \note It is synonym of \c edgeSection().
 		    const std::string& arcSection(int i) const {
 		      return _edge_sections[i];
+		    }
 		    /// \brief Gives back the arc/edge maps for the given section.
 		    ///
 		    /// Gives back the arc/edge maps for the given section.
 		    /// \note It is synonym of \c edgeMapNames().
 		    const std::vector<std::string>& arcMapNames(int i) const {
 		      return _edge_maps[i];
+		    }
 		    /// @}
 		    /// \name Synonyms
 		    /// @{
 		    /// \brief Gives back the number of arc/edge sections in the file.
 		    ///
 		    /// Gives back the number of arc/edge sections in the file.
 		    /// \note It is synonym of \c arcSectionNum().
 		    int edgeSectionNum() const {
 		      return _edge_sections.size();
+		    }
 		    /// \brief Returns the section name at the given position.
 		    ///
 		    /// Returns the section name at the given position.
 		    /// \note It is synonym of \c arcSection().
 		    const std::string& edgeSection(int i) const {
 		      return _edge_sections[i];
+		    }
 		    /// \brief Gives back the edge maps for the given section.
 		    ///
 		    /// Gives back the edge maps for the given section.
 		    /// \note It is synonym of \c arcMapNames().
 		    const std::vector<std::string>& edgeMapNames(int i) const {
 		      return _edge_maps[i];
+		    }
 		    /// @}
 		    /// \name Attribute sections
 		    /// @{
 		    /// \brief Gives back the number of attribute sections in the file.
 		    ///
 		    /// Gives back the number of attribute sections in the file.
 		    int attributeSectionNum() const {
 		      return _attribute_sections.size();
+		    }
 		    /// \brief Returns the attribute section name at the given position.
 		    ///
 		    /// Returns the attribute section name at the given position.
 		    const std::string& attributeSectionNames(int i) const {
 		      return _attribute_sections[i];
+		    }
 		    /// \brief Gives back the attributes for the given section.
 		    ///
 		    /// Gives back the attributes for the given section.
 		    const std::vector<std::string>& attributes(int i) const {
 		      return _attributes[i];
+		    }
 		    /// @}
 		    /// \name Extra sections
 		    /// @{
 		    /// \brief Gives back the number of extra sections in the file.
 		    ///
 		    /// Gives back the number of extra sections in the file.
 		    int extraSectionNum() const {
 		      return _extra_sections.size();
+		    }
 		    /// \brief Returns the extra section type at the given position.
 		    ///
 		    /// Returns the section type at the given position.
 		    const std::string& extraSection(int i) const {
 		      return _extra_sections[i];
+		    }
 		    /// @}
 		  private:
 		    bool readLine() {
 		      std::string str;
 		      while(++line_num, std::getline(*_is, str)) {
 		        line.clear(); line.str(str);
 		        char c;
 		        if (line >> std::ws >> c && c != '#') {
 		          line.putback(c);
 		          return true;
+		        }
+		      }
 		      return false;
+		    }
 		    bool readSuccess() {
 		      return static_cast<bool>(*_is);
+		    }
 		    void skipSection() {
 		      char c;
 		      while (readSuccess() && line >> c && c != '@') {
 		        readLine();
+		      }
 		      line.putback(c);
+		    }
 		    void readMaps(std::vector<std::string>& maps) {
 		      char c;
 		      if (!readLine() || !(line >> c) || c == '@') {
 		        if (readSuccess() && line) line.putback(c);
 		        return;
+		      }
 		      line.putback(c);
 		      std::string map;
 		      while (_reader_bits::readToken(line, map)) {
 		        maps.push_back(map);
+		      }
+		    }
 		    void readAttributes(std::vector<std::string>& attrs) {
 		      readLine();
 		      char c;
 		      while (readSuccess() && line >> c && c != '@') {
 		        line.putback(c);
 		        std::string attr;
 		        _reader_bits::readToken(line, attr);

lemon/lgf_writer.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-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.
+		 *
 		 */
 		///\ingroup lemon_io
 		///\file
-		///\brief \ref lgf-format "Lemon Graph Format" writer.
+		///\brief \ref lgf-format "LEMON Graph Format" writer.
 		#ifndef LEMON_LGF_WRITER_H
 		#define LEMON_LGF_WRITER_H
 		#include <iostream>
 		#include <fstream>
 		#include <sstream>
 		#include <algorithm>
 		#include <vector>
 		#include <functional>
 		#include <lemon/assert.h>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		namespace lemon {
 		  namespace _writer_bits {
 		    template <typename Value>
 		    struct DefaultConverter {
 		      std::string operator()(const Value& value) {
 		        std::ostringstream os;
 		        os << value;
 		        return os.str();
+		      }
 		    };
 		    template <typename T>
 		    bool operator<(const T&, const T&) {
 		      throw DataFormatError("Label map is not comparable");
+		    }
 		    template <typename _Map>
 		    class MapLess {
 		    public:
 		      typedef _Map Map;
 		      typedef typename Map::Key Item;
 		    private:
 		      const Map& _map;
 		    public:
 		      MapLess(const Map& map) : _map(map) {}
 		      bool operator()(const Item& left, const Item& right) {
 		        return _map[left] < _map[right];
+		      }
 		    };
 		    template <typename _Graph, bool _dir, typename _Map>
 		    class GraphArcMapLess {
 		    public:
 		      typedef _Map Map;
 		      typedef _Graph Graph;
 		      typedef typename Graph::Edge Item;
 		    private:
 		      const Graph& _graph;
 		      const Map& _map;
 		    public:
 		      GraphArcMapLess(const Graph& graph, const Map& map)
 		        : _graph(graph), _map(map) {}
 		      bool operator()(const Item& left, const Item& right) {
 		        return _map[_graph.direct(left, _dir)] <
 		          _map[_graph.direct(right, _dir)];
+		      }
 		    };
 		    template <typename _Item>
 		    class MapStorageBase {
 		    public:
 		      typedef _Item Item;
 		    public:
 		      MapStorageBase() {}
 		      virtual ~MapStorageBase() {}
 		      virtual std::string get(const Item& item) = 0;
 		      virtual void sort(std::vector<Item>&) = 0;
 		    };
 		    template <typename _Item, typename _Map,
 		              typename _Converter = DefaultConverter<typename _Map::Value> >
 		    class MapStorage : public MapStorageBase<_Item> {
 		    public:
 		      typedef _Map Map;
 		      typedef _Converter Converter;
 		      typedef _Item Item;
 		    private:
 		      const Map& _map;
 		      Converter _converter;
 		    public:
 		      MapStorage(const Map& map, const Converter& converter = Converter())
 		        : _map(map), _converter(converter) {}
 		      virtual ~MapStorage() {}
 		      virtual std::string get(const Item& item) {
 		        return _converter(_map[item]);
+		      }
 		      virtual void sort(std::vector<Item>& items) {
 		        MapLess<Map> less(_map);
 		        std::sort(items.begin(), items.end(), less);
+		      }
 		    };
 		    template <typename _Graph, bool _dir, typename _Map,
 		              typename _Converter = DefaultConverter<typename _Map::Value> >
 		    class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
 		    public:
 		      typedef _Map Map;
 		      typedef _Converter Converter;
 		      typedef _Graph Graph;
 		      typedef typename Graph::Edge Item;
 		      static const bool dir = _dir;
 		    private:
 		      const Graph& _graph;
 		      const Map& _map;
 		      Converter _converter;
 		    public:
 		      GraphArcMapStorage(const Graph& graph, const Map& map,
 		                         const Converter& converter = Converter())
 		        : _graph(graph), _map(map), _converter(converter) {}
 		      virtual ~GraphArcMapStorage() {}
 		      virtual std::string get(const Item& item) {
 		        return _converter(_map[_graph.direct(item, dir)]);
+		      }
 		      virtual void sort(std::vector<Item>& items) {
 		        GraphArcMapLess<Graph, dir, Map> less(_graph, _map);
 		        std::sort(items.begin(), items.end(), less);
+		      }
 		    };
 		    class ValueStorageBase {
 		    public:
 		      ValueStorageBase() {}
 		      virtual ~ValueStorageBase() {}
 		      virtual std::string get() = 0;
 		    };
 		    template <typename _Value, typename _Converter = DefaultConverter<_Value> >
 		    class ValueStorage : public ValueStorageBase {
 		    public:
 		      typedef _Value Value;
 		      typedef _Converter Converter;
 		    private:
 		      const Value& _value;
 		      Converter _converter;
 		    public:
 		      ValueStorage(const Value& value, const Converter& converter = Converter())
 		        : _value(value), _converter(converter) {}
 		      virtual std::string get() {
 		        return _converter(_value);
+		      }
 		    };
 		    template <typename Value>
 		    struct MapLookUpConverter {
 		      const std::map<Value, std::string>& _map;
 		      MapLookUpConverter(const std::map<Value, std::string>& map)
 		        : _map(map) {}
 		      std::string operator()(const Value& str) {
 		        typename std::map<Value, std::string>::const_iterator it =
 		          _map.find(str);
 		        if (it == _map.end()) {
 		          throw DataFormatError("Item not found");
+		        }
 		        return it->second;
+		      }
 		    };
 		    template <typename Graph>
 		    struct GraphArcLookUpConverter {
 		      const Graph& _graph;
 		      const std::map<typename Graph::Edge, std::string>& _map;
 		      GraphArcLookUpConverter(const Graph& graph,
 		                              const std::map<typename Graph::Edge,
 		                                             std::string>& map)
 		        : _graph(graph), _map(map) {}
 		      std::string operator()(const typename Graph::Arc& val) {
 		        typename std::map<typename Graph::Edge, std::string>
 		          ::const_iterator it = _map.find(val);
 		        if (it == _map.end()) {
 		          throw DataFormatError("Item not found");
+		        }
 		        return (_graph.direction(val) ? '+' : '-') + it->second;
+		      }
 		    };
 		    inline bool isWhiteSpace(char c) {
 		      return c == ' ' || c == '\t' || c == '\v' ||
 		        c == '\n' || c == '\r' || c == '\f';
+		    }
 		    inline bool isEscaped(char c) {
 		      return c == '\\' || c == '\"' || c == '\'' ||
 		        c == '\a' || c == '\b';
+		    }
 		    inline static void writeEscape(std::ostream& os, char c) {
 		      switch (c) {
 		      case '\\':
 		        os << "\\\\";
 		        return;
 		      case '\"':
 		        os << "\\\"";
 		        return;
 		      case '\a':
 		        os << "\\a";
 		        return;
 		      case '\b':
 		        os << "\\b";
 		        return;
 		      case '\f':
 		        os << "\\f";
 		        return;
 		      case '\r':
 		        os << "\\r";
 		        return;
 		      case '\n':
 		        os << "\\n";
 		        return;
 		      case '\t':
 		        os << "\\t";
 		        return;
 		      case '\v':
 		        os << "\\v";
 		        return;
 		      default:
 		        if (c < 0x20) {
 		          std::ios::fmtflags flags = os.flags();
 		          os << '\\' << std::oct << static_cast<int>(c);
 		          os.flags(flags);
 		        } else {
 		          os << c;
+		        }
 		        return;
+		      }

lemon/path.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-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.
+		 *
 		 */
 		///\ingroup paths
 		///\file
 		///\brief Classes for representing paths in digraphs.
 		///
 		#ifndef LEMON_PATH_H
 		#define LEMON_PATH_H
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/error.h>
 		#include <lemon/core.h>
 		#include <lemon/concepts/path.h>
 		namespace lemon {
 		  /// \addtogroup paths
 		  /// @{
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \tparam _Digraph The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
 		  /// lemon path type stores just this list. As a consequence, it
 		  /// cannot enumerate the nodes of the path and the source node of
 		  /// a zero length path is undefined.
 		  ///
 		  /// This implementation is a back and front insertable and erasable
 		  /// path type. It can be indexed in O(1) time. The front and back
 		  /// insertion and erase is done in O(1) (amortized) time. The
 		  /// implementation uses two vectors for storing the front and back
 		  /// insertions.
 		  template <typename _Digraph>
 		  class Path {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    Path() {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This constuctor initializes the path from any other path type.
 		    /// It simply makes a copy of the given path.
 		    template <typename CPath>
 		    Path(const CPath& cpath) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This operator makes a copy of a path of any other type.
 		    template <typename CPath>
 		    Path& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
-		    /// \brief Lemon style iterator for path arcs
+		    /// \brief LEMON style iterator for path arcs
 		    ///
 		    /// This class is used to iterate on the arcs of the paths.
 		    class ArcIt {
 		      friend class Path;
 		    public:
 		      /// \brief Default constructor
 		      ArcIt() {}
 		      /// \brief Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// \brief Initializate the iterator to the first arc of path
 		      ArcIt(const Path &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      ArcIt(const Path &_path, int _idx)
 		        : path(&_path), idx(_idx) {}
 		    public:
 		      /// \brief Conversion to Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// \brief Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// \brief Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// \brief Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// \brief Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const Path *path;
 		      int idx;
 		    };
 		    /// \brief Length of the path.
 		    int length() const { return head.size() + tail.size(); }
 		    /// \brief Return whether the path is empty.
 		    bool empty() const { return head.empty() && tail.empty(); }
 		    /// \brief Reset the path to an empty one.
 		    void clear() { head.clear(); tail.clear(); }
 		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return n < int(head.size()) ? *(head.rbegin() + n) :
 		        *(tail.begin() + (n - head.size()));
+		    }
 		    /// \brief Initialize arc iterator to point to the nth arc
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
 		    /// \brief The first arc of the path
 		    const Arc& front() const {
 		      return head.empty() ? tail.front() : head.back();
+		    }
 		    /// \brief Add a new arc before the current path
 		    void addFront(const Arc& arc) {
 		      head.push_back(arc);
+		    }
 		    /// \brief Erase the first arc of the path
 		    void eraseFront() {
 		      if (!head.empty()) {
 		        head.pop_back();
 		      } else {
 		        head.clear();
 		        int halfsize = tail.size() / 2;
 		        head.resize(halfsize);
 		        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
 		                  head.rbegin());
 		        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
 		        tail.resize(tail.size() - halfsize - 1);
+		      }
+		    }
 		    /// \brief The last arc of the path
 		    const Arc& back() const {
 		      return tail.empty() ? head.front() : tail.back();
+		    }
 		    /// \brief Add a new arc behind the current path
 		    void addBack(const Arc& arc) {
 		      tail.push_back(arc);
+		    }
 		    /// \brief Erase the last arc of the path
 		    void eraseBack() {
 		      if (!tail.empty()) {
 		        tail.pop_back();
 		      } else {
 		        int halfsize = head.size() / 2;
 		        tail.resize(halfsize);
 		        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
 		                  tail.rbegin());
 		        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
 		        head.resize(head.size() - halfsize - 1);
+		      }
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      int len = path.length();
 		      tail.reserve(len);
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        tail.push_back(it);
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      int len = path.length();
 		      head.reserve(len);
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        head.push_back(it);
+		      }
+		    }
 		  protected:
 		    typedef std::vector<Arc> Container;
 		    Container head, tail;
 		  };
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \tparam _Digraph The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
 		  /// lemon path type stores just this list. As a consequence it
 		  /// cannot enumerate the nodes in the path and the zero length paths
 		  /// cannot store the source.
 		  ///
 		  /// This implementation is a just back insertable and erasable path
 		  /// type. It can be indexed in O(1) time. The back insertion and
 		  /// erasure is amortized O(1) time. This implementation is faster
 		  /// then the \c Path type because it use just one vector for the
 		  /// arcs.
 		  template <typename _Digraph>
 		  class SimplePath {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    SimplePath() {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    SimplePath(const CPath& cpath) {
 		      copyPath(*this, cpath);
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    SimplePath& operator=(const CPath& cpath) {
 		      copyPath(*this, cpath);
 		      return *this;
+		    }
 		    /// \brief Iterator class to iterate on the arcs of the paths
 		    ///
 		    /// This class is used to iterate on the arcs of the paths
 		    ///
 		    /// Of course it converts to Digraph::Arc
 		    class ArcIt {
 		      friend class SimplePath;
 		    public:
 		      /// Default constructor
 		      ArcIt() {}
 		      /// Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// \brief Initializate the constructor to the first arc of path
 		      ArcIt(const SimplePath &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      /// Constructor with starting point
 		      ArcIt(const SimplePath &_path, int _idx)
 		        : idx(_idx), path(&_path) {}
 		    public:
 		      ///Conversion to Digraph::Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const SimplePath *path;
 		      int idx;
 		    };
 		    /// \brief Length of the path.
 		    int length() const { return data.size(); }
 		    /// \brief Return true if the path is empty.
 		    bool empty() const { return data.empty(); }
 		    /// \brief Reset the path to an empty one.
 		    void clear() { data.clear(); }
 		    /// \brief The nth arc.
 		    ///
 		    /// \pre n is in the [0..length() - 1] range
 		    const Arc& nth(int n) const {
 		      return data[n];
+		    }
 		    /// \brief  Initializes arc iterator to point to the nth arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }

lemon/unionfind.h

Show inline comments

@@ -244,875 +244,875 @@
 		        int next = items[idx].parent;
 		        const_cast<int&>(items[idx].parent) = k;
 		        idx = next;
+		      }
 		      return k;
+		    }
 		    int classIndex(int idx) const {
 		      return ~(items[repIndex(idx)].parent);
+		    }
 		    void singletonItem(int idx) {
 		      items[idx].next = idx;
 		      items[idx].prev = idx;
+		    }
 		    void laceItem(int idx, int rdx) {
 		      items[idx].prev = rdx;
 		      items[idx].next = items[rdx].next;
 		      items[items[rdx].next].prev = idx;
 		      items[rdx].next = idx;
+		    }
 		    void unlaceItem(int idx) {
 		      items[items[idx].prev].next = items[idx].next;
 		      items[items[idx].next].prev = items[idx].prev;
 		      items[idx].next = firstFreeItem;
 		      firstFreeItem = idx;
+		    }
 		    void spliceItems(int ak, int bk) {
 		      items[items[ak].prev].next = bk;
 		      items[items[bk].prev].next = ak;
 		      int tmp = items[ak].prev;
 		      items[ak].prev = items[bk].prev;
 		      items[bk].prev = tmp;
+		    }
 		    void laceClass(int cls) {
 		      if (firstClass != -1) {
 		        classes[firstClass].prev = cls;
+		      }
 		      classes[cls].next = firstClass;
 		      classes[cls].prev = -1;
 		      firstClass = cls;
+		    }
 		    void unlaceClass(int cls) {
 		      if (classes[cls].prev != -1) {
 		        classes[classes[cls].prev].next = classes[cls].next;
 		      } else {
 		        firstClass = classes[cls].next;
+		      }
 		      if (classes[cls].next != -1) {
 		        classes[classes[cls].next].prev = classes[cls].prev;
+		      }
 		      classes[cls].next = firstFreeClass;
 		      firstFreeClass = cls;
+		    }
 		  public:
 		    UnionFindEnum(ItemIntMap& _index)
 		      : index(_index), items(), firstFreeItem(-1),
 		        firstClass(-1), firstFreeClass(-1) {}
 		    /// \brief Inserts the given element into a new component.
 		    ///
 		    /// This method creates a new component consisting only of the
 		    /// given element.
 		    ///
 		    int insert(const Item& item) {
 		      int idx = newItem();
 		      index.set(item, idx);
 		      singletonItem(idx);
 		      items[idx].item = item;
 		      int cdx = newClass();
 		      items[idx].parent = ~cdx;
 		      laceClass(cdx);
 		      classes[cdx].size = 1;
 		      classes[cdx].firstItem = idx;
 		      firstClass = cdx;
 		      return cdx;
+		    }
 		    /// \brief Inserts the given element into the component of the others.
 		    ///
 		    /// This methods inserts the element \e a into the component of the
 		    /// element \e comp.
 		    void insert(const Item& item, int cls) {
 		      int rdx = classes[cls].firstItem;
 		      int idx = newItem();
 		      index.set(item, idx);
 		      laceItem(idx, rdx);
 		      items[idx].item = item;
 		      items[idx].parent = rdx;
 		      ++classes[~(items[rdx].parent)].size;
+		    }
 		    /// \brief Clears the union-find data structure
 		    ///
 		    /// Erase each item from the data structure.
 		    void clear() {
 		      items.clear();
 		      firstClass = -1;
 		      firstFreeItem = -1;
+		    }
 		    /// \brief Finds the component of the given element.
 		    ///
 		    /// The method returns the component id of the given element.
 		    int find(const Item &item) const {
 		      return ~(items[repIndex(index[item])].parent);
+		    }
 		    /// \brief Joining the component of element \e a and element \e b.
 		    ///
 		    /// This is the \e union operation of the Union-Find structure.
 		    /// Joins the component of element \e a and component of
 		    /// element \e b. If \e a and \e b are in the same component then
 		    /// returns -1 else returns the remaining class.
 		    int join(const Item& a, const Item& b) {
 		      int ak = repIndex(index[a]);
 		      int bk = repIndex(index[b]);
 		      if (ak == bk) {
 		        return -1;
+		      }
 		      int acx = ~(items[ak].parent);
 		      int bcx = ~(items[bk].parent);
 		      int rcx;
 		      if (classes[acx].size > classes[bcx].size) {
 		        classes[acx].size += classes[bcx].size;
 		        items[bk].parent = ak;
 		        unlaceClass(bcx);
 		        rcx = acx;
 		      } else {
 		        classes[bcx].size += classes[acx].size;
 		        items[ak].parent = bk;
 		        unlaceClass(acx);
 		        rcx = bcx;
+		      }
 		      spliceItems(ak, bk);
 		      return rcx;
+		    }
 		    /// \brief Returns the size of the class.
 		    ///
 		    /// Returns the size of the class.
 		    int size(int cls) const {
 		      return classes[cls].size;
+		    }
 		    /// \brief Splits up the component.
 		    ///
 		    /// Splitting the component into singleton components (component
 		    /// of size one).
 		    void split(int cls) {
 		      int fdx = classes[cls].firstItem;
 		      int idx = items[fdx].next;
 		      while (idx != fdx) {
 		        int next = items[idx].next;
 		        singletonItem(idx);
 		        int cdx = newClass();
 		        items[idx].parent = ~cdx;
 		        laceClass(cdx);
 		        classes[cdx].size = 1;
 		        classes[cdx].firstItem = idx;
 		        idx = next;
+		      }
 		      items[idx].prev = idx;
 		      items[idx].next = idx;
 		      classes[~(items[idx].parent)].size = 1;
+		    }
 		    /// \brief Removes the given element from the structure.
 		    ///
 		    /// Removes the element from its component and if the component becomes
 		    /// empty then removes that component from the component list.
 		    ///
 		    /// \warning It is an error to remove an element which is not in
 		    /// the structure.
 		    /// \warning This running time of this operation is proportional to the
 		    /// number of the items in this class.
 		    void erase(const Item& item) {
 		      int idx = index[item];
 		      int fdx = items[idx].next;
 		      int cdx = classIndex(idx);
 		      if (idx == fdx) {
 		        unlaceClass(cdx);
 		        items[idx].next = firstFreeItem;
 		        firstFreeItem = idx;
 		        return;
 		      } else {
 		        classes[cdx].firstItem = fdx;
 		        --classes[cdx].size;
 		        items[fdx].parent = ~cdx;
 		        unlaceItem(idx);
 		        idx = items[fdx].next;
 		        while (idx != fdx) {
 		          items[idx].parent = fdx;
 		          idx = items[idx].next;
+		        }
+		      }
+		    }
 		    /// \brief Gives back a representant item of the component.
 		    ///
 		    /// Gives back a representant item of the component.
 		    Item item(int cls) const {
 		      return items[classes[cls].firstItem].item;
+		    }
 		    /// \brief Removes the component of the given element from the structure.
 		    ///
 		    /// Removes the component of the given element from the structure.
 		    ///
 		    /// \warning It is an error to give an element which is not in the
 		    /// structure.
 		    void eraseClass(int cls) {
 		      int fdx = classes[cls].firstItem;
 		      unlaceClass(cls);
 		      items[items[fdx].prev].next = firstFreeItem;
 		      firstFreeItem = fdx;
+		    }
-		    /// \brief Lemon style iterator for the representant items.
+		    /// \brief LEMON style iterator for the representant items.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the ids of the classes.
 		    class ClassIt {
 		    public:
 		      /// \brief Constructor of the iterator
 		      ///
 		      /// Constructor of the iterator
 		      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
 		        cdx = unionFind->firstClass;
+		      }
 		      /// \brief Constructor to get invalid iterator
 		      ///
 		      /// Constructor to get invalid iterator
 		      ClassIt(Invalid) : unionFind(0), cdx(-1) {}
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next representant item.
 		      ClassIt& operator++() {
 		        cdx = unionFind->classes[cdx].next;
 		        return *this;
+		      }
 		      /// \brief Conversion operator
 		      ///
 		      /// It converts the iterator to the current representant item.
 		      operator int() const {
 		        return cdx;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ClassIt& i) {
 		        return i.cdx == cdx;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ClassIt& i) {
 		        return i.cdx != cdx;
+		      }
 		    private:
 		      const UnionFindEnum* unionFind;
 		      int cdx;
 		    };
-		    /// \brief Lemon style iterator for the items of a component.
+		    /// \brief LEMON style iterator for the items of a component.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the items of a class. By example if you want to iterate on
 		    /// each items of each classes then you may write the next code.
 		    ///\code
 		    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
 		    ///   std::cout << "Class: ";
 		    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
 		    ///     std::cout << toString(iit) << ' ' << std::endl;
 		    ///   }
 		    ///   std::cout << std::endl;
 		    /// }
 		    ///\endcode
 		    class ItemIt {
 		    public:
 		      /// \brief Constructor of the iterator
 		      ///
 		      /// Constructor of the iterator. The iterator iterates
 		      /// on the class of the \c item.
 		      ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
 		        fdx = idx = unionFind->classes[cls].firstItem;
+		      }
 		      /// \brief Constructor to get invalid iterator
 		      ///
 		      /// Constructor to get invalid iterator
 		      ItemIt(Invalid) : unionFind(0), idx(-1) {}
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next item in the class.
 		      ItemIt& operator++() {
 		        idx = unionFind->items[idx].next;
 		        if (idx == fdx) idx = -1;
 		        return *this;
+		      }
 		      /// \brief Conversion operator
 		      ///
 		      /// It converts the iterator to the current item.
 		      operator const Item&() const {
 		        return unionFind->items[idx].item;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ItemIt& i) {
 		        return i.idx == idx;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ItemIt& i) {
 		        return i.idx != idx;
+		      }
 		    private:
 		      const UnionFindEnum* unionFind;
 		      int idx, fdx;
 		    };
 		  };
 		  /// \ingroup auxdat
 		  ///
 		  /// \brief A \e Extend-Find data structure implementation which
 		  /// is able to enumerate the components.
 		  ///
 		  /// The class implements an \e Extend-Find data structure which is
 		  /// able to enumerate the components and the items in a
 		  /// component. The data structure is a simplification of the
 		  /// Union-Find structure, and it does not allow to merge two components.
 		  ///
 		  /// \pre You need to add all the elements by the \ref insert()
 		  /// method.
 		  template <typename _ItemIntMap>
 		  class ExtendFindEnum {
 		  public:
 		    typedef _ItemIntMap ItemIntMap;
 		    typedef typename ItemIntMap::Key Item;
 		  private:
 		    ItemIntMap& index;
 		    struct ItemT {
 		      int cls;
 		      Item item;
 		      int next, prev;
 		    };
 		    std::vector<ItemT> items;
 		    int firstFreeItem;
 		    struct ClassT {
 		      int firstItem;
 		      int next, prev;
 		    };
 		    std::vector<ClassT> classes;
 		    int firstClass, firstFreeClass;
 		    int newClass() {
 		      if (firstFreeClass != -1) {
 		        int cdx = firstFreeClass;
 		        firstFreeClass = classes[cdx].next;
 		        return cdx;
 		      } else {
 		        classes.push_back(ClassT());
 		        return classes.size() - 1;
+		      }
+		    }
 		    int newItem() {
 		      if (firstFreeItem != -1) {
 		        int idx = firstFreeItem;
 		        firstFreeItem = items[idx].next;
 		        return idx;
 		      } else {
 		        items.push_back(ItemT());
 		        return items.size() - 1;
+		      }
+		    }
 		  public:
 		    /// \brief Constructor
 		    ExtendFindEnum(ItemIntMap& _index)
 		      : index(_index), items(), firstFreeItem(-1),
 		        classes(), firstClass(-1), firstFreeClass(-1) {}
 		    /// \brief Inserts the given element into a new component.
 		    ///
 		    /// This method creates a new component consisting only of the
 		    /// given element.
 		    int insert(const Item& item) {
 		      int cdx = newClass();
 		      classes[cdx].prev = -1;
 		      classes[cdx].next = firstClass;
 		      if (firstClass != -1) {
 		        classes[firstClass].prev = cdx;
+		      }
 		      firstClass = cdx;
 		      int idx = newItem();
 		      items[idx].item = item;
 		      items[idx].cls = cdx;
 		      items[idx].prev = idx;
 		      items[idx].next = idx;
 		      classes[cdx].firstItem = idx;
 		      index.set(item, idx);
 		      return cdx;
+		    }
 		    /// \brief Inserts the given element into the given component.
 		    ///
 		    /// This methods inserts the element \e item a into the \e cls class.
 		    void insert(const Item& item, int cls) {
 		      int idx = newItem();
 		      int rdx = classes[cls].firstItem;
 		      items[idx].item = item;
 		      items[idx].cls = cls;
 		      items[idx].prev = rdx;
 		      items[idx].next = items[rdx].next;
 		      items[items[rdx].next].prev = idx;
 		      items[rdx].next = idx;
 		      index.set(item, idx);
+		    }
 		    /// \brief Clears the union-find data structure
 		    ///
 		    /// Erase each item from the data structure.
 		    void clear() {
 		      items.clear();
 		      classes.clear;
 		      firstClass = firstFreeClass = firstFreeItem = -1;
+		    }
 		    /// \brief Gives back the class of the \e item.
 		    ///
 		    /// Gives back the class of the \e item.
 		    int find(const Item &item) const {
 		      return items[index[item]].cls;
+		    }
 		    /// \brief Gives back a representant item of the component.
 		    ///
 		    /// Gives back a representant item of the component.
 		    Item item(int cls) const {
 		      return items[classes[cls].firstItem].item;
+		    }
 		    /// \brief Removes the given element from the structure.
 		    ///
 		    /// Removes the element from its component and if the component becomes
 		    /// empty then removes that component from the component list.
 		    ///
 		    /// \warning It is an error to remove an element which is not in
 		    /// the structure.
 		    void erase(const Item &item) {
 		      int idx = index[item];
 		      int cdx = items[idx].cls;
 		      if (idx == items[idx].next) {
 		        if (classes[cdx].prev != -1) {
 		          classes[classes[cdx].prev].next = classes[cdx].next;
 		        } else {
 		          firstClass = classes[cdx].next;
+		        }
 		        if (classes[cdx].next != -1) {
 		          classes[classes[cdx].next].prev = classes[cdx].prev;
+		        }
 		        classes[cdx].next = firstFreeClass;
 		        firstFreeClass = cdx;
 		      } else {
 		        classes[cdx].firstItem = items[idx].next;
 		        items[items[idx].next].prev = items[idx].prev;
 		        items[items[idx].prev].next = items[idx].next;
+		      }
 		      items[idx].next = firstFreeItem;
 		      firstFreeItem = idx;
+		    }
 		    /// \brief Removes the component of the given element from the structure.
 		    ///
 		    /// Removes the component of the given element from the structure.
 		    ///
 		    /// \warning It is an error to give an element which is not in the
 		    /// structure.
 		    void eraseClass(int cdx) {
 		      int idx = classes[cdx].firstItem;
 		      items[items[idx].prev].next = firstFreeItem;
 		      firstFreeItem = idx;
 		      if (classes[cdx].prev != -1) {
 		        classes[classes[cdx].prev].next = classes[cdx].next;
 		      } else {
 		        firstClass = classes[cdx].next;
+		      }
 		      if (classes[cdx].next != -1) {
 		        classes[classes[cdx].next].prev = classes[cdx].prev;
+		      }
 		      classes[cdx].next = firstFreeClass;
 		      firstFreeClass = cdx;
+		    }
-		    /// \brief Lemon style iterator for the classes.
+		    /// \brief LEMON style iterator for the classes.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the ids of classes.
 		    class ClassIt {
 		    public:
 		      /// \brief Constructor of the iterator
 		      ///
 		      /// Constructor of the iterator
 		      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
 		        cdx = extendFind->firstClass;
+		      }
 		      /// \brief Constructor to get invalid iterator
 		      ///
 		      /// Constructor to get invalid iterator
 		      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next representant item.
 		      ClassIt& operator++() {
 		        cdx = extendFind->classes[cdx].next;
 		        return *this;
+		      }
 		      /// \brief Conversion operator
 		      ///
 		      /// It converts the iterator to the current class id.
 		      operator int() const {
 		        return cdx;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ClassIt& i) {
 		        return i.cdx == cdx;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ClassIt& i) {
 		        return i.cdx != cdx;
+		      }
 		    private:
 		      const ExtendFindEnum* extendFind;
 		      int cdx;
 		    };
-		    /// \brief Lemon style iterator for the items of a component.
+		    /// \brief LEMON style iterator for the items of a component.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the items of a class. By example if you want to iterate on
 		    /// each items of each classes then you may write the next code.
 		    ///\code
 		    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
 		    ///   std::cout << "Class: ";
 		    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
 		    ///     std::cout << toString(iit) << ' ' << std::endl;
 		    ///   }
 		    ///   std::cout << std::endl;
 		    /// }
 		    ///\endcode
 		    class ItemIt {
 		    public:
 		      /// \brief Constructor of the iterator
 		      ///
 		      /// Constructor of the iterator. The iterator iterates
 		      /// on the class of the \c item.
 		      ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
 		        fdx = idx = extendFind->classes[cls].firstItem;
+		      }
 		      /// \brief Constructor to get invalid iterator
 		      ///
 		      /// Constructor to get invalid iterator
 		      ItemIt(Invalid) : extendFind(0), idx(-1) {}
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next item in the class.
 		      ItemIt& operator++() {
 		        idx = extendFind->items[idx].next;
 		        if (fdx == idx) idx = -1;
 		        return *this;
+		      }
 		      /// \brief Conversion operator
 		      ///
 		      /// It converts the iterator to the current item.
 		      operator const Item&() const {
 		        return extendFind->items[idx].item;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ItemIt& i) {
 		        return i.idx == idx;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ItemIt& i) {
 		        return i.idx != idx;
+		      }
 		    private:
 		      const ExtendFindEnum* extendFind;
 		      int idx, fdx;
 		    };
 		  };
 		  /// \ingroup auxdat
 		  ///
 		  /// \brief A \e Union-Find data structure implementation which
 		  /// is able to store a priority for each item and retrieve the minimum of
 		  /// each class.
 		  ///
 		  /// A \e Union-Find data structure implementation which is able to
 		  /// store a priority for each item and retrieve the minimum of each
 		  /// class. In addition, it supports the joining and splitting the
 		  /// components. If you don't need this feature then you makes
 		  /// better to use the \ref UnionFind class which is more efficient.
 		  ///
 		  /// The union-find data strcuture based on a (2, 16)-tree with a
 		  /// tournament minimum selection on the internal nodes. The insert
 		  /// operation takes O(1), the find, set, decrease and increase takes
 		  /// O(log(n)), where n is the number of nodes in the current
 		  /// component.  The complexity of join and split is O(log(n)*k),
 		  /// where n is the sum of the number of the nodes and k is the
 		  /// number of joined components or the number of the components
 		  /// after the split.
 		  ///
 		  /// \pre You need to add all the elements by the \ref insert()
 		  /// method.
 		  ///
 		  template <typename _Value, typename _ItemIntMap,
 		            typename _Comp = std::less<_Value> >
 		  class HeapUnionFind {
 		  public:
 		    typedef _Value Value;
 		    typedef typename _ItemIntMap::Key Item;
 		    typedef _ItemIntMap ItemIntMap;
 		    typedef _Comp Comp;
 		  private:
 		    static const int cmax = 16;
 		    ItemIntMap& index;
 		    struct ClassNode {
 		      int parent;
 		      int depth;
 		      int left, right;
 		      int next, prev;
 		    };
 		    int first_class;
 		    int first_free_class;
 		    std::vector<ClassNode> classes;
 		    int newClass() {
 		      if (first_free_class < 0) {
 		        int id = classes.size();
 		        classes.push_back(ClassNode());
 		        return id;
 		      } else {
 		        int id = first_free_class;
 		        first_free_class = classes[id].next;
 		        return id;
+		      }
+		    }
 		    void deleteClass(int id) {
 		      classes[id].next = first_free_class;
 		      first_free_class = id;
+		    }
 		    struct ItemNode {
 		      int parent;
 		      Item item;
 		      Value prio;
 		      int next, prev;
 		      int left, right;
 		      int size;
 		    };
 		    int first_free_node;
 		    std::vector<ItemNode> nodes;
 		    int newNode() {
 		      if (first_free_node < 0) {
 		        int id = nodes.size();
 		        nodes.push_back(ItemNode());
 		        return id;
 		      } else {
 		        int id = first_free_node;
 		        first_free_node = nodes[id].next;
 		        return id;
+		      }
+		    }
 		    void deleteNode(int id) {
 		      nodes[id].next = first_free_node;
 		      first_free_node = id;
+		    }
 		    Comp comp;
 		    int findClass(int id) const {
 		      int kd = id;
 		      while (kd >= 0) {
 		        kd = nodes[kd].parent;
+		      }
 		      return ~kd;
+		    }
 		    int leftNode(int id) const {
 		      int kd = ~(classes[id].parent);
 		      for (int i = 0; i < classes[id].depth; ++i) {
 		        kd = nodes[kd].left;
+		      }
 		      return kd;
+		    }
 		    int nextNode(int id) const {
 		      int depth = 0;
 		      while (id >= 0 && nodes[id].next == -1) {
 		        id = nodes[id].parent;
 		        ++depth;
+		      }
 		      if (id < 0) {
 		        return -1;
+		      }
 		      id = nodes[id].next;
 		      while (depth--) {
 		        id = nodes[id].left;
+		      }
 		      return id;
+		    }
 		    void setPrio(int id) {
 		      int jd = nodes[id].left;
 		      nodes[id].prio = nodes[jd].prio;
 		      nodes[id].item = nodes[jd].item;
 		      jd = nodes[jd].next;
 		      while (jd != -1) {
 		        if (comp(nodes[jd].prio, nodes[id].prio)) {
 		          nodes[id].prio = nodes[jd].prio;
 		          nodes[id].item = nodes[jd].item;
+		        }
 		        jd = nodes[jd].next;
+		      }
+		    }
 		    void push(int id, int jd) {
 		      nodes[id].size = 1;
 		      nodes[id].left = nodes[id].right = jd;
 		      nodes[jd].next = nodes[jd].prev = -1;
 		      nodes[jd].parent = id;
+		    }
 		    void pushAfter(int id, int jd) {
 		      int kd = nodes[id].parent;
 		      if (nodes[id].next != -1) {
 		        nodes[nodes[id].next].prev = jd;
 		        if (kd >= 0) {
 		          nodes[kd].size += 1;
+		        }
 		      } else {
 		        if (kd >= 0) {
 		          nodes[kd].right = jd;
 		          nodes[kd].size += 1;
+		        }
+		      }
 		      nodes[jd].next = nodes[id].next;
 		      nodes[jd].prev = id;
 		      nodes[id].next = jd;
 		      nodes[jd].parent = kd;
+		    }
 		    void pushRight(int id, int jd) {
 		      nodes[id].size += 1;
 		      nodes[jd].prev = nodes[id].right;
 		      nodes[jd].next = -1;
 		      nodes[nodes[id].right].next = jd;
 		      nodes[id].right = jd;
 		      nodes[jd].parent = id;
+		    }
 		    void popRight(int id) {
 		      nodes[id].size -= 1;
 		      int jd = nodes[id].right;
 		      nodes[nodes[jd].prev].next = -1;
 		      nodes[id].right = nodes[jd].prev;
+		    }
@@ -1402,395 +1402,395 @@
 		              pushRight(new_id, ~(classes[r].parent));
 		              setPrio(new_id);
 		              id = nodes[id].parent;
 		              classes[r].parent = ~new_id;
+		            }
 		            if (id < 0) {
 		              int new_parent = newNode();
 		              nodes[new_parent].next = -1;
 		              nodes[new_parent].prev = -1;
 		              nodes[new_parent].parent = ~l;
 		              push(new_parent, ~(classes[l].parent));
 		              pushRight(new_parent, ~(classes[r].parent));
 		              setPrio(new_parent);
 		              classes[l].parent = ~new_parent;
 		              classes[l].depth += 1;
 		            } else {
 		              pushRight(id, ~(classes[r].parent));
 		              while (id >= 0 && less(~(classes[r].parent), id)) {
 		                nodes[id].prio = nodes[~(classes[r].parent)].prio;
 		                nodes[id].item = nodes[~(classes[r].parent)].item;
 		                id = nodes[id].parent;
+		              }
+		            }
 		          } else if (classes[r].depth > classes[l].depth) {
 		            int id = ~(classes[r].parent);
 		            for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
 		              id = nodes[id].left;
+		            }
 		            while (id >= 0 && nodes[id].size == cmax) {
 		              int new_id = newNode();
 		              int left_id = nodes[id].left;
 		              popLeft(id);
 		              if (nodes[id].prio == nodes[left_id].prio) {
 		                setPrio(id);
+		              }
 		              push(new_id, left_id);
 		              pushLeft(new_id, ~(classes[l].parent));
 		              setPrio(new_id);
 		              id = nodes[id].parent;
 		              classes[l].parent = ~new_id;
+		            }
 		            if (id < 0) {
 		              int new_parent = newNode();
 		              nodes[new_parent].next = -1;
 		              nodes[new_parent].prev = -1;
 		              nodes[new_parent].parent = ~l;
 		              push(new_parent, ~(classes[r].parent));
 		              pushLeft(new_parent, ~(classes[l].parent));
 		              setPrio(new_parent);
 		              classes[r].parent = ~new_parent;
 		              classes[r].depth += 1;
 		            } else {
 		              pushLeft(id, ~(classes[l].parent));
 		              while (id >= 0 && less(~(classes[l].parent), id)) {
 		                nodes[id].prio = nodes[~(classes[l].parent)].prio;
 		                nodes[id].item = nodes[~(classes[l].parent)].item;
 		                id = nodes[id].parent;
+		              }
+		            }
 		            nodes[~(classes[r].parent)].parent = ~l;
 		            classes[l].parent = classes[r].parent;
 		            classes[l].depth = classes[r].depth;
 		          } else {
 		            if (classes[l].depth != 0 &&
 		                nodes[~(classes[l].parent)].size +
 		                nodes[~(classes[r].parent)].size <= cmax) {
 		              splice(~(classes[l].parent), ~(classes[r].parent));
 		              deleteNode(~(classes[r].parent));
 		              if (less(~(classes[r].parent), ~(classes[l].parent))) {
 		                nodes[~(classes[l].parent)].prio =
 		                  nodes[~(classes[r].parent)].prio;
 		                nodes[~(classes[l].parent)].item =
 		                  nodes[~(classes[r].parent)].item;
+		              }
 		            } else {
 		              int new_parent = newNode();
 		              nodes[new_parent].next = nodes[new_parent].prev = -1;
 		              push(new_parent, ~(classes[l].parent));
 		              pushRight(new_parent, ~(classes[r].parent));
 		              setPrio(new_parent);
 		              classes[l].parent = ~new_parent;
 		              classes[l].depth += 1;
 		              nodes[new_parent].parent = ~l;
+		            }
+		          }
 		          if (classes[r].next != -1) {
 		            classes[classes[r].next].prev = classes[r].prev;
+		          }
 		          classes[classes[r].prev].next = classes[r].next;
 		          classes[r].prev = classes[l].right;
 		          classes[classes[l].right].next = r;
 		          classes[l].right = r;
 		          classes[r].parent = l;
 		          classes[r].next = -1;
 		          classes[r].depth = rln;
+		        }
+		      }
 		      return class_id;
+		    }
 		    /// \brief Split the class to subclasses.
 		    ///
 		    /// The current function splits the given class. The join, which
 		    /// made the current class, stored a reference to the
 		    /// subclasses. The \c splitClass() member restores the classes
 		    /// and creates the heaps. The parameter is an STL output iterator
 		    /// which will be filled with the subclass ids. The time
 		    /// complexity is O(log(n)*k) where n is the overall number of
 		    /// nodes in the splitted classes and k is the number of the
 		    /// classes.
 		    template <typename Iterator>
 		    void split(int cls, Iterator out) {
 		      std::vector<int> cs;
 		      { // splitting union-find
 		        int id = cls;
 		        int l = classes[id].left;
 		        classes[l].parent = classes[id].parent;
 		        classes[l].depth = classes[id].depth;
 		        nodes[~(classes[l].parent)].parent = ~l;
 		        *out++ = l;
 		        while (l != -1) {
 		          cs.push_back(l);
 		          l = classes[l].next;
+		        }
 		        classes[classes[id].right].next = first_class;
 		        classes[first_class].prev = classes[id].right;
 		        first_class = classes[id].left;
 		        if (classes[id].next != -1) {
 		          classes[classes[id].next].prev = classes[id].prev;
+		        }
 		        classes[classes[id].prev].next = classes[id].next;
 		        deleteClass(id);
+		      }
+		      {
 		        for (int i = 1; i < int(cs.size()); ++i) {
 		          int l = classes[cs[i]].depth;
 		          while (nodes[nodes[l].parent].left == l) {
 		            l = nodes[l].parent;
+		          }
 		          int r = l;
 		          while (nodes[l].parent >= 0) {
 		            l = nodes[l].parent;
 		            int new_node = newNode();
 		            nodes[new_node].prev = -1;
 		            nodes[new_node].next = -1;
 		            split(r, new_node);
 		            pushAfter(l, new_node);
 		            setPrio(l);
 		            setPrio(new_node);
 		            r = new_node;
+		          }
 		          classes[cs[i]].parent = ~r;
 		          classes[cs[i]].depth = classes[~(nodes[l].parent)].depth;
 		          nodes[r].parent = ~cs[i];
 		          nodes[l].next = -1;
 		          nodes[r].prev = -1;
 		          repairRight(~(nodes[l].parent));
 		          repairLeft(cs[i]);
 		          *out++ = cs[i];
+		        }
+		      }
+		    }
 		    /// \brief Gives back the priority of the current item.
 		    ///
 		    /// \return Gives back the priority of the current item.
 		    const Value& operator[](const Item& item) const {
 		      return nodes[index[item]].prio;
+		    }
 		    /// \brief Sets the priority of the current item.
 		    ///
 		    /// Sets the priority of the current item.
 		    void set(const Item& item, const Value& prio) {
 		      if (comp(prio, nodes[index[item]].prio)) {
 		        decrease(item, prio);
 		      } else if (!comp(prio, nodes[index[item]].prio)) {
 		        increase(item, prio);
+		      }
+		    }
 		    /// \brief Increase the priority of the current item.
 		    ///
 		    /// Increase the priority of the current item.
 		    void increase(const Item& item, const Value& prio) {
 		      int id = index[item];
 		      int kd = nodes[id].parent;
 		      nodes[id].prio = prio;
 		      while (kd >= 0 && nodes[kd].item == item) {
 		        setPrio(kd);
 		        kd = nodes[kd].parent;
+		      }
+		    }
 		    /// \brief Increase the priority of the current item.
 		    ///
 		    /// Increase the priority of the current item.
 		    void decrease(const Item& item, const Value& prio) {
 		      int id = index[item];
 		      int kd = nodes[id].parent;
 		      nodes[id].prio = prio;
 		      while (kd >= 0 && less(id, kd)) {
 		        nodes[kd].prio = prio;
 		        nodes[kd].item = item;
 		        kd = nodes[kd].parent;
+		      }
+		    }
 		    /// \brief Gives back the minimum priority of the class.
 		    ///
 		    /// \return Gives back the minimum priority of the class.
 		    const Value& classPrio(int cls) const {
 		      return nodes[~(classes[cls].parent)].prio;
+		    }
 		    /// \brief Gives back the minimum priority item of the class.
 		    ///
 		    /// \return Gives back the minimum priority item of the class.
 		    const Item& classTop(int cls) const {
 		      return nodes[~(classes[cls].parent)].item;
+		    }
 		    /// \brief Gives back a representant item of the class.
 		    ///
 		    /// The representant is indpendent from the priorities of the
 		    /// items.
 		    /// \return Gives back a representant item of the class.
 		    const Item& classRep(int id) const {
 		      int parent = classes[id].parent;
 		      return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
+		    }
-		    /// \brief Lemon style iterator for the items of a class.
+		    /// \brief LEMON style iterator for the items of a class.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the items of a class. By example if you want to iterate on
 		    /// each items of each classes then you may write the next code.
 		    ///\code
 		    /// for (ClassIt cit(huf); cit != INVALID; ++cit) {
 		    ///   std::cout << "Class: ";
 		    ///   for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {
 		    ///     std::cout << toString(iit) << ' ' << std::endl;
 		    ///   }
 		    ///   std::cout << std::endl;
 		    /// }
 		    ///\endcode
 		    class ItemIt {
 		    private:
 		      const HeapUnionFind* _huf;
 		      int _id, _lid;
 		    public:
 		      /// \brief Default constructor
 		      ///
 		      /// Default constructor
 		      ItemIt() {}
 		      ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
 		        int id = cls;
 		        int parent = _huf->classes[id].parent;
 		        if (parent >= 0) {
 		          _id = _huf->classes[id].depth;
 		          if (_huf->classes[id].next != -1) {
 		            _lid = _huf->classes[_huf->classes[id].next].depth;
 		          } else {
 		            _lid = -1;
+		          }
 		        } else {
 		          _id = _huf->leftNode(id);
 		          _lid = -1;
+		        }
+		      }
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next item in the class.
 		      ItemIt& operator++() {
 		        _id = _huf->nextNode(_id);
 		        return *this;
+		      }
 		      /// \brief Conversion operator
 		      ///
 		      /// It converts the iterator to the current item.
 		      operator const Item&() const {
 		        return _huf->nodes[_id].item;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ItemIt& i) {
 		        return i._id == _id;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ItemIt& i) {
 		        return i._id != _id;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(Invalid) {
 		        return _id == _lid;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(Invalid) {
 		        return _id != _lid;
+		      }
 		    };
 		    /// \brief Class iterator
 		    ///
 		    /// The iterator stores
 		    class ClassIt {
 		    private:
 		      const HeapUnionFind* _huf;
 		      int _id;
 		    public:
 		      ClassIt(const HeapUnionFind& huf)
 		        : _huf(&huf), _id(huf.first_class) {}
 		      ClassIt(const HeapUnionFind& huf, int cls)
 		        : _huf(&huf), _id(huf.classes[cls].left) {}
 		      ClassIt(Invalid) : _huf(0), _id(-1) {}
 		      const ClassIt& operator++() {
 		        _id = _huf->classes[_id].next;
 		        return *this;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ClassIt& i) {
 		        return i._id == _id;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ClassIt& i) {
 		        return i._id != _id;
+		      }
 		      operator int() const {
 		        return _id;
+		      }
 		    };
 		  };
 		  //! @}
 		} //namespace lemon
 		#endif //LEMON_UNION_FIND_H

0 comments (0 inline)

RhodeCode

Login to your account