LEMON/LEMON-official Changeset - r844:c01a98ce01fd

Repositories » LEMON » LEMON-official

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

Changeset - r844:c01a98ce01fd

« 712:e652b6
« 843:189760

845:06f816 »

r844:c01a98ce01fd

Tue, 12 May 2009 13:09:55

[Not Reviewed]

0 comments (0 inline)

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

Merge

1 21 2

merge 1.1

2 files changed:

doc/min_cost_flow.dox

153

CMakeLists.txt

NEWS

README

doc/Makefile.am

doc/groups.dox

doc/mainpage.dox

lemon/Makefile.am

lemon/adaptors.h

lemon/concepts/graph.h

lemon/bits/base_extender.h

495

Changeset was too big and was cut off... Show full diff

↑ Collapse diff ↑

doc/min_cost_flow.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		namespace lemon {
 		/**
 		\page min_cost_flow Minimum Cost Flow Problem
 		\section mcf_def Definition (GEQ form)
 		The \e minimum \e cost \e flow \e problem is to find a feasible flow of
 		minimum total cost from a set of supply nodes to a set of demand nodes
 		in a network with capacity constraints (lower and upper bounds)
 		and arc costs.
 		Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
 		\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
 		upper bounds for the flow values on the arcs, for which
 		\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
 		\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
 		on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
 		signed supply values of the nodes.
 		If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		\f$-sup(u)\f$ demand.
 		A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
 		of the following optimization problem.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		zero or negative in order to have a feasible solution (since the sum
 		of the expressions on the left-hand side of the inequalities is zero).
 		It means that the total demand must be greater or equal to the total
 		supply and all the supplies have to be carried out from the supply nodes,
 		but there could be demands that are not satisfied.
 		If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		constraints have to be satisfied with equality, i.e. all demands
 		have to be satisfied and all supplies have to be used.
 		\section mcf_algs Algorithms
 		LEMON contains several algorithms for solving this problem, for more
 		information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
 		A feasible solution for this problem can be found using \ref Circulation.
 		\section mcf_dual Dual Solution
 		The dual solution of the minimum cost flow problem is represented by
 		node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
 		An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
 		if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
 		the following \e complementary \e slackness optimality conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
 		   - \f$\pi(u)<=0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
 		\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
 		\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
 		All algorithms provide dual solution (node potentials), as well,
 		if an optimal flow is found.
 		\section mcf_eq Equality Form
 		The above \ref mcf_def "definition" is actually more general than the
 		usual formulation of the minimum cost flow problem, in which strict
 		equalities are required in the supply/demand contraints.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		However if the sum of the supply values is zero, then these two problems
 		are equivalent.
 		The \ref min_cost_flow_algs "algorithms" in LEMON support the general
 		form, so if you need the equality form, you have to ensure this additional
 		contraint manually.
 		\section mcf_leq Opposite Inequalites (LEQ Form)
 		Another possible definition of the minimum cost flow problem is
 		when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
 		instead of the <em>"greater or equal"</em> (GEQ) constraints.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		It means that the total demand must be less or equal to the
 		total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 		positive) and all the demands have to be satisfied, but there
 		could be supplies that are not carried out from the supply
 		nodes.
 		The equality form is also a special case of this form, of course.
 		You could easily transform this case to the \ref mcf_def "GEQ form"
 		of the problem by reversing the direction of the arcs and taking the
 		negative of the supply values (e.g. using \ref ReverseDigraph and
 		\ref NegMap adaptors).
 		However \ref NetworkSimplex algorithm also supports this form directly
 		for the sake of convenience.
 		Note that the optimality conditions for this supply constraint type are
 		slightly differ from the conditions that are discussed for the GEQ form,
 		namely the potentials have to be non-negative instead of non-positive.
 		An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
 		is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
 		node potentials the following conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
 		   - \f$\pi(u)>=0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		*/
+		}

CMakeLists.txt

Show inline comments

 		CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
 		IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		  INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		  SET(PROJECT_NAME "LEMON")
 		  SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")
 		ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
 		PROJECT(${PROJECT_NAME})
 		SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
 		INCLUDE(FindDoxygen)
 		INCLUDE(FindGhostscript)
 		FIND_PACKAGE(GLPK 4.33)
 		FIND_PACKAGE(CPLEX)
 		FIND_PACKAGE(COIN)
 		IF(MSVC)
 		  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
 		# Suppressed warnings:
 		# C4250: 'class1' : inherits 'class2::member' via dominance
 		# C4355: 'this' : used in base member initializer list
 		# C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
 		# C4996: 'function': was declared deprecated
 		ENDIF(MSVC)
 		INCLUDE(CheckTypeSize)
 		CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
 		ENABLE_TESTING()
 		ADD_SUBDIRECTORY(lemon)
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		  ADD_SUBDIRECTORY(demo)
 		  ADD_SUBDIRECTORY(tools)
 		  ADD_SUBDIRECTORY(doc)
 		  ADD_SUBDIRECTORY(test)
 		ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
 		  IF(WIN32)
 		    SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
 		    SET(CPACK_PACKAGE_VENDOR "EGRES")
 		    SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
-		      "LEMON - Library of Efficient Models and Optimization in Networks")
+		      "LEMON - Library for Efficient Modeling and Optimization in Networks")
 		    SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
 		    SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
 		    SET(CPACK_PACKAGE_INSTALL_DIRECTORY
 		      "${PROJECT_NAME} ${PROJECT_VERSION}")
 		    SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
 		      "${PROJECT_NAME} ${PROJECT_VERSION}")
 		    SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
 		    SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
 		    SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
 		    SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
 		    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
 		    SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
 		      "C++ header files")
 		    SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
 		      "DLL and import library")
 		    SET(CPACK_COMPONENT_BIN_DESCRIPTION
 		      "Command line utilities")
 		    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
 		      "Doxygen generated documentation")
 		    SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
 		    SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
 		    SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
 		    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
 		    SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
 		      "Components needed to develop software using LEMON")
 		    SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
 		      "Documentation of LEMON")
 		    SET(CPACK_ALL_INSTALL_TYPES Full Developer)
 		    SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
 		    SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
 		    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
 		    SET(CPACK_GENERATOR "NSIS")
 		    SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
 		    SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
 		    #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
 		    SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
 		    SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
 		    SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
 		    SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
 		    SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
 		    SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
 		      CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
 		      ")
 		    SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
 		      !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
 		      Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
 		      ")
 		    INCLUDE(CPack)
 		  ENDIF(WIN32)
 		ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})

NEWS

Show inline comments

 -05-13 Version 1.1 released
 		        This is the second stable release of the 1.x series. It
 		        features a better coverage of the tools available in the 0.x
 		        series, a thoroughly reworked LP/MIP interface plus various
 		        improvements in the existing tools.
 		        * Much improved M$ Windows support
 		          * Various improvements in the CMAKE build system
 		          * Compilation warnings are fixed/suppressed
 		        * Support IBM xlC compiler
 		        * New algorithms
 		          * Connectivity related algorithms (#61)
 		          * Euler walks (#65)
 		          * Preflow push-relabel max. flow algorithm (#176)
 		          * Circulation algorithm (push-relabel based) (#175)
 		          * Suurballe algorithm (#47)
 		          * Gomory-Hu algorithm (#66)
 		          * Hao-Orlin algorithm (#58)
 		          * Edmond's maximum cardinality and weighted matching algorithms
 		            in general graphs (#48,#265)
 		          * Minimum cost arborescence/branching (#60)
 		          * Network Simplex min. cost flow algorithm (#234)
 		        * New data structures
 		          * Full graph structure (#57)
 		          * Grid graph structure (#57)
 		          * Hypercube graph structure (#57)
 		          * Graph adaptors (#67)
 		          * ArcSet and EdgeSet classes (#67)
 		          * Elevator class (#174)
 		        * Other new tools
 		          * LP/MIP interface (#44)
 		            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
 		          * Reader for the Nauty file format (#55)
 		          * DIMACS readers (#167)
 		          * Radix sort algorithms (#72)
 		          * RangeIdMap and CrossRefMap (#160)
 		        * New command line tools
 		          * DIMACS to LGF converter (#182)
 		          * lgf-gen - a graph generator (#45)
 		          * DIMACS solver utility (#226)
 		        * Other code improvements
 		          * Lognormal distribution added to Random (#102)
 		          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
 		          * The standard maps of graphs are guaranteed to be
 		            reference maps (#190)
 		        * Miscellaneous
 		          * Various doc improvements
 		          * Improved 0.x -> 1.x converter script
 		        * Several bugfixes (compared to release 1.0):
 		          #170: Bugfix SmartDigraph::split()
 		          #171: Bugfix in SmartGraph::restoreSnapshot()
 		          #172: Extended test cases for graphs and digraphs
 		          #173: Bugfix in Random
 		                * operator()s always return a double now
 		                * the faulty real<Num>(Num) and real<Num>(Num,Num)
 		                  have been removed
 		          #187: Remove DijkstraWidestPathOperationTraits
 		          #61:  Bugfix in DfsVisit
 		          #193: Bugfix in GraphReader::skipSection()
 		          #195: Bugfix in ConEdgeIt()
 		          #197: Bugfix in heap unionfind
 		                * This bug affects Edmond's general matching algorithms
 		          #207: Fix 'make install' without 'make html' using CMAKE
 		          #208: Suppress or fix VS2008 compilation warnings
 		          ----: Update the LEMON icon
 		          ----: Enable the component-based installer
 		                (in installers made by CPACK)
 		          ----: Set the proper version for CMAKE in the tarballs
 		                (made by autotools)
 		          ----: Minor clarification in the LICENSE file
 		          ----: Add missing unistd.h include to time_measure.h
 		          #204: Compilation bug fixed in graph_to_eps.h with VS2005
 		          #214,#215: windows.h should never be included by lemon headers
 		          #230: Build systems check the availability of 'long long' type
 		          #229: Default implementation of Tolerance<> is used for integer types
 		          #211,#212: Various fixes for compiling on AIX
 		          ----: Improvements in CMAKE config
 		                - docs is installed in share/doc/
 		                - detects newer versions of Ghostscript
 		          #239: Fix missing 'inline' specifier in time_measure.h
 		          #274,#280: Install lemon/config.h
 		          #275: Prefix macro names with LEMON_ in lemon/config.h
 		          ----: Small script for making the release tarballs added
 		          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
 -03-27 LEMON joins to the COIN-OR initiative
 		        COIN-OR (Computational Infrastructure for Operations Research,
 		        http://www.coin-or.org) project is an initiative to spur the
 		        development of open-source software for the operations research
 		        community.
 -10-13 Version 1.0 released
 			This is the first stable release of LEMON. Compared to the 0.x
 			release series, it features a considerably smaller but more
 			matured set of tools. The API has also completely revised and
 			changed in several places.
 			* The major name changes compared to the 0.x series (see the
 		          Migration Guide in the doc for more details)
 		          * Graph -> Digraph, UGraph -> Graph
 		          * Edge -> Arc, UEdge -> Edge
 			  * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
 			* Other improvements
 			  * Better documentation
 			  * Reviewed and cleaned up codebase
 			  * CMake based build system (along with the autotools based one)
 			* Contents of the library (ported from 0.x)
 			  * Algorithms
 		       	    * breadth-first search (bfs.h)
 		       	    * depth-first search (dfs.h)
 		       	    * Dijkstra's algorithm (dijkstra.h)
 		       	    * Kruskal's algorithm (kruskal.h)
 		    	  * Data structures
 		       	    * graph data structures (list_graph.h, smart_graph.h)
 		       	    * path data structures (path.h)
 		       	    * binary heap data structure (bin_heap.h)
 		       	    * union-find data structures (unionfind.h)
 		       	    * miscellaneous property maps (maps.h)
 		       	    * two dimensional vector and bounding box (dim2.h)
 		          * Concepts
 		       	    * graph structure concepts (concepts/digraph.h, concepts/graph.h,
 		              concepts/graph_components.h)
 		       	    * concepts for other structures (concepts/heap.h, concepts/maps.h,
 			      concepts/path.h)
 		    	  * Tools
 		       	    * Mersenne twister random number generator (random.h)
 		       	    * tools for measuring cpu and wall clock time (time_measure.h)
 		       	    * tools for counting steps and events (counter.h)
 		       	    * tool for parsing command line arguments (arg_parser.h)
 		       	    * tool for visualizing graphs (graph_to_eps.h)
 		       	    * tools for reading and writing data in LEMON Graph Format
 		              (lgf_reader.h, lgf_writer.h)
 		            * tools to handle the anomalies of calculations with
 			      floating point numbers (tolerance.h)
 		            * tools to manage RGB colors (color.h)
 		    	  * Infrastructure
 		       	    * extended assertion handling (assert.h)
 		       	    * exception classes and error handling (error.h)
 		      	    * concept checking (concept_check.h)
 		       	    * commonly used mathematical constants (math.h)

README

Show inline comments

 		==================================================================
 		LEMON - a Library of Efficient Models and Optimization in Networks
 		==================================================================
+		=====================================================================
 		LEMON - a Library for Efficient Modeling and Optimization in Networks
 		=====================================================================
 		LEMON is an open source library written in C++. It provides
 		easy-to-use implementations of common data structures and algorithms
 		in the area of optimization and helps implementing new ones. The main
 		focus is on graphs and graph algorithms, thus it is especially
 		suitable for solving design and optimization problems of
 		telecommunication networks. To achieve wide usability its data
 		structures and algorithms provide generic interfaces.
 		Contents
 		========
 		LICENSE
 		   Copying, distribution and modification conditions and terms.
 		INSTALL
 		   General building and installation instructions.
 		lemon/
 		   Source code of LEMON library.
 		doc/
 		   Documentation of LEMON. The starting page is doc/html/index.html.
 		demo/
 		   Some example programs to make you easier to get familiar with LEMON.
 		test/
 		   Programs to check the integrity and correctness of LEMON.
 		tools/
 		   Various utilities related to LEMON.

doc/Makefile.am

Show inline comments

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

doc/groups.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		namespace lemon {
 		/**
 		@defgroup datas Data Structures
 		This group contains the several data structures implemented in LEMON.
 		*/
 		/**
 		@defgroup graphs Graph Structures
 		@ingroup datas
 		\brief Graph structures implemented in LEMON.
 		The implementation of combinatorial algorithms heavily relies on
 		efficient graph implementations. LEMON offers data structures which are
 		planned to be easily used in an experimental phase of implementation studies,
 		and thereafter the program code can be made efficient by small modifications.
 		The most efficient implementation of diverse applications require the
 		usage of different physical graph implementations. These differences
 		appear in the size of graph we require to handle, memory or time usage
 		limitations or in the set of operations through which the graph can be
 		accessed.  LEMON provides several physical graph structures to meet
 		the diverging requirements of the possible users.  In order to save on
 		running time or on memory usage, some structures may fail to provide
 		some graph features like arc/edge or node deletion.
 		Alteration of standard containers need a very limited number of
 		operations, these together satisfy the everyday requirements.
 		In the case of graph structures, different operations are needed which do
 		not alter the physical graph, but gives another view. If some nodes or
 		arcs have to be hidden or the reverse oriented graph have to be used, then
 		this is the case. It also may happen that in a flow implementation
 		the residual graph can be accessed by another algorithm, or a node-set
 		is to be shrunk for another algorithm.
 		LEMON also provides a variety of graphs for these requirements called
 		\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
 		in conjunction with other graph representations.
 		You are free to use the graph structure that fit your requirements
 		the best, most graph algorithms and auxiliary data structures can be used
 		with any graph structure.
 		<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		@defgroup graph_adaptors Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Adaptor classes for digraphs and graphs
 		This group contains several useful adaptor classes for digraphs and graphs.
 		The main parts of LEMON are the different graph structures, generic
 		graph algorithms, graph concepts, which couple them, and graph
 		adaptors. While the previous notions are more or less clear, the
 		latter one needs further explanation. Graph adaptors are graph classes
 		which serve for considering graph structures in different ways.
 		A short example makes this much clearer.  Suppose that we have an
 		instance \c g of a directed graph type, say ListDigraph and an algorithm
 		\code
 		template <typename Digraph>
 		int algorithm(const Digraph&);
 		\endcode
 		is needed to run on the reverse oriented graph.  It may be expensive
 		(in time or in memory usage) to copy \c g with the reversed
 		arcs.  In this case, an adaptor class is used, which (according
 		to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
 		The adaptor uses the original digraph structure and digraph operations when
 		methods of the reversed oriented graph are called.  This means that the adaptor
 		have minor memory usage, and do not perform sophisticated algorithmic
 		actions.  The purpose of it is to give a tool for the cases when a
 		graph have to be used in a specific alteration.  If this alteration is
 		obtained by a usual construction like filtering the node or the arc set or
 		considering a new orientation, then an adaptor is worthwhile to use.
 		To come back to the reverse oriented graph, in this situation
 		\code
 		template<typename Digraph> class ReverseDigraph;
 		\endcode
 		template class can be used. The code looks as follows
 		\code
 		ListDigraph g;
 		ReverseDigraph<ListDigraph> rg(g);
 		int result = algorithm(rg);
 		\endcode
 		During running the algorithm, the original digraph \c g is untouched.
 		This techniques give rise to an elegant code, and based on stable
 		graph adaptors, complex algorithms can be implemented easily.
 		In flow, circulation and matching problems, the residual
 		graph is of particular importance. Combining an adaptor implementing
 		this with shortest path algorithms or minimum mean cycle algorithms,
 		a range of weighted and cardinality optimization algorithms can be
 		obtained. For other examples, the interested user is referred to the
 		detailed documentation of particular adaptors.
 		The behavior of graph adaptors can be very different. Some of them keep
 		capabilities of the original graph while in other cases this would be
 		meaningless. This means that the concepts that they meet depend
 		on the graph adaptor, and the wrapped graph.
 		For example, if an arc of a reversed digraph is deleted, this is carried
 		out by deleting the corresponding arc of the original digraph, thus the
 		adaptor modifies the original digraph.
 		However in case of a residual digraph, this operation has no sense.
 		Let us stand one more example here to simplify your work.
 		ReverseDigraph has constructor
 		\code
 		ReverseDigraph(Digraph& digraph);
 		\endcode
 		This means that in a situation, when a <tt>const %ListDigraph&</tt>
 		reference to a graph is given, then it have to be instantiated with
 		<tt>Digraph=const %ListDigraph</tt>.
 		\code
 		int algorithm1(const ListDigraph& g) {
 		  ReverseDigraph<const ListDigraph> rg(g);
 		  return algorithm2(rg);
+		}
 		\endcode
 		*/
 		/**
 		@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Graph types between real graphs and graph adaptors.
 		This group contains some graph types between real graphs and graph adaptors.
 		These classes wrap graphs to give new functionality as the adaptors do it.
 		On the other hand they are not light-weight structures as the adaptors.
 		*/
 		/**
 		@defgroup maps Maps
 		@ingroup datas
 		\brief Map structures implemented in LEMON.
 		This group contains the map structures implemented in LEMON.
 		LEMON provides several special purpose maps and map adaptors that e.g. combine
 		new maps from existing ones.
 		<b>See also:</b> \ref map_concepts "Map Concepts".
 		*/
 		/**
 		@defgroup graph_maps Graph Maps
 		@ingroup maps
 		\brief Special graph-related maps.
 		This group contains maps that are specifically designed to assign
 		values to the nodes and arcs/edges of graphs.
 		If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
 		\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		\defgroup map_adaptors Map Adaptors
 		\ingroup maps
 		\brief Tools to create new maps from existing ones
 		This group contains map adaptors that are used to create "implicit"
 		maps from other maps.
 		Most of them are \ref 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 graphToEps() 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);
 		  graphToEps(graph, "graph.eps")
 		    .coords(coords).scaleToA4().undirected()
 		    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
 		    .run();
 		\endcode
 		The \c functorToMap() function makes an \c int to \c Color map from the
 		\c nodeColor() function. The \c composeMap() compose the \c degree_map
 		and the previously created map. The composed map is a proper function to
 		get the color of each node.
 		The usage with class type algorithms is little bit harder. In this
 		case the function type map adaptors can not be used, because the
 		function map adaptors give back temporary objects.
 		\code
 		  Digraph graph;
 		  typedef Digraph::ArcMap<double> DoubleArcMap;
 		  DoubleArcMap length(graph);
 		  DoubleArcMap speed(graph);
 		  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
 		  TimeMap time(length, speed);
 		  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 		  dijkstra.run(source, target);
 		\endcode
 		We have a length map and a maximum speed map on the arcs of a digraph.
 		The minimum time to pass the arc can be calculated as the division of
 		the two maps which can be done implicitly with the \c DivMap template
 		class. We use the implicit minimum time map as the length map of the
 		\c Dijkstra algorithm.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief %Path structures implemented in LEMON.
 		This group contains the path structures implemented in LEMON.
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
 		\sa lemon::concepts::Path
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group contains some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group contains the several algorithms
 		implemented in LEMON.
 		This group contains the several algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
 		This group contains the common graph search algorithms, namely
 		\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
 		*/
 		/**
 		@defgroup shortest_path Shortest Path Algorithms
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
 		This group contains the algorithms for finding shortest paths in digraphs.
 		 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
 		   source node when all arc lengths are non-negative.
 		 - \ref Suurballe A successive shortest path algorithm for finding
 		   arc-disjoint paths between two nodes having minimum total length.
 		*/
 		/**
 		@defgroup max_flow Maximum Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding maximum flows.
 		This group contains the algorithms for finding maximum flows and
 		feasible circulations.
 		The \e maximum \e flow \e problem is to find a flow of maximum value between
 		a single source and a single target. Formally, there is a \f$G=(V,A)\f$
 		digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
 		\f$s, t \in V\f$ source and target nodes.
 		A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
 		following optimization problem.
 		\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
 		\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
 		    \quad \forall u\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 		\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
 		Tarjan for solving this problem. It also provides functions to query the
 		minimum cut, which is the dual problem of maximum flow.
 		\ref Circulation is a preflow push-relabel algorithm implemented directly
 		for finding feasible circulations, which is a somewhat different problem,
 		but it is strongly related to maximum flow.
 		For more information, see \ref Circulation.
 		*/
 		/**
-		@defgroup min_cost_flow Minimum Cost Flow Algorithms
+		@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost flows and circulations.
 		This group contains the algorithms for finding minimum cost flows and
 		circulations.
 		The \e minimum \e cost \e flow \e problem is to find a feasible flow of
 		minimum total cost from a set of supply nodes to a set of demand nodes
 		in a network with capacity constraints (lower and upper bounds)
 		and arc costs.
 		Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
 		\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
 		upper bounds for the flow values on the arcs, for which
 		\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
 		\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
 		on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
 		signed supply values of the nodes.
 		If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		\f$-sup(u)\f$ demand.
 		A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
 		of the following optimization problem.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		zero or negative in order to have a feasible solution (since the sum
 		of the expressions on the left-hand side of the inequalities is zero).
 		It means that the total demand must be greater or equal to the total
 		supply and all the supplies have to be carried out from the supply nodes,
 		but there could be demands that are not satisfied.
 		If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		constraints have to be satisfied with equality, i.e. all demands
 		have to be satisfied and all supplies have to be used.
 		If you need the opposite inequalities in the supply/demand constraints
 		(i.e. the total demand is less than the total supply and all the demands
 		have to be satisfied while there could be supplies that are not used),
 		then you could easily transform the problem to the above form by reversing
 		the direction of the arcs and taking the negative of the supply values
 		(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
 		However \ref NetworkSimplex algorithm also supports this form directly
 		for the sake of convenience.
 		A feasible solution for this problem can be found using \ref Circulation.
 		Note that the above formulation is actually more general than the usual
 		definition of the minimum cost flow problem, in which strict equalities
 		are required in the supply/demand contraints, i.e.
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
 		    sup(u) \quad \forall u\in V. \f]
 		However if the sum of the supply values is zero, then these two problems
 		are equivalent. So if you need the equality form, you have to ensure this
 		additional contraint for the algorithms.
 		The dual solution of the minimum cost flow problem is represented by node
 		potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
 		An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
 		is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
 		node potentials the following \e complementary \e slackness optimality
 		conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
 		\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
 		\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
 		circulations. For more information about this problem and its dual
 		solution see \ref min_cost_flow "Minimum Cost Flow Problem".
 		\ref NetworkSimplex is an efficient implementation of the primal Network
 		Simplex algorithm for finding minimum cost flows. It also provides dual
 		solution (node potentials), if an optimal flow is found.
 		*/
 		/**
 		@defgroup min_cut Minimum Cut Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cut in graphs.
 		This group contains the algorithms for finding minimum cut in graphs.
 		The \e minimum \e cut \e problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the nodes with minimum overall capacity on
 		outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
 		\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		cut is the \f$X\f$ solution of the next optimization problem:
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
 		    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
 		LEMON contains several algorithms related to minimum cut problems:
 		- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
 		  in directed graphs.
 		- \ref GomoryHu "Gomory-Hu tree computation" for calculating
 		  all-pairs minimum cut in undirected graphs.
 		If you want to find minimum cut just between two distinict nodes,
 		see the \ref max_flow "maximum flow problem".
 		*/
 		/**
 		@defgroup graph_properties Connectivity and Other Graph Properties
 		@ingroup algs
 		\brief Algorithms for discovering the graph properties
 		This group contains 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 matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains the algorithms for calculating matchings in graphs.
 		The general matching problem is finding a subset of the edges for which
 		each node has at most one incident edge.
 		There are several different algorithms for calculate matchings in
 		graphs. The goal of the matching optimization
 		can be finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		The matching algorithms implemented in LEMON:
 		- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum cardinality matching in general graphs.
 		- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum weighted matching in general graphs.
 		- \ref MaxWeightedPerfectMatching
 		  Edmond's blossom shrinking algorithm for calculating maximum weighted
 		  perfect matching in general graphs.
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
-		\brief Algorithms for finding a minimum cost spanning tree in a graph.
+		\brief Algorithms for finding minimum cost spanning trees and arborescences.
 		This group contains the algorithms for finding a minimum cost spanning
 		tree in a graph.
 		This group contains the algorithms for finding minimum cost spanning
 		trees and arborescences.
 		*/
 		/**
 		@defgroup auxalg Auxiliary Algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
 		This group contains some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group contains some general optimization frameworks
 		implemented in LEMON.
 		This group contains some general optimization frameworks
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup lp_group Lp and Mip Solvers
 		@ingroup gen_opt_group
 		\brief Lp and Mip solver interfaces for LEMON.
 		This group contains Lp and Mip solver interfaces for LEMON. The
 		various LP solvers could be used in the same manner with this
 		interface.
 		*/
 		/**
 		@defgroup utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
 		This group contains some simple basic graph utilities.
 		*/
 		/**
 		@defgroup misc Miscellaneous Tools
 		@ingroup utils
 		\brief Tools for development, debugging and testing.
 		This group contains several useful tools for development,
 		debugging and testing.
 		*/
 		/**
 		@defgroup timecount Time Measuring and Counting
 		@ingroup misc
 		\brief Simple tools for measuring the performance of algorithms.
 		This group contains simple tools for measuring the performance
 		of algorithms.
 		*/
 		/**
 		@defgroup exceptions Exceptions
 		@ingroup utils
 		\brief Exceptions defined in LEMON.
 		This group contains the exceptions defined in LEMON.
 		*/
 		/**
 		@defgroup io_group Input-Output
 		\brief Graph Input-Output methods
 		This group contains the tools for importing and exporting graphs
 		and graph related data. Now it supports the \ref lgf-format
 		"LEMON Graph Format", the \c DIMACS format and the encapsulated
 		postscript (EPS) format.
 		*/
 		/**
 		@defgroup lemon_io LEMON Graph Format
 		@ingroup io_group
 		\brief Reading and writing LEMON Graph Format.
 		This group contains methods for reading and writing
 		\ref lgf-format "LEMON Graph Format".
 		*/
 		/**
 		@defgroup eps_io Postscript Exporting
 		@ingroup io_group
 		\brief General \c EPS drawer and graph exporter
 		This group contains general \c EPS drawing methods and special
 		graph exporting tools.
 		*/
 		/**
 		@defgroup dimacs_group DIMACS format
 		@ingroup io_group
 		\brief Read and write files in DIMACS format
 		Tools to read a digraph from or write it to a file in DIMACS format data.
 		*/
 		/**
 		@defgroup nauty_group NAUTY Format
 		@ingroup io_group
 		\brief Read \e Nauty format
 		Tool to read graphs from \e Nauty format data.
 		*/
 		/**
 		@defgroup concept Concepts
 		\brief Skeleton classes and concept checking classes
 		This group contains the data/algorithm skeletons and concept checking
 		classes implemented in LEMON.
 		The purpose of the classes in this group is fourfold.
 		- These classes contain the documentations of the %concepts. In order
 		  to avoid document multiplications, an implementation of a concept
 		  simply refers to the corresponding concept class.
 		- These classes declare every functions, <tt>typedef</tt>s etc. an
 		  implementation of the %concepts should provide, however completely
 		  without implementations and real data structures behind the
 		  interface. On the other hand they should provide nothing else. All
 		  the algorithms working on a data structure meeting a certain concept
 		  should compile with these classes. (Though it will not run properly,
 		  of course.) In this way it is easily to check if an algorithm
 		  doesn't use any extra feature of a certain implementation.
 		- The concept descriptor classes also provide a <em>checker class</em>
 		  that makes it possible to check whether a certain implementation of a
 		  concept indeed provides all the required features.
 		- Finally, They can serve as a skeleton of a new implementation of a concept.
 		*/
 		/**
 		@defgroup graph_concepts Graph Structure Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for graph structures
 		This group contains the skeletons and concept checking classes of LEMON's
 		graph structures and helper classes used to implement these.
 		*/
 		/**
 		@defgroup map_concepts Map Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for maps
 		This group contains the skeletons and concept checking classes of maps.
 		*/
 		/**
 		\anchor demoprograms
 		@defgroup demos Demo Programs
 		Some demo programs are listed here. Their full source codes can be found in
 		the \c demo subdirectory of the source tree.
 		In order to compile them, use the <tt>make demo</tt> or the
 		<tt>make check</tt> commands.
 		*/
 		/**
 		@defgroup tools Standalone Utility Applications
 		Some utility applications are listed here.
 		The standard compilation procedure (<tt>./configure;make</tt>) will compile
 		them, as well.
 		*/
+		}

doc/mainpage.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		/**
 		\mainpage LEMON Documentation
 		\section intro Introduction
 		\subsection whatis What is LEMON
 		LEMON stands for
 		<b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
 		LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
 		and <b>O</b>ptimization in <b>N</b>etworks.
 		It is a C++ template
 		library aimed at combinatorial optimization tasks which
 		often involve in working
 		with graphs.
 		<b>
 		LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>
 		project.
 		You are free to use it in your commercial or
 		non-commercial applications under very permissive
 		\ref license "license terms".
 		</b>
 		\subsection howtoread How to read the documentation
 		If you want to get a quick start and see the most important features then
 		take a look at our \ref quicktour
 		"Quick Tour to LEMON" which will guide you along.
-		If you already feel like using our library, see the
+		If you would like to get to know the library, see
 		<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
 		If you know what you are looking for then try to find it under the
+		If you know what you are looking for, then try to find it under the
 		<a class="el" href="modules.html">Modules</a> section.
 		If you are a user of the old (0.x) series of LEMON, please check out the
 		\ref migration "Migration Guide" for the backward incompatibilities.
 		*/

lemon/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			lemon/lemon.pc.in \
 			lemon/CMakeLists.txt
 		pkgconfig_DATA += lemon/lemon.pc
 		lib_LTLIBRARIES += lemon/libemon.la
 		lemon_libemon_la_SOURCES = \
 			lemon/arg_parser.cc \
 			lemon/base.cc \
 			lemon/color.cc \
 			lemon/lp_base.cc \
 			lemon/lp_skeleton.cc \
 			lemon/random.cc \
 			lemon/bits/windows.cc
 		nodist_lemon_HEADERS = lemon/config.h
 		lemon_libemon_la_CXXFLAGS = \
 			$(AM_CXXFLAGS) \
 			$(GLPK_CFLAGS) \
 			$(CPLEX_CFLAGS) \
 			$(SOPLEX_CXXFLAGS) \
 			$(CLP_CXXFLAGS) \
 			$(CBC_CXXFLAGS)
 		lemon_libemon_la_LDFLAGS = \
 			$(GLPK_LIBS) \
 			$(CPLEX_LIBS) \
 			$(SOPLEX_LIBS) \
 			$(CLP_LIBS) \
 			$(CBC_LIBS)
 		if HAVE_GLPK
 		lemon_libemon_la_SOURCES += lemon/glpk.cc
 		endif
 		if HAVE_CPLEX
 		lemon_libemon_la_SOURCES += lemon/cplex.cc
 		endif
 		if HAVE_SOPLEX
 		lemon_libemon_la_SOURCES += lemon/soplex.cc
 		endif
 		if HAVE_CLP
 		lemon_libemon_la_SOURCES += lemon/clp.cc
 		endif
 		if HAVE_CBC
 		lemon_libemon_la_SOURCES += lemon/cbc.cc
 		endif
 		lemon_HEADERS += \
 			lemon/adaptors.h \
 			lemon/arg_parser.h \
 			lemon/assert.h \
 			lemon/bfs.h \
 			lemon/bin_heap.h \
 			lemon/cbc.h \
 			lemon/circulation.h \
 			lemon/clp.h \
 			lemon/color.h \
 			lemon/concept_check.h \
 			lemon/connectivity.h \
 			lemon/counter.h \
 			lemon/core.h \
 			lemon/cplex.h \
 			lemon/dfs.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
 			lemon/dimacs.h \
 			lemon/edge_set.h \
 			lemon/elevator.h \
 			lemon/error.h \
 			lemon/euler.h \
 			lemon/full_graph.h \
 			lemon/glpk.h \
 			lemon/gomory_hu.h \
 			lemon/graph_to_eps.h \
 			lemon/grid_graph.h \
 			lemon/hypercube_graph.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
 			lemon/lgf_writer.h \
 			lemon/list_graph.h \
 			lemon/lp.h \
 			lemon/lp_base.h \
 			lemon/lp_skeleton.h \
 			lemon/list_graph.h \
 			lemon/maps.h \
 			lemon/matching.h \
 			lemon/math.h \
 			lemon/min_cost_arborescence.h \
 			lemon/nauty_reader.h \
 			lemon/network_simplex.h \
 			lemon/path.h \
 			lemon/preflow.h \
 			lemon/radix_sort.h \
 			lemon/random.h \
 			lemon/smart_graph.h \
 			lemon/soplex.h \
 			lemon/suurballe.h \
 			lemon/time_measure.h \
 			lemon/tolerance.h \
 			lemon/unionfind.h \
 			lemon/bits/windows.h
 		bits_HEADERS += \
 			lemon/bits/alteration_notifier.h \
 			lemon/bits/array_map.h \
 			lemon/bits/base_extender.h \
 			lemon/bits/bezier.h \
 			lemon/bits/default_map.h \
 			lemon/bits/edge_set_extender.h \
 			lemon/bits/enable_if.h \
 			lemon/bits/graph_adaptor_extender.h \
 			lemon/bits/graph_extender.h \
 			lemon/bits/map_extender.h \
 			lemon/bits/path_dump.h \
 			lemon/bits/solver_bits.h \
 			lemon/bits/traits.h \
 			lemon/bits/variant.h \
 			lemon/bits/vector_map.h
 		concept_HEADERS += \
 			lemon/concepts/digraph.h \
 			lemon/concepts/graph.h \
 			lemon/concepts/graph_components.h \
 			lemon/concepts/heap.h \
 			lemon/concepts/maps.h \
 			lemon/concepts/path.h

lemon/adaptors.h

Show inline comments

@@ -306,3218 +306,3215 @@
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename DGR>
 		  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
 		    typedef DigraphAdaptorBase<DGR> Parent;
 		  public:
 		    typedef DGR Digraph;
 		  protected:
 		    ReverseDigraphBase() : Parent() { }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
 		    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
 		    void nextIn(Arc& a) const { Parent::nextOut(a); }
 		    void nextOut(Arc& a) const { Parent::nextIn(a); }
 		    Node source(const Arc& a) const { return Parent::target(a); }
 		    Node target(const Arc& a) const { return Parent::source(a); }
 		    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      return Parent::findArc(v, u, prev);
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for reversing the orientation of the arcs in
 		  /// a digraph.
 		  ///
 		  /// ReverseDigraph can be used for reversing the arcs in a digraph.
 		  /// It conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  ///
 		  /// \note The \c Node and \c Arc types of this adaptor and the adapted
 		  /// digraph are convertible to each other.
 		  template<typename DGR>
 		#ifdef DOXYGEN
 		  class ReverseDigraph {
 		#else
 		  class ReverseDigraph :
 		    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
 		#endif
 		    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		  protected:
 		    ReverseDigraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a reverse digraph adaptor for the given digraph.
 		    explicit ReverseDigraph(DGR& digraph) {
 		      Parent::initialize(digraph);
+		    }
 		  };
 		  /// \brief Returns a read-only ReverseDigraph adaptor
 		  ///
 		  /// This function just returns a read-only \ref ReverseDigraph adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates ReverseDigraph
 		  template<typename DGR>
 		  ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
 		    return ReverseDigraph<const DGR>(digraph);
+		  }
 		  template <typename DGR, typename NF, typename AF, bool ch = true>
 		  class SubDigraphBase : public DigraphAdaptorBase<DGR> {
 		    typedef DigraphAdaptorBase<DGR> Parent;
 		  public:
 		    typedef DGR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef AF ArcFilterMap;
 		    typedef SubDigraphBase Adaptor;
 		  protected:
 		    NF* _node_filter;
 		    AF* _arc_filter;
 		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
 		      Parent::initialize(digraph);
 		      _node_filter = &node_filter;
 		      _arc_filter = &arc_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
 		    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
 		    bool status(const Node& n) const { return (*_node_filter)[n]; }
 		    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
 		    typedef False NodeNumTag;
 		    typedef False ArcNumTag;
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& source, const Node& target,
 		                const Arc& prev = INVALID) const {
 		      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(source, target, prev);
 		      while (arc != INVALID && !(*_arc_filter)[arc]) {
 		        arc = Parent::findArc(source, target, arc);
+		      }
 		      return arc;
+		    }
 		  public:
 		    template <typename V>
 		    class NodeMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 			      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 			LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 			      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename DGR, typename NF, typename AF>
 		  class SubDigraphBase<DGR, NF, AF, false>
 		    : public DigraphAdaptorBase<DGR> {
 		    typedef DigraphAdaptorBase<DGR> Parent;
 		  public:
 		    typedef DGR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef AF ArcFilterMap;
 		    typedef SubDigraphBase Adaptor;
 		  protected:
 		    NF* _node_filter;
 		    AF* _arc_filter;
 		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
 		      Parent::initialize(digraph);
 		      _node_filter = &node_filter;
 		      _arc_filter = &arc_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
+		    }
 		    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
 		    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
 		    bool status(const Node& n) const { return (*_node_filter)[n]; }
 		    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
 		    typedef False NodeNumTag;
 		    typedef False ArcNumTag;
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& source, const Node& target,
 		                const Arc& prev = INVALID) const {
 		      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(source, target, prev);
 		      while (arc != INVALID && !(*_arc_filter)[arc]) {
 		        arc = Parent::findArc(source, target, arc);
+		      }
 		      return arc;
+		    }
 		    template <typename V>
 		    class NodeMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding nodes and arcs in a digraph
 		  ///
 		  /// SubDigraph can be used for hiding nodes and arcs in a digraph.
 		  /// A \c bool node map and a \c bool arc map must be specified, which
 		  /// define the filters for nodes and arcs.
 		  /// Only the nodes and arcs with \c true filter value are
 		  /// shown in the subdigraph. The arcs that are incident to hidden
 		  /// nodes are also filtered out.
 		  /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam NF The type of the node filter map.
 		  /// It must be a \c bool (or convertible) node map of the
 		  /// adapted digraph. The default type is
 		  /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".
 		  /// \tparam AF The type of the arc filter map.
 		  /// It must be \c bool (or convertible) arc map of the
 		  /// adapted digraph. The default type is
 		  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
 		  ///
 		  /// \note The \c Node and \c Arc types of this adaptor and the adapted
 		  /// digraph are convertible to each other.
 		  ///
 		  /// \see FilterNodes
 		  /// \see FilterArcs
 		#ifdef DOXYGEN
 		  template<typename DGR, typename NF, typename AF>
 		  class SubDigraph {
 		#else
 		  template<typename DGR,
 		           typename NF = typename DGR::template NodeMap<bool>,
 		           typename AF = typename DGR::template ArcMap<bool> >
 		  class SubDigraph :
 		    public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > {
 		#endif
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		    /// The type of the node filter map.
 		    typedef NF NodeFilterMap;
 		    /// The type of the arc filter map.
 		    typedef AF ArcFilterMap;
 		    typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> >
 		      Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    SubDigraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subdigraph for the given digraph with the
 		    /// given node and arc filter maps.
 		    SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) {
 		      Parent::initialize(digraph, node_filter, arc_filter);
+		    }
 		    /// \brief Sets the status of the given node
 		    ///
 		    /// This function sets the status of the given node.
 		    /// It is done by simply setting the assigned value of \c n
 		    /// to \c v in the node filter map.
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    /// \brief Sets the status of the given arc
 		    ///
 		    /// This function sets the status of the given arc.
 		    /// It is done by simply setting the assigned value of \c a
 		    /// to \c v in the arc filter map.
 		    void status(const Arc& a, bool v) const { Parent::status(a, v); }
 		    /// \brief Returns the status of the given node
 		    ///
 		    /// This function returns the status of the given node.
 		    /// It is \c true if the given node is enabled (i.e. not hidden).
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    /// \brief Returns the status of the given arc
 		    ///
 		    /// This function returns the status of the given arc.
 		    /// It is \c true if the given arc is enabled (i.e. not hidden).
 		    bool status(const Arc& a) const { return Parent::status(a); }
 		    /// \brief Disables the given node
 		    ///
 		    /// This function disables the given node in the subdigraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(n, false)".
 		    void disable(const Node& n) const { Parent::status(n, false); }
 		    /// \brief Disables the given arc
 		    ///
 		    /// This function disables the given arc in the subdigraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(a, false)".
 		    void disable(const Arc& a) const { Parent::status(a, false); }
 		    /// \brief Enables the given node
 		    ///
 		    /// This function enables the given node in the subdigraph.
 		    /// It is the same as \ref status() "status(n, true)".
 		    void enable(const Node& n) const { Parent::status(n, true); }
 		    /// \brief Enables the given arc
 		    ///
 		    /// This function enables the given arc in the subdigraph.
 		    /// It is the same as \ref status() "status(a, true)".
 		    void enable(const Arc& a) const { Parent::status(a, true); }
 		  };
 		  /// \brief Returns a read-only SubDigraph adaptor
 		  ///
 		  /// This function just returns a read-only \ref SubDigraph adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates SubDigraph
 		  template<typename DGR, typename NF, typename AF>
 		  SubDigraph<const DGR, NF, AF>
 		  subDigraph(const DGR& digraph,
 		             NF& node_filter, AF& arc_filter) {
 		    return SubDigraph<const DGR, NF, AF>
 		      (digraph, node_filter, arc_filter);
+		  }
 		  template<typename DGR, typename NF, typename AF>
 		  SubDigraph<const DGR, const NF, AF>
 		  subDigraph(const DGR& digraph,
 		             const NF& node_filter, AF& arc_filter) {
 		    return SubDigraph<const DGR, const NF, AF>
 		      (digraph, node_filter, arc_filter);
+		  }
 		  template<typename DGR, typename NF, typename AF>
 		  SubDigraph<const DGR, NF, const AF>
 		  subDigraph(const DGR& digraph,
 		             NF& node_filter, const AF& arc_filter) {
 		    return SubDigraph<const DGR, NF, const AF>
 		      (digraph, node_filter, arc_filter);
+		  }
 		  template<typename DGR, typename NF, typename AF>
 		  SubDigraph<const DGR, const NF, const AF>
 		  subDigraph(const DGR& digraph,
 		             const NF& node_filter, const AF& arc_filter) {
 		    return SubDigraph<const DGR, const NF, const AF>
 		      (digraph, node_filter, arc_filter);
+		  }
 		  template <typename GR, typename NF, typename EF, bool ch = true>
 		  class SubGraphBase : public GraphAdaptorBase<GR> {
 		    typedef GraphAdaptorBase<GR> Parent;
 		  public:
 		    typedef GR Graph;
 		    typedef NF NodeFilterMap;
 		    typedef EF EdgeFilterMap;
 		    typedef SubGraphBase Adaptor;
 		  protected:
 		    NF* _node_filter;
 		    EF* _edge_filter;
 		    SubGraphBase()
 		      : Parent(), _node_filter(0), _edge_filter(0) { }
 		    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
 		      Parent::initialize(graph);
 		      _node_filter = &node_filter;
 		      _edge_filter = &edge_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::source(i)]
 		                            || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void first(Edge& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::u(i)]
 		                            || !(*_node_filter)[Parent::v(i)]))
 		        Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void firstInc(Edge& i, bool& d, const Node& n) const {
 		      Parent::firstInc(i, d, n);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::u(i)]
 		                            || !(*_node_filter)[Parent::v(i)]))
 		        Parent::nextInc(i, d);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::source(i)]
 		                            || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void next(Edge& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::u(i)]
 		                            || !(*_node_filter)[Parent::v(i)]))
 		        Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void nextInc(Edge& i, bool& d) const {
 		      Parent::nextInc(i, d);
 		      while (i!=INVALID && (!(*_edge_filter)[i]
 		                            || !(*_node_filter)[Parent::u(i)]
 		                            || !(*_node_filter)[Parent::v(i)]))
 		        Parent::nextInc(i, d);
+		    }
 		    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
 		    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
 		    bool status(const Node& n) const { return (*_node_filter)[n]; }
 		    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
 		    typedef False NodeNumTag;
 		    typedef False ArcNumTag;
 		    typedef False EdgeNumTag;
 		    typedef FindArcTagIndicator<Graph> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(u, v, prev);
 		      while (arc != INVALID && !(*_edge_filter)[arc]) {
 		        arc = Parent::findArc(u, v, arc);
+		      }
 		      return arc;
+		    }
 		    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 		    Edge findEdge(const Node& u, const Node& v,
 		                  const Edge& prev = INVALID) const {
 		      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
 		        return INVALID;
+		      }
 		      Edge edge = Parent::findEdge(u, v, prev);
 		      while (edge != INVALID && !(*_edge_filter)[edge]) {
 		        edge = Parent::findEdge(u, v, edge);
+		      }
 		      return edge;
+		    }
 		    template <typename V>
 		    class NodeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class EdgeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename GR, typename NF, typename EF>
 		  class SubGraphBase<GR, NF, EF, false>
 		    : public GraphAdaptorBase<GR> {
 		    typedef GraphAdaptorBase<GR> Parent;
 		  public:
 		    typedef GR Graph;
 		    typedef NF NodeFilterMap;
 		    typedef EF EdgeFilterMap;
 		    typedef SubGraphBase Adaptor;
 		  protected:
 		    NF* _node_filter;
 		    EF* _edge_filter;
 		    SubGraphBase()
 			  : Parent(), _node_filter(0), _edge_filter(0) { }
 		    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
 		      Parent::initialize(graph);
 		      _node_filter = &node_filter;
 		      _edge_filter = &edge_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
+		    }
 		    void first(Edge& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
+		    }
 		    void firstInc(Edge& i, bool& d, const Node& n) const {
 		      Parent::firstInc(i, d, n);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
+		    }
 		    void next(Edge& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i);
+		    }
 		    void nextInc(Edge& i, bool& d) const {
 		      Parent::nextInc(i, d);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);
+		    }
 		    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
 		    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }
 		    bool status(const Node& n) const { return (*_node_filter)[n]; }
 		    bool status(const Edge& e) const { return (*_edge_filter)[e]; }
 		    typedef False NodeNumTag;
 		    typedef False ArcNumTag;
 		    typedef False EdgeNumTag;
 		    typedef FindArcTagIndicator<Graph> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      Arc arc = Parent::findArc(u, v, prev);
 		      while (arc != INVALID && !(*_edge_filter)[arc]) {
 		        arc = Parent::findArc(u, v, arc);
+		      }
 		      return arc;
+		    }
 		    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 		    Edge findEdge(const Node& u, const Node& v,
 		                  const Edge& prev = INVALID) const {
 		      Edge edge = Parent::findEdge(u, v, prev);
 		      while (edge != INVALID && !(*_edge_filter)[edge]) {
 		        edge = Parent::findEdge(u, v, edge);
+		      }
 		      return edge;
+		    }
 		    template <typename V>
 		    class NodeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class EdgeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 			LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding nodes and edges in an undirected
 		  /// graph.
 		  ///
 		  /// SubGraph can be used for hiding nodes and edges in a graph.
 		  /// A \c bool node map and a \c bool edge map must be specified, which
 		  /// define the filters for nodes and edges.
 		  /// Only the nodes and edges with \c true filter value are
 		  /// shown in the subgraph. The edges that are incident to hidden
 		  /// nodes are also filtered out.
 		  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
 		  ///
 		  /// The adapted graph can also be modified through this adaptor
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam NF The type of the node filter map.
 		  /// It must be a \c bool (or convertible) node map of the
 		  /// adapted graph. The default type is
 		  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
 		  /// \tparam EF The type of the edge filter map.
 		  /// It must be a \c bool (or convertible) edge map of the
 		  /// adapted graph. The default type is
 		  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
 		  ///
 		  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
 		  /// adapted graph are convertible to each other.
 		  ///
 		  /// \see FilterNodes
 		  /// \see FilterEdges
 		#ifdef DOXYGEN
 		  template<typename GR, typename NF, typename EF>
 		  class SubGraph {
 		#else
 		  template<typename GR,
 		           typename NF = typename GR::template NodeMap<bool>,
 		           typename EF = typename GR::template EdgeMap<bool> >
 		  class SubGraph :
 		    public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {
 		#endif
 		  public:
 		    /// The type of the adapted graph.
 		    typedef GR Graph;
 		    /// The type of the node filter map.
 		    typedef NF NodeFilterMap;
 		    /// The type of the edge filter map.
 		    typedef EF EdgeFilterMap;
 		    typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> >
 		      Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    SubGraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given graph with the given node
 		    /// and edge filter maps.
 		    SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
 		      initialize(graph, node_filter, edge_filter);
+		    }
 		    /// \brief Sets the status of the given node
 		    ///
 		    /// This function sets the status of the given node.
 		    /// It is done by simply setting the assigned value of \c n
 		    /// to \c v in the node filter map.
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    /// \brief Sets the status of the given edge
 		    ///
 		    /// This function sets the status of the given edge.
 		    /// It is done by simply setting the assigned value of \c e
 		    /// to \c v in the edge filter map.
 		    void status(const Edge& e, bool v) const { Parent::status(e, v); }
 		    /// \brief Returns the status of the given node
 		    ///
 		    /// This function returns the status of the given node.
 		    /// It is \c true if the given node is enabled (i.e. not hidden).
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    /// \brief Returns the status of the given edge
 		    ///
 		    /// This function returns the status of the given edge.
 		    /// It is \c true if the given edge is enabled (i.e. not hidden).
 		    bool status(const Edge& e) const { return Parent::status(e); }
 		    /// \brief Disables the given node
 		    ///
 		    /// This function disables the given node in the subdigraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(n, false)".
 		    void disable(const Node& n) const { Parent::status(n, false); }
 		    /// \brief Disables the given edge
 		    ///
 		    /// This function disables the given edge in the subgraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(e, false)".
 		    void disable(const Edge& e) const { Parent::status(e, false); }
 		    /// \brief Enables the given node
 		    ///
 		    /// This function enables the given node in the subdigraph.
 		    /// It is the same as \ref status() "status(n, true)".
 		    void enable(const Node& n) const { Parent::status(n, true); }
 		    /// \brief Enables the given edge
 		    ///
 		    /// This function enables the given edge in the subgraph.
 		    /// It is the same as \ref status() "status(e, true)".
 		    void enable(const Edge& e) const { Parent::status(e, true); }
 		  };
 		  /// \brief Returns a read-only SubGraph adaptor
 		  ///
 		  /// This function just returns a read-only \ref SubGraph adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates SubGraph
 		  template<typename GR, typename NF, typename EF>
 		  SubGraph<const GR, NF, EF>
 		  subGraph(const GR& graph, NF& node_filter, EF& edge_filter) {
 		    return SubGraph<const GR, NF, EF>
 		      (graph, node_filter, edge_filter);
+		  }
 		  template<typename GR, typename NF, typename EF>
 		  SubGraph<const GR, const NF, EF>
 		  subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) {
 		    return SubGraph<const GR, const NF, EF>
 		      (graph, node_filter, edge_filter);
+		  }
 		  template<typename GR, typename NF, typename EF>
 		  SubGraph<const GR, NF, const EF>
 		  subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) {
 		    return SubGraph<const GR, NF, const EF>
 		      (graph, node_filter, edge_filter);
+		  }
 		  template<typename GR, typename NF, typename EF>
 		  SubGraph<const GR, const NF, const EF>
 		  subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {
 		    return SubGraph<const GR, const NF, const EF>
 		      (graph, node_filter, edge_filter);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding nodes in a digraph or a graph.
 		  ///
 		  /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
 		  /// graph. A \c bool node map must be specified, which defines the filter
 		  /// for the nodes. Only the nodes with \c true filter value and the
 		  /// arcs/edges incident to nodes both with \c true filter value are shown
 		  /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
 		  /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
 		  /// depending on the \c GR template parameter.
 		  ///
 		  /// The adapted (di)graph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs/edges, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam GR The type of the adapted digraph or graph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept
 		  /// or the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam NF The type of the node filter map.
 		  /// It must be a \c bool (or convertible) node map of the
 		  /// adapted (di)graph. The default type is
 		  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
 		  ///
 		  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
 		  /// adapted (di)graph are convertible to each other.
 		#ifdef DOXYGEN
 		  template<typename GR, typename NF>
 		  class FilterNodes {
 		#else
 		  template<typename GR,
 		           typename NF = typename GR::template NodeMap<bool>,
 		           typename Enable = void>
 		  class FilterNodes :
 		    public DigraphAdaptorExtender<
 		      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
 		                     true> > {
 		#endif
 		    typedef DigraphAdaptorExtender<
 		      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
 		                     true> > Parent;
 		  public:
 		    typedef GR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
 		    FilterNodes() : const_true_map() {}
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given digraph or graph with the
 		    /// given node filter map.
 		    FilterNodes(GR& graph, NF& node_filter)
 		      : Parent(), const_true_map()
+		    {
 		      Parent::initialize(graph, node_filter, const_true_map);
+		    }
 		    /// \brief Sets the status of the given node
 		    ///
 		    /// This function sets the status of the given node.
 		    /// It is done by simply setting the assigned value of \c n
 		    /// to \c v in the node filter map.
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    /// \brief Returns the status of the given node
 		    ///
 		    /// This function returns the status of the given node.
 		    /// It is \c true if the given node is enabled (i.e. not hidden).
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    /// \brief Disables the given node
 		    ///
 		    /// This function disables the given node, so the iteration
 		    /// jumps over it.
 		    /// It is the same as \ref status() "status(n, false)".
 		    void disable(const Node& n) const { Parent::status(n, false); }
 		    /// \brief Enables the given node
 		    ///
 		    /// This function enables the given node.
 		    /// It is the same as \ref status() "status(n, true)".
 		    void enable(const Node& n) const { Parent::status(n, true); }
 		  };
 		  template<typename GR, typename NF>
 		  class FilterNodes<GR, NF,
 		                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
 		    public GraphAdaptorExtender<
 		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		                   true> > {
 		    typedef GraphAdaptorExtender<
 		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		                   true> > Parent;
 		  public:
 		    typedef GR Graph;
 		    typedef NF NodeFilterMap;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
 		    FilterNodes() : const_true_map() {}
 		  public:
 		    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
 		      Parent(), const_true_map() {
 		      Parent::initialize(graph, node_filter, const_true_map);
+		    }
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    void disable(const Node& n) const { Parent::status(n, false); }
 		    void enable(const Node& n) const { Parent::status(n, true); }
 		  };
 		  /// \brief Returns a read-only FilterNodes adaptor
 		  ///
 		  /// This function just returns a read-only \ref FilterNodes adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates FilterNodes
 		  template<typename GR, typename NF>
 		  FilterNodes<const GR, NF>
 		  filterNodes(const GR& graph, NF& node_filter) {
 		    return FilterNodes<const GR, NF>(graph, node_filter);
+		  }
 		  template<typename GR, typename NF>
 		  FilterNodes<const GR, const NF>
 		  filterNodes(const GR& graph, const NF& node_filter) {
 		    return FilterNodes<const GR, const NF>(graph, node_filter);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding arcs in a digraph.
 		  ///
 		  /// FilterArcs adaptor can be used for hiding arcs in a digraph.
 		  /// A \c bool arc map must be specified, which defines the filter for
 		  /// the arcs. Only the arcs with \c true filter value are shown in the
 		  /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
 		  /// "Digraph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam AF The type of the arc filter map.
 		  /// It must be a \c bool (or convertible) arc map of the
 		  /// adapted digraph. The default type is
 		  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
 		  ///
 		  /// \note The \c Node and \c Arc types of this adaptor and the adapted
 		  /// digraph are convertible to each other.
 		#ifdef DOXYGEN
 		  template<typename DGR,
 		           typename AF>
 		  class FilterArcs {
 		#else
 		  template<typename DGR,
 		           typename AF = typename DGR::template ArcMap<bool> >
 		  class FilterArcs :
 		    public DigraphAdaptorExtender<
 		      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
 		                     AF, false> > {
 		#endif
 		    typedef DigraphAdaptorExtender<
 		      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
 		                     AF, false> > Parent;
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		    /// The type of the arc filter map.
 		    typedef AF ArcFilterMap;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
 		    FilterArcs() : const_true_map() {}
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subdigraph for the given digraph with the given arc
 		    /// filter map.
 		    FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
 		      : Parent(), const_true_map() {
 		      Parent::initialize(digraph, const_true_map, arc_filter);
+		    }
 		    /// \brief Sets the status of the given arc
 		    ///
 		    /// This function sets the status of the given arc.
 		    /// It is done by simply setting the assigned value of \c a
 		    /// to \c v in the arc filter map.
 		    void status(const Arc& a, bool v) const { Parent::status(a, v); }
 		    /// \brief Returns the status of the given arc
 		    ///
 		    /// This function returns the status of the given arc.
 		    /// It is \c true if the given arc is enabled (i.e. not hidden).
 		    bool status(const Arc& a) const { return Parent::status(a); }
 		    /// \brief Disables the given arc
 		    ///
 		    /// This function disables the given arc in the subdigraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(a, false)".
 		    void disable(const Arc& a) const { Parent::status(a, false); }
 		    /// \brief Enables the given arc
 		    ///
 		    /// This function enables the given arc in the subdigraph.
 		    /// It is the same as \ref status() "status(a, true)".
 		    void enable(const Arc& a) const { Parent::status(a, true); }
 		  };
 		  /// \brief Returns a read-only FilterArcs adaptor
 		  ///
 		  /// This function just returns a read-only \ref FilterArcs adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates FilterArcs
 		  template<typename DGR, typename AF>
 		  FilterArcs<const DGR, AF>
 		  filterArcs(const DGR& digraph, AF& arc_filter) {
 		    return FilterArcs<const DGR, AF>(digraph, arc_filter);
+		  }
 		  template<typename DGR, typename AF>
 		  FilterArcs<const DGR, const AF>
 		  filterArcs(const DGR& digraph, const AF& arc_filter) {
 		    return FilterArcs<const DGR, const AF>(digraph, arc_filter);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for hiding edges in a graph.
 		  ///
 		  /// FilterEdges adaptor can be used for hiding edges in a graph.
 		  /// A \c bool edge map must be specified, which defines the filter for
 		  /// the edges. Only the edges with \c true filter value are shown in the
 		  /// subgraph. This adaptor conforms to the \ref concepts::Graph
 		  /// "Graph" concept.
 		  ///
 		  /// The adapted graph can also be modified through this adaptor
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam EF The type of the edge filter map.
 		  /// It must be a \c bool (or convertible) edge map of the
 		  /// adapted graph. The default type is
 		  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
 		  ///
 		  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
 		  /// adapted graph are convertible to each other.
 		#ifdef DOXYGEN
 		  template<typename GR,
 		           typename EF>
 		  class FilterEdges {
 		#else
 		  template<typename GR,
 		           typename EF = typename GR::template EdgeMap<bool> >
 		  class FilterEdges :
 		    public GraphAdaptorExtender<
 		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
 		                   EF, false> > {
 		#endif
 		    typedef GraphAdaptorExtender<
 		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
 		                   EF, false> > Parent;
 		  public:
 		    /// The type of the adapted graph.
 		    typedef GR Graph;
 		    /// The type of the edge filter map.
 		    typedef EF EdgeFilterMap;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
 		    FilterEdges() : const_true_map(true) {
 		      Parent::setNodeFilterMap(const_true_map);
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given graph with the given edge
 		    /// filter map.
 		    FilterEdges(GR& graph, EF& edge_filter)
 		      : Parent(), const_true_map() {
 		      Parent::initialize(graph, const_true_map, edge_filter);
+		    }
 		    /// \brief Sets the status of the given edge
 		    ///
 		    /// This function sets the status of the given edge.
 		    /// It is done by simply setting the assigned value of \c e
 		    /// to \c v in the edge filter map.
 		    void status(const Edge& e, bool v) const { Parent::status(e, v); }
 		    /// \brief Returns the status of the given edge
 		    ///
 		    /// This function returns the status of the given edge.
 		    /// It is \c true if the given edge is enabled (i.e. not hidden).
 		    bool status(const Edge& e) const { return Parent::status(e); }
 		    /// \brief Disables the given edge
 		    ///
 		    /// This function disables the given edge in the subgraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(e, false)".
 		    void disable(const Edge& e) const { Parent::status(e, false); }
 		    /// \brief Enables the given edge
 		    ///
 		    /// This function enables the given edge in the subgraph.
 		    /// It is the same as \ref status() "status(e, true)".
 		    void enable(const Edge& e) const { Parent::status(e, true); }
 		  };
 		  /// \brief Returns a read-only FilterEdges adaptor
 		  ///
 		  /// This function just returns a read-only \ref FilterEdges adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates FilterEdges
 		  template<typename GR, typename EF>
 		  FilterEdges<const GR, EF>
 		  filterEdges(const GR& graph, EF& edge_filter) {
 		    return FilterEdges<const GR, EF>(graph, edge_filter);
+		  }
 		  template<typename GR, typename EF>
 		  FilterEdges<const GR, const EF>
 		  filterEdges(const GR& graph, const EF& edge_filter) {
 		    return FilterEdges<const GR, const EF>(graph, edge_filter);
+		  }
 		  template <typename DGR>
 		  class UndirectorBase {
 		  public:
 		    typedef DGR Digraph;
 		    typedef UndirectorBase Adaptor;
 		    typedef True UndirectedTag;
 		    typedef typename Digraph::Arc Edge;
 		    typedef typename Digraph::Node Node;
-		    class Arc : public Edge {
 		    class Arc {
 		      friend class UndirectorBase;
 		    protected:
 		      Edge _edge;
 		      bool _forward;
 		      Arc(const Edge& edge, bool forward) :
 		        Edge(edge), _forward(forward) {}
 		      Arc(const Edge& edge, bool forward)
 		        : _edge(edge), _forward(forward) {}
 		    public:
 		      Arc() {}
-		      Arc(Invalid) : Edge(INVALID), _forward(true) {}
+		      Arc(Invalid) : _edge(INVALID), _forward(true) {}
 		      operator const Edge&() const { return _edge; }
 		      bool operator==(const Arc &other) const {
 		        return _forward == other._forward &&
 		          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
 		        return _forward == other._forward && _edge == other._edge;
+		      }
 		      bool operator!=(const Arc &other) const {
 		        return _forward != other._forward ||
 		          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
 		        return _forward != other._forward || _edge != other._edge;
+		      }
 		      bool operator<(const Arc &other) const {
 		        return _forward < other._forward ||
 		          (_forward == other._forward &&
 		           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
 		          (_forward == other._forward && _edge < other._edge);
+		      }
 		    };
 		    void first(Node& n) const {
 		      _digraph->first(n);
+		    }
 		    void next(Node& n) const {
 		      _digraph->next(n);
+		    }
 		    void first(Arc& a) const {
 		      _digraph->first(a);
+		      _digraph->first(a._edge);
 		      a._forward = true;
+		    }
 		    void next(Arc& a) const {
 		      if (a._forward) {
 		        a._forward = false;
 		      } else {
 		        _digraph->next(a);
+		        _digraph->next(a._edge);
 		        a._forward = true;
+		      }
+		    }
 		    void first(Edge& e) const {
 		      _digraph->first(e);
+		    }
 		    void next(Edge& e) const {
 		      _digraph->next(e);
+		    }
 		    void firstOut(Arc& a, const Node& n) const {
 		      _digraph->firstIn(a, n);
 		      if( static_cast<const Edge&>(a) != INVALID ) {
 		      _digraph->firstIn(a._edge, n);
 		      if (a._edge != INVALID ) {
 		        a._forward = false;
 		      } else {
 		        _digraph->firstOut(a, n);
+		        _digraph->firstOut(a._edge, n);
 		        a._forward = true;
+		      }
+		    }
 		    void nextOut(Arc &a) const {
 		      if (!a._forward) {
 		        Node n = _digraph->target(a);
 		        _digraph->nextIn(a);
 		        if (static_cast<const Edge&>(a) == INVALID ) {
 		          _digraph->firstOut(a, n);
 		        Node n = _digraph->target(a._edge);
 		        _digraph->nextIn(a._edge);
 		        if (a._edge == INVALID) {
 		          _digraph->firstOut(a._edge, n);
 		          a._forward = true;
+		        }
+		      }
 		      else {
 		        _digraph->nextOut(a);
+		        _digraph->nextOut(a._edge);
+		      }
+		    }
 		    void firstIn(Arc &a, const Node &n) const {
 		      _digraph->firstOut(a, n);
 		      if (static_cast<const Edge&>(a) != INVALID ) {
 		      _digraph->firstOut(a._edge, n);
 		      if (a._edge != INVALID ) {
 		        a._forward = false;
 		      } else {
 		        _digraph->firstIn(a, n);
+		        _digraph->firstIn(a._edge, n);
 		        a._forward = true;
+		      }
+		    }
 		    void nextIn(Arc &a) const {
 		      if (!a._forward) {
 		        Node n = _digraph->source(a);
 		        _digraph->nextOut(a);
 		        if( static_cast<const Edge&>(a) == INVALID ) {
 		          _digraph->firstIn(a, n);
 		        Node n = _digraph->source(a._edge);
 		        _digraph->nextOut(a._edge);
 		        if (a._edge == INVALID ) {
 		          _digraph->firstIn(a._edge, n);
 		          a._forward = true;
+		        }
+		      }
 		      else {
 		        _digraph->nextIn(a);
+		        _digraph->nextIn(a._edge);
+		      }
+		    }
 		    void firstInc(Edge &e, bool &d, const Node &n) const {
 		      d = true;
 		      _digraph->firstOut(e, n);
 		      if (e != INVALID) return;
 		      d = false;
 		      _digraph->firstIn(e, n);
+		    }
 		    void nextInc(Edge &e, bool &d) const {
 		      if (d) {
 		        Node s = _digraph->source(e);
 		        _digraph->nextOut(e);
 		        if (e != INVALID) return;
 		        d = false;
 		        _digraph->firstIn(e, s);
 		      } else {
 		        _digraph->nextIn(e);
+		      }
+		    }
 		    Node u(const Edge& e) const {
 		      return _digraph->source(e);
+		    }
 		    Node v(const Edge& e) const {
 		      return _digraph->target(e);
+		    }
 		    Node source(const Arc &a) const {
 		      return a._forward ? _digraph->source(a) : _digraph->target(a);
+		      return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
+		    }
 		    Node target(const Arc &a) const {
 		      return a._forward ? _digraph->target(a) : _digraph->source(a);
+		      return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
+		    }
 		    static Arc direct(const Edge &e, bool d) {
 		      return Arc(e, d);
+		    }
 		    Arc direct(const Edge &e, const Node& n) const {
 		      return Arc(e, _digraph->source(e) == n);
+		    }
 		    static bool direction(const Arc &a) { return a._forward; }
 		    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const {
 		      return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
+		    }
 		    Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
 		    int id(const Node &n) const { return _digraph->id(n); }
 		    int id(const Arc &a) const {
 		      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
+		    }
 		    int id(const Edge &e) const { return _digraph->id(e); }
 		    int maxNodeId() const { return _digraph->maxNodeId(); }
 		    int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
 		    int maxEdgeId() const { return _digraph->maxArcId(); }
 		    Node addNode() { return _digraph->addNode(); }
 		    Edge addEdge(const Node& u, const Node& v) {
 		      return _digraph->addArc(u, v);
+		    }
 		    void erase(const Node& i) { _digraph->erase(i); }
 		    void erase(const Edge& i) { _digraph->erase(i); }
 		    void clear() { _digraph->clear(); }
 		    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
 		    int nodeNum() const { return _digraph->nodeNum(); }
 		    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
 		    int arcNum() const { return 2 * _digraph->arcNum(); }
 		    typedef ArcNumTag EdgeNumTag;
 		    int edgeNum() const { return _digraph->arcNum(); }
 		    typedef FindArcTagIndicator<Digraph> FindArcTag;
 		    Arc findArc(Node s, Node t, Arc p = INVALID) const {
 		      if (p == INVALID) {
 		        Edge arc = _digraph->findArc(s, t);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = _digraph->findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else if (direction(p)) {
 		        Edge arc = _digraph->findArc(s, t, p);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = _digraph->findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else {
 		        Edge arc = _digraph->findArc(t, s, p);
 		        if (arc != INVALID) return direct(arc, false);
+		      }
 		      return INVALID;
+		    }
 		    typedef FindArcTag FindEdgeTag;
 		    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
 		      if (s != t) {
 		        if (p == INVALID) {
 		          Edge arc = _digraph->findArc(s, t);
 		          if (arc != INVALID) return arc;
 		          arc = _digraph->findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else if (_digraph->source(p) == s) {
 		          Edge arc = _digraph->findArc(s, t, p);
 		          if (arc != INVALID) return arc;
 		          arc = _digraph->findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else {
 		          Edge arc = _digraph->findArc(t, s, p);
 		          if (arc != INVALID) return arc;
+		        }
 		      } else {
 		        return _digraph->findArc(s, t, p);
+		      }
 		      return INVALID;
+		    }
 		  private:
 		    template <typename V>
 		    class ArcMapBase {
 		    private:
 		      typedef typename DGR::template ArcMap<V> MapImpl;
 		    public:
 		      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
 		      typedef V Value;
 		      typedef Arc Key;
 		      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
 		      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
 		      ArcMapBase(const UndirectorBase<DGR>& adaptor) :
 		        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
 		      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
 		        : _forward(*adaptor._digraph, value),
 		          _backward(*adaptor._digraph, value) {}
 		      void set(const Arc& a, const V& value) {
 		        if (direction(a)) {
 		          _forward.set(a, value);
 		        } else {
 		          _backward.set(a, value);
+		        }
+		      }
 		      ConstReturnValue operator[](const Arc& a) const {
 		        if (direction(a)) {
 		          return _forward[a];
 		        } else {
 		          return _backward[a];
+		        }
+		      }
 		      ReturnValue operator[](const Arc& a) {
 		        if (direction(a)) {
 		          return _forward[a];
 		        } else {
 		          return _backward[a];
+		        }
+		      }
 		    protected:
 		      MapImpl _forward, _backward;
 		    };
 		  public:
 		    template <typename V>
 		    class NodeMap : public DGR::template NodeMap<V> {
 		      typedef typename DGR::template NodeMap<V> Parent;
 		    public:
 		      typedef V Value;
 		      explicit NodeMap(const UndirectorBase<DGR>& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
 		        : Parent(*adaptor._digraph, value) { }
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
 		      typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
 		    public:
 		      typedef V Value;
 		      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class EdgeMap : public Digraph::template ArcMap<V> {
 		      typedef typename Digraph::template ArcMap<V> Parent;
 		    public:
 		      typedef V Value;
 		      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
 		        : Parent(*adaptor._digraph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
 		    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
 		    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
 		    typedef EdgeNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
 		  protected:
 		    UndirectorBase() : _digraph(0) {}
 		    DGR* _digraph;
 		    void initialize(DGR& digraph) {
 		      _digraph = &digraph;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for viewing a digraph as an undirected graph.
 		  ///
 		  /// Undirector adaptor can be used for viewing a digraph as an undirected
 		  /// graph. All arcs of the underlying digraph are showed in the
 		  /// adaptor as an edge (and also as a pair of arcs, of course).
 		  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  ///
 		  /// \note The \c Node type of this adaptor and the adapted digraph are
 		  /// convertible to each other, moreover the \c Edge type of the adaptor
 		  /// and the \c Arc type of the adapted digraph are also convertible to
 		  /// each other.
 		  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
 		  /// of the adapted digraph.)
 		  template<typename DGR>
 		#ifdef DOXYGEN
 		  class Undirector {
 		#else
 		  class Undirector :
 		    public GraphAdaptorExtender<UndirectorBase<DGR> > {
 		#endif
 		    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		  protected:
 		    Undirector() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates an undirected graph from the given digraph.
 		    Undirector(DGR& digraph) {
 		      initialize(digraph);
+		    }
 		    /// \brief Arc map combined from two original arc maps
 		    ///
 		    /// This map adaptor class adapts two arc maps of the underlying
 		    /// digraph to get an arc map of the undirected graph.
 		    /// Its value type is inherited from the first arc map type (\c FW).
 		    /// \tparam FW The type of the "foward" arc map.
 		    /// \tparam BK The type of the "backward" arc map.
 		    template <typename FW, typename BK>
 		    class CombinedArcMap {
 		    public:
 		      /// The key type of the map
 		      typedef typename Parent::Arc Key;
 		      /// The value type of the map
 		      typedef typename FW::Value Value;
 		      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<FW>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<FW>::ReturnValue Reference;
 		      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
 		      /// Constructor
 		      CombinedArcMap(FW& forward, BK& backward)
 		        : _forward(&forward), _backward(&backward) {}
 		      /// Sets the value associated with the given key.
 		      void set(const Key& e, const Value& a) {
 		        if (Parent::direction(e)) {
 		          _forward->set(e, a);
 		        } else {
 		          _backward->set(e, a);
+		        }
+		      }
 		      /// Returns the value associated with the given key.
 		      ConstReturnValue operator[](const Key& e) const {
 		        if (Parent::direction(e)) {
 		          return (*_forward)[e];
 		        } else {
 		          return (*_backward)[e];
+		        }
+		      }
 		      /// Returns a reference to the value associated with the given key.
 		      ReturnValue operator[](const Key& e) {
 		        if (Parent::direction(e)) {
 		          return (*_forward)[e];
 		        } else {
 		          return (*_backward)[e];
+		        }
+		      }
 		    protected:
 		      FW* _forward;
 		      BK* _backward;
 		    };
 		    /// \brief Returns a combined arc map
 		    ///
 		    /// This function just returns a combined arc map.
 		    template <typename FW, typename BK>
 		    static CombinedArcMap<FW, BK>
 		    combinedArcMap(FW& forward, BK& backward) {
 		      return CombinedArcMap<FW, BK>(forward, backward);
+		    }
 		    template <typename FW, typename BK>
 		    static CombinedArcMap<const FW, BK>
 		    combinedArcMap(const FW& forward, BK& backward) {
 		      return CombinedArcMap<const FW, BK>(forward, backward);
+		    }
 		    template <typename FW, typename BK>
 		    static CombinedArcMap<FW, const BK>
 		    combinedArcMap(FW& forward, const BK& backward) {
 		      return CombinedArcMap<FW, const BK>(forward, backward);
+		    }
 		    template <typename FW, typename BK>
 		    static CombinedArcMap<const FW, const BK>
 		    combinedArcMap(const FW& forward, const BK& backward) {
 		      return CombinedArcMap<const FW, const BK>(forward, backward);
+		    }
 		  };
 		  /// \brief Returns a read-only Undirector adaptor
 		  ///
 		  /// This function just returns a read-only \ref Undirector adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates Undirector
 		  template<typename DGR>
 		  Undirector<const DGR> undirector(const DGR& digraph) {
 		    return Undirector<const DGR>(digraph);
+		  }
 		  template <typename GR, typename DM>
 		  class OrienterBase {
 		  public:
 		    typedef GR Graph;
 		    typedef DM DirectionMap;
 		    typedef typename GR::Node Node;
 		    typedef typename GR::Edge Arc;
 		    void reverseArc(const Arc& arc) {
 		      _direction->set(arc, !(*_direction)[arc]);
+		    }
 		    void first(Node& i) const { _graph->first(i); }
 		    void first(Arc& i) const { _graph->first(i); }
 		    void firstIn(Arc& i, const Node& n) const {
 		      bool d = true;
 		      _graph->firstInc(i, d, n);
 		      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    void firstOut(Arc& i, const Node& n ) const {
 		      bool d = true;
 		      _graph->firstInc(i, d, n);
 		      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    void next(Node& i) const { _graph->next(i); }
 		    void next(Arc& i) const { _graph->next(i); }
 		    void nextIn(Arc& i) const {
 		      bool d = !(*_direction)[i];
 		      _graph->nextInc(i, d);
 		      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    void nextOut(Arc& i) const {
 		      bool d = (*_direction)[i];
 		      _graph->nextInc(i, d);
 		      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    Node source(const Arc& e) const {
 		      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
+		    }
 		    Node target(const Arc& e) const {
 		      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
+		    }
 		    typedef NodeNumTagIndicator<Graph> NodeNumTag;
 		    int nodeNum() const { return _graph->nodeNum(); }
 		    typedef EdgeNumTagIndicator<Graph> ArcNumTag;
 		    int arcNum() const { return _graph->edgeNum(); }
 		    typedef FindEdgeTagIndicator<Graph> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      Arc arc = _graph->findEdge(u, v, prev);
 		      while (arc != INVALID && source(arc) != u) {
 		        arc = _graph->findEdge(u, v, arc);
+		      }
 		      return arc;
+		    }
 		    Node addNode() {
 		      return Node(_graph->addNode());
+		    }
 		    Arc addArc(const Node& u, const Node& v) {
 		      Arc arc = _graph->addEdge(u, v);
 		      _direction->set(arc, _graph->u(arc) == u);
 		      return arc;
+		    }
 		    void erase(const Node& i) { _graph->erase(i); }
 		    void erase(const Arc& i) { _graph->erase(i); }
 		    void clear() { _graph->clear(); }
 		    int id(const Node& v) const { return _graph->id(v); }
 		    int id(const Arc& e) const { return _graph->id(e); }
 		    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
 		    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
 		    int maxNodeId() const { return _graph->maxNodeId(); }
 		    int maxArcId() const { return _graph->maxEdgeId(); }
 		    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 		    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 		    template <typename V>
 		    class NodeMap : public GR::template NodeMap<V> {
 		      typedef typename GR::template NodeMap<V> Parent;
 		    public:
 		      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
 		        : Parent(*adapter._graph) {}
 		      NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap : public GR::template EdgeMap<V> {
 		      typedef typename Graph::template EdgeMap<V> Parent;
 		    public:
 		      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
 		        : Parent(*adapter._graph) { }
 		      ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
 		        : Parent(*adapter._graph, value) { }
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  protected:
 		    Graph* _graph;
 		    DM* _direction;
 		    void initialize(GR& graph, DM& direction) {
 		      _graph = &graph;
 		      _direction = &direction;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for orienting the edges of a graph to get a digraph
 		  ///
 		  /// Orienter adaptor can be used for orienting the edges of a graph to
 		  /// get a digraph. A \c bool edge map of the underlying graph must be
 		  /// specified, which define the direction of the arcs in the adaptor.
 		  /// The arcs can be easily reversed by the \c reverseArc() member function
 		  /// of the adaptor.
 		  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// The adapted graph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam DM The type of the direction map.
 		  /// It must be a \c bool (or convertible) edge map of the
 		  /// adapted graph. The default type is
 		  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
 		  ///
 		  /// \note The \c Node type of this adaptor and the adapted graph are
 		  /// convertible to each other, moreover the \c Arc type of the adaptor
 		  /// and the \c Edge type of the adapted graph are also convertible to
 		  /// each other.
 		#ifdef DOXYGEN
 		  template<typename GR,
 		           typename DM>
 		  class Orienter {
 		#else
 		  template<typename GR,
 		           typename DM = typename GR::template EdgeMap<bool> >
 		  class Orienter :
 		    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
 		#endif
 		    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
 		  public:
 		    /// The type of the adapted graph.
 		    typedef GR Graph;
 		    /// The type of the direction edge map.
 		    typedef DM DirectionMap;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    Orienter() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the adaptor.
 		    Orienter(GR& graph, DM& direction) {
 		      Parent::initialize(graph, direction);
+		    }
 		    /// \brief Reverses the given arc
 		    ///
 		    /// This function reverses the given arc.
 		    /// It is done by simply negate the assigned value of \c a
 		    /// in the direction map.
 		    void reverseArc(const Arc& a) {
 		      Parent::reverseArc(a);
+		    }
 		  };
 		  /// \brief Returns a read-only Orienter adaptor
 		  ///
 		  /// This function just returns a read-only \ref Orienter adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates Orienter
 		  template<typename GR, typename DM>
 		  Orienter<const GR, DM>
 		  orienter(const GR& graph, DM& direction) {
 		    return Orienter<const GR, DM>(graph, direction);
+		  }
 		  template<typename GR, typename DM>
 		  Orienter<const GR, const DM>
 		  orienter(const GR& graph, const DM& direction) {
 		    return Orienter<const GR, const DM>(graph, direction);
+		  }
 		  namespace _adaptor_bits {
 		    template <typename DGR, typename CM, typename FM, typename TL>
 		    class ResForwardFilter {
 		    public:
 		      typedef typename DGR::Arc Key;
 		      typedef bool Value;
 		    private:
 		      const CM* _capacity;
 		      const FM* _flow;
 		      TL _tolerance;
 		    public:
 		      ResForwardFilter(const CM& capacity, const FM& flow,
 		                       const TL& tolerance = TL())
 		        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
 		      bool operator[](const typename DGR::Arc& a) const {
 		        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
+		      }
 		    };
 		    template<typename DGR,typename CM, typename FM, typename TL>
 		    class ResBackwardFilter {
 		    public:
 		      typedef typename DGR::Arc Key;
 		      typedef bool Value;
 		    private:
 		      const CM* _capacity;
 		      const FM* _flow;
 		      TL _tolerance;
 		    public:
 		      ResBackwardFilter(const CM& capacity, const FM& flow,
 		                        const TL& tolerance = TL())
 		        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
 		      bool operator[](const typename DGR::Arc& a) const {
 		        return _tolerance.positive((*_flow)[a]);
+		      }
 		    };
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for composing the residual digraph for directed
 		  /// flow and circulation problems.
 		  ///
 		  /// ResidualDigraph can be used for composing the \e residual digraph
 		  /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
 		  /// be a directed graph and let \f$ F \f$ be a number type.
 		  /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
 		  /// This adaptor implements a digraph structure with node set \f$ V \f$
 		  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
 		  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
 		  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
 		  /// called residual digraph.
 		  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
 		  /// multiplicities are counted, i.e. the adaptor has exactly
 		  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
 		  /// arcs).
 		  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It is implicitly \c const.
 		  /// \tparam CM The type of the capacity map.
 		  /// It must be an arc map of some numerical type, which defines
 		  /// the capacities in the flow problem. It is implicitly \c const.
 		  /// The default type is
 		  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam FM The type of the flow map.
 		  /// It must be an arc map of some numerical type, which defines
 		  /// the flow values in the flow problem. The default type is \c CM.
 		  /// \tparam TL The tolerance type for handling inexact computation.
 		  /// The default tolerance type depends on the value type of the
 		  /// capacity map.
 		  ///
 		  /// \note This adaptor is implemented using Undirector and FilterArcs
 		  /// adaptors.
 		  ///
 		  /// \note The \c Node type of this adaptor and the adapted digraph are
 		  /// convertible to each other, moreover the \c Arc type of the adaptor
 		  /// is convertible to the \c Arc type of the adapted digraph.
 		#ifdef DOXYGEN
 		  template<typename DGR, typename CM, typename FM, typename TL>
 		  class ResidualDigraph
 		#else
 		  template<typename DGR,
 		           typename CM = typename DGR::template ArcMap<int>,
 		           typename FM = CM,
 		           typename TL = Tolerance<typename CM::Value> >
 		  class ResidualDigraph
 		    : public SubDigraph<
 		        Undirector<const DGR>,
 		        ConstMap<typename DGR::Node, Const<bool, true> >,
 		        typename Undirector<const DGR>::template CombinedArcMap<
 		          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
 		          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
 		#endif
+		  {
 		  public:
 		    /// The type of the underlying digraph.
 		    typedef DGR Digraph;
 		    /// The type of the capacity map.
 		    typedef CM CapacityMap;
 		    /// The type of the flow map.
 		    typedef FM FlowMap;
 		    /// The tolerance type.
 		    typedef TL Tolerance;
 		    typedef typename CapacityMap::Value Value;
 		    typedef ResidualDigraph Adaptor;
 		  protected:
 		    typedef Undirector<const Digraph> Undirected;
 		    typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter;
 		    typedef _adaptor_bits::ResForwardFilter<const DGR, CM,
 		                                            FM, TL> ForwardFilter;
 		    typedef _adaptor_bits::ResBackwardFilter<const DGR, CM,
 		                                             FM, TL> BackwardFilter;
 		    typedef typename Undirected::
 		      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
 		    typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
 		    const CapacityMap* _capacity;
 		    FlowMap* _flow;
 		    Undirected _graph;
 		    NodeFilter _node_filter;
 		    ForwardFilter _forward_filter;
 		    BackwardFilter _backward_filter;
 		    ArcFilter _arc_filter;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the residual digraph adaptor. The parameters are the
 		    /// digraph, the capacity map, the flow map, and a tolerance object.
 		    ResidualDigraph(const DGR& digraph, const CM& capacity,
 		                    FM& flow, const TL& tolerance = Tolerance())
 		      : Parent(), _capacity(&capacity), _flow(&flow),
 		        _graph(digraph), _node_filter(),
 		        _forward_filter(capacity, flow, tolerance),
 		        _backward_filter(capacity, flow, tolerance),
 		        _arc_filter(_forward_filter, _backward_filter)
+		    {
 		      Parent::initialize(_graph, _node_filter, _arc_filter);
+		    }
 		    typedef typename Parent::Arc Arc;
 		    /// \brief Returns the residual capacity of the given arc.
 		    ///
 		    /// Returns the residual capacity of the given arc.
 		    Value residualCapacity(const Arc& a) const {
 		      if (Undirected::direction(a)) {
 		        return (*_capacity)[a] - (*_flow)[a];
 		      } else {
 		        return (*_flow)[a];
+		      }
+		    }
 		    /// \brief Augments on the given arc in the residual digraph.
 		    ///
 		    /// Augments on the given arc in the residual digraph. It increases
 		    /// or decreases the flow value on the original arc according to the
 		    /// direction of the residual arc.
 		    void augment(const Arc& a, const Value& v) const {
 		      if (Undirected::direction(a)) {
 		        _flow->set(a, (*_flow)[a] + v);
 		      } else {
 		        _flow->set(a, (*_flow)[a] - v);
+		      }
+		    }
 		    /// \brief Returns \c true if the given residual arc is a forward arc.
 		    ///
 		    /// Returns \c true if the given residual arc has the same orientation
 		    /// as the original arc, i.e. it is a so called forward arc.
 		    static bool forward(const Arc& a) {
 		      return Undirected::direction(a);
+		    }
 		    /// \brief Returns \c true if the given residual arc is a backward arc.
 		    ///
 		    /// Returns \c true if the given residual arc has the opposite orientation
 		    /// than the original arc, i.e. it is a so called backward arc.
 		    static bool backward(const Arc& a) {
 		      return !Undirected::direction(a);
+		    }
 		    /// \brief Returns the forward oriented residual arc.
 		    ///
 		    /// Returns the forward oriented residual arc related to the given
 		    /// arc of the underlying digraph.
 		    static Arc forward(const typename Digraph::Arc& a) {
 		      return Undirected::direct(a, true);
+		    }
 		    /// \brief Returns the backward oriented residual arc.
 		    ///
 		    /// Returns the backward oriented residual arc related to the given
 		    /// arc of the underlying digraph.
 		    static Arc backward(const typename Digraph::Arc& a) {
 		      return Undirected::direct(a, false);
+		    }
 		    /// \brief Residual capacity map.
 		    ///
 		    /// This map adaptor class can be used for obtaining the residual
 		    /// capacities as an arc map of the residual digraph.
 		    /// Its value type is inherited from the capacity map.
 		    class ResidualCapacity {
 		    protected:
 		      const Adaptor* _adaptor;
 		    public:
 		      /// The key type of the map
 		      typedef Arc Key;
 		      /// The value type of the map
 		      typedef typename CapacityMap::Value Value;
 		      /// Constructor
 		      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
 		        : _adaptor(&adaptor) {}
 		      /// Returns the value associated with the given residual arc
 		      Value operator[](const Arc& a) const {
 		        return _adaptor->residualCapacity(a);
+		      }
 		    };
 		    /// \brief Returns a residual capacity map
 		    ///
 		    /// This function just returns a residual capacity map.
 		    ResidualCapacity residualCapacity() const {
 		      return ResidualCapacity(*this);
+		    }
 		  };
 		  /// \brief Returns a (read-only) Residual adaptor
 		  ///
 		  /// This function just returns a (read-only) \ref ResidualDigraph adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates ResidualDigraph
 		    template<typename DGR, typename CM, typename FM>
 		  ResidualDigraph<DGR, CM, FM>
 		  residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {
 		    return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);
+		  }
 		  template <typename DGR>
 		  class SplitNodesBase {
 		    typedef DigraphAdaptorBase<const DGR> Parent;
 		  public:
 		    typedef DGR Digraph;
 		    typedef SplitNodesBase Adaptor;
 		    typedef typename DGR::Node DigraphNode;
 		    typedef typename DGR::Arc DigraphArc;
 		    class Node;
 		    class Arc;
 		  private:
 		    template <typename T> class NodeMapBase;
 		    template <typename T> class ArcMapBase;
 		  public:
 		    class Node : public DigraphNode {
 		      friend class SplitNodesBase;
 		      template <typename T> friend class NodeMapBase;
 		    private:
 		      bool _in;
 		      Node(DigraphNode node, bool in)
 		        : DigraphNode(node), _in(in) {}
 		    public:
 		      Node() {}
 		      Node(Invalid) : DigraphNode(INVALID), _in(true) {}
 		      bool operator==(const Node& node) const {
 		        return DigraphNode::operator==(node) && _in == node._in;
+		      }
 		      bool operator!=(const Node& node) const {
 		        return !(*this == node);
+		      }
 		      bool operator<(const Node& node) const {
 		        return DigraphNode::operator<(node) ||
 		          (DigraphNode::operator==(node) && _in < node._in);
+		      }
 		    };
 		    class Arc {
 		      friend class SplitNodesBase;
 		      template <typename T> friend class ArcMapBase;
 		    private:
 		      typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
 		      explicit Arc(const DigraphArc& arc) : _item(arc) {}
 		      explicit Arc(const DigraphNode& node) : _item(node) {}
 		      ArcImpl _item;
 		    public:
 		      Arc() {}
 		      Arc(Invalid) : _item(DigraphArc(INVALID)) {}
 		      bool operator==(const Arc& arc) const {
 		        if (_item.firstState()) {
 		          if (arc._item.firstState()) {
 		            return _item.first() == arc._item.first();
+		          }
 		        } else {
 		          if (arc._item.secondState()) {
 		            return _item.second() == arc._item.second();
+		          }
+		        }
 		        return false;
+		      }
 		      bool operator!=(const Arc& arc) const {
 		        return !(*this == arc);
+		      }
 		      bool operator<(const Arc& arc) const {
 		        if (_item.firstState()) {
 		          if (arc._item.firstState()) {
 		            return _item.first() < arc._item.first();
+		          }
 		          return false;
 		        } else {
 		          if (arc._item.secondState()) {
 		            return _item.second() < arc._item.second();
+		          }
 		          return true;
+		        }
+		      }
 		      operator DigraphArc() const { return _item.first(); }
 		      operator DigraphNode() const { return _item.second(); }
 		    };
 		    void first(Node& n) const {
 		      _digraph->first(n);
 		      n._in = true;
+		    }
 		    void next(Node& n) const {
 		      if (n._in) {
 		        n._in = false;
 		      } else {
 		        n._in = true;
 		        _digraph->next(n);
+		      }
+		    }
 		    void first(Arc& e) const {
 		      e._item.setSecond();
 		      _digraph->first(e._item.second());
 		      if (e._item.second() == INVALID) {
 		        e._item.setFirst();
 		        _digraph->first(e._item.first());
+		      }
+		    }
 		    void next(Arc& e) const {
 		      if (e._item.secondState()) {
 		        _digraph->next(e._item.second());
 		        if (e._item.second() == INVALID) {
 		          e._item.setFirst();
 		          _digraph->first(e._item.first());
+		        }
 		      } else {
 		        _digraph->next(e._item.first());
+		      }
+		    }
 		    void firstOut(Arc& e, const Node& n) const {
 		      if (n._in) {
 		        e._item.setSecond(n);
 		      } else {
 		        e._item.setFirst();
 		        _digraph->firstOut(e._item.first(), n);
+		      }
+		    }
 		    void nextOut(Arc& e) const {
 		      if (!e._item.firstState()) {
 		        e._item.setFirst(INVALID);
 		      } else {
 		        _digraph->nextOut(e._item.first());
+		      }
+		    }
 		    void firstIn(Arc& e, const Node& n) const {
 		      if (!n._in) {
 		        e._item.setSecond(n);
 		      } else {
 		        e._item.setFirst();
 		        _digraph->firstIn(e._item.first(), n);
+		      }
+		    }
 		    void nextIn(Arc& e) const {
 		      if (!e._item.firstState()) {
 		        e._item.setFirst(INVALID);
 		      } else {
 		        _digraph->nextIn(e._item.first());
+		      }
+		    }
 		    Node source(const Arc& e) const {
 		      if (e._item.firstState()) {
 		        return Node(_digraph->source(e._item.first()), false);
 		      } else {
 		        return Node(e._item.second(), true);
+		      }
+		    }
 		    Node target(const Arc& e) const {
 		      if (e._item.firstState()) {
 		        return Node(_digraph->target(e._item.first()), true);
 		      } else {
 		        return Node(e._item.second(), false);
+		      }
+		    }
 		    int id(const Node& n) const {
 		      return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
+		    }
 		    Node nodeFromId(int ix) const {
 		      return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
+		    }
 		    int maxNodeId() const {
 		      return 2 * _digraph->maxNodeId() + 1;
+		    }
 		    int id(const Arc& e) const {
 		      if (e._item.firstState()) {
 		        return _digraph->id(e._item.first()) << 1;
 		      } else {
 		        return (_digraph->id(e._item.second()) << 1) | 1;
+		      }
+		    }
 		    Arc arcFromId(int ix) const {
 		      if ((ix & 1) == 0) {
 		        return Arc(_digraph->arcFromId(ix >> 1));
 		      } else {
 		        return Arc(_digraph->nodeFromId(ix >> 1));
+		      }
+		    }
 		    int maxArcId() const {
 		      return std::max(_digraph->maxNodeId() << 1,
 		                      (_digraph->maxArcId() << 1) | 1);
+		    }
 		    static bool inNode(const Node& n) {
 		      return n._in;
+		    }
 		    static bool outNode(const Node& n) {
 		      return !n._in;
+		    }
 		    static bool origArc(const Arc& e) {
 		      return e._item.firstState();
+		    }
 		    static bool bindArc(const Arc& e) {
 		      return e._item.secondState();
+		    }
 		    static Node inNode(const DigraphNode& n) {
 		      return Node(n, true);
+		    }
 		    static Node outNode(const DigraphNode& n) {
 		      return Node(n, false);
+		    }
 		    static Arc arc(const DigraphNode& n) {
 		      return Arc(n);
+		    }
 		    static Arc arc(const DigraphArc& e) {
 		      return Arc(e);
+		    }
 		    typedef True NodeNumTag;
 		    int nodeNum() const {
 		      return  2 * countNodes(*_digraph);
+		    }
 		    typedef True ArcNumTag;
 		    int arcNum() const {
 		      return countArcs(*_digraph) + countNodes(*_digraph);
+		    }
 		    typedef True FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      if (inNode(u) && outNode(v)) {
 		        if (static_cast<const DigraphNode&>(u) ==
 		            static_cast<const DigraphNode&>(v) && prev == INVALID) {
 		          return Arc(u);
+		        }
+		      }
 		      else if (outNode(u) && inNode(v)) {
 		        return Arc(::lemon::findArc(*_digraph, u, v, prev));
+		      }
 		      return INVALID;
+		    }
 		  private:
 		    template <typename V>
 		    class NodeMapBase
 		      : public MapTraits<typename Parent::template NodeMap<V> > {
 		      typedef typename Parent::template NodeMap<V> NodeImpl;
 		    public:
 		      typedef Node Key;
 		      typedef V Value;
 		      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
 		      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
 		      NodeMapBase(const SplitNodesBase<DGR>& adaptor)
 		        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
 		      NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
 		        : _in_map(*adaptor._digraph, value),
 		          _out_map(*adaptor._digraph, value) {}
 		      void set(const Node& key, const V& val) {
 		        if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }
 		        else {_out_map.set(key, val); }
+		      }
 		      ReturnValue operator[](const Node& key) {
 		        if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }
 		        else { return _out_map[key]; }
+		      }
 		      ConstReturnValue operator[](const Node& key) const {
 		        if (Adaptor::inNode(key)) { return _in_map[key]; }
 		        else { return _out_map[key]; }
+		      }
 		    private:
 		      NodeImpl _in_map, _out_map;
 		    };
 		    template <typename V>
 		    class ArcMapBase
 		      : public MapTraits<typename Parent::template ArcMap<V> > {
 		      typedef typename Parent::template ArcMap<V> ArcImpl;
 		      typedef typename Parent::template NodeMap<V> NodeImpl;
 		    public:
 		      typedef Arc Key;
 		      typedef V Value;
 		      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
 		      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
 		      ArcMapBase(const SplitNodesBase<DGR>& adaptor)
 		        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
 		      ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)
 		        : _arc_map(*adaptor._digraph, value),
 		          _node_map(*adaptor._digraph, value) {}
 		      void set(const Arc& key, const V& val) {
 		        if (SplitNodesBase<DGR>::origArc(key)) {
 		          _arc_map.set(static_cast<const DigraphArc&>(key), val);
 		        } else {
 		          _node_map.set(static_cast<const DigraphNode&>(key), val);
+		        }
+		      }
 		      ReturnValue operator[](const Arc& key) {
 		        if (SplitNodesBase<DGR>::origArc(key)) {
 		          return _arc_map[static_cast<const DigraphArc&>(key)];
 		        } else {
 		          return _node_map[static_cast<const DigraphNode&>(key)];
+		        }
+		      }
 		      ConstReturnValue operator[](const Arc& key) const {
 		        if (SplitNodesBase<DGR>::origArc(key)) {
 		          return _arc_map[static_cast<const DigraphArc&>(key)];
 		        } else {
 		          return _node_map[static_cast<const DigraphNode&>(key)];
+		        }
+		      }
 		    private:
 		      ArcImpl _arc_map;
 		      NodeImpl _node_map;
 		    };
 		  public:
 		    template <typename V>
 		    class NodeMap
 		      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
 		      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SplitNodesBase<DGR>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
 		      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SplitNodesBase<DGR>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  protected:
 		    SplitNodesBase() : _digraph(0) {}
 		    DGR* _digraph;
 		    void initialize(Digraph& digraph) {
 		      _digraph = &digraph;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for splitting the nodes of a digraph.
 		  ///
 		  /// SplitNodes adaptor can be used for splitting each node into an
 		  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
 		  /// replaces each node \f$ u \f$ in the digraph with two nodes,
 		  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
 		  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
 		  /// new target of the arc will be \f$ u_{in} \f$ and similarly the
 		  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
 		  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
 		  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
 		  ///
 		  /// The aim of this class is running an algorithm with respect to node
 		  /// costs or capacities if the algorithm considers only arc costs or
 		  /// capacities directly.
 		  /// In this case you can use \c SplitNodes adaptor, and set the node
 		  /// costs/capacities of the original digraph to the \e bind \e arcs
 		  /// in the adaptor.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It is implicitly \c const.
 		  ///
 		  /// \note The \c Node type of this adaptor is converible to the \c Node
 		  /// type of the adapted digraph.
 		  template <typename DGR>
 		#ifdef DOXYGEN
 		  class SplitNodes {
 		#else
 		  class SplitNodes
 		    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
 		#endif
 		    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
 		  public:
 		    typedef DGR Digraph;
 		    typedef typename DGR::Node DigraphNode;
 		    typedef typename DGR::Arc DigraphArc;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the adaptor.
 		    SplitNodes(const DGR& g) {
 		      Parent::initialize(g);
+		    }
 		    /// \brief Returns \c true if the given node is an in-node.
 		    ///
 		    /// Returns \c true if the given node is an in-node.
 		    static bool inNode(const Node& n) {
 		      return Parent::inNode(n);
+		    }
 		    /// \brief Returns \c true if the given node is an out-node.
 		    ///
 		    /// Returns \c true if the given node is an out-node.
 		    static bool outNode(const Node& n) {
 		      return Parent::outNode(n);
+		    }
 		    /// \brief Returns \c true if the given arc is an original arc.
 		    ///
 		    /// Returns \c true if the given arc is one of the arcs in the
 		    /// original digraph.
 		    static bool origArc(const Arc& a) {
 		      return Parent::origArc(a);
+		    }
 		    /// \brief Returns \c true if the given arc is a bind arc.
 		    ///
 		    /// Returns \c true if the given arc is a bind arc, i.e. it connects
 		    /// an in-node and an out-node.
 		    static bool bindArc(const Arc& a) {
 		      return Parent::bindArc(a);
+		    }
 		    /// \brief Returns the in-node created from the given original node.
 		    ///
 		    /// Returns the in-node created from the given original node.
 		    static Node inNode(const DigraphNode& n) {
 		      return Parent::inNode(n);
+		    }
 		    /// \brief Returns the out-node created from the given original node.
 		    ///
 		    /// Returns the out-node created from the given original node.
 		    static Node outNode(const DigraphNode& n) {
 		      return Parent::outNode(n);
+		    }
 		    /// \brief Returns the bind arc that corresponds to the given
 		    /// original node.
 		    ///
 		    /// Returns the bind arc in the adaptor that corresponds to the given
 		    /// original node, i.e. the arc connecting the in-node and out-node
 		    /// of \c n.
 		    static Arc arc(const DigraphNode& n) {
 		      return Parent::arc(n);
+		    }
 		    /// \brief Returns the arc that corresponds to the given original arc.
 		    ///
 		    /// Returns the arc in the adaptor that corresponds to the given
 		    /// original arc.
 		    static Arc arc(const DigraphArc& a) {
 		      return Parent::arc(a);
+		    }
 		    /// \brief Node map combined from two original node maps
 		    ///
 		    /// This map adaptor class adapts two node maps of the original digraph
 		    /// to get a node map of the split digraph.
 		    /// Its value type is inherited from the first node map type (\c IN).
 		    /// \tparam IN The type of the node map for the in-nodes.
 		    /// \tparam OUT The type of the node map for the out-nodes.
 		    template <typename IN, typename OUT>
 		    class CombinedNodeMap {
 		    public:
 		      /// The key type of the map
 		      typedef Node Key;
 		      /// The value type of the map
 		      typedef typename IN::Value Value;
 		      typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<IN>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<IN>::ReturnValue Reference;
 		      typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
 		      /// Constructor
 		      CombinedNodeMap(IN& in_map, OUT& out_map)
 		        : _in_map(in_map), _out_map(out_map) {}
 		      /// Returns the value associated with the given key.
 		      Value operator[](const Key& key) const {
 		        if (SplitNodesBase<const DGR>::inNode(key)) {
 		          return _in_map[key];
 		        } else {
 		          return _out_map[key];
+		        }
+		      }
 		      /// Returns a reference to the value associated with the given key.
 		      Value& operator[](const Key& key) {
 		        if (SplitNodesBase<const DGR>::inNode(key)) {
 		          return _in_map[key];
 		        } else {
 		          return _out_map[key];
+		        }
+		      }
 		      /// Sets the value associated with the given key.
 		      void set(const Key& key, const Value& value) {
 		        if (SplitNodesBase<const DGR>::inNode(key)) {
 		          _in_map.set(key, value);
 		        } else {
 		          _out_map.set(key, value);
+		        }
+		      }
 		    private:
 		      IN& _in_map;
 		      OUT& _out_map;
 		    };
 		    /// \brief Returns a combined node map
 		    ///
 		    /// This function just returns a combined node map.
 		    template <typename IN, typename OUT>
 		    static CombinedNodeMap<IN, OUT>
 		    combinedNodeMap(IN& in_map, OUT& out_map) {
 		      return CombinedNodeMap<IN, OUT>(in_map, out_map);
+		    }
 		    template <typename IN, typename OUT>
 		    static CombinedNodeMap<const IN, OUT>
 		    combinedNodeMap(const IN& in_map, OUT& out_map) {
 		      return CombinedNodeMap<const IN, OUT>(in_map, out_map);
+		    }
 		    template <typename IN, typename OUT>
 		    static CombinedNodeMap<IN, const OUT>
 		    combinedNodeMap(IN& in_map, const OUT& out_map) {
 		      return CombinedNodeMap<IN, const OUT>(in_map, out_map);
+		    }
 		    template <typename IN, typename OUT>
 		    static CombinedNodeMap<const IN, const OUT>
 		    combinedNodeMap(const IN& in_map, const OUT& out_map) {
 		      return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
+		    }
 		    /// \brief Arc map combined from an arc map and a node map of the
 		    /// original digraph.
 		    ///
 		    /// This map adaptor class adapts an arc map and a node map of the
 		    /// original digraph to get an arc map of the split digraph.
 		    /// Its value type is inherited from the original arc map type (\c AM).
 		    /// \tparam AM The type of the arc map.
 		    /// \tparam NM the type of the node map.
 		    template <typename AM, typename NM>
 		    class CombinedArcMap {
 		    public:

lemon/concepts/graph.h

Show inline comments

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

lemon/bits/base_extender.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_BASE_EXTENDER_H
 		#define LEMON_BITS_BASE_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/bits/map_extender.h>
 		#include <lemon/bits/default_map.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		//\ingroup digraphbits
 		//\file
 		//\brief Extenders for the graph types
 		namespace lemon {
 		  // \ingroup digraphbits
 		  //
 		  // \brief BaseDigraph to BaseGraph extender
 		  template <typename Base>
 		  class UndirDigraphExtender : public Base {
 		    typedef Base Parent;
 		  public:
 		    typedef typename Parent::Arc Edge;
 		    typedef typename Parent::Node Node;
 		    typedef True UndirectedTag;
 		    class Arc : public Edge {
 		      friend class UndirDigraphExtender;
 		    protected:
 		      bool forward;
 		      Arc(const Edge &ue, bool _forward) :
 		        Edge(ue), forward(_forward) {}
 		    public:
 		      Arc() {}
 		      // Invalid arc constructor
 		      Arc(Invalid i) : Edge(i), forward(true) {}
 		      bool operator==(const Arc &that) const {
 		        return forward==that.forward && Edge(*this)==Edge(that);
+		      }
 		      bool operator!=(const Arc &that) const {
 		        return forward!=that.forward || Edge(*this)!=Edge(that);
+		      }
 		      bool operator<(const Arc &that) const {
 		        return forward<that.forward ||
 		          (!(that.forward<forward) && Edge(*this)<Edge(that));
+		      }
 		    };
 		    // First node of the edge
 		    Node u(const Edge &e) const {
 		      return Parent::source(e);
+		    }
 		    // Source of the given arc
 		    Node source(const Arc &e) const {
 		      return e.forward ? Parent::source(e) : Parent::target(e);
+		    }
 		    // Second node of the edge
 		    Node v(const Edge &e) const {
 		      return Parent::target(e);
+		    }
 		    // Target of the given arc
 		    Node target(const Arc &e) const {
 		      return e.forward ? Parent::target(e) : Parent::source(e);
+		    }
 		    // \brief Directed arc from an edge.
 		    //
 		    // Returns a directed arc corresponding to the specified edge.
 		    // If the given bool is true, the first node of the given edge and
 		    // the source node of the returned arc are the same.
 		    static Arc direct(const Edge &e, bool d) {
 		      return Arc(e, d);
+		    }
 		    // Returns whether the given directed arc has the same orientation
 		    // as the corresponding edge.
 		    static bool direction(const Arc &a) { return a.forward; }
 		    using Parent::first;
 		    using Parent::next;
 		    void first(Arc &e) const {
 		      Parent::first(e);
 		      e.forward=true;
+		    }
 		    void next(Arc &e) const {
 		      if( e.forward ) {
 		        e.forward = false;
+		      }
 		      else {
 		        Parent::next(e);
 		        e.forward = true;
+		      }
+		    }
 		    void firstOut(Arc &e, const Node &n) const {
 		      Parent::firstIn(e,n);
 		      if( Edge(e) != INVALID ) {
 		        e.forward = false;
+		      }
 		      else {
 		        Parent::firstOut(e,n);
 		        e.forward = true;
+		      }
+		    }
 		    void nextOut(Arc &e) const {
 		      if( ! e.forward ) {
 		        Node n = Parent::target(e);
 		        Parent::nextIn(e);
 		        if( Edge(e) == INVALID ) {
 		          Parent::firstOut(e, n);
 		          e.forward = true;
+		        }
+		      }
 		      else {
 		        Parent::nextOut(e);
+		      }
+		    }
 		    void firstIn(Arc &e, const Node &n) const {
 		      Parent::firstOut(e,n);
 		      if( Edge(e) != INVALID ) {
 		        e.forward = false;
+		      }
 		      else {
 		        Parent::firstIn(e,n);
 		        e.forward = true;
+		      }
+		    }
 		    void nextIn(Arc &e) const {
 		      if( ! e.forward ) {
 		        Node n = Parent::source(e);
 		        Parent::nextOut(e);
 		        if( Edge(e) == INVALID ) {
 		          Parent::firstIn(e, n);
 		          e.forward = true;
+		        }
+		      }
 		      else {
 		        Parent::nextIn(e);
+		      }
+		    }
 		    void firstInc(Edge &e, bool &d, const Node &n) const {
 		      d = true;
 		      Parent::firstOut(e, n);
 		      if (e != INVALID) return;
 		      d = false;
 		      Parent::firstIn(e, n);
+		    }
 		    void nextInc(Edge &e, bool &d) const {
 		      if (d) {
 		        Node s = Parent::source(e);
 		        Parent::nextOut(e);
 		        if (e != INVALID) return;
 		        d = false;
 		        Parent::firstIn(e, s);
 		      } else {
 		        Parent::nextIn(e);
+		      }
+		    }
 		    Node nodeFromId(int ix) const {
 		      return Parent::nodeFromId(ix);
+		    }
 		    Arc arcFromId(int ix) const {
 		      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
+		    }
 		    Edge edgeFromId(int ix) const {
 		      return Parent::arcFromId(ix);
+		    }
 		    int id(const Node &n) const {
 		      return Parent::id(n);
+		    }
 		    int id(const Edge &e) const {
 		      return Parent::id(e);
+		    }
 		    int id(const Arc &e) const {
 		      return 2 * Parent::id(e) + int(e.forward);
+		    }
 		    int maxNodeId() const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxArcId() const {
 		      return 2 * Parent::maxArcId() + 1;
+		    }
 		    int maxEdgeId() const {
 		      return Parent::maxArcId();
+		    }
 		    int arcNum() const {
 		      return 2 * Parent::arcNum();
+		    }
 		    int edgeNum() const {
 		      return Parent::arcNum();
+		    }
 		    Arc findArc(Node s, Node t, Arc p = INVALID) const {
 		      if (p == INVALID) {
 		        Edge arc = Parent::findArc(s, t);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = Parent::findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else if (direction(p)) {
 		        Edge arc = Parent::findArc(s, t, p);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = Parent::findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else {
 		        Edge arc = Parent::findArc(t, s, p);
 		        if (arc != INVALID) return direct(arc, false);
+		      }
 		      return INVALID;
+		    }
 		    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
 		      if (s != t) {
 		        if (p == INVALID) {
 		          Edge arc = Parent::findArc(s, t);
 		          if (arc != INVALID) return arc;
 		          arc = Parent::findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else if (Parent::s(p) == s) {
 		          Edge arc = Parent::findArc(s, t, p);
 		          if (arc != INVALID) return arc;
 		          arc = Parent::findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else {
 		          Edge arc = Parent::findArc(t, s, p);
 		          if (arc != INVALID) return arc;
+		        }
 		      } else {
 		        return Parent::findArc(s, t, p);
+		      }
 		      return INVALID;
+		    }
 		  };
 		  template <typename Base>
 		  class BidirBpGraphExtender : public Base {
 		    typedef Base Parent;
 		  public:
 		    typedef BidirBpGraphExtender Digraph;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Edge Edge;
 		    using Parent::first;
 		    using Parent::next;
 		    using Parent::id;
 		    class Red : public Node {
 		      friend class BidirBpGraphExtender;
 		    public:
 		      Red() {}
 		      Red(const Node& node) : Node(node) {
 		        LEMON_DEBUG(Parent::red(node) || node == INVALID,
 		                    typename Parent::NodeSetError());
+		      }
 		      Red& operator=(const Node& node) {
 		        LEMON_DEBUG(Parent::red(node) || node == INVALID,
 		                    typename Parent::NodeSetError());
 		        Node::operator=(node);
 		        return *this;
+		      }
 		      Red(Invalid) : Node(INVALID) {}
 		      Red& operator=(Invalid) {
 		        Node::operator=(INVALID);
 		        return *this;
+		      }
 		    };
 		    void first(Red& node) const {
 		      Parent::firstRed(static_cast<Node&>(node));
+		    }
 		    void next(Red& node) const {
 		      Parent::nextRed(static_cast<Node&>(node));
+		    }
 		    int id(const Red& node) const {
 		      return Parent::redId(node);
+		    }
 		    class Blue : public Node {
 		      friend class BidirBpGraphExtender;
 		    public:
 		      Blue() {}
 		      Blue(const Node& node) : Node(node) {
 		        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
 		                    typename Parent::NodeSetError());
+		      }
 		      Blue& operator=(const Node& node) {
 		        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
 		                    typename Parent::NodeSetError());
 		        Node::operator=(node);
 		        return *this;
+		      }
 		      Blue(Invalid) : Node(INVALID) {}
 		      Blue& operator=(Invalid) {
 		        Node::operator=(INVALID);
 		        return *this;
+		      }
 		    };
 		    void first(Blue& node) const {
 		      Parent::firstBlue(static_cast<Node&>(node));
+		    }
 		    void next(Blue& node) const {
 		      Parent::nextBlue(static_cast<Node&>(node));
+		    }
 		    int id(const Blue& node) const {
 		      return Parent::redId(node);
+		    }
 		    Node source(const Edge& arc) const {
 		      return red(arc);
+		    }
 		    Node target(const Edge& arc) const {
 		      return blue(arc);
+		    }
 		    void firstInc(Edge& arc, bool& dir, const Node& node) const {
 		      if (Parent::red(node)) {
 		        Parent::firstFromRed(arc, node);
 		        dir = true;
 		      } else {
 		        Parent::firstFromBlue(arc, node);
 		        dir = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    void nextInc(Edge& arc, bool& dir) const {
 		      if (dir) {
 		        Parent::nextFromRed(arc);
 		      } else {
 		        Parent::nextFromBlue(arc);
 		        if (arc == INVALID) dir = true;
+		      }
+		    }
 		    class Arc : public Edge {
 		      friend class BidirBpGraphExtender;
 		    protected:
 		      bool forward;
 		      Arc(const Edge& arc, bool _forward)
 		        : Edge(arc), forward(_forward) {}
 		    public:
 		      Arc() {}
 		      Arc (Invalid) : Edge(INVALID), forward(true) {}
 		      bool operator==(const Arc& i) const {
 		        return Edge::operator==(i) && forward == i.forward;
+		      }
 		      bool operator!=(const Arc& i) const {
 		        return Edge::operator!=(i) || forward != i.forward;
+		      }
 		      bool operator<(const Arc& i) const {
 		        return Edge::operator<(i) ||
 		          (!(i.forward<forward) && Edge(*this)<Edge(i));
+		      }
 		    };
 		    void first(Arc& arc) const {
 		      Parent::first(static_cast<Edge&>(arc));
 		      arc.forward = true;
+		    }
 		    void next(Arc& arc) const {
 		      if (!arc.forward) {
 		        Parent::next(static_cast<Edge&>(arc));
+		      }
 		      arc.forward = !arc.forward;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      if (Parent::red(node)) {
 		        Parent::firstFromRed(arc, node);
 		        arc.forward = true;
 		      } else {
 		        Parent::firstFromBlue(arc, node);
 		        arc.forward = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    void nextOut(Arc& arc) const {
 		      if (arc.forward) {
 		        Parent::nextFromRed(arc);
 		      } else {
 		        Parent::nextFromBlue(arc);
 		        arc.forward = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      if (Parent::blue(node)) {
 		        Parent::firstFromBlue(arc, node);
 		        arc.forward = true;
 		      } else {
 		        Parent::firstFromRed(arc, node);
 		        arc.forward = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    void nextIn(Arc& arc) const {
 		      if (arc.forward) {
 		        Parent::nextFromBlue(arc);
 		      } else {
 		        Parent::nextFromRed(arc);
 		        arc.forward = static_cast<Edge&>(arc) == INVALID;
+		      }
+		    }
 		    Node source(const Arc& arc) const {
 		      return arc.forward ? Parent::red(arc) : Parent::blue(arc);
+		    }
 		    Node target(const Arc& arc) const {
 		      return arc.forward ? Parent::blue(arc) : Parent::red(arc);
+		    }
 		    int id(const Arc& arc) const {
 		      return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
 		        (arc.forward ? 0 : 1);
+		    }
 		    Arc arcFromId(int ix) const {
 		      return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
+		    }
 		    int maxArcId() const {
 		      return (Parent::maxEdgeId() << 1) + 1;
+		    }
 		    bool direction(const Arc& arc) const {
 		      return arc.forward;
+		    }
 		    Arc direct(const Edge& arc, bool dir) const {
 		      return Arc(arc, dir);
+		    }
 		    int arcNum() const {
 		      return 2 * Parent::edgeNum();
+		    }
 		    int edgeNum() const {
 		      return Parent::edgeNum();
+		    }
 		  };
+		}
 		#endif

Changeset was too big and was cut off... Show full diff

0 comments (0 inline)

RhodeCode

Login to your account

Changeset was too big and was cut off... Show full diff

Changeset was too big and was cut off... Show full diff