LEMON/LEMON-main Changeset - r559:c5fd2d996909

Repositories » LEMON » LEMON-main

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

Changeset - r559:c5fd2d996909

« 548:94387d

560:49a39b »

r559:c5fd2d996909

Sun, 29 Mar 2009 23:08:20

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Various doc improvements (#248) - Rename all the ugly template parameters (too long and/or starting with an underscore). - Rename function parameters starting with an underscore. - Extend the doc for many classes. - Use LaTeX-style O(...) expressions only for the complicated ones. - A lot of small unification changes. - Small fixes. - Some other improvements.

0 33 0

default

33 files changed:

doc/groups.dox

doc/mainpage.dox

lemon/adaptors.h

lemon/bin_heap.h

lemon/bits/edge_set_extender.h

lemon/circulation.h

lemon/concepts/graph.h

lemon/concepts/graph_components.h

lemon/concepts/heap.h

lemon/concepts/path.h

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

↑ Collapse diff ↑

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 describes the several data structures implemented in LEMON.
+		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 describes some 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 describes the 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 describes maps that are specifically designed to assign
+		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 describes map adaptors that are used to create "implicit"
+		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 matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
-		This group describes two dimensional data storages implemented in LEMON.
+		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief %Path structures implemented in LEMON.
-		This group describes the path structures implemented in LEMON.
+		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 describes some data structures implemented in LEMON in
+		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 describes the several algorithms
+		\brief This group contains the several algorithms
 		implemented in LEMON.
-		This group describes the several algorithms
+		This group contains the several algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
-		This group describes the common graph search algorithms, namely
+		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 describes the algorithms for finding shortest paths in digraphs.
+		This group contains the algorithms for finding shortest paths in digraphs.
 		 - \ref Dijkstra algorithm for finding shortest paths from a source node
 		   when all arc lengths are non-negative.
 		 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
 		   from a source node when arc lenghts can be either positive or negative,
 		   but the digraph should not contain directed cycles with negative total
 		   length.
 		 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
 		   for solving the \e all-pairs \e shortest \e paths \e problem when arc
 		   lenghts can be either positive or negative, but the digraph should
 		   not contain directed cycles with negative total length.
 		 - \ref Suurballe A successive shortest path algorithm for finding
 		   arc-disjoint paths between two nodes having minimum total length.
 		*/
 		/**
 		@defgroup max_flow Maximum Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding maximum flows.
-		This group describes the algorithms for finding maximum flows and
+		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_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
 		\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
 		    \qquad \forall v\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
 		LEMON contains several algorithms for solving maximum flow problems:
 		- \ref EdmondsKarp Edmonds-Karp algorithm.
 		- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
 		- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
 		- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
 		In most cases the \ref Preflow "Preflow" algorithm provides the
 		fastest method for computing a maximum flow. All implementations
 		provides functions to also query the minimum cut, which is the dual
 		problem of the maximum flow.
 		*/
 		/**
 		@defgroup min_cost_flow Minimum Cost Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost flows and circulations.
-		This group describes the algorithms for finding minimum cost flows and
+		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 and arc costs.
 		Formally, let \f$G=(V,A)\f$ be a digraph,
 		\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
 		upper bounds for the flow values on the arcs,
 		\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
 		on the arcs, and
 		\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
 		of the nodes.
 		A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
 		the following optimization problem.
 		\f[ \min\sum_{a\in A} f(a) cost(a) \f]
 		\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
 		    supply(v) \qquad \forall v\in V \f]
 		\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
 		LEMON contains several algorithms for solving minimum cost flow problems:
 		 - \ref CycleCanceling Cycle-canceling algorithms.
 		 - \ref CapacityScaling Successive shortest path algorithm with optional
 		   capacity scaling.
 		 - \ref CostScaling Push-relabel and augment-relabel algorithms based on
 		   cost scaling.
 		 - \ref NetworkSimplex Primal network simplex algorithm with various
 		   pivot strategies.
 		*/
 		/**
 		@defgroup min_cut Minimum Cut Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cut in graphs.
-		This group describes the algorithms for finding minimum cut in graphs.
+		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 NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
 		  calculating minimum cut in undirected graphs.
-		- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
+		- \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_prop Connectivity and Other Graph Properties
 		@ingroup algs
 		\brief Algorithms for discovering the graph properties
-		This group describes the algorithms for discovering the graph properties
+		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 planar Planarity Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
-		This group describes the algorithms for planarity checking,
+		This group contains the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains algorithm objects and functions to calculate
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the arcs which does not shares common endpoints.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		The matching algorithms implemented in LEMON:
 		- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref PrBipartiteMatching Push-relabel algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref MaxWeightedBipartiteMatching
 		  Successive shortest path algorithm for calculating maximum weighted
 		  matching and maximum weighted bipartite matching in bipartite graphs.
 		- \ref MinCostMaxBipartiteMatching
 		  Successive shortest path algorithm for calculating minimum cost maximum
 		  matching in bipartite graphs.
 		- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum cardinality matching in general graphs.
 		- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum weighted matching in general graphs.
 		- \ref MaxWeightedPerfectMatching
 		  Edmond's blossom shrinking algorithm for calculating maximum weighted
 		  perfect matching in general graphs.
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
 		\brief Algorithms for finding a minimum cost spanning tree in a graph.
-		This group describes the algorithms for finding a minimum cost spanning
+		This group contains the algorithms for finding a minimum cost spanning
 		tree in a graph.
 		*/
 		/**
 		@defgroup auxalg Auxiliary Algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
-		This group describes some algorithms implemented in LEMON
+		This group contains some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
 		@defgroup approx Approximation Algorithms
 		@ingroup algs
 		\brief Approximation algorithms.
-		This group describes the approximation and heuristic algorithms
+		This group contains the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
-		\brief This group describes some general optimization frameworks
+		\brief This group contains some general optimization frameworks
 		implemented in LEMON.
-		This group describes some general optimization frameworks
+		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 describes Lp and Mip solver interfaces for LEMON. The
+		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 lp_utils Tools for Lp and Mip Solvers
 		@ingroup lp_group
 		\brief Helper tools to the Lp and Mip solvers.
 		This group adds some helper tools to general optimization framework
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup metah Metaheuristics
 		@ingroup gen_opt_group
 		\brief Metaheuristics for LEMON library.
-		This group describes some metaheuristic optimization tools.
+		This group contains some metaheuristic optimization tools.
 		*/
 		/**
 		@defgroup utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
-		This group describes some 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 describes several useful tools for development,
+		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 describes simple tools for measuring the performance
+		This group contains simple tools for measuring the performance
 		of algorithms.
 		*/
 		/**
 		@defgroup exceptions Exceptions
 		@ingroup utils
 		\brief Exceptions defined in LEMON.
-		This group describes the exceptions defined in LEMON.
+		This group contains the exceptions defined in LEMON.
 		*/
 		/**
 		@defgroup io_group Input-Output
 		\brief Graph Input-Output methods
-		This group describes the tools for importing and exporting graphs
+		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 describes methods for reading and writing
+		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 describes general \c EPS drawing methods and special
+		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 describes the data/algorithm skeletons and concept checking
+		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 describes the skeletons and concept checking classes of LEMON's
+		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 describes the skeletons and concept checking classes of 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.
 		It order to compile them, use <tt>--enable-demo</tt> configure option when
 		build the library.
 		*/
 		/**
 		@defgroup tools Standalone Utility Applications
 		Some utility applications are listed here.
 		The standard compilation procedure (<tt>./configure;make</tt>) will compile
 		them, as well.
 		*/
+		}

doc/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
 		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 page that tells you
 		\ref getstart "How to start using LEMON".
 		If you
 		want to see how LEMON works, see
 		some \ref demoprograms "demo programs".
 		If you already feel like using our library, see the
 		<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
 		If you know what you are looking for then try to find it under the
 		<a class="el" href="modules.html">Modules</a>
 		section.
 		<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/adaptors.h

Show inline comments

@@ -1873,852 +1873,850 @@
 		        _digraph->next(a);
 		        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 ) {
 		        a._forward = false;
 		      } else {
 		        _digraph->firstOut(a, 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);
 		          a._forward = true;
+		        }
+		      }
 		      else {
 		        _digraph->nextOut(a);
+		      }
+		    }
 		    void firstIn(Arc &a, const Node &n) const {
 		      _digraph->firstOut(a, n);
 		      if (static_cast<const Edge&>(a) != INVALID ) {
 		        a._forward = false;
 		      } else {
 		        _digraph->firstIn(a, 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);
 		          a._forward = true;
+		        }
+		      }
 		      else {
 		        _digraph->nextIn(a);
+		      }
+		    }
 		    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);
+		    }
 		    Node target(const Arc &a) const {
 		      return a._forward ? _digraph->target(a) : _digraph->source(a);
+		    }
 		    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> {
 		    public:
 		      typedef V Value;
 		      typedef typename DGR::template NodeMap<Value> Parent;
 		      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> >
+		    {
 		    public:
 		      typedef V Value;
 		      typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent;
 		      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> {
 		    public:
 		      typedef V Value;
 		      typedef typename Digraph::template ArcMap<V> Parent;
 		      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()); }
 		  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
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
 		  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 %ForwardMap).
-		    template <typename ForwardMap, typename BackwardMap>
+		    /// 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 ForwardMap::Value Value;
 		      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
 		      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
 		      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(ForwardMap& forward, BackwardMap& backward)
+		      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:
 		      ForwardMap* _forward;
 		      BackwardMap* _backward;
 		      FW* _forward;
 		      BK* _backward;
 		    };
 		    /// \brief Returns a combined arc map
 		    ///
 		    /// This function just returns a combined arc map.
 		    template <typename ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<ForwardMap, BackwardMap>
 		    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
 		      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
 		    template <typename FW, typename BK>
 		    static CombinedArcMap<FW, BK>
 		    combinedArcMap(FW& forward, BK& backward) {
 		      return CombinedArcMap<FW, BK>(forward, backward);
+		    }
 		    template <typename ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<const ForwardMap, BackwardMap>
 		    combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
 		      return CombinedArcMap<const ForwardMap,
-		        BackwardMap>(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 ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<ForwardMap, const BackwardMap>
 		    combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
 		      return CombinedArcMap<ForwardMap,
-		        const BackwardMap>(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 ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<const ForwardMap, const BackwardMap>
 		    combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
 		      return CombinedArcMap<const ForwardMap,
-		        const BackwardMap>(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> {
 		    public:
 		      typedef typename GR::template NodeMap<V> Parent;
 		      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> {
 		    public:
 		      typedef typename Graph::template EdgeMap<V> Parent;
 		      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
 		  public:
 		    /// The type of the adapted graph.
 		    typedef GR Graph;
 		    /// The type of the direction edge map.
 		    typedef DM DirectionMap;
 		    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
 		    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;
@@ -3025,571 +3023,574 @@
+		    }
 		    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> >
+		    {
 		    public:
 		      typedef V Value;
 		      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;
 		      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> >
+		    {
 		    public:
 		      typedef V Value;
 		      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;
 		      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
 		  public:
 		    typedef DGR Digraph;
 		    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
 		    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 InNodeMap).
-		    template <typename InNodeMap, typename OutNodeMap>
+		    /// 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 InNodeMap::Value Value;
 		      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
-		      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
+		      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(InNodeMap& in_map, OutNodeMap& out_map)
+		      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:
 		      InNodeMap& _in_map;
 		      OutNodeMap& _out_map;
 		      IN& _in_map;
 		      OUT& _out_map;
 		    };
 		    /// \brief Returns a combined node map
 		    ///
 		    /// This function just returns a combined node map.
 		    template <typename InNodeMap, typename OutNodeMap>
 		    static CombinedNodeMap<InNodeMap, OutNodeMap>
 		    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
 		      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_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 InNodeMap, typename OutNodeMap>
 		    static CombinedNodeMap<const InNodeMap, OutNodeMap>
 		    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
 		      return CombinedNodeMap<const InNodeMap, OutNodeMap>(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 InNodeMap, typename OutNodeMap>
 		    static CombinedNodeMap<InNodeMap, const OutNodeMap>
 		    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
 		      return CombinedNodeMap<InNodeMap, const OutNodeMap>(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 InNodeMap, typename OutNodeMap>
 		    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
 		    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
 		      return CombinedNodeMap<const InNodeMap,
-		        const OutNodeMap>(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 ArcMap).
-		    template <typename ArcMap, typename NodeMap>
+		    /// 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:
 		      /// The key type of the map
 		      typedef Arc Key;
 		      /// The value type of the map
 		      typedef typename ArcMap::Value Value;
 		      typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<ArcMap>::ReturnValue Reference;
-		      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
+		      typedef typename AM::Value Value;
 		      typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<AM>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<AM>::ReturnValue Reference;
 		      typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
 		      /// Constructor
-		      CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
+		      CombinedArcMap(AM& arc_map, NM& node_map)
 		        : _arc_map(arc_map), _node_map(node_map) {}
 		      /// Returns the value associated with the given key.
 		      Value operator[](const Key& arc) const {
 		        if (SplitNodesBase<const DGR>::origArc(arc)) {
 		          return _arc_map[arc];
 		        } else {
 		          return _node_map[arc];
+		        }
+		      }
 		      /// Returns a reference to the value associated with the given key.
 		      Value& operator[](const Key& arc) {
 		        if (SplitNodesBase<const DGR>::origArc(arc)) {
 		          return _arc_map[arc];
 		        } else {
 		          return _node_map[arc];
+		        }
+		      }
 		      /// Sets the value associated with the given key.
 		      void set(const Arc& arc, const Value& val) {
 		        if (SplitNodesBase<const DGR>::origArc(arc)) {
 		          _arc_map.set(arc, val);
 		        } else {
 		          _node_map.set(arc, val);
+		        }
+		      }
 		    private:
 		      ArcMap& _arc_map;
 		      NodeMap& _node_map;
 		      AM& _arc_map;
 		      NM& _node_map;
 		    };
 		    /// \brief Returns a combined arc map
 		    ///
 		    /// This function just returns a combined arc map.
 		    template <typename ArcMap, typename NodeMap>
 		    static CombinedArcMap<ArcMap, NodeMap>
 		    combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
 		      return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
+		    }
 		    template <typename ArcMap, typename NodeMap>
 		    static CombinedArcMap<const ArcMap, NodeMap>
 		    combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
 		      return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
+		    }
 		    template <typename ArcMap, typename NodeMap>
 		    static CombinedArcMap<ArcMap, const NodeMap>
 		    combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
 		      return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
+		    }
 		    template <typename ArcMap, typename NodeMap>
 		    static CombinedArcMap<const ArcMap, const NodeMap>
 		    combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
 		      return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
+		    }
 		  };
 		  /// \brief Returns a (read-only) SplitNodes adaptor
 		  ///
 		  /// This function just returns a (read-only) \ref SplitNodes adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates SplitNodes
 		  template<typename DGR>
 		  SplitNodes<DGR>
 		  splitNodes(const DGR& digraph) {
 		    return SplitNodes<DGR>(digraph);
+		  }
 		#undef LEMON_SCOPE_FIX
 		} //namespace lemon
 		#endif //LEMON_ADAPTORS_H

lemon/bin_heap.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_BIN_HEAP_H
 		#define LEMON_BIN_HEAP_H
 		///\ingroup auxdat
 		///\file
 		///\brief Binary Heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
 		  ///\ingroup auxdat
 		  ///
 		  ///\brief A Binary Heap implementation.
 		  ///
 		  ///This class implements the \e binary \e heap data structure. A \e heap
 		  ///is a data structure for storing items with specified values called \e
 		  ///priorities in such a way that finding the item with minimum priority is
 		  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
-		  ///one can change the priority of an item, add or erase an item, etc.
+		  ///This class implements the \e binary \e heap data structure.
 		  ///
 		  ///A \e heap is a data structure for storing items with specified values
 		  ///called \e priorities in such a way that finding the item with minimum
 		  ///priority is efficient. \c Comp specifies the ordering of the priorities.
 		  ///In a heap one can change the priority of an item, add or erase an
 		  ///item, etc.
 		  ///
 		  ///\tparam _Prio Type of the priority of the items.
 		  ///\tparam _ItemIntMap A read and writable Item int map, used internally
 		  ///\tparam PR Type of the priority of the items.
 		  ///\tparam IM A read and writable item map with int values, used internally
 		  ///to handle the cross references.
 		  ///\tparam _Compare A class for the ordering of the priorities. The
 		  ///default is \c std::less<_Prio>.
 		  ///\tparam Comp A functor class for the ordering of the priorities.
 		  ///The default is \c std::less<PR>.
 		  ///
 		  ///\sa FibHeap
 		  ///\sa Dijkstra
 		  template <typename _Prio, typename _ItemIntMap,
 		            typename _Compare = std::less<_Prio> >
 		  template <typename PR, typename IM, typename Comp = std::less<PR> >
 		  class BinHeap {
 		  public:
 		    ///\e
-		    typedef _ItemIntMap ItemIntMap;
+		    typedef IM ItemIntMap;
 		    ///\e
-		    typedef _Prio Prio;
+		    typedef PR Prio;
 		    ///\e
 		    typedef typename ItemIntMap::Key Item;
 		    ///\e
 		    typedef std::pair<Item,Prio> Pair;
 		    ///\e
-		    typedef _Compare Compare;
+		    typedef Comp Compare;
 		    /// \brief Type to represent the items states.
 		    ///
 		    /// Each Item element have a state associated to it. It may be "in heap",
 		    /// "pre heap" or "post heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// The ItemIntMap \e should be initialized in such way that it maps
 		    /// PRE_HEAP (-1) to any element to be put in the heap...
 		    /// The item-int map must be initialized in such way that it assigns
 		    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		    enum State {
 		      IN_HEAP = 0,
 		      PRE_HEAP = -1,
-		      POST_HEAP = -2
+		      IN_HEAP = 0,    ///< \e
 		      PRE_HEAP = -1,  ///< \e
 		      POST_HEAP = -2  ///< \e
 		    };
 		  private:
 		    std::vector<Pair> data;
 		    Compare comp;
-		    ItemIntMap &iim;
+		    std::vector<Pair> _data;
 		    Compare _comp;
 		    ItemIntMap &_iim;
 		  public:
 		    /// \brief The constructor.
 		    ///
 		    /// The constructor.
-		    /// \param _iim should be given to the constructor, since it is used
+		    /// \param map should be given to the constructor, since it is used
 		    /// internally to handle the cross references. The value of the map
 		    /// should be PRE_HEAP (-1) for each element.
 		    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
 		    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
 		    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
 		    /// \brief The constructor.
 		    ///
 		    /// The constructor.
-		    /// \param _iim should be given to the constructor, since it is used
+		    /// \param map should be given to the constructor, since it is used
 		    /// internally to handle the cross references. The value of the map
 		    /// should be PRE_HEAP (-1) for each element.
 		    ///
 		    /// \param _comp The comparator function object.
 		    BinHeap(ItemIntMap &_iim, const Compare &_comp)
-		      : iim(_iim), comp(_comp) {}
+		    /// \param comp The comparator function object.
 		    BinHeap(ItemIntMap &map, const Compare &comp)
 		      : _iim(map), _comp(comp) {}
 		    /// The number of items stored in the heap.
 		    ///
 		    /// \brief Returns the number of items stored in the heap.
-		    int size() const { return data.size(); }
+		    int size() const { return _data.size(); }
 		    /// \brief Checks if the heap stores no items.
 		    ///
 		    /// Returns \c true if and only if the heap stores no items.
-		    bool empty() const { return data.empty(); }
+		    bool empty() const { return _data.empty(); }
 		    /// \brief Make empty this heap.
 		    ///
 		    /// Make empty this heap. It does not change the cross reference map.
 		    /// If you want to reuse what is not surely empty you should first clear
 		    /// the heap and after that you should set the cross reference map for
 		    /// each item to \c PRE_HEAP.
 		    void clear() {
-		      data.clear();
+		      _data.clear();
+		    }
 		  private:
 		    static int parent(int i) { return (i-1)/2; }
 		    static int second_child(int i) { return 2*i+2; }
 		    bool less(const Pair &p1, const Pair &p2) const {
-		      return comp(p1.second, p2.second);
+		      return _comp(p1.second, p2.second);
+		    }
 		    int bubble_up(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,data[par]) ) {
 		        move(data[par],hole);
 		      while( hole>0 && less(p,_data[par]) ) {
 		        move(_data[par],hole);
 		        hole = par;
 		        par = parent(hole);
+		      }
 		      move(p, hole);
 		      return hole;
+		    }
 		    int bubble_down(int hole, Pair p, int length) {
 		      int child = second_child(hole);
 		      while(child < length) {
-		        if( less(data[child-1], data[child]) ) {
+		        if( less(_data[child-1], _data[child]) ) {
 		          --child;
+		        }
-		        if( !less(data[child], p) )
+		        if( !less(_data[child], p) )
 		          goto ok;
-		        move(data[child], hole);
+		        move(_data[child], hole);
 		        hole = child;
 		        child = second_child(hole);
+		      }
 		      child--;
 		      if( child<length && less(data[child], p) ) {
 		        move(data[child], hole);
 		      if( child<length && less(_data[child], p) ) {
 		        move(_data[child], hole);
 		        hole=child;
+		      }
 		    ok:
 		      move(p, hole);
 		      return hole;
+		    }
 		    void move(const Pair &p, int i) {
 		      data[i] = p;
 		      iim.set(p.first, i);
 		      _data[i] = p;
 		      _iim.set(p.first, i);
+		    }
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
 		    /// Adds \c p.first to the heap with priority \c p.second.
 		    /// \param p The pair to insert.
 		    void push(const Pair &p) {
 		      int n = data.size();
 		      data.resize(n+1);
 		      int n = _data.size();
 		      _data.resize(n+1);
 		      bubble_up(n, p);
+		    }
 		    /// \brief Insert an item into the heap with the given heap.
 		    ///
 		    /// Adds \c i to the heap with priority \c p.
 		    /// \param i The item to insert.
 		    /// \param p The priority of the item.
 		    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
 		    /// \brief Returns the item with minimum priority relative to \c Compare.
 		    ///
 		    /// This method returns the item with minimum priority relative to \c
 		    /// Compare.
 		    /// \pre The heap must be nonempty.
 		    Item top() const {
-		      return data[0].first;
+		      return _data[0].first;
+		    }
 		    /// \brief Returns the minimum priority relative to \c Compare.
 		    ///
 		    /// It returns the minimum priority relative to \c Compare.
 		    /// \pre The heap must be nonempty.
 		    Prio prio() const {
-		      return data[0].second;
+		      return _data[0].second;
+		    }
 		    /// \brief Deletes the item with minimum priority relative to \c Compare.
 		    ///
 		    /// This method deletes the item with minimum priority relative to \c
 		    /// Compare from the heap.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      int n = data.size()-1;
 		      iim.set(data[0].first, POST_HEAP);
 		      int n = _data.size()-1;
 		      _iim.set(_data[0].first, POST_HEAP);
 		      if (n > 0) {
-		        bubble_down(0, data[n], n);
+		        bubble_down(0, _data[n], n);
+		      }
-		      data.pop_back();
+		      _data.pop_back();
+		    }
 		    /// \brief Deletes \c i from the heap.
 		    ///
 		    /// This method deletes item \c i from the heap.
 		    /// \param i The item to erase.
 		    /// \pre The item should be in the heap.
 		    void erase(const Item &i) {
 		      int h = iim[i];
 		      int n = data.size()-1;
-		      iim.set(data[h].first, POST_HEAP);
+		      int h = _iim[i];
 		      int n = _data.size()-1;
 		      _iim.set(_data[h].first, POST_HEAP);
 		      if( h < n ) {
 		        if ( bubble_up(h, data[n]) == h) {
 		          bubble_down(h, data[n], n);
 		        if ( bubble_up(h, _data[n]) == h) {
 		          bubble_down(h, _data[n], n);
+		        }
+		      }
-		      data.pop_back();
+		      _data.pop_back();
+		    }
 		    /// \brief Returns the priority of \c i.
 		    ///
 		    /// This function returns the priority of item \c i.
 		    /// \param i The item.
 		    /// \pre \c i must be in the heap.
 		    /// \param i The item.
 		    Prio operator[](const Item &i) const {
 		      int idx = iim[i];
 		      return data[idx].second;
 		      int idx = _iim[i];
 		      return _data[idx].second;
+		    }
 		    /// \brief \c i gets to the heap with priority \c p independently
 		    /// if \c i was already there.
 		    ///
 		    /// This method calls \ref push(\c i, \c p) if \c i is not stored
 		    /// in the heap and sets the priority of \c i to \c p otherwise.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    void set(const Item &i, const Prio &p) {
-		      int idx = iim[i];
+		      int idx = _iim[i];
 		      if( idx < 0 ) {
 		        push(i,p);
+		      }
-		      else if( comp(p, data[idx].second) ) {
+		      else if( _comp(p, _data[idx].second) ) {
 		        bubble_up(idx, Pair(i,p));
+		      }
 		      else {
-		        bubble_down(idx, Pair(i,p), data.size());
+		        bubble_down(idx, Pair(i,p), _data.size());
+		      }
+		    }
 		    /// \brief Decreases the priority of \c i to \c p.
 		    ///
 		    /// This method decreases the priority of item \c i to \c p.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \c i must be stored in the heap with priority at least \c
 		    /// p relative to \c Compare.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    void decrease(const Item &i, const Prio &p) {
-		      int idx = iim[i];
+		      int idx = _iim[i];
 		      bubble_up(idx, Pair(i,p));
+		    }
 		    /// \brief Increases the priority of \c i to \c p.
 		    ///
 		    /// This method sets the priority of item \c i to \c p.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \c i must be stored in the heap with priority at most \c
 		    /// p relative to \c Compare.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    void increase(const Item &i, const Prio &p) {
 		      int idx = iim[i];
 		      bubble_down(idx, Pair(i,p), data.size());
 		      int idx = _iim[i];
 		      bubble_down(idx, Pair(i,p), _data.size());
+		    }
 		    /// \brief Returns if \c item is in, has already been in, or has
 		    /// never been in the heap.
 		    ///
 		    /// This method returns PRE_HEAP if \c item has never been in the
 		    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
 		    /// otherwise. In the latter case it is possible that \c item will
 		    /// get back to the heap again.
 		    /// \param i The item.
 		    State state(const Item &i) const {
-		      int s = iim[i];
+		      int s = _iim[i];
 		      if( s>=0 )
 		        s=0;
 		      return State(s);
+		    }
 		    /// \brief Sets the state of the \c item in the heap.
 		    ///
 		    /// Sets the state of the \c item in the heap. It can be used to
 		    /// manually clear the heap when it is important to achive the
 		    /// better time complexity.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
-		        iim[i] = st;
+		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
 		    /// \brief Replaces an item in the heap.
 		    ///
 		    /// The \c i item is replaced with \c j item. The \c i item should
 		    /// be in the heap, while the \c j should be out of the heap. The
 		    /// \c i item will out of the heap and \c j will be in the heap
 		    /// with the same prioriority as prevoiusly the \c i item.
 		    void replace(const Item& i, const Item& j) {
 		      int idx = iim[i];
 		      iim.set(i, iim[j]);
 		      iim.set(j, idx);
 		      data[idx].first = j;
 		      int idx = _iim[i];
 		      _iim.set(i, _iim[j]);
 		      _iim.set(j, idx);
 		      _data[idx].first = j;
+		    }
 		  }; // class BinHeap
 		} // namespace lemon
 		#endif // LEMON_BIN_HEAP_H

lemon/bits/edge_set_extender.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_EDGE_SET_EXTENDER_H
 		#define LEMON_BITS_EDGE_SET_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/bits/default_map.h>
 		#include <lemon/bits/map_extender.h>
 		///\ingroup digraphbits
 		///\file
-		///\brief Extenders for the arc set types
+		//\ingroup digraphbits
 		//\file
 		//\brief Extenders for the arc set types
 		namespace lemon {
 		  /// \ingroup digraphbits
 		  ///
-		  /// \brief Extender for the ArcSets
+		  // \ingroup digraphbits
 		  //
 		  // \brief Extender for the ArcSets
 		  template <typename Base>
 		  class ArcSetExtender : public Base {
 		  public:
 		    typedef Base Parent;
 		    typedef ArcSetExtender Digraph;
 		    // Base extensions
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    Node fromId(int id, Node) const {
 		      return Parent::nodeFromId(id);
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Arc &e) const {
 		      if (n == Parent::source(e))
 			return Parent::target(e);
 		      else if(n==Parent::target(e))
 			return Parent::source(e);
 		      else
 			return INVALID;
+		    }
 		    // Alteration notifier extensions
-		    /// The arc observer registry.
 		    // The arc observer registry.
 		    typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
 		  protected:
 		    mutable ArcNotifier arc_notifier;
 		  public:
 		    using Parent::notifier;
 		    /// \brief Gives back the arc alteration notifier.
 		    ///
-		    /// Gives back the arc alteration notifier.
 		    // Gives back the arc alteration notifier.
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    // Iterable extensions
 		    class NodeIt : public Node {
 		      const Digraph* digraph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
 			_graph.first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Digraph& _graph, const Node& node)
 			: Node(node), digraph(&_graph) {}
 		      NodeIt& operator++() {
 			digraph->next(*this);
 			return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
 			_graph.first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Digraph& _graph, const Arc& e) :
 			Arc(e), digraph(&_graph) { }
 		      ArcIt& operator++() {
 			digraph->next(*this);
 			return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Digraph& _graph, const Node& node)
 			: digraph(&_graph) {
 			_graph.firstOut(*this, node);
+		      }
 		      OutArcIt(const Digraph& _graph, const Arc& arc)
 			: Arc(arc), digraph(&_graph) {}
 		      OutArcIt& operator++() {
 			digraph->nextOut(*this);
 			return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Digraph& _graph, const Node& node)
 			: digraph(&_graph) {
 			_graph.firstIn(*this, node);
+		      }
 		      InArcIt(const Digraph& _graph, const Arc& arc) :
 			Arc(arc), digraph(&_graph) {}
 		      InArcIt& operator++() {
 			digraph->nextIn(*this);
 			return *this;
+		      }
 		    };
 		    /// \brief Base node of the iterator
 		    ///
-		    /// Returns the base node (ie. the source in this case) of the iterator
+		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (ie. the source in this case) of the iterator
 		    Node baseNode(const OutArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the target in this case) of the
 		    /// iterator
 		    // \brief Running node of the iterator
 		    //
 		    // Returns the running node (ie. the target in this case) of the
 		    // iterator
 		    Node runningNode(const OutArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Base node of the iterator
 		    ///
-		    /// Returns the base node (ie. the target in this case) of the iterator
+		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (ie. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the source in this case) of the
 		    /// iterator
 		    // \brief Running node of the iterator
 		    //
 		    // Returns the running node (ie. the source in this case) of the
 		    // iterator
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    using Parent::first;
 		    // Mappable extension
 		    template <typename _Value>
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
 		    public:
 		      typedef ArcSetExtender Digraph;
 		      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
 		      explicit ArcMap(const Digraph& _g)
 			: Parent(_g) {}
 		      ArcMap(const Digraph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      ArcMap& operator=(const ArcMap& cmap) {
 			return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    // Alteration extension
 		    Arc addArc(const Node& from, const Node& to) {
 		      Arc arc = Parent::addArc(from, to);
 		      notifier(Arc()).add(arc);
 		      return arc;
+		    }
 		    void clear() {
 		      notifier(Arc()).clear();
 		      Parent::clear();
+		    }
 		    void erase(const Arc& arc) {
 		      notifier(Arc()).erase(arc);
 		      Parent::erase(arc);
+		    }
 		    ArcSetExtender() {
 		      arc_notifier.setContainer(*this);
+		    }
 		    ~ArcSetExtender() {
 		      arc_notifier.clear();
+		    }
 		  };
 		  /// \ingroup digraphbits
 		  ///
-		  /// \brief Extender for the EdgeSets
+		  // \ingroup digraphbits
 		  //
 		  // \brief Extender for the EdgeSets
 		  template <typename Base>
 		  class EdgeSetExtender : public Base {
 		  public:
 		    typedef Base Parent;
 		    typedef EdgeSetExtender Digraph;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    int maxId(Edge) const {
 		      return Parent::maxEdgeId();
+		    }
 		    Node fromId(int id, Node) const {
 		      return Parent::nodeFromId(id);
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Edge fromId(int id, Edge) const {
 		      return Parent::edgeFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Edge &e) const {
 		      if( n == Parent::u(e))
 			return Parent::v(e);
 		      else if( n == Parent::v(e))
 			return Parent::u(e);
 		      else
 			return INVALID;
+		    }
 		    Arc oppositeArc(const Arc &e) const {
 		      return Parent::direct(e, !Parent::direction(e));
+		    }
 		    using Parent::direct;
 		    Arc direct(const Edge &e, const Node &s) const {
 		      return Parent::direct(e, Parent::u(e) == s);
+		    }
 		    typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
 		    typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
 		  protected:
 		    mutable ArcNotifier arc_notifier;
 		    mutable EdgeNotifier edge_notifier;
 		  public:
 		    using Parent::notifier;
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    EdgeNotifier& notifier(Edge) const {
 		      return edge_notifier;
+		    }
 		    class NodeIt : public Node {
 		      const Digraph* digraph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
 			_graph.first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Digraph& _graph, const Node& node)
 			: Node(node), digraph(&_graph) {}
 		      NodeIt& operator++() {
 			digraph->next(*this);
 			return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
 			_graph.first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Digraph& _graph, const Arc& e) :
 			Arc(e), digraph(&_graph) { }
 		      ArcIt& operator++() {
 			digraph->next(*this);
 			return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Digraph& _graph, const Node& node)
 			: digraph(&_graph) {
 			_graph.firstOut(*this, node);
+		      }
 		      OutArcIt(const Digraph& _graph, const Arc& arc)
 			: Arc(arc), digraph(&_graph) {}
 		      OutArcIt& operator++() {
 			digraph->nextOut(*this);
 			return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Digraph& _graph, const Node& node)
 			: digraph(&_graph) {
 			_graph.firstIn(*this, node);
+		      }
 		      InArcIt(const Digraph& _graph, const Arc& arc) :
 			Arc(arc), digraph(&_graph) {}
 		      InArcIt& operator++() {
 			digraph->nextIn(*this);
 			return *this;
+		      }
 		    };
 		    class EdgeIt : public Parent::Edge {
 		      const Digraph* digraph;
 		    public:
 		      EdgeIt() { }
 		      EdgeIt(Invalid i) : Edge(i) { }
 		      explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
 			_graph.first(static_cast<Edge&>(*this));
+		      }
 		      EdgeIt(const Digraph& _graph, const Edge& e) :
 			Edge(e), digraph(&_graph) { }
 		      EdgeIt& operator++() {
 			digraph->next(*this);
 			return *this;
+		      }
 		    };
 		    class IncEdgeIt : public Parent::Edge {
 		      friend class EdgeSetExtender;
 		      const Digraph* digraph;
 		      bool direction;
 		    public:
 		      IncEdgeIt() { }
 		      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
 		      IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
 			_graph.firstInc(*this, direction, n);
+		      }
 		      IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
 			: digraph(&_graph), Edge(ue) {
 			direction = (_graph.source(ue) == n);
+		      }
 		      IncEdgeIt& operator++() {
 			digraph->nextInc(*this, direction);
 			return *this;
+		      }
 		    };
 		    /// \brief Base node of the iterator
 		    ///
-		    /// Returns the base node (ie. the source in this case) of the iterator
+		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (ie. the source in this case) of the iterator
 		    Node baseNode(const OutArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the target in this case) of the
 		    /// iterator
 		    // \brief Running node of the iterator
 		    //
 		    // Returns the running node (ie. the target in this case) of the
 		    // iterator
 		    Node runningNode(const OutArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Base node of the iterator
 		    ///
-		    /// Returns the base node (ie. the target in this case) of the iterator
+		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (ie. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the source in this case) of the
 		    /// iterator
 		    // \brief Running node of the iterator
 		    //
 		    // Returns the running node (ie. the source in this case) of the
 		    // iterator
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    /// Base node of the iterator
 		    ///
-		    /// Returns the base node of the iterator
+		    // Base node of the iterator
 		    //
 		    // Returns the base node of the iterator
 		    Node baseNode(const IncEdgeIt &e) const {
 		      return e.direction ? u(e) : v(e);
+		    }
 		    /// Running node of the iterator
 		    ///
-		    /// Returns the running node of the iterator
+		    // Running node of the iterator
 		    //
 		    // Returns the running node of the iterator
 		    Node runningNode(const IncEdgeIt &e) const {
 		      return e.direction ? v(e) : u(e);
+		    }
 		    template <typename _Value>
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
 		    public:
 		      typedef EdgeSetExtender Digraph;
 		      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
 		      ArcMap(const Digraph& _g)
 			: Parent(_g) {}
 		      ArcMap(const Digraph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      ArcMap& operator=(const ArcMap& cmap) {
 			return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap
 		      : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
 		    public:
 		      typedef EdgeSetExtender Digraph;
 		      typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
 		      EdgeMap(const Digraph& _g)
 			: Parent(_g) {}
 		      EdgeMap(const Digraph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 			return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    // Alteration extension
 		    Edge addEdge(const Node& from, const Node& to) {
 		      Edge edge = Parent::addEdge(from, to);
 		      notifier(Edge()).add(edge);
 		      std::vector<Arc> arcs;
 		      arcs.push_back(Parent::direct(edge, true));
 		      arcs.push_back(Parent::direct(edge, false));
 		      notifier(Arc()).add(arcs);
 		      return edge;
+		    }
 		    void clear() {
 		      notifier(Arc()).clear();
 		      notifier(Edge()).clear();
 		      Parent::clear();
+		    }
 		    void erase(const Edge& edge) {
 		      std::vector<Arc> arcs;
 		      arcs.push_back(Parent::direct(edge, true));
 		      arcs.push_back(Parent::direct(edge, false));
 		      notifier(Arc()).erase(arcs);
 		      notifier(Edge()).erase(edge);
 		      Parent::erase(edge);
+		    }
 		    EdgeSetExtender() {
 		      arc_notifier.setContainer(*this);
 		      edge_notifier.setContainer(*this);
+		    }
 		    ~EdgeSetExtender() {
 		      edge_notifier.clear();
 		      arc_notifier.clear();
+		    }
 		  };
+		}
 		#endif

lemon/circulation.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_CIRCULATION_H
 		#define LEMON_CIRCULATION_H
 		#include <lemon/tolerance.h>
 		#include <lemon/elevator.h>
 		///\ingroup max_flow
 		///\file
 		///\brief Push-relabel algorithm for finding a feasible circulation.
 		///
 		namespace lemon {
 		  /// \brief Default traits class of Circulation class.
 		  ///
 		  /// Default traits class of Circulation class.
 		  /// \tparam GR Digraph type.
 		  /// \tparam LM Lower bound capacity map type.
 		  /// \tparam UM Upper bound capacity map type.
 		  /// \tparam DM Delta map type.
 		  template <typename GR, typename LM,
 		            typename UM, typename DM>
 		  struct CirculationDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the circulation lower
 		    /// bound.
 		    ///
 		    /// The type of the map that stores the circulation lower bound.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LM LCapMap;
 		    /// \brief The type of the map that stores the circulation upper
 		    /// bound.
 		    ///
 		    /// The type of the map that stores the circulation upper bound.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef UM UCapMap;
 		    /// \brief The type of the map that stores the lower bound for
 		    /// the supply of the nodes.
 		    ///
 		    /// The type of the map that stores the lower bound for the supply
 		    /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
 		    /// concept.
 		    typedef DM DeltaMap;
 		    /// \brief The type of the flow values.
 		    typedef typename DeltaMap::Value Value;
 		    /// \brief The type of the map that stores the flow values.
 		    ///
 		    /// The type of the map that stores the flow values.
 		    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
 		    /// \param digraph The digraph, to which we would like to define
 		    /// the flow map.
 		    static FlowMap* createFlowMap(const Digraph& digraph) {
 		      return new FlowMap(digraph);
+		    }
 		    /// \brief The elevator type used by the algorithm.
 		    ///
 		    /// The elevator type used by the algorithm.
 		    ///
 		    /// \sa Elevator
 		    /// \sa LinkedElevator
 		    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
 		    /// \brief Instantiates an Elevator.
 		    ///
 		    /// This function instantiates an \ref Elevator.
 		    /// \param digraph The digraph, to which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
 		    ///
 		    /// The tolerance used by the algorithm to handle inexact computation.
 		    typedef lemon::Tolerance<Value> Tolerance;
 		  };
 		  /**
 		     \brief Push-relabel algorithm for the network circulation problem.
 		     \ingroup max_flow
 		     This class implements a push-relabel algorithm for the network
 		     circulation problem.
 		     It is to find a feasible circulation when lower and upper bounds
 		     are given for the flow values on the arcs and lower bounds
 		     are given for the supply values of the nodes.
 		     The exact formulation of this problem is the following.
 		     Let \f$G=(V,A)\f$ be a digraph,
 		     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
 		     \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
 		     \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
 		     \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
 		     \geq delta(v) \quad \forall v\in V, \f]
 		     \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
 		     \note \f$delta(v)\f$ specifies a lower bound for the supply of node
 		     \f$v\f$. It can be either positive or negative, however note that
 		     \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
 		     have a feasible solution.
 		     \note A special case of this problem is when
 		     \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
 		     will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
 		     Thus a feasible solution for the
 		     \ref min_cost_flow "minimum cost flow" problem can be calculated
 		     in this way.
 		     \tparam GR The type of the digraph the algorithm runs on.
 		     \tparam LM The type of the lower bound capacity map. The default
 		     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		     \tparam UM The type of the upper bound capacity map. The default
 		     map type is \c LM.
 		     \tparam DM The type of the map that stores the lower bound
 		     for the supply of the nodes. The default map type is
 		     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
 		  */
 		#ifdef DOXYGEN
 		template< typename GR,
 		          typename LM,
 		          typename UM,
 		          typename DM,
 		          typename TR >
 		#else
 		template< typename GR,
 		          typename LM = typename GR::template ArcMap<int>,
 		          typename UM = LM,
 		          typename DM = typename GR::template NodeMap<typename UM::Value>,
 		          typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
 		#endif
 		  class Circulation {
 		  public:
 		    ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The type of the flow values.
 		    typedef typename Traits::Value Value;
 		    /// The type of the lower bound capacity map.
 		    typedef typename Traits::LCapMap LCapMap;
 		    /// The type of the upper bound capacity map.
 		    typedef typename Traits::UCapMap UCapMap;
 		    /// \brief The type of the map that stores the lower bound for
 		    /// the supply of the nodes.
 		    typedef typename Traits::DeltaMap DeltaMap;
 		    ///The type of the flow map.
 		    typedef typename Traits::FlowMap FlowMap;
 		    ///The type of the elevator.
 		    typedef typename Traits::Elevator Elevator;
 		    ///The type of the tolerance.
 		    typedef typename Traits::Tolerance Tolerance;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph &_g;
 		    int _node_num;
 		    const LCapMap *_lo;
 		    const UCapMap *_up;
 		    const DeltaMap *_delta;
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tol;
 		    int _el;
 		  public:
 		    typedef Circulation Create;
 		    ///\name Named Template Parameters
 		    ///@{
-		    template <typename _FlowMap>
+		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
-		      typedef _FlowMap FlowMap;
+		      typedef T FlowMap;
 		      static FlowMap *createFlowMap(const Digraph&) {
 		        LEMON_ASSERT(false, "FlowMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// FlowMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting FlowMap
 		    /// type.
-		    template <typename _FlowMap>
+		    template <typename T>
 		    struct SetFlowMap
 		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-		                           SetFlowMapTraits<_FlowMap> > {
+		                           SetFlowMapTraits<T> > {
 		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-		                          SetFlowMapTraits<_FlowMap> > Create;
+		                          SetFlowMapTraits<T> > Create;
 		    };
-		    template <typename _Elevator>
+		    template <typename T>
 		    struct SetElevatorTraits : public Traits {
-		      typedef _Elevator Elevator;
+		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph&, int) {
 		        LEMON_ASSERT(false, "Elevator is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type. If this named parameter is used, then an external
 		    /// elevator object must be passed to the algorithm using the
 		    /// \ref elevator(Elevator&) "elevator()" function before calling
 		    /// \ref run() or \ref init().
 		    /// \sa SetStandardElevator
-		    template <typename _Elevator>
+		    template <typename T>
 		    struct SetElevator
 		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-		                           SetElevatorTraits<_Elevator> > {
+		                           SetElevatorTraits<T> > {
 		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-		                          SetElevatorTraits<_Elevator> > Create;
+		                          SetElevatorTraits<T> > Create;
 		    };
-		    template <typename _Elevator>
+		    template <typename T>
 		    struct SetStandardElevatorTraits : public Traits {
-		      typedef _Elevator Elevator;
+		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph& digraph, int max_level) {
 		        return new Elevator(digraph, max_level);
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type with automatic allocation
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type with automatic allocation.
 		    /// The Elevator should have standard constructor interface to be
 		    /// able to automatically created by the algorithm (i.e. the
 		    /// digraph and the maximum level should be passed to it).
 		    /// However an external elevator object could also be passed to the
 		    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
 		    /// before calling \ref run() or \ref init().
 		    /// \sa SetElevator
-		    template <typename _Elevator>
+		    template <typename T>
 		    struct SetStandardElevator
 		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-		                       SetStandardElevatorTraits<_Elevator> > {
+		                       SetStandardElevatorTraits<T> > {
 		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-		                      SetStandardElevatorTraits<_Elevator> > Create;
+		                      SetStandardElevatorTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Circulation() {}
 		  public:
 		    /// The constructor of the class.
 		    /// The constructor of the class.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param lo The lower bound capacity of the arcs.
 		    /// \param up The upper bound capacity of the arcs.
 		    /// \param delta The lower bound for the supply of the nodes.
 		    Circulation(const Digraph &g,const LCapMap &lo,
 		                const UCapMap &up,const DeltaMap &delta)
 		      : _g(g), _node_num(),
 		        _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
 		        _level(0), _local_level(false), _excess(0), _el() {}
 		    /// Destructor.
 		    ~Circulation() {
 		      destroyStructures();
+		    }
 		  private:
 		    void createStructures() {
 		      _node_num = _el = countNodes(_g);
 		      if (!_flow) {
 		        _flow = Traits::createFlowMap(_g);
 		        _local_flow = true;
+		      }
 		      if (!_level) {
 		        _level = Traits::createElevator(_g, _node_num);
 		        _local_level = true;
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_g);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_local_flow) {
 		        delete _flow;
+		      }
 		      if (_local_level) {
 		        delete _level;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
+		    }
 		  public:
 		    /// Sets the lower bound capacity map.
 		    /// Sets the lower bound capacity map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& lowerCapMap(const LCapMap& map) {
 		      _lo = &map;
 		      return *this;
+		    }
 		    /// Sets the upper bound capacity map.
 		    /// Sets the upper bound capacity map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& upperCapMap(const LCapMap& map) {
 		      _up = &map;
 		      return *this;
+		    }
 		    /// Sets the lower bound map for the supply of the nodes.
 		    /// Sets the lower bound map for the supply of the nodes.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& deltaMap(const DeltaMap& map) {
 		      _delta = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the flow map.
 		    ///
 		    /// Sets the flow map.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& flowMap(FlowMap& map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the elevator used by algorithm.
 		    ///
 		    /// Sets the elevator used by algorithm.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated elevator,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& elevator(Elevator& elevator) {
 		      if (_local_level) {
 		        delete _level;
 		        _local_level = false;
+		      }
 		      _level = &elevator;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the elevator.
 		    ///
 		    /// Returns a const reference to the elevator.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const Elevator& elevator() const {
 		      return *_level;
+		    }
 		    /// \brief Sets the tolerance used by algorithm.
 		    ///
 		    /// Sets the tolerance used by algorithm.
 		    Circulation& tolerance(const Tolerance& tolerance) const {
 		      _tol = tolerance;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the tolerance.
 		    ///
 		    /// Returns a const reference to the tolerance.
 		    const Tolerance& tolerance() const {
 		      return tolerance;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to call \ref run().\n
 		    /// If you need more control on the initial solution or the execution,
 		    /// first you have to call one of the \ref init() functions, then
 		    /// the \ref start() function.
 		    ///@{
 		    /// Initializes the internal data structures.
 		    /// Initializes the internal data structures and sets all flow values
 		    /// to the lower bound.
 		    void init()
+		    {
 		      createStructures();
 		      for(NodeIt n(_g);n!=INVALID;++n) {
 		        _excess->set(n, (*_delta)[n]);
+		      }
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        _flow->set(e, (*_lo)[e]);
 		        _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);
 		        _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);
+		      }
 		      // global relabeling tested, but in general case it provides
 		      // worse performance for random digraphs
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    /// Initializes the internal data structures using a greedy approach.
 		    /// Initializes the internal data structures using a greedy approach
 		    /// to construct the initial solution.
 		    void greedyInit()
+		    {
 		      createStructures();
 		      for(NodeIt n(_g);n!=INVALID;++n) {
 		        _excess->set(n, (*_delta)[n]);
+		      }
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
 		          _flow->set(e, (*_up)[e]);
 		          _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);
 		          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);
 		        } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
 		          _flow->set(e, (*_lo)[e]);
 		          _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
 		          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
 		        } else {
 		          Value fc = -(*_excess)[_g.target(e)];
 		          _flow->set(e, fc);
 		          _excess->set(_g.target(e), 0);
 		          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
+		        }
+		      }
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    ///Executes the algorithm
 		    ///This function executes the algorithm.
 		    ///
 		    ///\return \c true if a feasible circulation is found.
 		    ///
 		    ///\sa barrier()
 		    ///\sa barrierMap()
 		    bool start()
+		    {
 		      Node act;
 		      Node bact=INVALID;
 		      Node last_activated=INVALID;
 		      while((act=_level->highestActive())!=INVALID) {
 		        int actlevel=(*_level)[act];
 		        int mlevel=_node_num;
 		        Value exc=(*_excess)[act];
 		        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
 		          Node v = _g.target(e);
 		          Value fc=(*_up)[e]-(*_flow)[e];
 		          if(!_tol.positive(fc)) continue;
 		          if((*_level)[v]<actlevel) {
 		            if(!_tol.less(fc, exc)) {
 		              _flow->set(e, (*_flow)[e] + exc);
 		              _excess->set(v, (*_excess)[v] + exc);
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              _excess->set(act,0);
 		              _level->deactivate(act);
 		              goto next_l;
+		            }
 		            else {
 		              _flow->set(e, (*_up)[e]);
 		              _excess->set(v, (*_excess)[v] + fc);
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              exc-=fc;
+		            }
+		          }
 		          else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
+		        }
 		        for(InArcIt e(_g,act);e!=INVALID; ++e) {
 		          Node v = _g.source(e);
 		          Value fc=(*_flow)[e]-(*_lo)[e];
 		          if(!_tol.positive(fc)) continue;
 		          if((*_level)[v]<actlevel) {
 		            if(!_tol.less(fc, exc)) {
 		              _flow->set(e, (*_flow)[e] - exc);
 		              _excess->set(v, (*_excess)[v] + exc);
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              _excess->set(act,0);
 		              _level->deactivate(act);
 		              goto next_l;
+		            }
 		            else {
 		              _flow->set(e, (*_lo)[e]);
 		              _excess->set(v, (*_excess)[v] + fc);
 		              if(!_level->active(v) && _tol.positive((*_excess)[v]))
 		                _level->activate(v);
 		              exc-=fc;
+		            }
+		          }
 		          else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
+		        }
 		        _excess->set(act, exc);
 		        if(!_tol.positive(exc)) _level->deactivate(act);
 		        else if(mlevel==_node_num) {
 		          _level->liftHighestActiveToTop();
 		          _el = _node_num;
 		          return false;
+		        }
 		        else {
 		          _level->liftHighestActive(mlevel+1);
 		          if(_level->onLevel(actlevel)==0) {
 		            _el = actlevel;
 		            return false;
+		          }
+		        }
 		      next_l:
+		        ;
+		      }
 		      return true;
+		    }
 		    /// Runs the algorithm.
 		    /// This function runs the algorithm.
 		    ///
 		    /// \return \c true if a feasible circulation is found.
 		    ///
 		    /// \note Apart from the return value, c.run() is just a shortcut of
 		    /// the following code.
 		    /// \code
 		    ///   c.greedyInit();
 		    ///   c.start();
 		    /// \endcode
 		    bool run() {
 		      greedyInit();
 		      return start();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the circulation algorithm can be obtained using
 		    /// these functions.\n
 		    /// Either \ref run() or \ref start() should be called before
 		    /// using them.
 		    ///@{
 		    /// \brief Returns the flow on the given arc.
 		    ///
 		    /// Returns the flow on the given arc.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Value flow(const Arc& arc) const {
 		      return (*_flow)[arc];
+		    }
 		    /// \brief Returns a const reference to the flow map.
 		    ///
 		    /// Returns a const reference to the arc map storing the found flow.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow;
+		    }
 		    /**
 		       \brief Returns \c true if the given node is in a barrier.
 		       Barrier is a set \e B of nodes for which
 		       \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
 		           \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
 		       holds. The existence of a set with this property prooves that a
 		       feasible circualtion cannot exist.
 		       This function returns \c true if the given node is in the found
 		       barrier. If a feasible circulation is found, the function
 		       gives back \c false for every node.
 		       \pre Either \ref run() or \ref init() must be called before
 		       using this function.
 		       \sa barrierMap()
 		       \sa checkBarrier()
 		    */
 		    bool barrier(const Node& node) const
+		    {
 		      return (*_level)[node] >= _el;
+		    }
 		    /// \brief Gives back a barrier.
 		    ///
 		    /// This function sets \c bar to the characteristic vector of the
 		    /// found barrier. \c bar should be a \ref concepts::WriteMap "writable"
 		    /// node map with \c bool (or convertible) value type.
 		    ///
 		    /// If a feasible circulation is found, the function gives back an
 		    /// empty set, so \c bar[v] will be \c false for all nodes \c v.
 		    ///
 		    /// \note This function calls \ref barrier() for each node,
-		    /// so it runs in \f$O(n)\f$ time.
 		    /// so it runs in O(n) time.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    ///
 		    /// \sa barrier()
 		    /// \sa checkBarrier()
 		    template<class BarrierMap>
 		    void barrierMap(BarrierMap &bar) const
+		    {
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        bar.set(n, (*_level)[n] >= _el);
+		    }
 		    /// @}
 		    /// \name Checker Functions
 		    /// The feasibility of the results can be checked using
 		    /// these functions.\n
 		    /// Either \ref run() or \ref start() should be called before
 		    /// using them.
 		    ///@{
 		    ///Check if the found flow is a feasible circulation
 		    ///Check if the found flow is a feasible circulation,
 		    ///
 		    bool checkFlow() const {
 		      for(ArcIt e(_g);e!=INVALID;++e)
 		        if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
 		      for(NodeIt n(_g);n!=INVALID;++n)
+		        {
 		          Value dif=-(*_delta)[n];
 		          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
 		          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
 		          if(_tol.negative(dif)) return false;
+		        }
 		      return true;
+		    }
 		    ///Check whether or not the last execution provides a barrier
 		    ///Check whether or not the last execution provides a barrier.
 		    ///\sa barrier()
 		    ///\sa barrierMap()
 		    bool checkBarrier() const
+		    {
 		      Value delta=0;
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(barrier(n))
 		          delta-=(*_delta)[n];
 		      for(ArcIt e(_g);e!=INVALID;++e)
+		        {
 		          Node s=_g.source(e);
 		          Node t=_g.target(e);
 		          if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
 		          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
+		        }
 		      return _tol.negative(delta);
+		    }
 		    /// @}
 		  };
+		}
 		#endif

lemon/concepts/graph.h

Show inline comments

@@ -220,532 +220,544 @@
 		      /// 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 {
 		      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) { }
 		        /// 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; }
 		      };
 		      /// 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 Read write map of the nodes to type \c T.
 		      ///
 		      /// ReadWrite map of the nodes to type \c T.
 		      /// \sa Reference
 		      template<class T>
 		      class NodeMap : public ReadWriteMap< Node, T >
+		      {
 		      public:
 		        ///\e
 		        NodeMap(const Graph&) { }
 		        ///\e
 		        NodeMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
 		        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \brief Read write map of the directed arcs to type \c T.
 		      ///
 		      /// Reference map of the directed arcs to type \c T.
 		      /// \sa Reference
 		      template<class T>
 		      class ArcMap : public ReadWriteMap<Arc,T>
+		      {
 		      public:
 		        ///\e
 		        ArcMap(const Graph&) { }
 		        ///\e
 		        ArcMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
 		        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// Read write map of the edges to type \c T.
 		      /// Reference map of the arcs to type \c T.
 		      /// \sa Reference
 		      template<class T>
 		      class EdgeMap : public ReadWriteMap<Edge,T>
+		      {
 		      public:
 		        ///\e
 		        EdgeMap(const Graph&) { }
 		        ///\e
 		        EdgeMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
 		        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,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
+		      /// \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.
+		      /// \return The first node of the given edge.
 		      ///
 		      /// Naturally edges don't have direction and thus
 		      /// don't have source and target node. But we use these two 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
+		      /// 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 direction
+		      /// \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<IterableGraphComponent<>, _Graph>();
 		          checkConcept<IDableGraphComponent<>, _Graph>();
 		          checkConcept<MappableGraphComponent<>, _Graph>();
+		        }
 		      };
 		    };
+		  }
+		}
 		#endif

lemon/concepts/graph_components.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup graph_concepts
 		///\file
 		///\brief The concept of graph components.
 		#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 		#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 		#include <lemon/core.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/bits/alteration_notifier.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \brief Skeleton class for graph Node and Arc types
 		    ///
 		    /// This class describes the interface of Node and Arc (and Edge
 		    /// in undirected graphs) subtypes of graph types.
 		    ///
 		    /// \note This class is a template class so that we can use it to
 		    /// create graph skeleton classes. The reason for this is than Node
 		    /// and Arc types should \em not derive from the same base class.
 		    /// For Node you should instantiate it with character 'n' and for Arc
 		    /// with 'a'.
 		#ifndef DOXYGEN
-		    template <char _selector = '0'>
+		    template <char sel = '0'>
 		#endif
 		    class GraphItem {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// \warning The default constructor is not required to set
 		      /// the item to some well-defined value. So you should consider it
 		      /// as uninitialized.
 		      GraphItem() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      ///
 		      GraphItem(const GraphItem &) {}
 		      /// \brief Invalid constructor \& conversion.
 		      ///
 		      /// This constructor initializes the item to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphItem(Invalid) {}
 		      /// \brief Assign operator for nodes.
 		      ///
 		      /// The nodes are assignable.
 		      ///
 		      GraphItem& operator=(GraphItem const&) { return *this; }
 		      /// \brief Equality operator.
 		      ///
 		      /// Two iterators are equal if and only if they represents the
 		      /// same node in the graph or both are invalid.
 		      bool operator==(GraphItem) const { return false; }
 		      /// \brief Inequality operator.
 		      ///
 		      /// \sa operator==(const Node& n)
 		      ///
 		      bool operator!=(GraphItem) const { return false; }
 		      /// \brief 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<(GraphItem) const { return false; }
 		      template<typename _GraphItem>
 		      struct Constraints {
 		        void constraints() {
 		          _GraphItem i1;
 		          _GraphItem i2 = i1;
 		          _GraphItem i3 = INVALID;
 		          i1 = i2 = i3;
 		          bool b;
 		          //          b = (ia == ib) && (ia != ib) && (ia < ib);
 		          b = (ia == ib) && (ia != ib);
 		          b = (ia == INVALID) && (ib != INVALID);
 		          b = (ia < ib);
+		        }
 		        const _GraphItem &ia;
 		        const _GraphItem &ib;
 		      };
 		    };
 		    /// \brief An empty base directed graph class.
 		    ///
 		    /// This class provides the minimal set of features needed for a
 		    /// directed graph structure. All digraph concepts have to
 		    /// conform to this base directed graph. It just provides types
 		    /// for nodes and arcs and functions to get the source and the
 		    /// target of the arcs.
 		    class BaseDigraphComponent {
 		    public:
 		      typedef BaseDigraphComponent Digraph;
 		      /// \brief Node class of the digraph.
 		      ///
 		      /// This class represents the Nodes of the digraph.
 		      ///
 		      typedef GraphItem<'n'> Node;
 		      /// \brief Arc class of the digraph.
 		      ///
 		      /// This class represents the Arcs of the digraph.
 		      ///
 		      typedef GraphItem<'e'> Arc;
 		      /// \brief Gives back the target node of an arc.
 		      ///
 		      /// Gives back the target node of an arc.
 		      ///
 		      Node target(const Arc&) const { return INVALID;}
 		      /// \brief Gives back the source node of an arc.
 		      ///
 		      /// Gives back the source node of an arc.
 		      ///
 		      Node source(const Arc&) const { return INVALID;}
 		      /// \brief Gives back the opposite node on the given arc.
 		      ///
 		      /// Gives back the opposite node on the given arc.
 		      Node oppositeNode(const Node&, const Arc&) const {
 		        return INVALID;
+		      }
 		      template <typename _Digraph>
 		      struct Constraints {
 		        typedef typename _Digraph::Node Node;
 		        typedef typename _Digraph::Arc Arc;
 		        void constraints() {
 		          checkConcept<GraphItem<'n'>, Node>();
 		          checkConcept<GraphItem<'a'>, Arc>();
+		          {
 		            Node n;
 		            Arc e(INVALID);
 		            n = digraph.source(e);
 		            n = digraph.target(e);
 		            n = digraph.oppositeNode(n, e);
+		          }
+		        }
 		        const _Digraph& digraph;
 		      };
 		    };
 		    /// \brief An empty base undirected graph class.
 		    ///
 		    /// This class provides the minimal set of features needed for an
 		    /// undirected graph structure. All undirected graph concepts have
 		    /// to conform to this base graph. It just provides types for
 		    /// nodes, arcs and edges and functions to get the
 		    /// source and the target of the arcs and edges,
 		    /// conversion from arcs to edges and function to get
 		    /// both direction of the edges.
 		    class BaseGraphComponent : public BaseDigraphComponent {
 		    public:
 		      typedef BaseDigraphComponent::Node Node;
 		      typedef BaseDigraphComponent::Arc Arc;
 		      /// \brief Undirected arc class of the graph.
 		      ///
 		      /// This class represents the edges of the graph.
 		      /// The undirected graphs can be used as a directed graph which
 		      /// for each arc contains the opposite arc too so the graph is
 		      /// bidirected. The edge represents two opposite
 		      /// directed arcs.
 		      class Edge : public GraphItem<'u'> {
 		      public:
 		        typedef GraphItem<'u'> Parent;
 		        /// \brief Default constructor.
 		        ///
 		        /// \warning The default constructor is not required to set
 		        /// the item to some well-defined value. So you should consider it
 		        /// as uninitialized.
 		        Edge() {}
 		        /// \brief Copy constructor.
 		        ///
 		        /// Copy constructor.
 		        ///
 		        Edge(const Edge &) : Parent() {}
 		        /// \brief Invalid constructor \& conversion.
 		        ///
 		        /// This constructor initializes the item to be invalid.
 		        /// \sa Invalid for more details.
 		        Edge(Invalid) {}
 		        /// \brief Converter from arc to edge.
 		        ///
 		        /// Besides the core graph item functionality each arc should
 		        /// be convertible to the represented edge.
 		        Edge(const Arc&) {}
 		        /// \brief Assign arc to edge.
 		        ///
 		        /// Besides the core graph item functionality each arc should
 		        /// be convertible to the represented edge.
 		        Edge& operator=(const Arc&) { return *this; }
 		      };
 		      /// \brief Returns the direction of the arc.
 		      ///
 		      /// Returns the direction of the arc. Each arc represents an
 		      /// edge with a direction. It gives back the
 		      /// direction.
 		      bool direction(const Arc&) const { return true; }
 		      /// \brief Returns the directed arc.
 		      ///
 		      /// Returns the directed arc from its direction and the
 		      /// represented edge.
 		      Arc direct(const Edge&, bool) const { return INVALID;}
 		      /// \brief Returns the directed arc.
 		      ///
 		      /// Returns the directed arc from its source and the
 		      /// represented edge.
 		      Arc direct(const Edge&, const Node&) const { return INVALID;}
 		      /// \brief Returns the opposite arc.
 		      ///
 		      /// Returns the opposite arc. It is the arc representing the
 		      /// same edge and has opposite direction.
 		      Arc oppositeArc(const Arc&) const { return INVALID;}
 		      /// \brief Gives back one ending of an edge.
 		      ///
 		      /// Gives back one ending of an edge.
 		      Node u(const Edge&) const { return INVALID;}
 		      /// \brief Gives back the other ending of an edge.
 		      ///
 		      /// Gives back the other ending of an edge.
 		      Node v(const Edge&) const { return INVALID;}
 		      template <typename _Graph>
 		      struct Constraints {
 		        typedef typename _Graph::Node Node;
 		        typedef typename _Graph::Arc Arc;
 		        typedef typename _Graph::Edge Edge;
 		        void constraints() {
 		          checkConcept<BaseDigraphComponent, _Graph>();
 		          checkConcept<GraphItem<'u'>, Edge>();
+		          {
 		            Node n;
 		            Edge ue(INVALID);
 		            Arc e;
 		            n = graph.u(ue);
 		            n = graph.v(ue);
 		            e = graph.direct(ue, true);
 		            e = graph.direct(ue, n);
 		            e = graph.oppositeArc(e);
 		            ue = e;
 		            bool d = graph.direction(e);
 		            ignore_unused_variable_warning(d);
+		          }
+		        }
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief An empty idable base digraph class.
 		    ///
 		    /// This class provides beside the core digraph features
 		    /// core id functions for the digraph structure.
 		    /// The most of the base digraphs should conform to this concept.
 		    /// The id's are unique and immutable.
 		    template <typename _Base = BaseDigraphComponent>
 		    class IDableDigraphComponent : public _Base {
 		    template <typename BAS = BaseDigraphComponent>
 		    class IDableDigraphComponent : public BAS {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// \brief Gives back an unique integer id for the Node.
 		      ///
 		      /// Gives back an unique integer id for the Node.
 		      ///
 		      int id(const Node&) const { return -1;}
 		      /// \brief Gives back the node by the unique id.
 		      ///
 		      /// Gives back the node by the unique id.
 		      /// If the digraph does not contain node with the given id
 		      /// then the result of the function is undetermined.
 		      Node nodeFromId(int) const { return INVALID;}
 		      /// \brief Gives back an unique integer id for the Arc.
 		      ///
 		      /// Gives back an unique integer id for the Arc.
 		      ///
 		      int id(const Arc&) const { return -1;}
 		      /// \brief Gives back the arc by the unique id.
 		      ///
 		      /// Gives back the arc by the unique id.
 		      /// If the digraph does not contain arc with the given id
 		      /// then the result of the function is undetermined.
 		      Arc arcFromId(int) const { return INVALID;}
 		      /// \brief Gives back an integer greater or equal to the maximum
 		      /// Node id.
 		      ///
 		      /// Gives back an integer greater or equal to the maximum Node
 		      /// id.
 		      int maxNodeId() const { return -1;}
 		      /// \brief Gives back an integer greater or equal to the maximum
 		      /// Arc id.
 		      ///
 		      /// Gives back an integer greater or equal to the maximum Arc
 		      /// id.
 		      int maxArcId() const { return -1;}
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph >();
 		          typename _Digraph::Node node;
 		          int nid = digraph.id(node);
 		          nid = digraph.id(node);
 		          node = digraph.nodeFromId(nid);
 		          typename _Digraph::Arc arc;
 		          int eid = digraph.id(arc);
 		          eid = digraph.id(arc);
 		          arc = digraph.arcFromId(eid);
 		          nid = digraph.maxNodeId();
 		          ignore_unused_variable_warning(nid);
 		          eid = digraph.maxArcId();
 		          ignore_unused_variable_warning(eid);
+		        }
 		        const _Digraph& digraph;
 		      };
 		    };
 		    /// \brief An empty idable base undirected graph class.
 		    ///
 		    /// This class provides beside the core undirected graph features
 		    /// core id functions for the undirected graph structure.  The
 		    /// most of the base undirected graphs should conform to this
 		    /// concept.  The id's are unique and immutable.
 		    template <typename _Base = BaseGraphComponent>
 		    class IDableGraphComponent : public IDableDigraphComponent<_Base> {
 		    template <typename BAS = BaseGraphComponent>
 		    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename Base::Edge Edge;
-		      using IDableDigraphComponent<_Base>::id;
+		      using IDableDigraphComponent<Base>::id;
 		      /// \brief Gives back an unique integer id for the Edge.
 		      ///
 		      /// Gives back an unique integer id for the Edge.
 		      ///
 		      int id(const Edge&) const { return -1;}
 		      /// \brief Gives back the edge by the unique id.
 		      ///
 		      /// Gives back the edge by the unique id.  If the
 		      /// graph does not contain arc with the given id then the
 		      /// result of the function is undetermined.
 		      Edge edgeFromId(int) const { return INVALID;}
 		      /// \brief Gives back an integer greater or equal to the maximum
 		      /// Edge id.
 		      ///
 		      /// Gives back an integer greater or equal to the maximum Edge
 		      /// id.
 		      int maxEdgeId() const { return -1;}
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Graph >();
 		          checkConcept<IDableDigraphComponent<Base>, _Graph >();
 		          typename _Graph::Edge edge;
 		          int ueid = graph.id(edge);
 		          ueid = graph.id(edge);
 		          edge = graph.edgeFromId(ueid);
 		          ueid = graph.maxEdgeId();
 		          ignore_unused_variable_warning(ueid);
+		        }
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief Skeleton class for graph NodeIt and ArcIt
 		    ///
 		    /// Skeleton class for graph NodeIt and ArcIt.
 		    ///
 		    template <typename _Graph, typename _Item>
 		    class GraphItemIt : public _Item {
 		    template <typename GR, typename Item>
 		    class GraphItemIt : public Item {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// @warning The default constructor sets the iterator
 		      /// to an undefined value.
 		      GraphItemIt() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      ///
 		      GraphItemIt(const GraphItemIt& ) {}
 		      /// \brief Sets the iterator to the first item.
 		      ///
 		      /// Sets the iterator to the first item of \c the graph.
 		      ///
-		      explicit GraphItemIt(const _Graph&) {}
+		      explicit GraphItemIt(const GR&) {}
 		      /// \brief Invalid constructor \& conversion.
 		      ///
 		      /// This constructor initializes the item to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphItemIt(Invalid) {}
 		      /// \brief Assign operator for items.
 		      ///
 		      /// The items are assignable.
 		      ///
 		      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
 		      /// \brief Next item.
 		      ///
 		      /// Assign the iterator to the next item.
 		      ///
 		      GraphItemIt& operator++() { return *this; }
 		      /// \brief Equality operator
 		      ///
 		      /// Two iterators are equal if and only if they point to the
 		      /// same object or both are invalid.
 		      bool operator==(const GraphItemIt&) const { return true;}
 		      /// \brief Inequality operator
 		      ///
 		      /// \sa operator==(Node n)
 		      ///
 		      bool operator!=(const GraphItemIt&) const { return true;}
 		      template<typename _GraphItemIt>
 		      struct Constraints {
 		        void constraints() {
 		          _GraphItemIt it1(g);
 		          _GraphItemIt it2;
 		          it2 = ++it1;
 		          ++it2 = it1;
 		          ++(++it1);
-		          _Item bi = it1;
+		          Item bi = it1;
 		          bi = it2;
+		        }
-		        _Graph& g;
+		        GR& g;
 		      };
 		    };
 		    /// \brief Skeleton class for graph InArcIt and OutArcIt
 		    ///
 		    /// \note Because InArcIt and OutArcIt may not inherit from the same
 		    /// base class, the _selector is a additional template parameter. For
 		    /// InArcIt you should instantiate it with character 'i' and for
 		    /// base class, the \c sel is a additional template parameter (selector).
 		    /// For InArcIt you should instantiate it with character 'i' and for
 		    /// OutArcIt with 'o'.
 		    template <typename _Graph,
 		              typename _Item = typename _Graph::Arc,
 		              typename _Base = typename _Graph::Node,
 		              char _selector = '0'>
-		    class GraphIncIt : public _Item {
+		    template <typename GR,
 		              typename Item = typename GR::Arc,
 		              typename Base = typename GR::Node,
 		              char sel = '0'>
 		    class GraphIncIt : public Item {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// @warning The default constructor sets the iterator
 		      /// to an undefined value.
 		      GraphIncIt() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      ///
-		      GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
+		      GraphIncIt(GraphIncIt const& gi) : Item(gi) {}
 		      /// \brief Sets the iterator to the first arc incoming into or outgoing
 		      /// from the node.
 		      ///
 		      /// Sets the iterator to the first arc incoming into or outgoing
 		      /// from the node.
 		      ///
-		      explicit GraphIncIt(const _Graph&, const _Base&) {}
+		      explicit GraphIncIt(const GR&, const Base&) {}
 		      /// \brief Invalid constructor \& conversion.
 		      ///
 		      /// This constructor initializes the item to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphIncIt(Invalid) {}
 		      /// \brief Assign operator for iterators.
 		      ///
 		      /// The iterators are assignable.
 		      ///
 		      GraphIncIt& operator=(GraphIncIt const&) { return *this; }
 		      /// \brief Next item.
 		      ///
 		      /// Assign the iterator to the next item.
 		      ///
 		      GraphIncIt& operator++() { return *this; }
 		      /// \brief Equality operator
 		      ///
 		      /// Two iterators are equal if and only if they point to the
 		      /// same object or both are invalid.
 		      bool operator==(const GraphIncIt&) const { return true;}
 		      /// \brief Inequality operator
 		      ///
 		      /// \sa operator==(Node n)
 		      ///
 		      bool operator!=(const GraphIncIt&) const { return true;}
 		      template <typename _GraphIncIt>
 		      struct Constraints {
 		        void constraints() {
-		          checkConcept<GraphItem<_selector>, _GraphIncIt>();
+		          checkConcept<GraphItem<sel>, _GraphIncIt>();
 		          _GraphIncIt it1(graph, node);
 		          _GraphIncIt it2;
 		          it2 = ++it1;
 		          ++it2 = it1;
 		          ++(++it1);
-		          _Item e = it1;
+		          Item e = it1;
 		          e = it2;
+		        }
 		        _Item arc;
 		        _Base node;
-		        _Graph graph;
+		        Item arc;
 		        Base node;
 		        GR graph;
 		        _GraphIncIt it;
 		      };
 		    };
 		    /// \brief An empty iterable digraph class.
 		    ///
 		    /// This class provides beside the core digraph features
 		    /// iterator based iterable interface for the digraph structure.
 		    /// This concept is part of the Digraph concept.
 		    template <typename _Base = BaseDigraphComponent>
 		    class IterableDigraphComponent : public _Base {
 		    template <typename BAS = BaseDigraphComponent>
 		    class IterableDigraphComponent : public BAS {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      typedef IterableDigraphComponent Digraph;
 		      /// \name Base iteration
 		      ///
 		      /// This interface provides functions for iteration on digraph items
 		      ///
 		      /// @{
 		      /// \brief Gives back the first node in the iterating order.
 		      ///
 		      /// Gives back the first node in the iterating order.
 		      ///
 		      void first(Node&) const {}
 		      /// \brief Gives back the next node in the iterating order.
 		      ///
 		      /// Gives back the next node in the iterating order.
 		      ///
 		      void next(Node&) const {}
 		      /// \brief Gives back the first arc in the iterating order.
 		      ///
 		      /// Gives back the first arc in the iterating order.
 		      ///
 		      void first(Arc&) const {}
 		      /// \brief Gives back the next arc in the iterating order.
 		      ///
 		      /// Gives back the next arc in the iterating order.
 		      ///
 		      void next(Arc&) const {}
 		      /// \brief Gives back the first of the arcs point to the given
 		      /// node.
 		      ///
 		      /// Gives back the first of the arcs point to the given node.
 		      ///
 		      void firstIn(Arc&, const Node&) const {}
 		      /// \brief Gives back the next of the arcs points to the given
 		      /// node.
 		      ///
 		      /// Gives back the next of the arcs points to the given node.
 		      ///
 		      void nextIn(Arc&) const {}
 		      /// \brief Gives back the first of the arcs start from the
 		      /// given node.
 		      ///
 		      /// Gives back the first of the arcs start from the given node.
 		      ///
 		      void firstOut(Arc&, const Node&) const {}
 		      /// \brief Gives back the next of the arcs start from the given
 		      /// node.
 		      ///
 		      /// Gives back the next of the arcs start from the given node.
 		      ///
 		      void nextOut(Arc&) const {}
 		      /// @}
 		      /// \name Class based iteration
 		      ///
 		      /// This interface provides functions for iteration on digraph items
 		      ///
 		      /// @{
 		      /// \brief This iterator goes through each node.
 		      ///
 		      /// This iterator goes through each node.
 		      ///
 		      typedef GraphItemIt<Digraph, Node> NodeIt;
 		      /// \brief This iterator goes through each node.
 		      ///
 		      /// This iterator goes through each node.
 		      ///
 		      typedef GraphItemIt<Digraph, Arc> ArcIt;
 		      /// \brief This iterator goes trough the incoming arcs of a node.
 		      ///
 		      /// This iterator goes trough the \e inccoming arcs of a certain node
 		      /// of a digraph.
 		      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
 		      /// \brief This iterator goes trough the outgoing arcs of a node.
 		      ///
 		      /// This iterator goes trough the \e outgoing arcs of a certain node
 		      /// of a digraph.
 		      typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Gives back the base node of the iterator.
 		      /// It is always the target of the pointed arc.
 		      Node baseNode(const InArcIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Gives back the running node of the iterator.
 		      /// It is always the source of the pointed arc.
 		      Node runningNode(const InArcIt&) const { return INVALID; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Gives back the base node of the iterator.
 		      /// It is always the source of the pointed arc.
 		      Node baseNode(const OutArcIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Gives back the running node of the iterator.
 		      /// It is always the target of the pointed arc.
 		      Node runningNode(const OutArcIt&) const { return INVALID; }
 		      /// @}
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
+		          {
 		            typename _Digraph::Node node(INVALID);
 		            typename _Digraph::Arc arc(INVALID);
+		            {
 		              digraph.first(node);
 		              digraph.next(node);
+		            }
+		            {
 		              digraph.first(arc);
 		              digraph.next(arc);
+		            }
+		            {
 		              digraph.firstIn(arc, node);
 		              digraph.nextIn(arc);
+		            }
+		            {
 		              digraph.firstOut(arc, node);
 		              digraph.nextOut(arc);
+		            }
+		          }
+		          {
 		            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
 		              typename _Digraph::ArcIt >();
 		            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
 		              typename _Digraph::NodeIt >();
 		            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
 		              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
 		            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
 		              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
 		            typename _Digraph::Node n;
 		            typename _Digraph::InArcIt ieit(INVALID);
 		            typename _Digraph::OutArcIt oeit(INVALID);
 		            n = digraph.baseNode(ieit);
 		            n = digraph.runningNode(ieit);
 		            n = digraph.baseNode(oeit);
 		            n = digraph.runningNode(oeit);
 		            ignore_unused_variable_warning(n);
+		          }
+		        }
 		        const _Digraph& digraph;
 		      };
 		    };
 		    /// \brief An empty iterable undirected graph class.
 		    ///
 		    /// This class provides beside the core graph features iterator
 		    /// based iterable interface for the undirected graph structure.
 		    /// This concept is part of the Graph concept.
 		    template <typename _Base = BaseGraphComponent>
 		    class IterableGraphComponent : public IterableDigraphComponent<_Base> {
 		    template <typename BAS = BaseGraphComponent>
 		    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      typedef typename Base::Edge Edge;
 		      typedef IterableGraphComponent Graph;
 		      /// \name Base iteration
 		      ///
 		      /// This interface provides functions for iteration on graph items
 		      /// @{
 		      using IterableDigraphComponent<_Base>::first;
 		      using IterableDigraphComponent<_Base>::next;
 		      using IterableDigraphComponent<Base>::first;
 		      using IterableDigraphComponent<Base>::next;
 		      /// \brief Gives back the first edge in the iterating
 		      /// order.
 		      ///
 		      /// Gives back the first edge in the iterating order.
 		      ///
 		      void first(Edge&) const {}
 		      /// \brief Gives back the next edge in the iterating
 		      /// order.
 		      ///
 		      /// Gives back the next edge in the iterating order.
 		      ///
 		      void next(Edge&) const {}
 		      /// \brief Gives back the first of the edges from the
 		      /// given node.
 		      ///
 		      /// Gives back the first of the edges from the given
 		      /// node. The bool parameter gives back that direction which
 		      /// gives a good direction of the edge so the source of the
 		      /// directed arc is the given node.
 		      void firstInc(Edge&, bool&, const Node&) const {}
 		      /// \brief Gives back the next of the edges from the
 		      /// given node.
 		      ///
 		      /// Gives back the next of the edges from the given
 		      /// node. The bool parameter should be used as the \c firstInc()
 		      /// use it.
 		      void nextInc(Edge&, bool&) const {}
 		      using IterableDigraphComponent<_Base>::baseNode;
 		      using IterableDigraphComponent<_Base>::runningNode;
 		      using IterableDigraphComponent<Base>::baseNode;
 		      using IterableDigraphComponent<Base>::runningNode;
 		      /// @}
 		      /// \name Class based iteration
 		      ///
 		      /// This interface provides functions for iteration on graph items
 		      ///
 		      /// @{
 		      /// \brief This iterator goes through each node.
 		      ///
 		      /// This iterator goes through each node.
 		      typedef GraphItemIt<Graph, Edge> EdgeIt;
 		      /// \brief This iterator goes trough the incident arcs of a
 		      /// node.
 		      ///
 		      /// This iterator goes trough the incident arcs of a certain
 		      /// node of a graph.
 		      typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt;
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Gives back the base node of the iterator.
 		      Node baseNode(const IncEdgeIt&) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Gives back the running node of the iterator.
 		      Node runningNode(const IncEdgeIt&) const { return INVALID; }
 		      /// @}
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<IterableDigraphComponent<Base>, _Graph>();
+		          {
 		            typename _Graph::Node node(INVALID);
 		            typename _Graph::Edge edge(INVALID);
 		            bool dir;
+		            {
 		              graph.first(edge);
 		              graph.next(edge);
+		            }
+		            {
 		              graph.firstInc(edge, dir, node);
 		              graph.nextInc(edge, dir);
+		            }
+		          }
+		          {
 		            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
 		              typename _Graph::EdgeIt >();
 		            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
 		              typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
 		            typename _Graph::Node n;
 		            typename _Graph::IncEdgeIt ueit(INVALID);
 		            n = graph.baseNode(ueit);
 		            n = graph.runningNode(ueit);
+		          }
+		        }
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief An empty alteration notifier digraph class.
 		    ///
 		    /// This class provides beside the core digraph features alteration
 		    /// notifier interface for the digraph structure.  This implements
 		    /// an observer-notifier pattern for each digraph item. More
 		    /// obsevers can be registered into the notifier and whenever an
 		    /// alteration occured in the digraph all the observers will
 		    /// notified about it.
 		    template <typename _Base = BaseDigraphComponent>
 		    class AlterableDigraphComponent : public _Base {
 		    template <typename BAS = BaseDigraphComponent>
 		    class AlterableDigraphComponent : public BAS {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// The node observer registry.
 		      typedef AlterationNotifier<AlterableDigraphComponent, Node>
 		      NodeNotifier;
 		      /// The arc observer registry.
 		      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
 		      ArcNotifier;
 		      /// \brief Gives back the node alteration notifier.
 		      ///
 		      /// Gives back the node alteration notifier.
 		      NodeNotifier& notifier(Node) const {
 		        return NodeNotifier();
+		      }
 		      /// \brief Gives back the arc alteration notifier.
 		      ///
 		      /// Gives back the arc alteration notifier.
 		      ArcNotifier& notifier(Arc) const {
 		        return ArcNotifier();
+		      }
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          typename _Digraph::NodeNotifier& nn
 		            = digraph.notifier(typename _Digraph::Node());
 		          typename _Digraph::ArcNotifier& en
 		            = digraph.notifier(typename _Digraph::Arc());
 		          ignore_unused_variable_warning(nn);
 		          ignore_unused_variable_warning(en);
+		        }
 		        const _Digraph& digraph;
 		      };
 		    };
 		    /// \brief An empty alteration notifier undirected graph class.
 		    ///
 		    /// This class provides beside the core graph features alteration
 		    /// notifier interface for the graph structure.  This implements
 		    /// an observer-notifier pattern for each graph item. More
 		    /// obsevers can be registered into the notifier and whenever an
 		    /// alteration occured in the graph all the observers will
 		    /// notified about it.
 		    template <typename _Base = BaseGraphComponent>
 		    class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
 		    template <typename BAS = BaseGraphComponent>
 		    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename Base::Edge Edge;
 		      /// The arc observer registry.
 		      typedef AlterationNotifier<AlterableGraphComponent, Edge>
 		      EdgeNotifier;
 		      /// \brief Gives back the arc alteration notifier.
 		      ///
 		      /// Gives back the arc alteration notifier.
 		      EdgeNotifier& notifier(Edge) const {
 		        return EdgeNotifier();
+		      }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<AlterableGraphComponent<Base>, _Graph>();
 		          typename _Graph::EdgeNotifier& uen
 		            = graph.notifier(typename _Graph::Edge());
 		          ignore_unused_variable_warning(uen);
+		        }
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief Class describing the concept of graph maps
 		    ///
 		    /// This class describes the common interface of the graph maps
 		    /// (NodeMap, ArcMap), that is maps that can be used to
 		    /// associate data to graph descriptors (nodes or arcs).
 		    template <typename _Graph, typename _Item, typename _Value>
 		    class GraphMap : public ReadWriteMap<_Item, _Value> {
 		    template <typename GR, typename K, typename V>
 		    class GraphMap : public ReadWriteMap<K, V> {
 		    public:
-		      typedef ReadWriteMap<_Item, _Value> Parent;
+		      typedef ReadWriteMap<K, V> Parent;
 		      /// The graph type of the map.
-		      typedef _Graph Graph;
+		      typedef GR Graph;
 		      /// The key type of the map.
-		      typedef _Item Key;
+		      typedef K Key;
 		      /// The value type of the map.
-		      typedef _Value Value;
+		      typedef V Value;
 		      /// \brief Construct a new map.
 		      ///
 		      /// Construct a new map for the graph.
 		      explicit GraphMap(const Graph&) {}
 		      /// \brief Construct a new map with default value.
 		      ///
 		      /// Construct a new map for the graph and initalise the values.
 		      GraphMap(const Graph&, const Value&) {}
 		    private:
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy Constructor.
 		      GraphMap(const GraphMap&) : Parent() {}
 		      /// \brief Assign operator.
 		      ///
 		      /// Assign operator. It does not mofify the underlying graph,
 		      /// it just iterates on the current item set and set the  map
 		      /// with the value returned by the assigned map.
 		      template <typename CMap>
 		      GraphMap& operator=(const CMap&) {
 		        checkConcept<ReadMap<Key, Value>, CMap>();
 		        return *this;
+		      }
 		    public:
 		      template<typename _Map>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<ReadWriteMap<Key, Value>, _Map >();
 		          // Construction with a graph parameter
 		          _Map a(g);
 		          // Constructor with a graph and a default value parameter
 		          _Map a2(g,t);
 		          // Copy constructor.
 		          // _Map b(c);
 		          // ReadMap<Key, Value> cmap;
 		          // b = cmap;
 		          ignore_unused_variable_warning(a);
 		          ignore_unused_variable_warning(a2);
 		          // ignore_unused_variable_warning(b);
+		        }
 		        const _Map &c;
 		        const Graph &g;
 		        const typename GraphMap::Value &t;
 		      };
 		    };
 		    /// \brief An empty mappable digraph class.
 		    ///
 		    /// This class provides beside the core digraph features
 		    /// map interface for the digraph structure.
 		    /// This concept is part of the Digraph concept.
 		    template <typename _Base = BaseDigraphComponent>
 		    class MappableDigraphComponent : public _Base  {
 		    template <typename BAS = BaseDigraphComponent>
 		    class MappableDigraphComponent : public BAS  {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      typedef MappableDigraphComponent Digraph;
 		      /// \brief ReadWrite map of the nodes.
 		      ///
 		      /// ReadWrite map of the nodes.
 		      ///
 		      template <typename _Value>
 		      class NodeMap : public GraphMap<Digraph, Node, _Value> {
 		      template <typename V>
 		      class NodeMap : public GraphMap<Digraph, Node, V> {
 		      public:
-		        typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;
+		        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
 		        /// \brief Construct a new map.
 		        ///
 		        /// Construct a new map for the digraph.
 		        explicit NodeMap(const MappableDigraphComponent& digraph)
 		          : Parent(digraph) {}
 		        /// \brief Construct a new map with default value.
 		        ///
 		        /// Construct a new map for the digraph and initalise the values.
-		        NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
+		        NodeMap(const MappableDigraphComponent& digraph, const V& value)
 		          : Parent(digraph, value) {}
 		      private:
 		        /// \brief Copy constructor.
 		        ///
 		        /// Copy Constructor.
 		        NodeMap(const NodeMap& nm) : Parent(nm) {}
 		        /// \brief Assign operator.
 		        ///
 		        /// Assign operator.
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
-		          checkConcept<ReadMap<Node, _Value>, CMap>();
+		          checkConcept<ReadMap<Node, V>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \brief ReadWrite map of the arcs.
 		      ///
 		      /// ReadWrite map of the arcs.
 		      ///
 		      template <typename _Value>
 		      class ArcMap : public GraphMap<Digraph, Arc, _Value> {
 		      template <typename V>
 		      class ArcMap : public GraphMap<Digraph, Arc, V> {
 		      public:
-		        typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;
+		        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
 		        /// \brief Construct a new map.
 		        ///
 		        /// Construct a new map for the digraph.
 		        explicit ArcMap(const MappableDigraphComponent& digraph)
 		          : Parent(digraph) {}
 		        /// \brief Construct a new map with default value.
 		        ///
 		        /// Construct a new map for the digraph and initalise the values.
-		        ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
+		        ArcMap(const MappableDigraphComponent& digraph, const V& value)
 		          : Parent(digraph, value) {}
 		      private:
 		        /// \brief Copy constructor.
 		        ///
 		        /// Copy Constructor.
 		        ArcMap(const ArcMap& nm) : Parent(nm) {}
 		        /// \brief Assign operator.
 		        ///
 		        /// Assign operator.
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
-		          checkConcept<ReadMap<Arc, _Value>, CMap>();
+		          checkConcept<ReadMap<Arc, V>, CMap>();
 		          return *this;
+		        }
 		      };
 		      template <typename _Digraph>
 		      struct Constraints {
 		        struct Dummy {
 		          int value;
 		          Dummy() : value(0) {}
 		          Dummy(int _v) : value(_v) {}
 		        };
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          { // int map test
 		            typedef typename _Digraph::template NodeMap<int> IntNodeMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
 		              IntNodeMap >();
 		          } { // bool map test
 		            typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
 		              BoolNodeMap >();
 		          } { // Dummy map test
 		            typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
 		              DummyNodeMap >();
+		          }
 		          { // int map test
 		            typedef typename _Digraph::template ArcMap<int> IntArcMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
 		              IntArcMap >();
 		          } { // bool map test
 		            typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
 		              BoolArcMap >();
 		          } { // Dummy map test
 		            typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
 		              DummyArcMap >();
+		          }
+		        }
 		        _Digraph& digraph;
 		      };
 		    };
 		    /// \brief An empty mappable base bipartite graph class.
 		    ///
 		    /// This class provides beside the core graph features
 		    /// map interface for the graph structure.
 		    /// This concept is part of the Graph concept.
 		    template <typename _Base = BaseGraphComponent>
 		    class MappableGraphComponent : public MappableDigraphComponent<_Base>  {
 		    template <typename BAS = BaseGraphComponent>
 		    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename Base::Edge Edge;
 		      typedef MappableGraphComponent Graph;
 		      /// \brief ReadWrite map of the edges.
 		      ///
 		      /// ReadWrite map of the edges.
 		      ///
 		      template <typename _Value>
 		      class EdgeMap : public GraphMap<Graph, Edge, _Value> {
 		      template <typename V>
 		      class EdgeMap : public GraphMap<Graph, Edge, V> {
 		      public:
-		        typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;
+		        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
 		        /// \brief Construct a new map.
 		        ///
 		        /// Construct a new map for the graph.
 		        explicit EdgeMap(const MappableGraphComponent& graph)
 		          : Parent(graph) {}
 		        /// \brief Construct a new map with default value.
 		        ///
 		        /// Construct a new map for the graph and initalise the values.
-		        EdgeMap(const MappableGraphComponent& graph, const _Value& value)
+		        EdgeMap(const MappableGraphComponent& graph, const V& value)
 		          : Parent(graph, value) {}
 		      private:
 		        /// \brief Copy constructor.
 		        ///
 		        /// Copy Constructor.
 		        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
 		        /// \brief Assign operator.
 		        ///
 		        /// Assign operator.
 		        template <typename CMap>
 		        EdgeMap& operator=(const CMap&) {
-		          checkConcept<ReadMap<Edge, _Value>, CMap>();
+		          checkConcept<ReadMap<Edge, V>, CMap>();
 		          return *this;
+		        }
 		      };
 		      template <typename _Graph>
 		      struct Constraints {
 		        struct Dummy {
 		          int value;
 		          Dummy() : value(0) {}
 		          Dummy(int _v) : value(_v) {}
 		        };
 		        void constraints() {
 		          checkConcept<MappableGraphComponent<Base>, _Graph>();
 		          { // int map test
 		            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
 		            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
 		              IntEdgeMap >();
 		          } { // bool map test
 		            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
 		            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
 		              BoolEdgeMap >();
 		          } { // Dummy map test
 		            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
 		            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
 		              DummyEdgeMap >();
+		          }
+		        }
 		        _Graph& graph;
 		      };
 		    };
 		    /// \brief An empty extendable digraph class.
 		    ///
 		    /// This class provides beside the core digraph features digraph
 		    /// extendable interface for the digraph structure.  The main
 		    /// difference between the base and this interface is that the
 		    /// digraph alterations should handled already on this level.
 		    template <typename _Base = BaseDigraphComponent>
 		    class ExtendableDigraphComponent : public _Base {
 		    template <typename BAS = BaseDigraphComponent>
 		    class ExtendableDigraphComponent : public BAS {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename _Base::Node Node;
 		      typedef typename _Base::Arc Arc;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// \brief Adds a new node to the digraph.
 		      ///
 		      /// Adds a new node to the digraph.
 		      ///
 		      Node addNode() {
 		        return INVALID;
+		      }
 		      /// \brief Adds a new arc connects the given two nodes.
 		      ///
 		      /// Adds a new arc connects the the given two nodes.
 		      Arc addArc(const Node&, const Node&) {
 		        return INVALID;
+		      }
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          typename _Digraph::Node node_a, node_b;
 		          node_a = digraph.addNode();
 		          node_b = digraph.addNode();
 		          typename _Digraph::Arc arc;
 		          arc = digraph.addArc(node_a, node_b);
+		        }
 		        _Digraph& digraph;
 		      };
 		    };
 		    /// \brief An empty extendable base undirected graph class.
 		    ///
 		    /// This class provides beside the core undirected graph features
 		    /// core undircted graph extend interface for the graph structure.
 		    /// The main difference between the base and this interface is
 		    /// that the graph alterations should handled already on this
 		    /// level.
 		    template <typename _Base = BaseGraphComponent>
 		    class ExtendableGraphComponent : public _Base {
 		    template <typename BAS = BaseGraphComponent>
 		    class ExtendableGraphComponent : public BAS {
 		    public:
 		      typedef _Base Base;
 		      typedef typename _Base::Node Node;
-		      typedef typename _Base::Edge Edge;
+		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Edge Edge;
 		      /// \brief Adds a new node to the graph.
 		      ///
 		      /// Adds a new node to the graph.
 		      ///
 		      Node addNode() {
 		        return INVALID;
+		      }
 		      /// \brief Adds a new arc connects the given two nodes.
 		      ///
 		      /// Adds a new arc connects the the given two nodes.
 		      Edge addArc(const Node&, const Node&) {
 		        return INVALID;
+		      }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Graph>();
 		          typename _Graph::Node node_a, node_b;
 		          node_a = graph.addNode();
 		          node_b = graph.addNode();
 		          typename _Graph::Edge edge;
 		          edge = graph.addEdge(node_a, node_b);
+		        }
 		        _Graph& graph;
 		      };
 		    };
 		    /// \brief An empty erasable digraph class.
 		    ///
 		    /// This class provides beside the core digraph features core erase
 		    /// functions for the digraph structure. The main difference between
 		    /// the base and this interface is that the digraph alterations
 		    /// should handled already on this level.
 		    template <typename _Base = BaseDigraphComponent>
 		    class ErasableDigraphComponent : public _Base {
 		    template <typename BAS = BaseDigraphComponent>
 		    class ErasableDigraphComponent : public BAS {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// \brief Erase a node from the digraph.
 		      ///
 		      /// Erase a node from the digraph. This function should
 		      /// erase all arcs connecting to the node.
 		      void erase(const Node&) {}
 		      /// \brief Erase an arc from the digraph.
 		      ///
 		      /// Erase an arc from the digraph.
 		      ///
 		      void erase(const Arc&) {}
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          typename _Digraph::Node node;
 		          digraph.erase(node);
 		          typename _Digraph::Arc arc;
 		          digraph.erase(arc);
+		        }
 		        _Digraph& digraph;
 		      };
 		    };
 		    /// \brief An empty erasable base undirected graph class.
 		    ///
 		    /// This class provides beside the core undirected graph features
 		    /// core erase functions for the undirceted graph structure. The
 		    /// main difference between the base and this interface is that
 		    /// the graph alterations should handled already on this level.
 		    template <typename _Base = BaseGraphComponent>
 		    class ErasableGraphComponent : public _Base {
 		    template <typename BAS = BaseGraphComponent>
 		    class ErasableGraphComponent : public BAS {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Edge Edge;
 		      /// \brief Erase a node from the graph.
 		      ///
 		      /// Erase a node from the graph. This function should erase
 		      /// arcs connecting to the node.
 		      void erase(const Node&) {}
 		      /// \brief Erase an arc from the graph.
 		      ///
 		      /// Erase an arc from the graph.
 		      ///
 		      void erase(const Edge&) {}
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Graph>();
 		          typename _Graph::Node node;
 		          graph.erase(node);
 		          typename _Graph::Edge edge;
 		          graph.erase(edge);
+		        }
 		        _Graph& graph;
 		      };
 		    };
 		    /// \brief An empty clearable base digraph class.
 		    ///
 		    /// This class provides beside the core digraph features core clear
 		    /// functions for the digraph structure. The main difference between
 		    /// the base and this interface is that the digraph alterations
 		    /// should handled already on this level.
 		    template <typename _Base = BaseDigraphComponent>
 		    class ClearableDigraphComponent : public _Base {
 		    template <typename BAS = BaseDigraphComponent>
 		    class ClearableDigraphComponent : public BAS {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      /// \brief Erase all nodes and arcs from the digraph.
 		      ///
 		      /// Erase all nodes and arcs from the digraph.
 		      ///
 		      void clear() {}
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          digraph.clear();
+		        }
 		        _Digraph digraph;
 		      };
 		    };
 		    /// \brief An empty clearable base undirected graph class.
 		    ///
 		    /// This class provides beside the core undirected graph features
 		    /// core clear functions for the undirected graph structure. The
 		    /// main difference between the base and this interface is that
 		    /// the graph alterations should handled already on this level.
 		    template <typename _Base = BaseGraphComponent>
 		    class ClearableGraphComponent : public ClearableDigraphComponent<_Base> {
 		    template <typename BAS = BaseGraphComponent>
 		    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
 		    public:
-		      typedef _Base Base;
+		      typedef BAS Base;
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<ClearableGraphComponent<Base>, _Graph>();
+		        }
 		        _Graph graph;
 		      };
 		    };
+		  }
+		}
 		#endif

lemon/concepts/heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup concept
 		///\file
 		///\brief The concept of heaps.
 		#ifndef LEMON_CONCEPTS_HEAP_H
 		#define LEMON_CONCEPTS_HEAP_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief The heap concept.
 		    ///
 		    /// Concept class describing the main interface of heaps.
 		    template <typename Priority, typename ItemIntMap>
 		    /// Concept class describing the main interface of heaps. A \e heap
 		    /// is a data structure for storing items with specified values called
 		    /// \e priorities in such a way that finding the item with minimum
 		    /// priority is efficient. In a heap one can change the priority of an
 		    /// item, add or erase an item, etc.
 		    ///
 		    /// \tparam PR Type of the priority of the items.
 		    /// \tparam IM A read and writable item map with int values, used
 		    /// internally to handle the cross references.
 		    /// \tparam Comp A functor class for the ordering of the priorities.
 		    /// The default is \c std::less<PR>.
 		#ifdef DOXYGEN
 		    template <typename PR, typename IM, typename Comp = std::less<PR> >
 		#else
 		    template <typename PR, typename IM>
 		#endif
 		    class Heap {
 		    public:
 		      /// Type of the item-int map.
 		      typedef IM ItemIntMap;
 		      /// Type of the priorities.
 		      typedef PR Prio;
 		      /// Type of the items stored in the heap.
 		      typedef typename ItemIntMap::Key Item;
 		      /// Type of the priorities.
 		      typedef Priority Prio;
 		      /// \brief Type to represent the states of the items.
 		      ///
 		      /// Each item has a state associated to it. It can be "in heap",
 		      /// "pre heap" or "post heap". The later two are indifferent
 		      /// from the point of view of the heap, but may be useful for
 		      /// the user.
 		      ///
 		      /// The \c ItemIntMap must be initialized in such a way, that it
 		      /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
 		      /// The item-int map must be initialized in such way that it assigns
 		      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		      enum State {
 		        IN_HEAP = 0,
 		        PRE_HEAP = -1,
-		        POST_HEAP = -2
+		        IN_HEAP = 0,    ///< The "in heap" state constant.
 		        PRE_HEAP = -1,  ///< The "pre heap" state constant.
 		        POST_HEAP = -2  ///< The "post heap" state constant.
 		      };
 		      /// \brief The constructor.
 		      ///
 		      /// The constructor.
 		      /// \param map A map that assigns \c int values to keys of type
 		      /// \c Item. It is used internally by the heap implementations to
 		      /// handle the cross references. The assigned value must be
 		      /// \c PRE_HEAP (<tt>-1</tt>) for every item.
 		      explicit Heap(ItemIntMap &map) {}
 		      /// \brief The number of items stored in the heap.
 		      ///
 		      /// Returns the number of items stored in the heap.
 		      int size() const { return 0; }
 		      /// \brief Checks if the heap is empty.
 		      ///
 		      /// Returns \c true if the heap is empty.
 		      bool empty() const { return false; }
 		      /// \brief Makes the heap empty.
 		      ///
 		      /// Makes the heap empty.
 		      void clear();
 		      /// \brief Inserts an item into the heap with the given priority.
 		      ///
 		      /// Inserts the given item into the heap with the given priority.
 		      /// \param i The item to insert.
 		      /// \param p The priority of the item.
 		      void push(const Item &i, const Prio &p) {}
 		      /// \brief Returns the item having minimum priority.
 		      ///
 		      /// Returns the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Item top() const {}
 		      /// \brief The minimum priority.
 		      ///
 		      /// Returns the minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Prio prio() const {}
 		      /// \brief Removes the item having minimum priority.
 		      ///
 		      /// Removes the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      void pop() {}
 		      /// \brief Removes an item from the heap.
 		      ///
 		      /// Removes the given item from the heap if it is already stored.
 		      /// \param i The item to delete.
 		      void erase(const Item &i) {}
 		      /// \brief The priority of an item.
 		      ///
 		      /// Returns the priority of the given item.
 		      /// \param i The item.
 		      /// \pre \c i must be in the heap.
 		      /// \param i The item.
 		      Prio operator[](const Item &i) const {}
 		      /// \brief Sets the priority of an item or inserts it, if it is
 		      /// not stored in the heap.
 		      ///
 		      /// This method sets the priority of the given item if it is
 		      /// already stored in the heap.
 		      /// Otherwise it inserts the given item with the given priority.
 		      ///
 		      /// \param i The item.
 		      /// \param p The priority.
 		      void set(const Item &i, const Prio &p) {}
 		      /// \brief Decreases the priority of an item to the given value.
 		      ///
 		      /// Decreases the priority of an item to the given value.
 		      /// \pre \c i must be stored in the heap with priority at least \c p.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      /// \pre \c i must be stored in the heap with priority at least \c p.
 		      void decrease(const Item &i, const Prio &p) {}
 		      /// \brief Increases the priority of an item to the given value.
 		      ///
 		      /// Increases the priority of an item to the given value.
 		      /// \pre \c i must be stored in the heap with priority at most \c p.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      /// \pre \c i must be stored in the heap with priority at most \c p.
 		      void increase(const Item &i, const Prio &p) {}
 		      /// \brief Returns if an item is in, has already been in, or has
 		      /// never been in the heap.
 		      ///
 		      /// This method returns \c PRE_HEAP if the given item has never
 		      /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		      /// and \c POST_HEAP otherwise.
 		      /// In the latter case it is possible that the item will get back
 		      /// to the heap again.
 		      /// \param i The item.
 		      State state(const Item &i) const {}
 		      /// \brief Sets the state of an item in the heap.
 		      ///
 		      /// Sets the state of the given item in the heap. It can be used
 		      /// to manually clear the heap when it is important to achive the
 		      /// better time complexity.
 		      /// \param i The item.
 		      /// \param st The state. It should not be \c IN_HEAP.
 		      void state(const Item& i, State st) {}
 		      template <typename _Heap>
 		      struct Constraints {
 		      public:
 		        void constraints() {
 		          typedef typename _Heap::Item OwnItem;
 		          typedef typename _Heap::Prio OwnPrio;
 		          typedef typename _Heap::State OwnState;
 		          Item item;
 		          Prio prio;
 		          item=Item();
 		          prio=Prio();
 		          ignore_unused_variable_warning(item);
 		          ignore_unused_variable_warning(prio);
 		          OwnItem own_item;
 		          OwnPrio own_prio;
 		          OwnState own_state;
 		          own_item=Item();
 		          own_prio=Prio();
 		          ignore_unused_variable_warning(own_item);
 		          ignore_unused_variable_warning(own_prio);
 		          ignore_unused_variable_warning(own_state);
 		          _Heap heap1(map);
 		          _Heap heap2 = heap1;
 		          ignore_unused_variable_warning(heap1);
 		          ignore_unused_variable_warning(heap2);
 		          int s = heap.size();
 		          ignore_unused_variable_warning(s);
 		          bool e = heap.empty();
 		          ignore_unused_variable_warning(e);
 		          prio = heap.prio();
 		          item = heap.top();
 		          prio = heap[item];
 		          own_prio = heap.prio();
 		          own_item = heap.top();
 		          own_prio = heap[own_item];
 		          heap.push(item, prio);
 		          heap.push(own_item, own_prio);
 		          heap.pop();
 		          heap.set(item, prio);
 		          heap.decrease(item, prio);
 		          heap.increase(item, prio);
 		          heap.set(own_item, own_prio);
 		          heap.decrease(own_item, own_prio);
 		          heap.increase(own_item, own_prio);
 		          heap.erase(item);
 		          heap.erase(own_item);
 		          heap.clear();
 		          own_state = heap.state(own_item);
 		          heap.state(own_item, own_state);
 		          own_state = _Heap::PRE_HEAP;
 		          own_state = _Heap::IN_HEAP;
 		          own_state = _Heap::POST_HEAP;
+		        }
 		        _Heap& heap;
 		        ItemIntMap& map;
 		      };
 		    };
 		    /// @}
 		  } // namespace lemon
+		}
 		#endif

lemon/concepts/path.h

Show inline comments

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

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