LEMON/LEMON-main Changeset - r314:2cc60866a0c9

Repositories » LEMON » LEMON-main

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

Changeset - r314:2cc60866a0c9

« 313:64f8f7

315:c175e3 »

r314:2cc60866a0c9

Thu, 09 Oct 2008 13:27:35

[Not Reviewed]

0 comments (0 inline)

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

Doc reorganization + improvements - Reorganize several tools (move them to other modules). - Add new module for map concepts. - Remove the doc of all tools in lemon/bits. - Improvements in groups.dox. - Fix some doxygen warnings.

0 17 0

default

17 files changed with 524 insertions and 555 deletions:

doc/groups.dox

doc/mainpage.dox

lemon/bits/alteration_notifier.h

209

222

lemon/bits/array_map.h

lemon/bits/base_extender.h

lemon/bits/bezier.h

lemon/bits/default_map.h

lemon/bits/enable_if.h

lemon/bits/graph_extender.h

lemon/bits/map_extender.h

lemon/bits/traits.h

lemon/bits/vector_map.h

lemon/concepts/maps.h

lemon/dim2.h

lemon/maps.h

↑ 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-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.
+		 *
 		 */
 		/**
 		@defgroup datas Data Structures
 		This group describes 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 structures.
+		with any graph structure.
 		<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		@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.
 		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.
 		LEMON provides several special purpose maps that e.g. combine
+		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
 		values to the nodes and arcs of graphs.
 		*/
 		/**
 		\defgroup map_adaptors Map Adaptors
 		\ingroup maps
 		\brief Tools to create new maps from existing ones
 		This group describes map adaptors that are used to create "implicit"
 		maps from other maps.
 		Most of them are \ref lemon::concepts::ReadMap "read-only maps".
 		They can make arithmetic and logical operations between one or two maps
 		(negation, shifting, addition, multiplication, logical 'and', 'or',
 		'not' etc.) or e.g. convert a map to another one of different Value type.
 		The typical usage of this classes is passing implicit maps to
 		algorithms.  If a function type algorithm is called then the function
 		type map adaptors can be used comfortable. For example let's see the
-		usage of map adaptors with the \c digraphToEps() function.
+		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);
-		  digraphToEps(graph, "graph.eps")
+		  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
-		\e nodeColor() function. The \c composeMap() compose the \e degree_map
+		\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.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief Path structures implemented in LEMON.
 		This group describes the path structures implemented in LEMON.
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
 		\sa lemon::concepts::Path
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group describes some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group describes the several algorithms
 		implemented in LEMON.
 		This group describes the several algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
 		This group describes the common graph search algorithms like
-		Breadth-first search (Bfs) and Depth-first search (Dfs).
+		Breadth-First Search (BFS) and Depth-First Search (DFS).
 		*/
 		/**
-		@defgroup shortest_path Shortest Path algorithms
+		@defgroup shortest_path Shortest Path Algorithms
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
 		This group describes the algorithms for finding shortest paths in graphs.
 		*/
 		/**
-		@defgroup max_flow Maximum Flow algorithms
+		@defgroup max_flow Maximum Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding maximum flows.
 		This group describes the algorithms for finding maximum flows and
 		feasible circulations.
 		The maximum flow problem is to find a flow between a single source and
 		a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
 		directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
 		function and given \f$s, t \in V\f$ source and target node. The
 		maximum flow is the \f$f_a\f$ solution of the next optimization problem:
 		\f[ 0 \le f_a \le c_a \f]
 		\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
 		\qquad \forall u \in V \setminus \{s,t\}\f]
 		\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
 		LEMON contains several algorithms for solving maximum flow problems:
 		- \ref lemon::EdmondsKarp "Edmonds-Karp"
 		- \ref lemon::Preflow "Goldberg's Preflow algorithm"
 		- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
 		- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
 		In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
 		fastest method to compute the maximum flow. All impelementations
 		provides functions to query the minimum cut, which is the dual linear
 		programming problem of the maximum flow.
 		*/
 		/**
-		@defgroup min_cost_flow Minimum Cost Flow algorithms
+		@defgroup min_cost_flow Minimum Cost Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost flows and circulations.
 		This group describes the algorithms for finding minimum cost flows and
 		circulations.
 		*/
 		/**
-		@defgroup min_cut Minimum Cut algorithms
+		@defgroup min_cut Minimum Cut Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cut in graphs.
 		This group describes the algorithms for finding minimum cut in graphs.
 		The minimum cut problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the vertices with minimum overall capacity on
 		outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
 		\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		cut is the \f$X\f$ solution of the next optimization problem:
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
 		\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
 		LEMON contains several algorithms related to minimum cut problems:
 		- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
 		  in directed graphs
 		- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
 		  calculate minimum cut in undirected graphs
 		- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
 		  pairs minimum cut in undirected graphs
 		If you want to find minimum cut just between two distinict nodes,
 		please see the \ref max_flow "Maximum Flow page".
 		*/
 		/**
-		@defgroup graph_prop Connectivity and other graph properties
+		@defgroup graph_prop Connectivity and Other Graph Properties
 		@ingroup algs
 		\brief Algorithms for discovering the graph properties
 		This group describes the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		*/
 		/**
-		@defgroup planar Planarity embedding and drawing
+		@defgroup planar Planarity Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This group describes the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
-		@defgroup matching Matching algorithms
+		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains algorithm objects and functions to calculate
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the arcs which does not shares common endpoints.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be the finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		LEMON contains the next algorithms:
 		- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
 		  augmenting path algorithm for calculate maximum cardinality matching in
 		  bipartite graphs
 		- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
 		  algorithm for calculate maximum cardinality matching in bipartite graphs
 		- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
 		  Successive shortest path algorithm for calculate maximum weighted matching
 		  and maximum weighted bipartite matching in bipartite graph
 		- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
 		  Successive shortest path algorithm for calculate minimum cost maximum
 		  matching in bipartite graph
 		- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
 		  for calculate maximum cardinality matching in general graph
 		- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
 		  shrinking algorithm for calculate maximum weighted matching in general
 		  graph
 		- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
 		  Edmond's blossom shrinking algorithm for calculate maximum weighted
 		  perfect matching in general graph
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
-		@defgroup spantree Minimum Spanning Tree algorithms
+		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
 		\brief Algorithms for finding a minimum cost spanning tree in a graph.
 		This group describes the algorithms for finding a minimum cost spanning
 		tree in a graph
 		*/
 		/**
-		@defgroup auxalg Auxiliary algorithms
+		@defgroup auxalg Auxiliary Algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
 		This group describes some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
-		@defgroup approx Approximation algorithms
+		@defgroup approx Approximation Algorithms
 		@ingroup algs
 		\brief Approximation algorithms.
 		This group describes the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group describes some general optimization frameworks
 		implemented in LEMON.
 		This group describes some general optimization frameworks
 		implemented in LEMON.
 		*/
 		/**
-		@defgroup lp_group Lp and Mip solvers
+		@defgroup lp_group Lp and Mip Solvers
 		@ingroup gen_opt_group
 		\brief Lp and Mip solver interfaces for LEMON.
 		This group describes Lp and Mip solver interfaces for LEMON. The
 		various LP solvers could be used in the same manner with this
 		interface.
 		*/
 		/**
-		@defgroup lp_utils Tools for Lp and Mip solvers
+		@defgroup lp_utils Tools for Lp and Mip Solvers
 		@ingroup lp_group
 		\brief Helper tools to the Lp and Mip solvers.
 		This group adds some helper tools to general optimization framework
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup metah Metaheuristics
 		@ingroup gen_opt_group
 		\brief Metaheuristics for LEMON library.
 		This group describes some metaheuristic optimization tools.
 		*/
 		/**
 		@defgroup utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
 		This group describes some simple basic graph utilities.
 		*/
 		/**
 		@defgroup misc Miscellaneous Tools
 		@ingroup utils
 		\brief Tools for development, debugging and testing.
 		This group describes several useful tools for development,
 		debugging and testing.
 		*/
 		/**
-		@defgroup timecount Time measuring and Counting
+		@defgroup timecount Time Measuring and Counting
 		@ingroup misc
 		\brief Simple tools for measuring the performance of algorithms.
 		This group describes simple tools for measuring the performance
 		of algorithms.
 		*/
 		/**
 		@defgroup graphbits Tools for Graph Implementation
 		@ingroup utils
 		\brief Tools to make it easier to create graphs.
 		This group describes the tools that makes it easier to create graphs and
 		the maps that dynamically update with the graph changes.
 		*/
 		/**
 		@defgroup exceptions Exceptions
 		@ingroup utils
 		\brief Exceptions defined in LEMON.
 		This group describes the exceptions defined in LEMON.
 		*/
 		/**
 		@defgroup io_group Input-Output
 		\brief Graph Input-Output methods
 		This group describes the tools for importing and exporting graphs
 		and graph related data. Now it supports the LEMON format, the
 		\c DIMACS format and the encapsulated postscript (EPS) format.
 		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 Input-Output
 		@ingroup io_group
-		\brief Reading and writing \ref lgf-format "LEMON Graph Format".
 		\brief Reading and writing LEMON Graph Format.
 		This group describes methods for reading and writing
 		\ref lgf-format "LEMON Graph Format".
 		*/
 		/**
-		@defgroup eps_io Postscript exporting
+		@defgroup eps_io Postscript Exporting
 		@ingroup io_group
 		\brief General \c EPS drawer and graph exporter
 		This group describes general \c EPS drawing methods and special
 		graph exporting tools.
 		*/
 		/**
 		@defgroup concept Concepts
 		\brief Skeleton classes and concept checking classes
 		This group describes the data/algorithm skeletons and concept checking
 		classes implemented in LEMON.
 		The purpose of the classes in this group is fourfold.
 		- These classes contain the documentations of the concepts. In order
 		  to avoid document multiplications, an implementation of a concept
 		  simply refers to the corresponding concept class.
 		- These classes declare every functions, <tt>typedef</tt>s etc. an
 		  implementation of the concepts should provide, however completely
 		  without implementations and real data structures behind the
 		  interface. On the other hand they should provide nothing else. All
 		  the algorithms working on a data structure meeting a certain concept
 		  should compile with these classes. (Though it will not run properly,
 		  of course.) In this way it is easily to check if an algorithm
 		  doesn't use any extra feature of a certain implementation.
 		- The concept descriptor classes also provide a <em>checker class</em>
 		  that makes it possible to check whether a certain implementation of a
 		  concept indeed provides all the required features.
 		- Finally, They can serve as a skeleton of a new implementation of a concept.
 		*/
 		/**
 		@defgroup graph_concepts Graph Structure Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for graph structures
 		This group describes the skeletons and concept checking classes of LEMON's
 		graph structures and helper classes used to implement these.
 		*/
 		/* --- Unused group
 		@defgroup experimental Experimental Structures and Algorithms
 		This group describes some Experimental structures and algorithms.
 		The stuff here is subject to change.
 		/**
 		@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.
 		*/
 		/**
 		\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-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.
+		 *
 		 */
 		/**
 		\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"!
+		some \ref demoprograms "demo programs".
 		If you know what you are looking for then try to find it under the
 		<a class="el" href="modules.html">Modules</a>
 		section.
-		If you are a user of the old (0.x) series of LEMON, please check out the \ref migration "Migration Guide" for the backward incompatibilities.
 		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/bits/alteration_notifier.h

Show inline comments

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

lemon/bits/array_map.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_ARRAY_MAP_H
 		#define LEMON_BITS_ARRAY_MAP_H
 		#include <memory>
 		#include <lemon/bits/traits.h>
 		#include <lemon/bits/alteration_notifier.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		/// \ingroup graphbits
 		/// \file
-		/// \brief Graph map based on the array storage.
+		// \ingroup graphbits
 		// \file
 		// \brief Graph map based on the array storage.
 		namespace lemon {
 		  /// \ingroup graphbits
 		  ///
 		  /// \brief Graph map based on the array storage.
 		  ///
 		  /// The ArrayMap template class is graph map structure what
 		  /// automatically updates the map when a key is added to or erased from
 		  /// the map. This map uses the allocators to implement
 		  /// the container functionality.
 		  ///
 		  /// The template parameters are the Graph the current Item type and
-		  /// the Value type of the map.
+		  // \ingroup graphbits
 		  //
 		  // \brief Graph map based on the array storage.
 		  //
 		  // The ArrayMap template class is graph map structure what
 		  // automatically updates the map when a key is added to or erased from
 		  // the map. This map uses the allocators to implement
 		  // the container functionality.
 		  //
 		  // The template parameters are the Graph the current Item type and
 		  // the Value type of the map.
 		  template <typename _Graph, typename _Item, typename _Value>
 		  class ArrayMap
 		    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
 		  public:
-		    /// The graph type of the maps.
 		    // The graph type of the maps.
 		    typedef _Graph Graph;
-		    /// The item type of the map.
 		    // The item type of the map.
 		    typedef _Item Item;
-		    /// The reference map tag.
 		    // The reference map tag.
 		    typedef True ReferenceMapTag;
-		    /// The key type of the maps.
 		    // The key type of the maps.
 		    typedef _Item Key;
-		    /// The value type of the map.
 		    // The value type of the map.
 		    typedef _Value Value;
-		    /// The const reference type of the map.
 		    // The const reference type of the map.
 		    typedef const _Value& ConstReference;
-		    /// The reference type of the map.
 		    // The reference type of the map.
 		    typedef _Value& Reference;
-		    /// The notifier type.
 		    // The notifier type.
 		    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
-		    /// The MapBase of the Map which imlements the core regisitry function.
 		    // The MapBase of the Map which imlements the core regisitry function.
 		    typedef typename Notifier::ObserverBase Parent;
 		  private:
 		    typedef std::allocator<Value> Allocator;
 		  public:
 		    /// \brief Graph initialized map constructor.
 		    ///
-		    /// Graph initialized map constructor.
+		    // \brief Graph initialized map constructor.
 		    //
 		    // Graph initialized map constructor.
 		    explicit ArrayMap(const Graph& graph) {
 		      Parent::attach(graph.notifier(Item()));
 		      allocate_memory();
 		      Notifier* nf = Parent::notifier();
 		      Item it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        int id = nf->id(it);;
 		        allocator.construct(&(values[id]), Value());
+		      }
+		    }
 		    /// \brief Constructor to use default value to initialize the map.
 		    ///
-		    /// It constructs a map and initialize all of the the map.
+		    // \brief Constructor to use default value to initialize the map.
 		    //
 		    // It constructs a map and initialize all of the the map.
 		    ArrayMap(const Graph& graph, const Value& value) {
 		      Parent::attach(graph.notifier(Item()));
 		      allocate_memory();
 		      Notifier* nf = Parent::notifier();
 		      Item it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        int id = nf->id(it);;
 		        allocator.construct(&(values[id]), value);
+		      }
+		    }
 		  private:
 		    /// \brief Constructor to copy a map of the same map type.
 		    ///
-		    /// Constructor to copy a map of the same map type.
+		    // \brief Constructor to copy a map of the same map type.
 		    //
 		    // Constructor to copy a map of the same map type.
 		    ArrayMap(const ArrayMap& copy) : Parent() {
 		      if (copy.attached()) {
 		        attach(*copy.notifier());
+		      }
 		      capacity = copy.capacity;
 		      if (capacity == 0) return;
 		      values = allocator.allocate(capacity);
 		      Notifier* nf = Parent::notifier();
 		      Item it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        int id = nf->id(it);;
 		        allocator.construct(&(values[id]), copy.values[id]);
+		      }
+		    }
 		    /// \brief Assign operator.
 		    ///
 		    /// This operator assigns for each item in the map the
 		    /// value mapped to the same item in the copied map.
 		    /// The parameter map should be indiced with the same
 		    /// itemset because this assign operator does not change
-		    /// the container of the map.
+		    // \brief Assign operator.
 		    //
 		    // This operator assigns for each item in the map the
 		    // value mapped to the same item in the copied map.
 		    // The parameter map should be indiced with the same
 		    // itemset because this assign operator does not change
 		    // the container of the map.
 		    ArrayMap& operator=(const ArrayMap& cmap) {
 		      return operator=<ArrayMap>(cmap);
+		    }
 		    /// \brief Template assign operator.
 		    ///
 		    /// The given parameter should be conform to the ReadMap
 		    /// concecpt and could be indiced by the current item set of
 		    /// the NodeMap. In this case the value for each item
 		    /// is assigned by the value of the given ReadMap.
 		    // \brief Template assign operator.
 		    //
 		    // The given parameter should be conform to the ReadMap
 		    // concecpt and could be indiced by the current item set of
 		    // the NodeMap. In this case the value for each item
 		    // is assigned by the value of the given ReadMap.
 		    template <typename CMap>
 		    ArrayMap& operator=(const CMap& cmap) {
 		      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
 		      const typename Parent::Notifier* nf = Parent::notifier();
 		      Item it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        set(it, cmap[it]);
+		      }
 		      return *this;
+		    }
 		  public:
 		    /// \brief The destructor of the map.
 		    ///
-		    /// The destructor of the map.
+		    // \brief The destructor of the map.
 		    //
 		    // The destructor of the map.
 		    virtual ~ArrayMap() {
 		      if (attached()) {
 		        clear();
 		        detach();
+		      }
+		    }
 		  protected:
 		    using Parent::attach;
 		    using Parent::detach;
 		    using Parent::attached;
 		  public:
 		    /// \brief The subscript operator.
 		    ///
 		    /// The subscript operator. The map can be subscripted by the
 		    /// actual keys of the graph.
 		    // \brief The subscript operator.
 		    //
 		    // The subscript operator. The map can be subscripted by the
 		    // actual keys of the graph.
 		    Value& operator[](const Key& key) {
 		      int id = Parent::notifier()->id(key);
 		      return values[id];
+		    }
 		    /// \brief The const subscript operator.
 		    ///
 		    /// The const subscript operator. The map can be subscripted by the
 		    /// actual keys of the graph.
 		    // \brief The const subscript operator.
 		    //
 		    // The const subscript operator. The map can be subscripted by the
 		    // actual keys of the graph.
 		    const Value& operator[](const Key& key) const {
 		      int id = Parent::notifier()->id(key);
 		      return values[id];
+		    }
 		    /// \brief Setter function of the map.
 		    ///
 		    /// Setter function of the map. Equivalent with map[key] = val.
 		    /// This is a compatibility feature with the not dereferable maps.
 		    // \brief Setter function of the map.
 		    //
 		    // Setter function of the map. Equivalent with map[key] = val.
 		    // This is a compatibility feature with the not dereferable maps.
 		    void set(const Key& key, const Value& val) {
 		      (*this)[key] = val;
+		    }
 		  protected:
 		    /// \brief Adds a new key to the map.
 		    ///
 		    /// It adds a new key to the map. It called by the observer notifier
 		    /// and it overrides the add() member function of the observer base.
 		    // \brief Adds a new key to the map.
 		    //
 		    // It adds a new key to the map. It called by the observer notifier
 		    // and it overrides the add() member function of the observer base.
 		    virtual void add(const Key& key) {
 		      Notifier* nf = Parent::notifier();
 		      int id = nf->id(key);
 		      if (id >= capacity) {
 		        int new_capacity = (capacity == 0 ? 1 : capacity);
 		        while (new_capacity <= id) {
 		          new_capacity <<= 1;
+		        }
 		        Value* new_values = allocator.allocate(new_capacity);
 		        Item it;
 		        for (nf->first(it); it != INVALID; nf->next(it)) {
 		          int jd = nf->id(it);;
 		          if (id != jd) {
 		            allocator.construct(&(new_values[jd]), values[jd]);
 		            allocator.destroy(&(values[jd]));
+		          }
+		        }
 		        if (capacity != 0) allocator.deallocate(values, capacity);
 		        values = new_values;
 		        capacity = new_capacity;
+		      }
 		      allocator.construct(&(values[id]), Value());
+		    }
 		    /// \brief Adds more new keys to the map.
 		    ///
 		    /// It adds more new keys to the map. It called by the observer notifier
 		    /// and it overrides the add() member function of the observer base.
 		    // \brief Adds more new keys to the map.
 		    //
 		    // It adds more new keys to the map. It called by the observer notifier
 		    // and it overrides the add() member function of the observer base.
 		    virtual void add(const std::vector<Key>& keys) {
 		      Notifier* nf = Parent::notifier();
 		      int max_id = -1;
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        int id = nf->id(keys[i]);
 		        if (id > max_id) {
 		          max_id = id;
+		        }
+		      }
 		      if (max_id >= capacity) {
 		        int new_capacity = (capacity == 0 ? 1 : capacity);
 		        while (new_capacity <= max_id) {
 		          new_capacity <<= 1;
+		        }
 		        Value* new_values = allocator.allocate(new_capacity);
 		        Item it;
 		        for (nf->first(it); it != INVALID; nf->next(it)) {
 		          int id = nf->id(it);
 		          bool found = false;
 		          for (int i = 0; i < int(keys.size()); ++i) {
 		            int jd = nf->id(keys[i]);
 		            if (id == jd) {
 		              found = true;
 		              break;
+		            }
+		          }
 		          if (found) continue;
 		          allocator.construct(&(new_values[id]), values[id]);
 		          allocator.destroy(&(values[id]));
+		        }
 		        if (capacity != 0) allocator.deallocate(values, capacity);
 		        values = new_values;
 		        capacity = new_capacity;
+		      }
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        int id = nf->id(keys[i]);
 		        allocator.construct(&(values[id]), Value());
+		      }
+		    }
 		    /// \brief Erase a key from the map.
 		    ///
 		    /// Erase a key from the map. It called by the observer notifier
 		    /// and it overrides the erase() member function of the observer base.
 		    // \brief Erase a key from the map.
 		    //
 		    // Erase a key from the map. It called by the observer notifier
 		    // and it overrides the erase() member function of the observer base.
 		    virtual void erase(const Key& key) {
 		      int id = Parent::notifier()->id(key);
 		      allocator.destroy(&(values[id]));
+		    }
 		    /// \brief Erase more keys from the map.
 		    ///
 		    /// Erase more keys from the map. It called by the observer notifier
 		    /// and it overrides the erase() member function of the observer base.
 		    // \brief Erase more keys from the map.
 		    //
 		    // Erase more keys from the map. It called by the observer notifier
 		    // and it overrides the erase() member function of the observer base.
 		    virtual void erase(const std::vector<Key>& keys) {
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        int id = Parent::notifier()->id(keys[i]);
 		        allocator.destroy(&(values[id]));
+		      }
+		    }
 		    /// \brief Buildes the map.
 		    ///
 		    /// It buildes the map. It called by the observer notifier
 		    /// and it overrides the build() member function of the observer base.
 		    // \brief Buildes the map.
 		    //
 		    // It buildes the map. It called by the observer notifier
 		    // and it overrides the build() member function of the observer base.
 		    virtual void build() {
 		      Notifier* nf = Parent::notifier();
 		      allocate_memory();
 		      Item it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        int id = nf->id(it);;
 		        allocator.construct(&(values[id]), Value());
+		      }
+		    }
 		    /// \brief Clear the map.
 		    ///
 		    /// It erase all items from the map. It called by the observer notifier
 		    /// and it overrides the clear() member function of the observer base.
 		    // \brief Clear the map.
 		    //
 		    // It erase all items from the map. It called by the observer notifier
 		    // and it overrides the clear() member function of the observer base.
 		    virtual void clear() {
 		      Notifier* nf = Parent::notifier();
 		      if (capacity != 0) {
 		        Item it;
 		        for (nf->first(it); it != INVALID; nf->next(it)) {
 		          int id = nf->id(it);
 		          allocator.destroy(&(values[id]));
+		        }
 		        allocator.deallocate(values, capacity);
 		        capacity = 0;
+		      }
+		    }
 		  private:
 		    void allocate_memory() {
 		      int max_id = Parent::notifier()->maxId();
 		      if (max_id == -1) {
 		        capacity = 0;
 		        values = 0;
 		        return;
+		      }
 		      capacity = 1;
 		      while (capacity <= max_id) {
 		        capacity <<= 1;
+		      }
 		      values = allocator.allocate(capacity);
+		    }
 		    int capacity;
 		    Value* values;
 		    Allocator allocator;
 		  };
+		}
 		#endif

lemon/bits/base_extender.h

Show inline comments

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-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_BASE_EXTENDER_H
#define LEMON_BITS_BASE_EXTENDER_H

#include <lemon/core.h>
#include <lemon/error.h>

#include <lemon/bits/map_extender.h>
#include <lemon/bits/default_map.h>

#include <lemon/concept_check.h>
#include <lemon/concepts/maps.h>

///\ingroup digraphbits
///\file
///\brief Extenders for the digraph types
//\ingroup digraphbits
//\file
//\brief Extenders for the digraph types
namespace lemon {

  /// \ingroup digraphbits
  ///
  /// \brief BaseDigraph to BaseGraph extender
  // \ingroup digraphbits
  //
  // \brief BaseDigraph to BaseGraph extender
  template <typename Base>
  class UndirDigraphExtender : public Base {

  public:

    typedef Base Parent;
    typedef typename Parent::Arc Edge;
    typedef typename Parent::Node Node;

    typedef True UndirectedTag;

    class Arc : public Edge {
      friend class UndirDigraphExtender;

    protected:
      bool forward;

      Arc(const Edge &ue, bool _forward) :
        Edge(ue), forward(_forward) {}

    public:
      Arc() {}

      // Invalid arc constructor
      Arc(Invalid i) : Edge(i), forward(true) {}

      bool operator==(const Arc &that) const {
        return forward==that.forward && Edge(*this)==Edge(that);
      }
      bool operator!=(const Arc &that) const {
        return forward!=that.forward || Edge(*this)!=Edge(that);
      }
      bool operator<(const Arc &that) const {
        return forward<that.forward ||
          (!(that.forward<forward) && Edge(*this)<Edge(that));
      }
    };

    /// First node of the edge
    // First node of the edge
    Node u(const Edge &e) const {
      return Parent::source(e);
    }

    /// Source of the given arc
    // Source of the given arc
    Node source(const Arc &e) const {
      return e.forward ? Parent::source(e) : Parent::target(e);
    }

    /// Second node of the edge
    // Second node of the edge
    Node v(const Edge &e) const {
      return Parent::target(e);
    }

    /// Target of the given arc
    // Target of the given arc
    Node target(const Arc &e) const {
      return e.forward ? Parent::target(e) : Parent::source(e);
    }

    /// \brief Directed arc from an edge.
    ///
    /// Returns a directed arc corresponding to the specified edge.
    /// If the given bool is true, the first node of the given edge and
    /// the source node of the returned arc are the same.
    // \brief Directed arc from an edge.
    //
    // Returns a directed arc corresponding to the specified edge.
    // If the given bool is true, the first node of the given edge and
    // the source node of the returned arc are the same.
    static Arc direct(const Edge &e, bool d) {
      return Arc(e, d);
    }

    /// Returns whether the given directed arc has the same orientation
    /// as the corresponding edge.
    // Returns whether the given directed arc has the same orientation
    // as the corresponding edge.
    static bool direction(const Arc &a) { return a.forward; }

    using Parent::first;
    using Parent::next;

    void first(Arc &e) const {
      Parent::first(e);
      e.forward=true;
    }

    void next(Arc &e) const {
      if( e.forward ) {
        e.forward = false;
      }
      else {
        Parent::next(e);
        e.forward = true;
      }
    }

    void firstOut(Arc &e, const Node &n) const {
      Parent::firstIn(e,n);
      if( Edge(e) != INVALID ) {
        e.forward = false;
      }
      else {
        Parent::firstOut(e,n);
        e.forward = true;
      }
    }
    void nextOut(Arc &e) const {
      if( ! e.forward ) {
        Node n = Parent::target(e);
        Parent::nextIn(e);
        if( Edge(e) == INVALID ) {
          Parent::firstOut(e, n);
          e.forward = true;
        }
      }
      else {
        Parent::nextOut(e);
      }
    }

    void firstIn(Arc &e, const Node &n) const {
      Parent::firstOut(e,n);
      if( Edge(e) != INVALID ) {
        e.forward = false;
      }
      else {
        Parent::firstIn(e,n);
        e.forward = true;
      }
    }
    void nextIn(Arc &e) const {
      if( ! e.forward ) {
        Node n = Parent::source(e);
        Parent::nextOut(e);
        if( Edge(e) == INVALID ) {
          Parent::firstIn(e, n);
          e.forward = true;
        }
      }
      else {
        Parent::nextIn(e);
      }
    }

    void firstInc(Edge &e, bool &d, const Node &n) const {
      d = true;
      Parent::firstOut(e, n);
      if (e != INVALID) return;
      d = false;
      Parent::firstIn(e, n);
    }

    void nextInc(Edge &e, bool &d) const {
      if (d) {
        Node s = Parent::source(e);
        Parent::nextOut(e);
        if (e != INVALID) return;
        d = false;
        Parent::firstIn(e, s);
      } else {
        Parent::nextIn(e);
      }
    }

    Node nodeFromId(int ix) const {
      return Parent::nodeFromId(ix);
    }

    Arc arcFromId(int ix) const {
      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
    }

    Edge edgeFromId(int ix) const {
      return Parent::arcFromId(ix);
    }

    int id(const Node &n) const {
      return Parent::id(n);
    }

    int id(const Edge &e) const {
      return Parent::id(e);
    }

    int id(const Arc &e) const {
      return 2 * Parent::id(e) + int(e.forward);
    }

    int maxNodeId() const {
      return Parent::maxNodeId();
    }

    int maxArcId() const {
      return 2 * Parent::maxArcId() + 1;
    }

    int maxEdgeId() const {
      return Parent::maxArcId();
    }

    int arcNum() const {
      return 2 * Parent::arcNum();
    }

    int edgeNum() const {
      return Parent::arcNum();
    }

    Arc findArc(Node s, Node t, Arc p = INVALID) const {
      if (p == INVALID) {
        Edge arc = Parent::findArc(s, t);
        if (arc != INVALID) return direct(arc, true);
        arc = Parent::findArc(t, s);
        if (arc != INVALID) return direct(arc, false);
      } else if (direction(p)) {
        Edge arc = Parent::findArc(s, t, p);
        if (arc != INVALID) return direct(arc, true);
        arc = Parent::findArc(t, s);
        if (arc != INVALID) return direct(arc, false);
      } else {
        Edge arc = Parent::findArc(t, s, p);
        if (arc != INVALID) return direct(arc, false);
      }
      return INVALID;
    }

    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
      if (s != t) {
        if (p == INVALID) {
          Edge arc = Parent::findArc(s, t);
          if (arc != INVALID) return arc;
          arc = Parent::findArc(t, s);
          if (arc != INVALID) return arc;
        } else if (Parent::s(p) == s) {
          Edge arc = Parent::findArc(s, t, p);
          if (arc != INVALID) return arc;
          arc = Parent::findArc(t, s);
          if (arc != INVALID) return arc;
        } else {
          Edge arc = Parent::findArc(t, s, p);
          if (arc != INVALID) return arc;
        }
      } else {
        return Parent::findArc(s, t, p);
      }
      return INVALID;
    }
  };

  template <typename Base>
  class BidirBpGraphExtender : public Base {
  public:
    typedef Base Parent;
    typedef BidirBpGraphExtender Digraph;

    typedef typename Parent::Node Node;
    typedef typename Parent::Edge Edge;


    using Parent::first;
    using Parent::next;

    using Parent::id;

    class Red : public Node {
      friend class BidirBpGraphExtender;
    public:
      Red() {}
      Red(const Node& node) : Node(node) {
        LEMON_DEBUG(Parent::red(node) || node == INVALID,
                    typename Parent::NodeSetError());
      }
      Red& operator=(const Node& node) {
        LEMON_DEBUG(Parent::red(node) || node == INVALID,
                    typename Parent::NodeSetError());
        Node::operator=(node);
        return *this;
      }
      Red(Invalid) : Node(INVALID) {}
      Red& operator=(Invalid) {
        Node::operator=(INVALID);
        return *this;
      }
    };

    void first(Red& node) const {
      Parent::firstRed(static_cast<Node&>(node));
    }
    void next(Red& node) const {
      Parent::nextRed(static_cast<Node&>(node));
    }

    int id(const Red& node) const {
      return Parent::redId(node);
    }

    class Blue : public Node {
      friend class BidirBpGraphExtender;
    public:
      Blue() {}
      Blue(const Node& node) : Node(node) {
        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
                    typename Parent::NodeSetError());
      }
      Blue& operator=(const Node& node) {
        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
                    typename Parent::NodeSetError());
        Node::operator=(node);
        return *this;
      }
      Blue(Invalid) : Node(INVALID) {}
      Blue& operator=(Invalid) {
        Node::operator=(INVALID);
        return *this;
      }
    };

    void first(Blue& node) const {
      Parent::firstBlue(static_cast<Node&>(node));
    }
    void next(Blue& node) const {
      Parent::nextBlue(static_cast<Node&>(node));
    }

    int id(const Blue& node) const {
      return Parent::redId(node);
    }

    Node source(const Edge& arc) const {
      return red(arc);
    }
    Node target(const Edge& arc) const {
      return blue(arc);
    }

    void firstInc(Edge& arc, bool& dir, const Node& node) const {
      if (Parent::red(node)) {
        Parent::firstFromRed(arc, node);
        dir = true;
      } else {
        Parent::firstFromBlue(arc, node);
        dir = static_cast<Edge&>(arc) == INVALID;
      }
    }
    void nextInc(Edge& arc, bool& dir) const {
      if (dir) {
        Parent::nextFromRed(arc);
      } else {
        Parent::nextFromBlue(arc);
        if (arc == INVALID) dir = true;
      }
    }

    class Arc : public Edge {
      friend class BidirBpGraphExtender;
    protected:
      bool forward;

      Arc(const Edge& arc, bool _forward)
        : Edge(arc), forward(_forward) {}

    public:
      Arc() {}
      Arc (Invalid) : Edge(INVALID), forward(true) {}
      bool operator==(const Arc& i) const {
        return Edge::operator==(i) && forward == i.forward;
      }
      bool operator!=(const Arc& i) const {
        return Edge::operator!=(i) || forward != i.forward;
      }
      bool operator<(const Arc& i) const {
        return Edge::operator<(i) ||
          (!(i.forward<forward) && Edge(*this)<Edge(i));
      }
    };

    void first(Arc& arc) const {
      Parent::first(static_cast<Edge&>(arc));
      arc.forward = true;
    }

    void next(Arc& arc) const {
      if (!arc.forward) {
        Parent::next(static_cast<Edge&>(arc));
      }
      arc.forward = !arc.forward;
    }

    void firstOut(Arc& arc, const Node& node) const {
      if (Parent::red(node)) {
        Parent::firstFromRed(arc, node);
        arc.forward = true;
      } else {
        Parent::firstFromBlue(arc, node);
        arc.forward = static_cast<Edge&>(arc) == INVALID;
      }
    }
    void nextOut(Arc& arc) const {
      if (arc.forward) {
        Parent::nextFromRed(arc);
      } else {
        Parent::nextFromBlue(arc);
        arc.forward = static_cast<Edge&>(arc) == INVALID;
      }
    }

    void firstIn(Arc& arc, const Node& node) const {
      if (Parent::blue(node)) {
        Parent::firstFromBlue(arc, node);
        arc.forward = true;
      } else {
        Parent::firstFromRed(arc, node);
        arc.forward = static_cast<Edge&>(arc) == INVALID;
      }
    }
    void nextIn(Arc& arc) const {
      if (arc.forward) {
        Parent::nextFromBlue(arc);
      } else {
        Parent::nextFromRed(arc);
        arc.forward = static_cast<Edge&>(arc) == INVALID;
      }
    }

    Node source(const Arc& arc) const {
      return arc.forward ? Parent::red(arc) : Parent::blue(arc);
    }
    Node target(const Arc& arc) const {
      return arc.forward ? Parent::blue(arc) : Parent::red(arc);
    }

    int id(const Arc& arc) const {
      return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
        (arc.forward ? 0 : 1);
    }
    Arc arcFromId(int ix) const {
      return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
    }
    int maxArcId() const {
      return (Parent::maxEdgeId() << 1) + 1;
    }

    bool direction(const Arc& arc) const {
      return arc.forward;
    }

    Arc direct(const Edge& arc, bool dir) const {
      return Arc(arc, dir);
    }

    int arcNum() const {
      return 2 * Parent::edgeNum();
    }

    int edgeNum() const {
      return Parent::edgeNum();
    }


  };
}

#endif

lemon/bits/bezier.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BEZIER_H
 		#define LEMON_BEZIER_H
 		///\ingroup misc
 		///\file
 		///\brief Classes to compute with Bezier curves.
 		///
-		///Up to now this file is used internally by \ref graph_to_eps.h
+		//\ingroup misc
 		//\file
 		//\brief Classes to compute with Bezier curves.
 		//
 		//Up to now this file is used internally by \ref graph_to_eps.h
 		#include<lemon/dim2.h>
 		namespace lemon {
 		  namespace dim2 {
 		class BezierBase {
 		public:
 		  typedef lemon::dim2::Point<double> Point;
 		protected:
 		  static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;}
 		};
 		class Bezier1 : public BezierBase
+		{
 		public:
 		  Point p1,p2;
 		  Bezier1() {}
 		  Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {}
 		  Point operator()(double t) const
+		  {
 		    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
 		    return conv(p1,p2,t);
+		  }
 		  Bezier1 before(double t) const
+		  {
 		    return Bezier1(p1,conv(p1,p2,t));
+		  }
 		  Bezier1 after(double t) const
+		  {
 		    return Bezier1(conv(p1,p2,t),p2);
+		  }
 		  Bezier1 revert() const { return Bezier1(p2,p1);}
 		  Bezier1 operator()(double a,double b) const { return before(b).after(a/b); }
 		  Point grad() const { return p2-p1; }
 		  Point norm() const { return rot90(p2-p1); }
 		  Point grad(double) const { return grad(); }
 		  Point norm(double t) const { return rot90(grad(t)); }
 		};
 		class Bezier2 : public BezierBase
+		{
 		public:
 		  Point p1,p2,p3;
 		  Bezier2() {}
 		  Bezier2(Point _p1, Point _p2, Point _p3) :p1(_p1), p2(_p2), p3(_p3) {}
 		  Bezier2(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,.5)), p3(b.p2) {}
 		  Point operator()(double t) const
+		  {
 		    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
 		    return ((1-t)*(1-t))*p1+(2*(1-t)*t)*p2+(t*t)*p3;
+		  }
 		  Bezier2 before(double t) const
+		  {
 		    Point q(conv(p1,p2,t));
 		    Point r(conv(p2,p3,t));
 		    return Bezier2(p1,q,conv(q,r,t));
+		  }
 		  Bezier2 after(double t) const
+		  {
 		    Point q(conv(p1,p2,t));
 		    Point r(conv(p2,p3,t));
 		    return Bezier2(conv(q,r,t),r,p3);
+		  }
 		  Bezier2 revert() const { return Bezier2(p3,p2,p1);}
 		  Bezier2 operator()(double a,double b) const { return before(b).after(a/b); }
 		  Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); }
 		  Bezier1 norm() const { return Bezier1(2.0*rot90(p2-p1),2.0*rot90(p3-p2)); }
 		  Point grad(double t) const { return grad()(t); }
 		  Point norm(double t) const { return rot90(grad(t)); }
 		};
 		class Bezier3 : public BezierBase
+		{
 		public:
 		  Point p1,p2,p3,p4;
 		  Bezier3() {}
 		  Bezier3(Point _p1, Point _p2, Point _p3, Point _p4)
 		    : p1(_p1), p2(_p2), p3(_p3), p4(_p4) {}
 		  Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)),
 		                              p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {}
 		  Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)),
 		                              p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {}
 		  Point operator()(double t) const
+		    {
 		      //    return Bezier2(conv(p1,p2,t),conv(p2,p3,t),conv(p3,p4,t))(t);
 		      return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+
 		        (3*t*t*(1-t))*p3+(t*t*t)*p4;
+		    }
 		  Bezier3 before(double t) const
+		    {
 		      Point p(conv(p1,p2,t));
 		      Point q(conv(p2,p3,t));
 		      Point r(conv(p3,p4,t));
 		      Point a(conv(p,q,t));
 		      Point b(conv(q,r,t));
 		      Point c(conv(a,b,t));
 		      return Bezier3(p1,p,a,c);
+		    }
 		  Bezier3 after(double t) const
+		    {
 		      Point p(conv(p1,p2,t));
 		      Point q(conv(p2,p3,t));
 		      Point r(conv(p3,p4,t));
 		      Point a(conv(p,q,t));
 		      Point b(conv(q,r,t));
 		      Point c(conv(a,b,t));
 		      return Bezier3(c,b,r,p4);
+		    }
 		  Bezier3 revert() const { return Bezier3(p4,p3,p2,p1);}
 		  Bezier3 operator()(double a,double b) const { return before(b).after(a/b); }
 		  Bezier2 grad() const { return Bezier2(3.0*(p2-p1),3.0*(p3-p2),3.0*(p4-p3)); }
 		  Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1),
 .0*rot90(p3-p2),
 .0*rot90(p4-p3)); }
 		  Point grad(double t) const { return grad()(t); }
 		  Point norm(double t) const { return rot90(grad(t)); }
 		  template<class R,class F,class S,class D>
 		  R recSplit(F &_f,const S &_s,D _d) const
+		  {
 		    const Point a=(p1+p2)/2;
 		    const Point b=(p2+p3)/2;
 		    const Point c=(p3+p4)/2;
 		    const Point d=(a+b)/2;
 		    const Point e=(b+c)/2;
 		    const Point f=(d+e)/2;
 		    R f1=_f(Bezier3(p1,a,d,e),_d);
 		    R f2=_f(Bezier3(e,d,c,p4),_d);
 		    return _s(f1,f2);
+		  }
 		};
 		} //END OF NAMESPACE dim2
 		} //END OF NAMESPACE lemon
 		#endif // LEMON_BEZIER_H

lemon/bits/default_map.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_DEFAULT_MAP_H
 		#define LEMON_BITS_DEFAULT_MAP_H
 		#include <lemon/bits/array_map.h>
 		#include <lemon/bits/vector_map.h>
 		//#include <lemon/bits/debug_map.h>
 		///\ingroup graphbits
 		///\file
-		///\brief Graph maps that construct and destruct their elements dynamically.
+		//\ingroup graphbits
 		//\file
 		//\brief Graph maps that construct and destruct their elements dynamically.
 		namespace lemon {
 		  //#ifndef LEMON_USE_DEBUG_MAP
 		  template <typename _Graph, typename _Item, typename _Value>
 		  struct DefaultMapSelector {
 		    typedef ArrayMap<_Graph, _Item, _Value> Map;
 		  };
 		  // bool
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, bool> {
 		    typedef VectorMap<_Graph, _Item, bool> Map;
 		  };
 		  // char
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, char> {
 		    typedef VectorMap<_Graph, _Item, char> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, signed char> {
 		    typedef VectorMap<_Graph, _Item, signed char> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, unsigned char> {
 		    typedef VectorMap<_Graph, _Item, unsigned char> Map;
 		  };
 		  // int
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, signed int> {
 		    typedef VectorMap<_Graph, _Item, signed int> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, unsigned int> {
 		    typedef VectorMap<_Graph, _Item, unsigned int> Map;
 		  };
 		  // short
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, signed short> {
 		    typedef VectorMap<_Graph, _Item, signed short> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, unsigned short> {
 		    typedef VectorMap<_Graph, _Item, unsigned short> Map;
 		  };
 		  // long
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, signed long> {
 		    typedef VectorMap<_Graph, _Item, signed long> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, unsigned long> {
 		    typedef VectorMap<_Graph, _Item, unsigned long> Map;
 		  };
 		#if defined __GNUC__ && !defined __STRICT_ANSI__
 		  // long long
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, signed long long> {
 		    typedef VectorMap<_Graph, _Item, signed long long> Map;
 		  };
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, unsigned long long> {
 		    typedef VectorMap<_Graph, _Item, unsigned long long> Map;
 		  };
 		#endif
 		  // float
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, float> {
 		    typedef VectorMap<_Graph, _Item, float> Map;
 		  };
 		  // double
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, double> {
 		    typedef VectorMap<_Graph, _Item,  double> Map;
 		  };
 		  // long double
 		  template <typename _Graph, typename _Item>
 		  struct DefaultMapSelector<_Graph, _Item, long double> {
 		    typedef VectorMap<_Graph, _Item, long double> Map;
 		  };
 		  // pointer
 		  template <typename _Graph, typename _Item, typename _Ptr>
 		  struct DefaultMapSelector<_Graph, _Item, _Ptr*> {
 		    typedef VectorMap<_Graph, _Item, _Ptr*> Map;
 		  };
 		// #else
 		//   template <typename _Graph, typename _Item, typename _Value>
 		//   struct DefaultMapSelector {
 		//     typedef DebugMap<_Graph, _Item, _Value> Map;
 		//   };
 		// #endif
-		  /// DefaultMap class
 		  // DefaultMap class
 		  template <typename _Graph, typename _Item, typename _Value>
 		  class DefaultMap
 		    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
 		  public:
 		    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
 		    typedef DefaultMap<_Graph, _Item, _Value> Map;
 		    typedef typename Parent::Graph Graph;
 		    typedef typename Parent::Value Value;
 		    explicit DefaultMap(const Graph& graph) : Parent(graph) {}
 		    DefaultMap(const Graph& graph, const Value& value)
 		      : Parent(graph, value) {}
 		    DefaultMap& operator=(const DefaultMap& cmap) {
 		      return operator=<DefaultMap>(cmap);
+		    }
 		    template <typename CMap>
 		    DefaultMap& operator=(const CMap& cmap) {
 		      Parent::operator=(cmap);
 		      return *this;
+		    }
 		  };
+		}
 		#endif

lemon/bits/enable_if.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		// This file contains a modified version of the enable_if library from BOOST.
 		// See the appropriate copyright notice below.
 		// Boost enable_if library
 		// Copyright 2003 (c) The Trustees of Indiana University.
 		// Use, modification, and distribution is subject to the Boost Software
 		// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
 		// http://www.boost.org/LICENSE_1_0.txt)
 		//    Authors: Jaakko Jarvi (jajarvi at osl.iu.edu)
 		//             Jeremiah Willcock (jewillco at osl.iu.edu)
 		//             Andrew Lumsdaine (lums at osl.iu.edu)
 		#ifndef LEMON_BITS_ENABLE_IF_H
 		#define LEMON_BITS_ENABLE_IF_H
 		///\file
 		///\brief Miscellaneous basic utilities
 		//\file
 		//\brief Miscellaneous basic utilities
 		namespace lemon
+		{
-		  /// Basic type for defining "tags". A "YES" condition for \c enable_if.
 		  // Basic type for defining "tags". A "YES" condition for \c enable_if.
 		  /// Basic type for defining "tags". A "YES" condition for \c enable_if.
 		  ///
-		  ///\sa False
+		  // Basic type for defining "tags". A "YES" condition for \c enable_if.
 		  //
 		  //\sa False
 		  struct True {
-		    ///\e
 		    //\e
 		    static const bool value = true;
 		  };
-		  /// Basic type for defining "tags". A "NO" condition for \c enable_if.
 		  // Basic type for defining "tags". A "NO" condition for \c enable_if.
 		  /// Basic type for defining "tags". A "NO" condition for \c enable_if.
 		  ///
-		  ///\sa True
+		  // Basic type for defining "tags". A "NO" condition for \c enable_if.
 		  //
 		  //\sa True
 		  struct False {
-		    ///\e
 		    //\e
 		    static const bool value = false;
 		  };
 		  template <typename T>
 		  struct Wrap {
 		    const T &value;
 		    Wrap(const T &t) : value(t) {}
 		  };
 		  /**************** dummy class to avoid ambiguity ****************/
 		  template<int T> struct dummy { dummy(int) {} };
 		  /**************** enable_if from BOOST ****************/
 		  template <typename Type, typename T = void>
 		  struct exists {
 		    typedef T type;
 		  };
 		  template <bool B, class T = void>
 		  struct enable_if_c {
 		    typedef T type;
 		  };
 		  template <class T>
 		  struct enable_if_c<false, T> {};
 		  template <class Cond, class T = void>
 		  struct enable_if : public enable_if_c<Cond::value, T> {};
 		  template <bool B, class T>
 		  struct lazy_enable_if_c {
 		    typedef typename T::type type;
 		  };
 		  template <class T>
 		  struct lazy_enable_if_c<false, T> {};
 		  template <class Cond, class T>
 		  struct lazy_enable_if : public lazy_enable_if_c<Cond::value, T> {};
 		  template <bool B, class T = void>
 		  struct disable_if_c {
 		    typedef T type;
 		  };
 		  template <class T>
 		  struct disable_if_c<true, T> {};
 		  template <class Cond, class T = void>
 		  struct disable_if : public disable_if_c<Cond::value, T> {};
 		  template <bool B, class T>
 		  struct lazy_disable_if_c {
 		    typedef typename T::type type;
 		  };
 		  template <class T>
 		  struct lazy_disable_if_c<true, T> {};
 		  template <class Cond, class T>
 		  struct lazy_disable_if : public lazy_disable_if_c<Cond::value, T> {};
 		} // namespace lemon
 		#endif

lemon/bits/graph_extender.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-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_GRAPH_EXTENDER_H
 		#define LEMON_BITS_GRAPH_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/bits/map_extender.h>
 		#include <lemon/bits/default_map.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		///\ingroup graphbits
 		///\file
-		///\brief Extenders for the digraph types
+		//\ingroup graphbits
 		//\file
 		//\brief Extenders for the digraph types
 		namespace lemon {
 		  /// \ingroup graphbits
 		  ///
-		  /// \brief Extender for the Digraphs
+		  // \ingroup graphbits
 		  //
 		  // \brief Extender for the Digraphs
 		  template <typename Base>
 		  class DigraphExtender : public Base {
 		  public:
 		    typedef Base Parent;
 		    typedef DigraphExtender 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 &node, const Arc &arc) const {
 		      if (node == Parent::source(arc))
 		        return Parent::target(arc);
 		      else if(node == Parent::target(arc))
 		        return Parent::source(arc);
 		      else
 		        return INVALID;
+		    }
 		    // Alterable extension
 		    typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
 		    typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
 		  protected:
 		    mutable NodeNotifier node_notifier;
 		    mutable ArcNotifier arc_notifier;
 		  public:
 		    NodeNotifier& notifier(Node) const {
 		      return node_notifier;
+		    }
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    class NodeIt : public Node {
 		      const Digraph* _digraph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
 		        _digraph->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Digraph& digraph, const Node& node)
 		        : Node(node), _digraph(&digraph) {}
 		      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& digraph) : _digraph(&digraph) {
 		        _digraph->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Digraph& digraph, const Arc& arc) :
 		        Arc(arc), _digraph(&digraph) { }
 		      ArcIt& operator++() {
 		        _digraph->next(*this);
 		        return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Digraph* _digraph;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Digraph& digraph, const Node& node)
 		        : _digraph(&digraph) {
 		        _digraph->firstOut(*this, node);
+		      }
 		      OutArcIt(const Digraph& digraph, const Arc& arc)
 		        : Arc(arc), _digraph(&digraph) {}
 		      OutArcIt& operator++() {
 		        _digraph->nextOut(*this);
 		        return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Digraph* _digraph;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Digraph& digraph, const Node& node)
 		        : _digraph(&digraph) {
 		        _digraph->firstIn(*this, node);
+		      }
 		      InArcIt(const Digraph& digraph, const Arc& arc) :
 		        Arc(arc), _digraph(&digraph) {}
 		      InArcIt& operator++() {
 		        _digraph->nextIn(*this);
 		        return *this;
+		      }
 		    };
 		    /// \brief Base node of the iterator
 		    ///
-		    /// Returns the base node (i.e. the source in this case) of the iterator
+		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (i.e. the source in this case) of the iterator
 		    Node baseNode(const OutArcIt &arc) const {
 		      return Parent::source(arc);
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (i.e. the target in this case) of the
 		    /// iterator
 		    // \brief Running node of the iterator
 		    //
 		    // Returns the running node (i.e. the target in this case) of the
 		    // iterator
 		    Node runningNode(const OutArcIt &arc) const {
 		      return Parent::target(arc);
+		    }
 		    /// \brief Base node of the iterator
 		    ///
-		    /// Returns the base node (i.e. the target in this case) of the iterator
+		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (i.e. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &arc) const {
 		      return Parent::target(arc);
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (i.e. the source in this case) of the
 		    /// iterator
 		    // \brief Running node of the iterator
 		    //
 		    // Returns the running node (i.e. the source in this case) of the
 		    // iterator
 		    Node runningNode(const InArcIt &arc) const {
 		      return Parent::source(arc);
+		    }
 		    template <typename _Value>
 		    class NodeMap
 		      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
 		    public:
 		      typedef DigraphExtender Digraph;
 		      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
 		      explicit NodeMap(const Digraph& digraph)
 		        : Parent(digraph) {}
 		      NodeMap(const Digraph& digraph, const _Value& value)
 		        : Parent(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 _Value>
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
 		    public:
 		      typedef DigraphExtender Digraph;
 		      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
 		      explicit ArcMap(const Digraph& digraph)
 		        : Parent(digraph) {}
 		      ArcMap(const Digraph& digraph, const _Value& value)
 		        : Parent(digraph, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    Node addNode() {
 		      Node node = Parent::addNode();
 		      notifier(Node()).add(node);
 		      return node;
+		    }
 		    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();
 		      notifier(Node()).clear();
 		      Parent::clear();
+		    }
 		    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
 		    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
 		      Parent::build(digraph, nodeRef, arcRef);
 		      notifier(Node()).build();
 		      notifier(Arc()).build();
+		    }
 		    void erase(const Node& node) {
 		      Arc arc;
 		      Parent::firstOut(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstOut(arc, node);
+		      }
 		      Parent::firstIn(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstIn(arc, node);
+		      }
 		      notifier(Node()).erase(node);
 		      Parent::erase(node);
+		    }
 		    void erase(const Arc& arc) {
 		      notifier(Arc()).erase(arc);
 		      Parent::erase(arc);
+		    }
 		    DigraphExtender() {
 		      node_notifier.setContainer(*this);
 		      arc_notifier.setContainer(*this);
+		    }
 		    ~DigraphExtender() {
 		      arc_notifier.clear();
 		      node_notifier.clear();
+		    }
 		  };
 		  /// \ingroup _graphbits
 		  ///
-		  /// \brief Extender for the Graphs
+		  // \ingroup _graphbits
 		  //
 		  // \brief Extender for the Graphs
 		  template <typename Base>
 		  class GraphExtender : public Base {
 		  public:
 		    typedef Base Parent;
 		    typedef GraphExtender Graph;
 		    typedef True UndirectedTag;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    // Graph extension
 		    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 &arc) const {
 		      return Parent::direct(arc, !Parent::direction(arc));
+		    }
 		    using Parent::direct;
 		    Arc direct(const Edge &edge, const Node &node) const {
 		      return Parent::direct(edge, Parent::u(edge) == node);
+		    }
 		    // Alterable extension
 		    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
 		    typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
 		    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
 		  protected:
 		    mutable NodeNotifier node_notifier;
 		    mutable ArcNotifier arc_notifier;
 		    mutable EdgeNotifier edge_notifier;
 		  public:
 		    NodeNotifier& notifier(Node) const {
 		      return node_notifier;
+		    }
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    EdgeNotifier& notifier(Edge) const {
 		      return edge_notifier;
+		    }
 		    class NodeIt : public Node {
 		      const Graph* _graph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Graph& graph) : _graph(&graph) {
 		        _graph->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Graph& graph, const Node& node)
 		        : Node(node), _graph(&graph) {}
 		      NodeIt& operator++() {
 		        _graph->next(*this);
 		        return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Graph* _graph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Graph& graph) : _graph(&graph) {
 		        _graph->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Graph& graph, const Arc& arc) :
 		        Arc(arc), _graph(&graph) { }
 		      ArcIt& operator++() {
 		        _graph->next(*this);
 		        return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Graph* _graph;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Graph& graph, const Node& node)
 		        : _graph(&graph) {
 		        _graph->firstOut(*this, node);
+		      }
 		      OutArcIt(const Graph& graph, const Arc& arc)
 		        : Arc(arc), _graph(&graph) {}
 		      OutArcIt& operator++() {
 		        _graph->nextOut(*this);
 		        return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Graph* _graph;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Graph& graph, const Node& node)
 		        : _graph(&graph) {
 		        _graph->firstIn(*this, node);
+		      }
 		      InArcIt(const Graph& graph, const Arc& arc) :
 		        Arc(arc), _graph(&graph) {}
 		      InArcIt& operator++() {
 		        _graph->nextIn(*this);
 		        return *this;
+		      }
 		    };
 		    class EdgeIt : public Parent::Edge {
 		      const Graph* _graph;
 		    public:
 		      EdgeIt() { }
 		      EdgeIt(Invalid i) : Edge(i) { }
 		      explicit EdgeIt(const Graph& graph) : _graph(&graph) {
 		        _graph->first(static_cast<Edge&>(*this));
+		      }
 		      EdgeIt(const Graph& graph, const Edge& edge) :
 		        Edge(edge), _graph(&graph) { }
 		      EdgeIt& operator++() {
 		        _graph->next(*this);
 		        return *this;
+		      }
 		    };
 		    class IncEdgeIt : public Parent::Edge {
 		      friend class GraphExtender;
 		      const Graph* _graph;
 		      bool _direction;
 		    public:
 		      IncEdgeIt() { }
 		      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
 		      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
 		        _graph->firstInc(*this, _direction, node);
+		      }
 		      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
 		        : _graph(&graph), Edge(edge) {
 		        _direction = (_graph->source(edge) == node);
+		      }
 		      IncEdgeIt& operator++() {
 		        _graph->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 &arc) const {
 		      return Parent::source(static_cast<const Arc&>(arc));
+		    }
 		    /// \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 &arc) const {
 		      return Parent::target(static_cast<const Arc&>(arc));
+		    }
 		    /// \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 &arc) const {
 		      return Parent::target(static_cast<const Arc&>(arc));
+		    }
 		    /// \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 &arc) const {
 		      return Parent::source(static_cast<const Arc&>(arc));
+		    }
 		    /// 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 &edge) const {
 		      return edge._direction ? u(edge) : v(edge);
+		    }
 		    /// 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 &edge) const {
 		      return edge._direction ? v(edge) : u(edge);
+		    }
 		    // Mappable extension
 		    template <typename _Value>
 		    class NodeMap
 		      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
 		    public:
 		      typedef GraphExtender Graph;
 		      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
 		      NodeMap(const Graph& graph)
 		        : Parent(graph) {}
 		      NodeMap(const Graph& graph, const _Value& value)
 		        : Parent(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 _Value>
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
 		    public:
 		      typedef GraphExtender Graph;
 		      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
 		      ArcMap(const Graph& graph)
 		        : Parent(graph) {}
 		      ArcMap(const Graph& graph, const _Value& value)
 		        : Parent(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;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap
 		      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
 		    public:
 		      typedef GraphExtender Graph;
 		      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
 		      EdgeMap(const Graph& graph)
 		        : Parent(graph) {}
 		      EdgeMap(const Graph& graph, const _Value& value)
 		        : Parent(graph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    // Alteration extension
 		    Node addNode() {
 		      Node node = Parent::addNode();
 		      notifier(Node()).add(node);
 		      return node;
+		    }
 		    Edge addEdge(const Node& from, const Node& to) {
 		      Edge edge = Parent::addEdge(from, to);
 		      notifier(Edge()).add(edge);
 		      std::vector<Arc> ev;
 		      ev.push_back(Parent::direct(edge, true));
 		      ev.push_back(Parent::direct(edge, false));
 		      notifier(Arc()).add(ev);
 		      return edge;
+		    }
 		    void clear() {
 		      notifier(Arc()).clear();
 		      notifier(Edge()).clear();
 		      notifier(Node()).clear();
 		      Parent::clear();
+		    }
 		    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
 		    void build(const Graph& graph, NodeRefMap& nodeRef,
 		               EdgeRefMap& edgeRef) {
 		      Parent::build(graph, nodeRef, edgeRef);
 		      notifier(Node()).build();
 		      notifier(Edge()).build();
 		      notifier(Arc()).build();
+		    }
 		    void erase(const Node& node) {
 		      Arc arc;
 		      Parent::firstOut(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstOut(arc, node);
+		      }
 		      Parent::firstIn(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstIn(arc, node);
+		      }
 		      notifier(Node()).erase(node);
 		      Parent::erase(node);
+		    }
 		    void erase(const Edge& edge) {
 		      std::vector<Arc> av;
 		      av.push_back(Parent::direct(edge, true));
 		      av.push_back(Parent::direct(edge, false));
 		      notifier(Arc()).erase(av);
 		      notifier(Edge()).erase(edge);
 		      Parent::erase(edge);
+		    }
 		    GraphExtender() {
 		      node_notifier.setContainer(*this);
 		      arc_notifier.setContainer(*this);
 		      edge_notifier.setContainer(*this);
+		    }
 		    ~GraphExtender() {
 		      edge_notifier.clear();
 		      arc_notifier.clear();
 		      node_notifier.clear();
+		    }
 		  };
+		}
 		#endif

lemon/bits/map_extender.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-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_MAP_EXTENDER_H
 		#define LEMON_BITS_MAP_EXTENDER_H
 		#include <iterator>
 		#include <lemon/bits/traits.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		///\file
 		///\brief Extenders for iterable maps.
 		//\file
 		//\brief Extenders for iterable maps.
 		namespace lemon {
 		  /// \ingroup graphbits
 		  ///
-		  /// \brief Extender for maps
+		  // \ingroup graphbits
 		  //
 		  // \brief Extender for maps
 		  template <typename _Map>
 		  class MapExtender : public _Map {
 		  public:
 		    typedef _Map Parent;
 		    typedef MapExtender Map;
 		    typedef typename Parent::Graph Graph;
 		    typedef typename Parent::Key Item;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    class MapIt;
 		    class ConstMapIt;
 		    friend class MapIt;
 		    friend class ConstMapIt;
 		  public:
 		    MapExtender(const Graph& graph)
 		      : Parent(graph) {}
 		    MapExtender(const Graph& graph, const Value& value)
 		      : Parent(graph, value) {}
 		  private:
 		    MapExtender& operator=(const MapExtender& cmap) {
 		      return operator=<MapExtender>(cmap);
+		    }
 		    template <typename CMap>
 		    MapExtender& operator=(const CMap& cmap) {
 		      Parent::operator=(cmap);
 		      return *this;
+		    }
 		  public:
 		    class MapIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      typedef typename Map::Value Value;
 		      MapIt() {}
 		      MapIt(Invalid i) : Parent(i) { }
 		      explicit MapIt(Map& _map) : map(_map) {
 		        map.notifier()->first(*this);
+		      }
 		      MapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      MapIt& operator++() {
 		        map.notifier()->next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		      typename MapTraits<Map>::ReturnValue operator*() {
 		        return map[*this];
+		      }
 		      void set(const Value& value) {
 		        map.set(*this, value);
+		      }
 		    protected:
 		      Map& map;
 		    };
 		    class ConstMapIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      typedef typename Map::Value Value;
 		      ConstMapIt() {}
 		      ConstMapIt(Invalid i) : Parent(i) { }
 		      explicit ConstMapIt(Map& _map) : map(_map) {
 		        map.notifier()->first(*this);
+		      }
 		      ConstMapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ConstMapIt& operator++() {
 		        map.notifier()->next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		    protected:
 		      const Map& map;
 		    };
 		    class ItemIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      ItemIt() {}
 		      ItemIt(Invalid i) : Parent(i) { }
 		      explicit ItemIt(Map& _map) : map(_map) {
 		        map.notifier()->first(*this);
+		      }
 		      ItemIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ItemIt& operator++() {
 		        map.notifier()->next(*this);
 		        return *this;
+		      }
 		    protected:
 		      const Map& map;
 		    };
 		  };
 		  /// \ingroup graphbits
 		  ///
-		  /// \brief Extender for maps which use a subset of the items.
+		  // \ingroup graphbits
 		  //
 		  // \brief Extender for maps which use a subset of the items.
 		  template <typename _Graph, typename _Map>
 		  class SubMapExtender : public _Map {
 		  public:
 		    typedef _Map Parent;
 		    typedef SubMapExtender Map;
 		    typedef _Graph Graph;
 		    typedef typename Parent::Key Item;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    class MapIt;
 		    class ConstMapIt;
 		    friend class MapIt;
 		    friend class ConstMapIt;
 		  public:
 		    SubMapExtender(const Graph& _graph)
 		      : Parent(_graph), graph(_graph) {}
 		    SubMapExtender(const Graph& _graph, const Value& _value)
 		      : Parent(_graph, _value), graph(_graph) {}
 		  private:
 		    SubMapExtender& operator=(const SubMapExtender& cmap) {
 		      return operator=<MapExtender>(cmap);
+		    }
 		    template <typename CMap>
 		    SubMapExtender& operator=(const CMap& cmap) {
 		      checkConcept<concepts::ReadMap<Key, Value>, CMap>();
 		      Item it;
 		      for (graph.first(it); it != INVALID; graph.next(it)) {
 		        Parent::set(it, cmap[it]);
+		      }
 		      return *this;
+		    }
 		  public:
 		    class MapIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      typedef typename Map::Value Value;
 		      MapIt() {}
 		      MapIt(Invalid i) : Parent(i) { }
 		      explicit MapIt(Map& _map) : map(_map) {
 		        map.graph.first(*this);
+		      }
 		      MapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      MapIt& operator++() {
 		        map.graph.next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		      typename MapTraits<Map>::ReturnValue operator*() {
 		        return map[*this];
+		      }
 		      void set(const Value& value) {
 		        map.set(*this, value);
+		      }
 		    protected:
 		      Map& map;
 		    };
 		    class ConstMapIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      typedef typename Map::Value Value;
 		      ConstMapIt() {}
 		      ConstMapIt(Invalid i) : Parent(i) { }
 		      explicit ConstMapIt(Map& _map) : map(_map) {
 		        map.graph.first(*this);
+		      }
 		      ConstMapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ConstMapIt& operator++() {
 		        map.graph.next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		    protected:
 		      const Map& map;
 		    };
 		    class ItemIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      ItemIt() {}
 		      ItemIt(Invalid i) : Parent(i) { }
 		      explicit ItemIt(Map& _map) : map(_map) {
 		        map.graph.first(*this);
+		      }
 		      ItemIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ItemIt& operator++() {
 		        map.graph.next(*this);
 		        return *this;
+		      }
 		    protected:
 		      const Map& map;
 		    };
 		  private:
 		    const Graph& graph;
 		  };
+		}
 		#endif

lemon/bits/traits.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_TRAITS_H
 		#define LEMON_BITS_TRAITS_H
 		///\file
 		///\brief Traits for graphs and maps
-		///
+		//\file
 		//\brief Traits for graphs and maps
 		//
 		#include <lemon/bits/enable_if.h>
 		namespace lemon {
 		  struct InvalidType {};
 		  template <typename _Graph, typename _Item>
 		  class ItemSetTraits {};
 		  template <typename Graph, typename Enable = void>
 		  struct NodeNotifierIndicator {
 		    typedef InvalidType Type;
 		  };
 		  template <typename Graph>
 		  struct NodeNotifierIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
 		  > {
 		    typedef typename Graph::NodeNotifier Type;
 		  };
 		  template <typename _Graph>
 		  class ItemSetTraits<_Graph, typename _Graph::Node> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Node Item;
 		    typedef typename Graph::NodeIt ItemIt;
 		    typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
 		    template <typename _Value>
 		    class Map : public Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename Graph::template NodeMap<_Value> Parent;
 		      typedef typename Graph::template NodeMap<_Value> Type;
 		      typedef typename Parent::Value Value;
 		      Map(const Graph& _digraph) : Parent(_digraph) {}
 		      Map(const Graph& _digraph, const Value& _value)
 		        : Parent(_digraph, _value) {}
 		     };
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct ArcNotifierIndicator {
 		    typedef InvalidType Type;
 		  };
 		  template <typename Graph>
 		  struct ArcNotifierIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type
 		  > {
 		    typedef typename Graph::ArcNotifier Type;
 		  };
 		  template <typename _Graph>
 		  class ItemSetTraits<_Graph, typename _Graph::Arc> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Arc Item;
 		    typedef typename Graph::ArcIt ItemIt;
 		    typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;
 		    template <typename _Value>
 		    class Map : public Graph::template ArcMap<_Value> {
 		    public:
 		      typedef typename Graph::template ArcMap<_Value> Parent;
 		      typedef typename Graph::template ArcMap<_Value> Type;
 		      typedef typename Parent::Value Value;
 		      Map(const Graph& _digraph) : Parent(_digraph) {}
 		      Map(const Graph& _digraph, const Value& _value)
 		        : Parent(_digraph, _value) {}
 		    };
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct EdgeNotifierIndicator {
 		    typedef InvalidType Type;
 		  };
 		  template <typename Graph>
 		  struct EdgeNotifierIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type
 		  > {
 		    typedef typename Graph::EdgeNotifier Type;
 		  };
 		  template <typename _Graph>
 		  class ItemSetTraits<_Graph, typename _Graph::Edge> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Edge Item;
 		    typedef typename Graph::EdgeIt ItemIt;
 		    typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;
 		    template <typename _Value>
 		    class Map : public Graph::template EdgeMap<_Value> {
 		    public:
 		      typedef typename Graph::template EdgeMap<_Value> Parent;
 		      typedef typename Graph::template EdgeMap<_Value> Type;
 		      typedef typename Parent::Value Value;
 		      Map(const Graph& _digraph) : Parent(_digraph) {}
 		      Map(const Graph& _digraph, const Value& _value)
 		        : Parent(_digraph, _value) {}
 		    };
 		  };
 		  template <typename Map, typename Enable = void>
 		  struct MapTraits {
 		    typedef False ReferenceMapTag;
 		    typedef typename Map::Key Key;
 		    typedef typename Map::Value Value;
 		    typedef Value ConstReturnValue;
 		    typedef Value ReturnValue;
 		  };
 		  template <typename Map>
 		  struct MapTraits<
 		    Map, typename enable_if<typename Map::ReferenceMapTag, void>::type >
+		  {
 		    typedef True ReferenceMapTag;
 		    typedef typename Map::Key Key;
 		    typedef typename Map::Value Value;
 		    typedef typename Map::ConstReference ConstReturnValue;
 		    typedef typename Map::Reference ReturnValue;
 		    typedef typename Map::ConstReference ConstReference;
 		    typedef typename Map::Reference Reference;
 		 };
 		  template <typename MatrixMap, typename Enable = void>
 		  struct MatrixMapTraits {
 		    typedef False ReferenceMapTag;
 		    typedef typename MatrixMap::FirstKey FirstKey;
 		    typedef typename MatrixMap::SecondKey SecondKey;
 		    typedef typename MatrixMap::Value Value;
 		    typedef Value ConstReturnValue;
 		    typedef Value ReturnValue;
 		  };
 		  template <typename MatrixMap>
 		  struct MatrixMapTraits<
 		    MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag,
 		                                  void>::type >
+		  {
 		    typedef True ReferenceMapTag;
 		    typedef typename MatrixMap::FirstKey FirstKey;
 		    typedef typename MatrixMap::SecondKey SecondKey;
 		    typedef typename MatrixMap::Value Value;
 		    typedef typename MatrixMap::ConstReference ConstReturnValue;
 		    typedef typename MatrixMap::Reference ReturnValue;
 		    typedef typename MatrixMap::ConstReference ConstReference;
 		    typedef typename MatrixMap::Reference Reference;
 		 };
 		  // Indicators for the tags
 		  template <typename Graph, typename Enable = void>
 		  struct NodeNumTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct NodeNumTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::NodeNumTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct EdgeNumTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct EdgeNumTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::EdgeNumTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct FindEdgeTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct FindEdgeTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::FindEdgeTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct UndirectedTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct UndirectedTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::UndirectedTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct BuildTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct BuildTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::BuildTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
+		}
 		#endif

lemon/bits/vector_map.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_VECTOR_MAP_H
 		#define LEMON_BITS_VECTOR_MAP_H
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/core.h>
 		#include <lemon/bits/alteration_notifier.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		///\ingroup graphbits
 		///
 		///\file
 		///\brief Vector based graph maps.
 		//\ingroup graphbits
 		//
 		//\file
 		//\brief Vector based graph maps.
 		namespace lemon {
 		  /// \ingroup graphbits
 		  ///
 		  /// \brief Graph map based on the std::vector storage.
 		  ///
 		  /// The VectorMap template class is graph map structure what
 		  /// automatically updates the map when a key is added to or erased from
 		  /// the map. This map type uses the std::vector to store the values.
 		  ///
 		  /// \tparam _Graph The graph this map is attached to.
 		  /// \tparam _Item The item type of the graph items.
-		  /// \tparam _Value The value type of the map.
+		  // \ingroup graphbits
 		  //
 		  // \brief Graph map based on the std::vector storage.
 		  //
 		  // The VectorMap template class is graph map structure what
 		  // automatically updates the map when a key is added to or erased from
 		  // the map. This map type uses the std::vector to store the values.
 		  //
 		  // \tparam _Graph The graph this map is attached to.
 		  // \tparam _Item The item type of the graph items.
 		  // \tparam _Value The value type of the map.
 		  template <typename _Graph, typename _Item, typename _Value>
 		  class VectorMap
 		    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
 		  private:
-		    /// The container type of the map.
 		    // The container type of the map.
 		    typedef std::vector<_Value> Container;
 		  public:
-		    /// The graph type of the map.
 		    // The graph type of the map.
 		    typedef _Graph Graph;
-		    /// The item type of the map.
 		    // The item type of the map.
 		    typedef _Item Item;
-		    /// The reference map tag.
 		    // The reference map tag.
 		    typedef True ReferenceMapTag;
-		    /// The key type of the map.
 		    // The key type of the map.
 		    typedef _Item Key;
-		    /// The value type of the map.
 		    // The value type of the map.
 		    typedef _Value Value;
-		    /// The notifier type.
 		    // The notifier type.
 		    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
-		    /// The map type.
 		    // The map type.
 		    typedef VectorMap Map;
-		    /// The base class of the map.
 		    // The base class of the map.
 		    typedef typename Notifier::ObserverBase Parent;
-		    /// The reference type of the map;
 		    // The reference type of the map;
 		    typedef typename Container::reference Reference;
-		    /// The const reference type of the map;
 		    // The const reference type of the map;
 		    typedef typename Container::const_reference ConstReference;
 		    /// \brief Constructor to attach the new map into the notifier.
 		    ///
 		    /// It constructs a map and attachs it into the notifier.
 		    /// It adds all the items of the graph to the map.
 		    // \brief Constructor to attach the new map into the notifier.
 		    //
 		    // It constructs a map and attachs it into the notifier.
 		    // It adds all the items of the graph to the map.
 		    VectorMap(const Graph& graph) {
 		      Parent::attach(graph.notifier(Item()));
 		      container.resize(Parent::notifier()->maxId() + 1);
+		    }
 		    /// \brief Constructor uses given value to initialize the map.
 		    ///
 		    /// It constructs a map uses a given value to initialize the map.
 		    /// It adds all the items of the graph to the map.
 		    // \brief Constructor uses given value to initialize the map.
 		    //
 		    // It constructs a map uses a given value to initialize the map.
 		    // It adds all the items of the graph to the map.
 		    VectorMap(const Graph& graph, const Value& value) {
 		      Parent::attach(graph.notifier(Item()));
 		      container.resize(Parent::notifier()->maxId() + 1, value);
+		    }
 		  private:
 		    /// \brief Copy constructor
 		    ///
-		    /// Copy constructor.
+		    // \brief Copy constructor
 		    //
 		    // Copy constructor.
 		    VectorMap(const VectorMap& _copy) : Parent() {
 		      if (_copy.attached()) {
 		        Parent::attach(*_copy.notifier());
 		        container = _copy.container;
+		      }
+		    }
 		    /// \brief Assign operator.
 		    ///
 		    /// This operator assigns for each item in the map the
 		    /// value mapped to the same item in the copied map.
 		    /// The parameter map should be indiced with the same
 		    /// itemset because this assign operator does not change
-		    /// the container of the map.
+		    // \brief Assign operator.
 		    //
 		    // This operator assigns for each item in the map the
 		    // value mapped to the same item in the copied map.
 		    // The parameter map should be indiced with the same
 		    // itemset because this assign operator does not change
 		    // the container of the map.
 		    VectorMap& operator=(const VectorMap& cmap) {
 		      return operator=<VectorMap>(cmap);
+		    }
 		    /// \brief Template assign operator.
 		    ///
 		    /// The given parameter should be conform to the ReadMap
 		    /// concecpt and could be indiced by the current item set of
 		    /// the NodeMap. In this case the value for each item
 		    /// is assigned by the value of the given ReadMap.
 		    // \brief Template assign operator.
 		    //
 		    // The given parameter should be conform to the ReadMap
 		    // concecpt and could be indiced by the current item set of
 		    // the NodeMap. In this case the value for each item
 		    // is assigned by the value of the given ReadMap.
 		    template <typename CMap>
 		    VectorMap& operator=(const CMap& cmap) {
 		      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
 		      const typename Parent::Notifier* nf = Parent::notifier();
 		      Item it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        set(it, cmap[it]);
+		      }
 		      return *this;
+		    }
 		  public:
 		    /// \brief The subcript operator.
 		    ///
 		    /// The subscript operator. The map can be subscripted by the
 		    /// actual items of the graph.
 		    // \brief The subcript operator.
 		    //
 		    // The subscript operator. The map can be subscripted by the
 		    // actual items of the graph.
 		    Reference operator[](const Key& key) {
 		      return container[Parent::notifier()->id(key)];
+		    }
 		    /// \brief The const subcript operator.
 		    ///
 		    /// The const subscript operator. The map can be subscripted by the
 		    /// actual items of the graph.
 		    // \brief The const subcript operator.
 		    //
 		    // The const subscript operator. The map can be subscripted by the
 		    // actual items of the graph.
 		    ConstReference operator[](const Key& key) const {
 		      return container[Parent::notifier()->id(key)];
+		    }
 		    /// \brief The setter function of the map.
 		    ///
-		    /// It the same as operator[](key) = value expression.
+		    // \brief The setter function of the map.
 		    //
 		    // It the same as operator[](key) = value expression.
 		    void set(const Key& key, const Value& value) {
 		      (*this)[key] = value;
+		    }
 		  protected:
 		    /// \brief Adds a new key to the map.
 		    ///
 		    /// It adds a new key to the map. It called by the observer notifier
 		    /// and it overrides the add() member function of the observer base.
 		    // \brief Adds a new key to the map.
 		    //
 		    // It adds a new key to the map. It called by the observer notifier
 		    // and it overrides the add() member function of the observer base.
 		    virtual void add(const Key& key) {
 		      int id = Parent::notifier()->id(key);
 		      if (id >= int(container.size())) {
 		        container.resize(id + 1);
+		      }
+		    }
 		    /// \brief Adds more new keys to the map.
 		    ///
 		    /// It adds more new keys to the map. It called by the observer notifier
 		    /// and it overrides the add() member function of the observer base.
 		    // \brief Adds more new keys to the map.
 		    //
 		    // It adds more new keys to the map. It called by the observer notifier
 		    // and it overrides the add() member function of the observer base.
 		    virtual void add(const std::vector<Key>& keys) {
 		      int max = container.size() - 1;
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        int id = Parent::notifier()->id(keys[i]);
 		        if (id >= max) {
 		          max = id;
+		        }
+		      }
 		      container.resize(max + 1);
+		    }
 		    /// \brief Erase a key from the map.
 		    ///
 		    /// Erase a key from the map. It called by the observer notifier
 		    /// and it overrides the erase() member function of the observer base.
 		    // \brief Erase a key from the map.
 		    //
 		    // Erase a key from the map. It called by the observer notifier
 		    // and it overrides the erase() member function of the observer base.
 		    virtual void erase(const Key& key) {
 		      container[Parent::notifier()->id(key)] = Value();
+		    }
 		    /// \brief Erase more keys from the map.
 		    ///
 		    /// Erase more keys from the map. It called by the observer notifier
 		    /// and it overrides the erase() member function of the observer base.
 		    // \brief Erase more keys from the map.
 		    //
 		    // Erase more keys from the map. It called by the observer notifier
 		    // and it overrides the erase() member function of the observer base.
 		    virtual void erase(const std::vector<Key>& keys) {
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        container[Parent::notifier()->id(keys[i])] = Value();
+		      }
+		    }
 		    /// \brief Buildes the map.
 		    ///
 		    /// It buildes the map. It called by the observer notifier
 		    /// and it overrides the build() member function of the observer base.
 		    // \brief Buildes the map.
 		    //
 		    // It buildes the map. It called by the observer notifier
 		    // and it overrides the build() member function of the observer base.
 		    virtual void build() {
 		      int size = Parent::notifier()->maxId() + 1;
 		      container.reserve(size);
 		      container.resize(size);
+		    }
 		    /// \brief Clear the map.
 		    ///
 		    /// It erase all items from the map. It called by the observer notifier
 		    /// and it overrides the clear() member function of the observer base.
 		    // \brief Clear the map.
 		    //
 		    // It erase all items from the map. It called by the observer notifier
 		    // and it overrides the clear() member function of the observer base.
 		    virtual void clear() {
 		      container.clear();
+		    }
 		  private:
 		    Container container;
 		  };
+		}
 		#endif

lemon/concepts/maps.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CONCEPT_MAPS_H
 		#define LEMON_CONCEPT_MAPS_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
-		///\ingroup concept
+		///\ingroup map_concepts
 		///\file
 		///\brief The concept of maps.
 		namespace lemon {
 		  namespace concepts {
-		    /// \addtogroup concept
+		    /// \addtogroup map_concepts
 		    /// @{
 		    /// Readable map concept
 		    /// Readable map concept.
 		    ///
 		    template<typename K, typename T>
 		    class ReadMap
+		    {
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// \brief The value type of the map.
 		      /// (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// Returns the value associated with the given key.
 		      Value operator[](const Key &) const {
 		        return *static_cast<Value *>(0);
+		      }
 		      template<typename _ReadMap>
 		      struct Constraints {
 		        void constraints() {
 		          Value val = m[key];
 		          val = m[key];
 		          typename _ReadMap::Value own_val = m[own_key];
 		          own_val = m[own_key];
 		          ignore_unused_variable_warning(key);
 		          ignore_unused_variable_warning(val);
 		          ignore_unused_variable_warning(own_key);
 		          ignore_unused_variable_warning(own_val);
+		        }
 		        const Key& key;
 		        const typename _ReadMap::Key& own_key;
 		        const _ReadMap& m;
 		      };
 		    };
 		    /// Writable map concept
 		    /// Writable map concept.
 		    ///
 		    template<typename K, typename T>
 		    class WriteMap
+		    {
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// \brief The value type of the map.
 		      /// (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// Sets the value associated with the given key.
 		      void set(const Key &, const Value &) {}
 		      /// Default constructor.
 		      WriteMap() {}
 		      template <typename _WriteMap>
 		      struct Constraints {
 		        void constraints() {
 		          m.set(key, val);
 		          m.set(own_key, own_val);
 		          ignore_unused_variable_warning(key);
 		          ignore_unused_variable_warning(val);
 		          ignore_unused_variable_warning(own_key);
 		          ignore_unused_variable_warning(own_val);
+		        }
 		        const Key& key;
 		        const Value& val;
 		        const typename _WriteMap::Key& own_key;
 		        const typename _WriteMap::Value& own_val;
 		        _WriteMap& m;
 		      };
 		    };
 		    /// Read/writable map concept
 		    /// Read/writable map concept.
 		    ///
 		    template<typename K, typename T>
 		    class ReadWriteMap : public ReadMap<K,T>,
 		                         public WriteMap<K,T>
+		    {
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// \brief The value type of the map.
 		      /// (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// Returns the value associated with the given key.
 		      Value operator[](const Key &) const {
 		        return *static_cast<Value *>(0);
+		      }
 		      /// Sets the value associated with the given key.
 		      void set(const Key &, const Value &) {}
 		      template<typename _ReadWriteMap>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<ReadMap<K, T>, _ReadWriteMap >();
 		          checkConcept<WriteMap<K, T>, _ReadWriteMap >();
+		        }
 		      };
 		    };
 		    /// Dereferable map concept
 		    /// Dereferable map concept.
 		    ///
 		    template<typename K, typename T, typename R, typename CR>
 		    class ReferenceMap : public ReadWriteMap<K,T>
+		    {
 		    public:
 		      /// Tag for reference maps.
 		      typedef True ReferenceMapTag;
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// \brief The value type of the map.
 		      /// (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// The reference type of the map.
 		      typedef R Reference;
 		      /// The const reference type of the map.
 		      typedef CR ConstReference;
 		    public:
 		      /// Returns a reference to the value associated with the given key.
 		      Reference operator[](const Key &) {
 		        return *static_cast<Value *>(0);
+		      }
 		      /// Returns a const reference to the value associated with the given key.
 		      ConstReference operator[](const Key &) const {
 		        return *static_cast<Value *>(0);
+		      }
 		      /// Sets the value associated with the given key.
 		      void set(const Key &k,const Value &t) { operator[](k)=t; }
 		      template<typename _ReferenceMap>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
 		          ref = m[key];
 		          m[key] = val;
 		          m[key] = ref;
 		          m[key] = cref;
 		          own_ref = m[own_key];
 		          m[own_key] = own_val;
 		          m[own_key] = own_ref;
 		          m[own_key] = own_cref;
 		          m[key] = m[own_key];
 		          m[own_key] = m[key];
+		        }
 		        const Key& key;
 		        Value& val;
 		        Reference ref;
 		        ConstReference cref;
 		        const typename _ReferenceMap::Key& own_key;
 		        typename _ReferenceMap::Value& own_val;
 		        typename _ReferenceMap::Reference own_ref;
 		        typename _ReferenceMap::ConstReference own_cref;
 		        _ReferenceMap& m;
 		      };
 		    };
 		    // @}
 		  } //namespace concepts
 		} //namespace lemon
 		#endif // LEMON_CONCEPT_MAPS_H

lemon/dim2.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_DIM2_H
 		#define LEMON_DIM2_H
 		#include <iostream>
 		///\ingroup misc
 		///\file
 		///\brief A simple two dimensional vector and a bounding box implementation
 		///
 		/// The class \ref lemon::dim2::Point "dim2::Point" implements
 		/// a two dimensional vector with the usual operations.
 		///
 		/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
 		/// the rectangular bounding box of a set of
 		/// \ref lemon::dim2::Point "dim2::Point"'s.
 		namespace lemon {
 		  ///Tools for handling two dimensional coordinates
 		  ///This namespace is a storage of several
 		  ///tools for handling two dimensional coordinates
 		  namespace dim2 {
 		  /// \addtogroup misc
 		  /// @{
 		  /// Two dimensional vector (plain vector)
 		  /// A simple two dimensional vector (plain vector) implementation
 		  /// with the usual vector operations.
 		  template<typename T>
 		    class Point {
 		    public:
 		      typedef T Value;
 		      ///First coordinate
 		      T x;
 		      ///Second coordinate
 		      T y;
 		      ///Default constructor
 		      Point() {}
 		      ///Construct an instance from coordinates
 		      Point(T a, T b) : x(a), y(b) { }
 		      ///Returns the dimension of the vector (i.e. returns 2).
 		      ///The dimension of the vector.
 		      ///This function always returns 2.
 		      int size() const { return 2; }
 		      ///Subscripting operator
 		      ///\c p[0] is \c p.x and \c p[1] is \c p.y
 		      ///
 		      T& operator[](int idx) { return idx == 0 ? x : y; }
 		      ///Const subscripting operator
 		      ///\c p[0] is \c p.x and \c p[1] is \c p.y
 		      ///
 		      const T& operator[](int idx) const { return idx == 0 ? x : y; }
 		      ///Conversion constructor
 		      template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
 		      ///Give back the square of the norm of the vector
 		      T normSquare() const {
 		        return x*x+y*y;
+		      }
 		      ///Increment the left hand side by \c u
 		      Point<T>& operator +=(const Point<T>& u) {
 		        x += u.x;
 		        y += u.y;
 		        return *this;
+		      }
 		      ///Decrement the left hand side by \c u
 		      Point<T>& operator -=(const Point<T>& u) {
 		        x -= u.x;
 		        y -= u.y;
 		        return *this;
+		      }
 		      ///Multiply the left hand side with a scalar
 		      Point<T>& operator *=(const T &u) {
 		        x *= u;
 		        y *= u;
 		        return *this;
+		      }
 		      ///Divide the left hand side by a scalar
 		      Point<T>& operator /=(const T &u) {
 		        x /= u;
 		        y /= u;
 		        return *this;
+		      }
 		      ///Return the scalar product of two vectors
 		      T operator *(const Point<T>& u) const {
 		        return x*u.x+y*u.y;
+		      }
 		      ///Return the sum of two vectors
 		      Point<T> operator+(const Point<T> &u) const {
 		        Point<T> b=*this;
 		        return b+=u;
+		      }
 		      ///Return the negative of the vector
 		      Point<T> operator-() const {
 		        Point<T> b=*this;
 		        b.x=-b.x; b.y=-b.y;
 		        return b;
+		      }
 		      ///Return the difference of two vectors
 		      Point<T> operator-(const Point<T> &u) const {
 		        Point<T> b=*this;
 		        return b-=u;
+		      }
 		      ///Return a vector multiplied by a scalar
 		      Point<T> operator*(const T &u) const {
 		        Point<T> b=*this;
 		        return b*=u;
+		      }
 		      ///Return a vector divided by a scalar
 		      Point<T> operator/(const T &u) const {
 		        Point<T> b=*this;
 		        return b/=u;
+		      }
 		      ///Test equality
 		      bool operator==(const Point<T> &u) const {
 		        return (x==u.x) && (y==u.y);
+		      }
 		      ///Test inequality
 		      bool operator!=(Point u) const {
 		        return  (x!=u.x) || (y!=u.y);
+		      }
 		    };
 		  ///Return a Point
 		  ///Return a Point.
 		  ///\relates Point
 		  template <typename T>
 		  inline Point<T> makePoint(const T& x, const T& y) {
 		    return Point<T>(x, y);
+		  }
 		  ///Return a vector multiplied by a scalar
 		  ///Return a vector multiplied by a scalar.
 		  ///\relates Point
 		  template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
 		    return x*u;
+		  }
 		  ///Read a plain vector from a stream
 		  ///Read a plain vector from a stream.
 		  ///\relates Point
 		  ///
 		  template<typename T>
 		  inline std::istream& operator>>(std::istream &is, Point<T> &z) {
 		    char c;
 		    if (is >> c) {
 		      if (c != '(') is.putback(c);
 		    } else {
 		      is.clear();
+		    }
 		    if (!(is >> z.x)) return is;
 		    if (is >> c) {
 		      if (c != ',') is.putback(c);
 		    } else {
 		      is.clear();
+		    }
 		    if (!(is >> z.y)) return is;
 		    if (is >> c) {
 		      if (c != ')') is.putback(c);
 		    } else {
 		      is.clear();
+		    }
 		    return is;
+		  }
 		  ///Write a plain vector to a stream
 		  ///Write a plain vector to a stream.
 		  ///\relates Point
 		  ///
 		  template<typename T>
 		  inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
+		  {
 		    os << "(" << z.x << "," << z.y << ")";
 		    return os;
+		  }
 		  ///Rotate by 90 degrees
 		  ///Returns the parameter rotated by 90 degrees in positive direction.
 		  ///\relates Point
 		  ///
 		  template<typename T>
 		  inline Point<T> rot90(const Point<T> &z)
+		  {
 		    return Point<T>(-z.y,z.x);
+		  }
 		  ///Rotate by 180 degrees
 		  ///Returns the parameter rotated by 180 degrees.
 		  ///\relates Point
 		  ///
 		  template<typename T>
 		  inline Point<T> rot180(const Point<T> &z)
+		  {
 		    return Point<T>(-z.x,-z.y);
+		  }
 		  ///Rotate by 270 degrees
 		  ///Returns the parameter rotated by 90 degrees in negative direction.
 		  ///\relates Point
 		  ///
 		  template<typename T>
 		  inline Point<T> rot270(const Point<T> &z)
+		  {
 		    return Point<T>(z.y,-z.x);
+		  }
 		  /// Bounding box of plain vectors (points).
 		  /// A class to calculate or store the bounding box of plain vectors
 		  /// (\ref Point "points").
 		  template<typename T>
 		  class Box {
 		      Point<T> _bottom_left, _top_right;
 		      bool _empty;
 		    public:
 		      ///Default constructor: creates an empty box
 		      Box() { _empty = true; }
 		      ///Construct a box from one point
 		      Box(Point<T> a) {
 		        _bottom_left = _top_right = a;
 		        _empty = false;
+		      }
 		      ///Construct a box from two points
 		      ///Construct a box from two points.
 		      ///\param a The bottom left corner.
 		      ///\param b The top right corner.
 		      ///\warning The coordinates of the bottom left corner must be no more
 		      ///than those of the top right one.
 		      Box(Point<T> a,Point<T> b)
+		      {
 		        _bottom_left = a;
 		        _top_right = b;
 		        _empty = false;
+		      }
 		      ///Construct a box from four numbers
 		      ///Construct a box from four numbers.
 		      ///\param l The left side of the box.
 		      ///\param b The bottom of the box.
 		      ///\param r The right side of the box.
 		      ///\param t The top of the box.
 		      ///\warning The left side must be no more than the right side and
 		      ///bottom must be no more than the top.
 		      Box(T l,T b,T r,T t)
+		      {
 		        _bottom_left=Point<T>(l,b);
 		        _top_right=Point<T>(r,t);
 		        _empty = false;
+		      }
 		      ///Return \c true if the box is empty.
 		      ///Return \c true if the box is empty (i.e. return \c false
 		      ///if at least one point was added to the box or the coordinates of
 		      ///the box were set).
 		      ///
 		      ///The coordinates of an empty box are not defined.
 		      bool empty() const {
 		        return _empty;
+		      }
 		      ///Make the box empty
 		      void clear() {
 		        _empty = true;
+		      }
 		      ///Give back the bottom left corner of the box
 		      ///Give back the bottom left corner of the box.
 		      ///If the box is empty, then the return value is not defined.
 		      Point<T> bottomLeft() const {
 		        return _bottom_left;
+		      }
 		      ///Set the bottom left corner of the box
 		      ///Set the bottom left corner of the box.
 		      ///\pre The box must not be empty.
 		      void bottomLeft(Point<T> p) {
 		        _bottom_left = p;
+		      }
 		      ///Give back the top right corner of the box
 		      ///Give back the top right corner of the box.
 		      ///If the box is empty, then the return value is not defined.
 		      Point<T> topRight() const {
 		        return _top_right;
+		      }
 		      ///Set the top right corner of the box
 		      ///Set the top right corner of the box.
 		      ///\pre The box must not be empty.
 		      void topRight(Point<T> p) {
 		        _top_right = p;
+		      }
 		      ///Give back the bottom right corner of the box
 		      ///Give back the bottom right corner of the box.
 		      ///If the box is empty, then the return value is not defined.
 		      Point<T> bottomRight() const {
 		        return Point<T>(_top_right.x,_bottom_left.y);
+		      }
 		      ///Set the bottom right corner of the box
 		      ///Set the bottom right corner of the box.
 		      ///\pre The box must not be empty.
 		      void bottomRight(Point<T> p) {
 		        _top_right.x = p.x;
 		        _bottom_left.y = p.y;
+		      }
 		      ///Give back the top left corner of the box
 		      ///Give back the top left corner of the box.
 		      ///If the box is empty, then the return value is not defined.
 		      Point<T> topLeft() const {
 		        return Point<T>(_bottom_left.x,_top_right.y);
+		      }
 		      ///Set the top left corner of the box
 		      ///Set the top left corner of the box.
 		      ///\pre The box must not be empty.
 		      void topLeft(Point<T> p) {
 		        _top_right.y = p.y;
 		        _bottom_left.x = p.x;
+		      }
 		      ///Give back the bottom of the box
 		      ///Give back the bottom of the box.
 		      ///If the box is empty, then the return value is not defined.
 		      T bottom() const {
 		        return _bottom_left.y;
+		      }
 		      ///Set the bottom of the box
 		      ///Set the bottom of the box.
 		      ///\pre The box must not be empty.
 		      void bottom(T t) {
 		        _bottom_left.y = t;
+		      }
 		      ///Give back the top of the box
 		      ///Give back the top of the box.
 		      ///If the box is empty, then the return value is not defined.
 		      T top() const {
 		        return _top_right.y;
+		      }
 		      ///Set the top of the box
 		      ///Set the top of the box.
 		      ///\pre The box must not be empty.
 		      void top(T t) {
 		        _top_right.y = t;
+		      }
 		      ///Give back the left side of the box
 		      ///Give back the left side of the box.
 		      ///If the box is empty, then the return value is not defined.
 		      T left() const {
 		        return _bottom_left.x;
+		      }
 		      ///Set the left side of the box
 		      ///Set the left side of the box.
 		      ///\pre The box must not be empty.
 		      void left(T t) {
 		        _bottom_left.x = t;
+		      }
 		      /// Give back the right side of the box
 		      /// Give back the right side of the box.
 		      ///If the box is empty, then the return value is not defined.
 		      T right() const {
 		        return _top_right.x;
+		      }
 		      ///Set the right side of the box
 		      ///Set the right side of the box.
 		      ///\pre The box must not be empty.
 		      void right(T t) {
 		        _top_right.x = t;
+		      }
 		      ///Give back the height of the box
 		      ///Give back the height of the box.
 		      ///If the box is empty, then the return value is not defined.
 		      T height() const {
 		        return _top_right.y-_bottom_left.y;
+		      }
 		      ///Give back the width of the box
 		      ///Give back the width of the box.
 		      ///If the box is empty, then the return value is not defined.
 		      T width() const {
 		        return _top_right.x-_bottom_left.x;
+		      }
 		      ///Checks whether a point is inside the box
 		      bool inside(const Point<T>& u) const {
 		        if (_empty)
 		          return false;
 		        else {
 		          return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 &&
 		                   (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 );
+		        }
+		      }
 		      ///Increments the box with a point
 		      ///Increments the box with a point.
 		      ///
 		      Box& add(const Point<T>& u){
 		        if (_empty) {
 		          _bottom_left = _top_right = u;
 		          _empty = false;
+		        }
 		        else {
 		          if (_bottom_left.x > u.x) _bottom_left.x = u.x;
 		          if (_bottom_left.y > u.y) _bottom_left.y = u.y;
 		          if (_top_right.x < u.x) _top_right.x = u.x;
 		          if (_top_right.y < u.y) _top_right.y = u.y;
+		        }
 		        return *this;
+		      }
 		      ///Increments the box to contain another box
 		      ///Increments the box to contain another box.
 		      ///
 		      Box& add(const Box &u){
 		        if ( !u.empty() ){
 		          add(u._bottom_left);
 		          add(u._top_right);
+		        }
 		        return *this;
+		      }
 		      ///Intersection of two boxes
 		      ///Intersection of two boxes.
 		      ///
 		      Box operator&(const Box& u) const {
 		        Box b;
 		        if (_empty || u._empty) {
 		          b._empty = true;
 		        } else {
 		          b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);
 		          b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);
 		          b._top_right.x = std::min(_top_right.x, u._top_right.x);
 		          b._top_right.y = std::min(_top_right.y, u._top_right.y);
 		          b._empty = b._bottom_left.x > b._top_right.x ||
 		                     b._bottom_left.y > b._top_right.y;
+		        }
 		        return b;
+		      }
 		  };//class Box
 		  ///Read a box from a stream
 		  ///Read a box from a stream.
 		  ///\relates Box
 		  template<typename T>
 		  inline std::istream& operator>>(std::istream &is, Box<T>& b) {
 		    char c;
 		    Point<T> p;
 		    if (is >> c) {
 		      if (c != '(') is.putback(c);
 		    } else {
 		      is.clear();
+		    }
 		    if (!(is >> p)) return is;
 		    b.bottomLeft(p);
 		    if (is >> c) {
 		      if (c != ',') is.putback(c);
 		    } else {
 		      is.clear();
+		    }
 		    if (!(is >> p)) return is;
 		    b.topRight(p);
 		    if (is >> c) {
 		      if (c != ')') is.putback(c);
 		    } else {
 		      is.clear();
+		    }
 		    return is;
+		  }
 		  ///Write a box to a stream
 		  ///Write a box to a stream.
 		  ///\relates Box
 		  template<typename T>
 		  inline std::ostream& operator<<(std::ostream &os, const Box<T>& b)
+		  {
 		    os << "(" << b.bottomLeft() << "," << b.topRight() << ")";
 		    return os;
+		  }
 		  ///Map of x-coordinates of a <tt>Point</tt>-map
 		  ///Map of x-coordinates of a \ref Point "Point"-map.
-		  ///\ingroup maps
 		  ///
 		  template<class M>
 		  class XMap
+		  {
 		    M& _map;
 		  public:
 		    typedef typename M::Value::Value Value;
 		    typedef typename M::Key Key;
 		    ///\e
 		    XMap(M& map) : _map(map) {}
 		    Value operator[](Key k) const {return _map[k].x;}
 		    void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
 		  };
 		  ///Returns an XMap class
 		  ///This function just returns an XMap class.
 		  ///
 		  ///\ingroup maps
 		  ///\relates XMap
 		  template<class M>
 		  inline XMap<M> xMap(M &m)
+		  {
 		    return XMap<M>(m);
+		  }
 		  template<class M>
 		  inline XMap<M> xMap(const M &m)
+		  {
 		    return XMap<M>(m);
+		  }
 		  ///Constant (read only) version of XMap
 		  ///Constant (read only) version of XMap.
-		  ///\ingroup maps
 		  ///
 		  template<class M>
 		  class ConstXMap
+		  {
 		    const M& _map;
 		  public:
 		    typedef typename M::Value::Value Value;
 		    typedef typename M::Key Key;
 		    ///\e
 		    ConstXMap(const M &map) : _map(map) {}
 		    Value operator[](Key k) const {return _map[k].x;}
 		  };
 		  ///Returns a ConstXMap class
 		  ///This function just returns a ConstXMap class.
 		  ///
 		  ///\ingroup maps
 		  ///\relates ConstXMap
 		  template<class M>
 		  inline ConstXMap<M> xMap(const M &m)
+		  {
 		    return ConstXMap<M>(m);
+		  }
 		  ///Map of y-coordinates of a <tt>Point</tt>-map
 		  ///Map of y-coordinates of a \ref Point "Point"-map.
-		  ///\ingroup maps
 		  ///
 		  template<class M>
 		  class YMap
+		  {
 		    M& _map;
 		  public:
 		    typedef typename M::Value::Value Value;
 		    typedef typename M::Key Key;
 		    ///\e
 		    YMap(M& map) : _map(map) {}
 		    Value operator[](Key k) const {return _map[k].y;}
 		    void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
 		  };
 		  ///Returns a YMap class
 		  ///This function just returns a YMap class.
 		  ///
 		  ///\ingroup maps
 		  ///\relates YMap
 		  template<class M>
 		  inline YMap<M> yMap(M &m)
+		  {
 		    return YMap<M>(m);
+		  }
 		  template<class M>
 		  inline YMap<M> yMap(const M &m)
+		  {
 		    return YMap<M>(m);
+		  }
 		  ///Constant (read only) version of YMap
 		  ///Constant (read only) version of YMap.
-		  ///\ingroup maps
 		  ///
 		  template<class M>
 		  class ConstYMap
+		  {
 		    const M& _map;
 		  public:
 		    typedef typename M::Value::Value Value;
 		    typedef typename M::Key Key;
 		    ///\e
 		    ConstYMap(const M &map) : _map(map) {}
 		    Value operator[](Key k) const {return _map[k].y;}
 		  };
 		  ///Returns a ConstYMap class
 		  ///This function just returns a ConstYMap class.
 		  ///
 		  ///\ingroup maps
 		  ///\relates ConstYMap
 		  template<class M>
 		  inline ConstYMap<M> yMap(const M &m)
+		  {
 		    return ConstYMap<M>(m);
+		  }
 		  ///\brief Map of the normSquare() of a <tt>Point</tt>-map
 		  ///
 		  ///Map of the \ref Point::normSquare() "normSquare()"
 		  ///of a \ref Point "Point"-map.
 		  ///\ingroup maps
 		  template<class M>
 		  class NormSquareMap
+		  {
 		    const M& _map;
 		  public:
 		    typedef typename M::Value::Value Value;
 		    typedef typename M::Key Key;
 		    ///\e
 		    NormSquareMap(const M &map) : _map(map) {}
 		    Value operator[](Key k) const {return _map[k].normSquare();}
 		  };
 		  ///Returns a NormSquareMap class
 		  ///This function just returns a NormSquareMap class.
 		  ///
 		  ///\ingroup maps
 		  ///\relates NormSquareMap
 		  template<class M>
 		  inline NormSquareMap<M> normSquareMap(const M &m)
+		  {
 		    return NormSquareMap<M>(m);
+		  }
 		  /// @}
 		  } //namespce dim2
 		} //namespace lemon
 		#endif //LEMON_DIM2_H

lemon/maps.h

Show inline comments

@@ -150,2552 +150,2558 @@
 		  template<typename T, T v>
 		  struct Const {};
 		  /// Constant map with inlined constant value.
 		  /// This \ref concepts::ReadMap "readable map" assigns a specified
 		  /// value to each key.
 		  ///
 		  /// In other aspects it is equivalent to \c NullMap.
 		  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
 		  /// concept, but it absorbs the data written to it.
 		  ///
 		  /// The simplest way of using this map is through the constMap()
 		  /// function.
 		  ///
 		  /// \sa NullMap
 		  /// \sa IdentityMap
 		  template<typename K, typename V, V v>
 		  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
 		  public:
 		    typedef MapBase<K, V> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor.
 		    ConstMap() {}
 		    /// Gives back the specified value.
 		    Value operator[](const Key&) const { return v; }
 		    /// Absorbs the value.
 		    void set(const Key&, const Value&) {}
 		  };
 		  /// Returns a \c ConstMap class with inlined constant value
 		  /// This function just returns a \c ConstMap class with inlined
 		  /// constant value.
 		  /// \relates ConstMap
 		  template<typename K, typename V, V v>
 		  inline ConstMap<K, Const<V, v> > constMap() {
 		    return ConstMap<K, Const<V, v> >();
+		  }
 		  /// Identity map.
 		  /// This \ref concepts::ReadMap "read-only map" gives back the given
 		  /// key as value without any modification.
 		  ///
 		  /// \sa ConstMap
 		  template <typename T>
 		  class IdentityMap : public MapBase<T, T> {
 		  public:
 		    typedef MapBase<T, T> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Gives back the given value without any modification.
 		    Value operator[](const Key &k) const {
 		      return k;
+		    }
 		  };
 		  /// Returns an \c IdentityMap class
 		  /// This function just returns an \c IdentityMap class.
 		  /// \relates IdentityMap
 		  template<typename T>
 		  inline IdentityMap<T> identityMap() {
 		    return IdentityMap<T>();
+		  }
 		  /// \brief Map for storing values for integer keys from the range
 		  /// <tt>[0..size-1]</tt>.
 		  ///
 		  /// This map is essentially a wrapper for \c std::vector. It assigns
 		  /// values to integer keys from the range <tt>[0..size-1]</tt>.
 		  /// It can be used with some data structures, for example
 		  /// \c UnionFind, \c BinHeap, when the used items are small
 		  /// integers. This map conforms the \ref concepts::ReferenceMap
 		  /// "ReferenceMap" concept.
 		  ///
 		  /// The simplest way of using this map is through the rangeMap()
 		  /// function.
 		  template <typename V>
 		  class RangeMap : public MapBase<int, V> {
 		    template <typename V1>
 		    friend class RangeMap;
 		  private:
 		    typedef std::vector<V> Vector;
 		    Vector _vector;
 		  public:
 		    typedef MapBase<int, V> Parent;
 		    /// Key type
 		    typedef typename Parent::Key Key;
 		    /// Value type
 		    typedef typename Parent::Value Value;
 		    /// Reference type
 		    typedef typename Vector::reference Reference;
 		    /// Const reference type
 		    typedef typename Vector::const_reference ConstReference;
 		    typedef True ReferenceMapTag;
 		  public:
 		    /// Constructor with specified default value.
 		    RangeMap(int size = 0, const Value &value = Value())
 		      : _vector(size, value) {}
 		    /// Constructs the map from an appropriate \c std::vector.
 		    template <typename V1>
 		    RangeMap(const std::vector<V1>& vector)
 		      : _vector(vector.begin(), vector.end()) {}
 		    /// Constructs the map from another \c RangeMap.
 		    template <typename V1>
 		    RangeMap(const RangeMap<V1> &c)
 		      : _vector(c._vector.begin(), c._vector.end()) {}
 		    /// Returns the size of the map.
 		    int size() {
 		      return _vector.size();
+		    }
 		    /// Resizes the map.
 		    /// Resizes the underlying \c std::vector container, so changes the
 		    /// keyset of the map.
 		    /// \param size The new size of the map. The new keyset will be the
 		    /// range <tt>[0..size-1]</tt>.
 		    /// \param value The default value to assign to the new keys.
 		    void resize(int size, const Value &value = Value()) {
 		      _vector.resize(size, value);
+		    }
 		  private:
 		    RangeMap& operator=(const RangeMap&);
 		  public:
 		    ///\e
 		    Reference operator[](const Key &k) {
 		      return _vector[k];
+		    }
 		    ///\e
 		    ConstReference operator[](const Key &k) const {
 		      return _vector[k];
+		    }
 		    ///\e
 		    void set(const Key &k, const Value &v) {
 		      _vector[k] = v;
+		    }
 		  };
 		  /// Returns a \c RangeMap class
 		  /// This function just returns a \c RangeMap class.
 		  /// \relates RangeMap
 		  template<typename V>
 		  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
 		    return RangeMap<V>(size, value);
+		  }
 		  /// \brief Returns a \c RangeMap class created from an appropriate
 		  /// \c std::vector
 		  /// This function just returns a \c RangeMap class created from an
 		  /// appropriate \c std::vector.
 		  /// \relates RangeMap
 		  template<typename V>
 		  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
 		    return RangeMap<V>(vector);
+		  }
 		  /// Map type based on \c std::map
 		  /// This map is essentially a wrapper for \c std::map with addition
 		  /// that you can specify a default value for the keys that are not
 		  /// stored actually. This value can be different from the default
 		  /// contructed value (i.e. \c %Value()).
 		  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
 		  /// concept.
 		  ///
 		  /// This map is useful if a default value should be assigned to most of
 		  /// the keys and different values should be assigned only to a few
 		  /// keys (i.e. the map is "sparse").
 		  /// The name of this type also refers to this important usage.
 		  ///
 		  /// Apart form that this map can be used in many other cases since it
 		  /// is based on \c std::map, which is a general associative container.
 		  /// However keep in mind that it is usually not as efficient as other
 		  /// maps.
 		  ///
 		  /// The simplest way of using this map is through the sparseMap()
 		  /// function.
 		  template <typename K, typename V, typename Compare = std::less<K> >
 		  class SparseMap : public MapBase<K, V> {
 		    template <typename K1, typename V1, typename C1>
 		    friend class SparseMap;
 		  public:
 		    typedef MapBase<K, V> Parent;
 		    /// Key type
 		    typedef typename Parent::Key Key;
 		    /// Value type
 		    typedef typename Parent::Value Value;
 		    /// Reference type
 		    typedef Value& Reference;
 		    /// Const reference type
 		    typedef const Value& ConstReference;
 		    typedef True ReferenceMapTag;
 		  private:
 		    typedef std::map<K, V, Compare> Map;
 		    Map _map;
 		    Value _value;
 		  public:
 		    /// \brief Constructor with specified default value.
 		    SparseMap(const Value &value = Value()) : _value(value) {}
 		    /// \brief Constructs the map from an appropriate \c std::map, and
 		    /// explicitly specifies a default value.
 		    template <typename V1, typename Comp1>
 		    SparseMap(const std::map<Key, V1, Comp1> &map,
 		              const Value &value = Value())
 		      : _map(map.begin(), map.end()), _value(value) {}
 		    /// \brief Constructs the map from another \c SparseMap.
 		    template<typename V1, typename Comp1>
 		    SparseMap(const SparseMap<Key, V1, Comp1> &c)
 		      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
 		  private:
 		    SparseMap& operator=(const SparseMap&);
 		  public:
 		    ///\e
 		    Reference operator[](const Key &k) {
 		      typename Map::iterator it = _map.lower_bound(k);
 		      if (it != _map.end() && !_map.key_comp()(k, it->first))
 		        return it->second;
 		      else
 		        return _map.insert(it, std::make_pair(k, _value))->second;
+		    }
 		    ///\e
 		    ConstReference operator[](const Key &k) const {
 		      typename Map::const_iterator it = _map.find(k);
 		      if (it != _map.end())
 		        return it->second;
 		      else
 		        return _value;
+		    }
 		    ///\e
 		    void set(const Key &k, const Value &v) {
 		      typename Map::iterator it = _map.lower_bound(k);
 		      if (it != _map.end() && !_map.key_comp()(k, it->first))
 		        it->second = v;
 		      else
 		        _map.insert(it, std::make_pair(k, v));
+		    }
 		    ///\e
 		    void setAll(const Value &v) {
 		      _value = v;
 		      _map.clear();
+		    }
 		  };
 		  /// Returns a \c SparseMap class
 		  /// This function just returns a \c SparseMap class with specified
 		  /// default value.
 		  /// \relates SparseMap
 		  template<typename K, typename V, typename Compare>
 		  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
 		    return SparseMap<K, V, Compare>(value);
+		  }
 		  template<typename K, typename V>
 		  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
 		    return SparseMap<K, V, std::less<K> >(value);
+		  }
 		  /// \brief Returns a \c SparseMap class created from an appropriate
 		  /// \c std::map
 		  /// This function just returns a \c SparseMap class created from an
 		  /// appropriate \c std::map.
 		  /// \relates SparseMap
 		  template<typename K, typename V, typename Compare>
 		  inline SparseMap<K, V, Compare>
 		    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
+		  {
 		    return SparseMap<K, V, Compare>(map, value);
+		  }
 		  /// @}
 		  /// \addtogroup map_adaptors
 		  /// @{
 		  /// Composition of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the
 		  /// composition of two given maps. That is to say, if \c m1 is of
 		  /// type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   ComposeMap<M1, M2> cm(m1,m2);
 		  /// \endcode
 		  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
 		  ///
 		  /// The \c Key type of the map is inherited from \c M2 and the
 		  /// \c Value type is from \c M1.
 		  /// \c M2::Value must be convertible to \c M1::Key.
 		  ///
 		  /// The simplest way of using this map is through the composeMap()
 		  /// function.
 		  ///
 		  /// \sa CombineMap
 		  template <typename M1, typename M2>
 		  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    typename MapTraits<M1>::ConstReturnValue
 		    operator[](const Key &k) const { return _m1[_m2[k]]; }
 		  };
 		  /// Returns a \c ComposeMap class
 		  /// This function just returns a \c ComposeMap class.
 		  ///
 		  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
 		  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
 		  /// will be equal to <tt>m1[m2[x]]</tt>.
 		  ///
 		  /// \relates ComposeMap
 		  template <typename M1, typename M2>
 		  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
 		    return ComposeMap<M1, M2>(m1, m2);
+		  }
 		  /// Combination of two maps using an STL (binary) functor.
 		  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
 		  /// binary functor and returns the combination of the two given maps
 		  /// using the functor.
 		  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
 		  /// and \c f is of \c F, then for
 		  /// \code
 		  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
 		  /// \endcode
 		  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
 		  ///
 		  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
 		  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
 		  /// \c M2::Value and \c M1::Value must be convertible to the
 		  /// corresponding input parameter of \c F and the return type of \c F
 		  /// must be convertible to \c V.
 		  ///
 		  /// The simplest way of using this map is through the combineMap()
 		  /// function.
 		  ///
 		  /// \sa ComposeMap
 		  template<typename M1, typename M2, typename F,
 		           typename V = typename F::result_type>
 		  class CombineMap : public MapBase<typename M1::Key, V> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		    F _f;
 		  public:
 		    typedef MapBase<typename M1::Key, V> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
 		      : _m1(m1), _m2(m2), _f(f) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
 		  };
 		  /// Returns a \c CombineMap class
 		  /// This function just returns a \c CombineMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then
 		  /// \code
 		  ///   combineMap(m1,m2,std::plus<double>())
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   addMap(m1,m2)
 		  /// \endcode
 		  ///
 		  /// This function is specialized for adaptable binary function
 		  /// classes and C++ functions.
 		  ///
 		  /// \relates CombineMap
 		  template<typename M1, typename M2, typename F, typename V>
 		  inline CombineMap<M1, M2, F, V>
 		  combineMap(const M1 &m1, const M2 &m2, const F &f) {
 		    return CombineMap<M1, M2, F, V>(m1,m2,f);
+		  }
 		  template<typename M1, typename M2, typename F>
 		  inline CombineMap<M1, M2, F, typename F::result_type>
 		  combineMap(const M1 &m1, const M2 &m2, const F &f) {
 		    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
+		  }
 		  template<typename M1, typename M2, typename K1, typename K2, typename V>
 		  inline CombineMap<M1, M2, V (*)(K1, K2), V>
 		  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
 		    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
+		  }
 		  /// Converts an STL style (unary) functor to a map
 		  /// This \ref concepts::ReadMap "read-only map" returns the value
 		  /// of a given functor. Actually, it just wraps the functor and
 		  /// provides the \c Key and \c Value typedefs.
 		  ///
 		  /// Template parameters \c K and \c V will become its \c Key and
 		  /// \c Value. In most cases they have to be given explicitly because
 		  /// a functor typically does not provide \c argument_type and
 		  /// \c result_type typedefs.
 		  /// Parameter \c F is the type of the used functor.
 		  ///
 		  /// The simplest way of using this map is through the functorToMap()
 		  /// function.
 		  ///
 		  /// \sa MapToFunctor
 		  template<typename F,
 		           typename K = typename F::argument_type,
 		           typename V = typename F::result_type>
 		  class FunctorToMap : public MapBase<K, V> {
 		    F _f;
 		  public:
 		    typedef MapBase<K, V> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    FunctorToMap(const F &f = F()) : _f(f) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _f(k); }
 		  };
 		  /// Returns a \c FunctorToMap class
 		  /// This function just returns a \c FunctorToMap class.
 		  ///
 		  /// This function is specialized for adaptable binary function
 		  /// classes and C++ functions.
 		  ///
 		  /// \relates FunctorToMap
 		  template<typename K, typename V, typename F>
 		  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
 		    return FunctorToMap<F, K, V>(f);
+		  }
 		  template <typename F>
 		  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
 		    functorToMap(const F &f)
+		  {
 		    return FunctorToMap<F, typename F::argument_type,
 		      typename F::result_type>(f);
+		  }
 		  template <typename K, typename V>
 		  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
 		    return FunctorToMap<V (*)(K), K, V>(f);
+		  }
 		  /// Converts a map to an STL style (unary) functor
 		  /// This class converts a map to an STL style (unary) functor.
 		  /// That is it provides an <tt>operator()</tt> to read its values.
 		  ///
 		  /// For the sake of convenience it also works as a usual
 		  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
 		  /// and the \c Key and \c Value typedefs also exist.
 		  ///
 		  /// The simplest way of using this map is through the mapToFunctor()
 		  /// function.
 		  ///
 		  ///\sa FunctorToMap
 		  template <typename M>
 		  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
 		    const M &_m;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    typedef typename Parent::Key argument_type;
 		    typedef typename Parent::Value result_type;
 		    /// Constructor
 		    MapToFunctor(const M &m) : _m(m) {}
 		    /// \e
 		    Value operator()(const Key &k) const { return _m[k]; }
 		    /// \e
 		    Value operator[](const Key &k) const { return _m[k]; }
 		  };
 		  /// Returns a \c MapToFunctor class
 		  /// This function just returns a \c MapToFunctor class.
 		  /// \relates MapToFunctor
 		  template<typename M>
 		  inline MapToFunctor<M> mapToFunctor(const M &m) {
 		    return MapToFunctor<M>(m);
+		  }
 		  /// \brief Map adaptor to convert the \c Value type of a map to
 		  /// another type using the default conversion.
 		  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
 		  /// "readable map" to another type using the default conversion.
 		  /// The \c Key type of it is inherited from \c M and the \c Value
 		  /// type is \c V.
 		  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
 		  ///
 		  /// The simplest way of using this map is through the convertMap()
 		  /// function.
 		  template <typename M, typename V>
 		  class ConvertMap : public MapBase<typename M::Key, V> {
 		    const M &_m;
 		  public:
 		    typedef MapBase<typename M::Key, V> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The underlying map.
 		    ConvertMap(const M &m) : _m(m) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m[k]; }
 		  };
 		  /// Returns a \c ConvertMap class
 		  /// This function just returns a \c ConvertMap class.
 		  /// \relates ConvertMap
 		  template<typename V, typename M>
 		  inline ConvertMap<M, V> convertMap(const M &map) {
 		    return ConvertMap<M, V>(map);
+		  }
 		  /// Applies all map setting operations to two maps
 		  /// This map has two \ref concepts::WriteMap "writable map" parameters
 		  /// and each write request will be passed to both of them.
 		  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
 		  /// operations will return the corresponding values of \c M1.
 		  ///
 		  /// The \c Key and \c Value types are inherited from \c M1.
 		  /// The \c Key and \c Value of \c M2 must be convertible from those
 		  /// of \c M1.
 		  ///
 		  /// The simplest way of using this map is through the forkMap()
 		  /// function.
 		  template<typename  M1, typename M2>
 		  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    M1 &_m1;
 		    M2 &_m2;
 		  public:
 		    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// Returns the value associated with the given key in the first map.
 		    Value operator[](const Key &k) const { return _m1[k]; }
 		    /// Sets the value associated with the given key in both maps.
 		    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
 		  };
 		  /// Returns a \c ForkMap class
 		  /// This function just returns a \c ForkMap class.
 		  /// \relates ForkMap
 		  template <typename M1, typename M2>
 		  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
 		    return ForkMap<M1,M2>(m1,m2);
+		  }
 		  /// Sum of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the sum
 		  /// of the values of the two given maps.
 		  /// Its \c Key and \c Value types are inherited from \c M1.
 		  /// The \c Key and \c Value of \c M2 must be convertible to those of
 		  /// \c M1.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   AddMap<M1,M2> am(m1,m2);
 		  /// \endcode
 		  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the addMap()
 		  /// function.
 		  ///
 		  /// \sa SubMap, MulMap, DivMap
 		  /// \sa ShiftMap, ShiftWriteMap
 		  template<typename M1, typename M2>
 		  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
 		  };
 		  /// Returns an \c AddMap class
 		  /// This function just returns an \c AddMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]+m2[x]</tt>.
 		  ///
 		  /// \relates AddMap
 		  template<typename M1, typename M2>
 		  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
 		    return AddMap<M1, M2>(m1,m2);
+		  }
 		  /// Difference of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the difference
 		  /// of the values of the two given maps.
 		  /// Its \c Key and \c Value types are inherited from \c M1.
 		  /// The \c Key and \c Value of \c M2 must be convertible to those of
 		  /// \c M1.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   SubMap<M1,M2> sm(m1,m2);
 		  /// \endcode
 		  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the subMap()
 		  /// function.
 		  ///
 		  /// \sa AddMap, MulMap, DivMap
 		  template<typename M1, typename M2>
 		  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
 		  };
 		  /// Returns a \c SubMap class
 		  /// This function just returns a \c SubMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]-m2[x]</tt>.
 		  ///
 		  /// \relates SubMap
 		  template<typename M1, typename M2>
 		  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
 		    return SubMap<M1, M2>(m1,m2);
+		  }
 		  /// Product of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the product
 		  /// of the values of the two given maps.
 		  /// Its \c Key and \c Value types are inherited from \c M1.
 		  /// The \c Key and \c Value of \c M2 must be convertible to those of
 		  /// \c M1.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   MulMap<M1,M2> mm(m1,m2);
 		  /// \endcode
 		  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the mulMap()
 		  /// function.
 		  ///
 		  /// \sa AddMap, SubMap, DivMap
 		  /// \sa ScaleMap, ScaleWriteMap
 		  template<typename M1, typename M2>
 		  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
 		  };
 		  /// Returns a \c MulMap class
 		  /// This function just returns a \c MulMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]*m2[x]</tt>.
 		  ///
 		  /// \relates MulMap
 		  template<typename M1, typename M2>
 		  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
 		    return MulMap<M1, M2>(m1,m2);
+		  }
 		  /// Quotient of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the quotient
 		  /// of the values of the two given maps.
 		  /// Its \c Key and \c Value types are inherited from \c M1.
 		  /// The \c Key and \c Value of \c M2 must be convertible to those of
 		  /// \c M1.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   DivMap<M1,M2> dm(m1,m2);
 		  /// \endcode
 		  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the divMap()
 		  /// function.
 		  ///
 		  /// \sa AddMap, SubMap, MulMap
 		  template<typename M1, typename M2>
 		  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
 		  };
 		  /// Returns a \c DivMap class
 		  /// This function just returns a \c DivMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]/m2[x]</tt>.
 		  ///
 		  /// \relates DivMap
 		  template<typename M1, typename M2>
 		  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
 		    return DivMap<M1, M2>(m1,m2);
+		  }
 		  /// Shifts a map with a constant.
 		  /// This \ref concepts::ReadMap "read-only map" returns the sum of
 		  /// the given map and a constant value (i.e. it shifts the map with
 		  /// the constant). Its \c Key and \c Value are inherited from \c M.
 		  ///
 		  /// Actually,
 		  /// \code
 		  ///   ShiftMap<M> sh(m,v);
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ConstMap<M::Key, M::Value> cm(v);
 		  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
 		  /// \endcode
 		  ///
 		  /// The simplest way of using this map is through the shiftMap()
 		  /// function.
 		  ///
 		  /// \sa ShiftWriteMap
 		  template<typename M, typename C = typename M::Value>
 		  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M &_m;
 		    C _v;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The undelying map.
 		    /// \param v The constant value.
 		    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m[k]+_v; }
 		  };
 		  /// Shifts a map with a constant (read-write version).
 		  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
 		  /// of the given map and a constant value (i.e. it shifts the map with
 		  /// the constant). Its \c Key and \c Value are inherited from \c M.
 		  /// It makes also possible to write the map.
 		  ///
 		  /// The simplest way of using this map is through the shiftWriteMap()
 		  /// function.
 		  ///
 		  /// \sa ShiftMap
 		  template<typename M, typename C = typename M::Value>
 		  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
 		    M &_m;
 		    C _v;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The undelying map.
 		    /// \param v The constant value.
 		    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m[k]+_v; }
 		    /// \e
 		    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
 		  };
 		  /// Returns a \c ShiftMap class
 		  /// This function just returns a \c ShiftMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values and \c v is
 		  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
 		  /// <tt>m[x]+v</tt>.
 		  ///
 		  /// \relates ShiftMap
 		  template<typename M, typename C>
 		  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
 		    return ShiftMap<M, C>(m,v);
+		  }
 		  /// Returns a \c ShiftWriteMap class
 		  /// This function just returns a \c ShiftWriteMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values and \c v is
 		  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
 		  /// <tt>m[x]+v</tt>.
 		  /// Moreover it makes also possible to write the map.
 		  ///
 		  /// \relates ShiftWriteMap
 		  template<typename M, typename C>
 		  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
 		    return ShiftWriteMap<M, C>(m,v);
+		  }
 		  /// Scales a map with a constant.
 		  /// This \ref concepts::ReadMap "read-only map" returns the value of
 		  /// the given map multiplied from the left side with a constant value.
 		  /// Its \c Key and \c Value are inherited from \c M.
 		  ///
 		  /// Actually,
 		  /// \code
 		  ///   ScaleMap<M> sc(m,v);
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ConstMap<M::Key, M::Value> cm(v);
 		  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
 		  /// \endcode
 		  ///
 		  /// The simplest way of using this map is through the scaleMap()
 		  /// function.
 		  ///
 		  /// \sa ScaleWriteMap
 		  template<typename M, typename C = typename M::Value>
 		  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M &_m;
 		    C _v;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The undelying map.
 		    /// \param v The constant value.
 		    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _v*_m[k]; }
 		  };
 		  /// Scales a map with a constant (read-write version).
 		  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
 		  /// the given map multiplied from the left side with a constant value.
 		  /// Its \c Key and \c Value are inherited from \c M.
 		  /// It can also be used as write map if the \c / operator is defined
 		  /// between \c Value and \c C and the given multiplier is not zero.
 		  ///
 		  /// The simplest way of using this map is through the scaleWriteMap()
 		  /// function.
 		  ///
 		  /// \sa ScaleMap
 		  template<typename M, typename C = typename M::Value>
 		  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
 		    M &_m;
 		    C _v;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The undelying map.
 		    /// \param v The constant value.
 		    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _v*_m[k]; }
 		    /// \e
 		    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
 		  };
 		  /// Returns a \c ScaleMap class
 		  /// This function just returns a \c ScaleMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values and \c v is
 		  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
 		  /// <tt>v*m[x]</tt>.
 		  ///
 		  /// \relates ScaleMap
 		  template<typename M, typename C>
 		  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
 		    return ScaleMap<M, C>(m,v);
+		  }
 		  /// Returns a \c ScaleWriteMap class
 		  /// This function just returns a \c ScaleWriteMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values and \c v is
 		  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
 		  /// <tt>v*m[x]</tt>.
 		  /// Moreover it makes also possible to write the map.
 		  ///
 		  /// \relates ScaleWriteMap
 		  template<typename M, typename C>
 		  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
 		    return ScaleWriteMap<M, C>(m,v);
+		  }
 		  /// Negative of a map
 		  /// This \ref concepts::ReadMap "read-only map" returns the negative
 		  /// of the values of the given map (using the unary \c - operator).
 		  /// Its \c Key and \c Value are inherited from \c M.
 		  ///
 		  /// If M::Value is \c int, \c double etc., then
 		  /// \code
 		  ///   NegMap<M> neg(m);
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ScaleMap<M> neg(m,-1);
 		  /// \endcode
 		  ///
 		  /// The simplest way of using this map is through the negMap()
 		  /// function.
 		  ///
 		  /// \sa NegWriteMap
 		  template<typename M>
 		  class NegMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M& _m;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    NegMap(const M &m) : _m(m) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return -_m[k]; }
 		  };
 		  /// Negative of a map (read-write version)
 		  /// This \ref concepts::ReadWriteMap "read-write map" returns the
 		  /// negative of the values of the given map (using the unary \c -
 		  /// operator).
 		  /// Its \c Key and \c Value are inherited from \c M.
 		  /// It makes also possible to write the map.
 		  ///
 		  /// If M::Value is \c int, \c double etc., then
 		  /// \code
 		  ///   NegWriteMap<M> neg(m);
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ScaleWriteMap<M> neg(m,-1);
 		  /// \endcode
 		  ///
 		  /// The simplest way of using this map is through the negWriteMap()
 		  /// function.
 		  ///
 		  /// \sa NegMap
 		  template<typename M>
 		  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
 		    M &_m;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    NegWriteMap(M &m) : _m(m) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return -_m[k]; }
 		    /// \e
 		    void set(const Key &k, const Value &v) { _m.set(k, -v); }
 		  };
 		  /// Returns a \c NegMap class
 		  /// This function just returns a \c NegMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values, then
 		  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
 		  ///
 		  /// \relates NegMap
 		  template <typename M>
 		  inline NegMap<M> negMap(const M &m) {
 		    return NegMap<M>(m);
+		  }
 		  /// Returns a \c NegWriteMap class
 		  /// This function just returns a \c NegWriteMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values, then
 		  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
 		  /// Moreover it makes also possible to write the map.
 		  ///
 		  /// \relates NegWriteMap
 		  template <typename M>
 		  inline NegWriteMap<M> negWriteMap(M &m) {
 		    return NegWriteMap<M>(m);
+		  }
 		  /// Absolute value of a map
 		  /// This \ref concepts::ReadMap "read-only map" returns the absolute
 		  /// value of the values of the given map.
 		  /// Its \c Key and \c Value are inherited from \c M.
 		  /// \c Value must be comparable to \c 0 and the unary \c -
 		  /// operator must be defined for it, of course.
 		  ///
 		  /// The simplest way of using this map is through the absMap()
 		  /// function.
 		  template<typename M>
 		  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M &_m;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    AbsMap(const M &m) : _m(m) {}
 		    /// \e
 		    Value operator[](const Key &k) const {
 		      Value tmp = _m[k];
 		      return tmp >= 0 ? tmp : -tmp;
+		    }
 		  };
 		  /// Returns an \c AbsMap class
 		  /// This function just returns an \c AbsMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values, then
 		  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
 		  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
 		  /// negative.
 		  ///
 		  /// \relates AbsMap
 		  template<typename M>
 		  inline AbsMap<M> absMap(const M &m) {
 		    return AbsMap<M>(m);
+		  }
 		  /// @}
 		  // Logical maps and map adaptors:
 		  /// \addtogroup maps
 		  /// @{
 		  /// Constant \c true map.
 		  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
 		  /// each key.
 		  ///
 		  /// Note that
 		  /// \code
 		  ///   TrueMap<K> tm;
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ConstMap<K,bool> tm(true);
 		  /// \endcode
 		  ///
 		  /// \sa FalseMap
 		  /// \sa ConstMap
 		  template <typename K>
 		  class TrueMap : public MapBase<K, bool> {
 		  public:
 		    typedef MapBase<K, bool> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Gives back \c true.
 		    Value operator[](const Key&) const { return true; }
 		  };
 		  /// Returns a \c TrueMap class
 		  /// This function just returns a \c TrueMap class.
 		  /// \relates TrueMap
 		  template<typename K>
 		  inline TrueMap<K> trueMap() {
 		    return TrueMap<K>();
+		  }
 		  /// Constant \c false map.
 		  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
 		  /// each key.
 		  ///
 		  /// Note that
 		  /// \code
 		  ///   FalseMap<K> fm;
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ConstMap<K,bool> fm(false);
 		  /// \endcode
 		  ///
 		  /// \sa TrueMap
 		  /// \sa ConstMap
 		  template <typename K>
 		  class FalseMap : public MapBase<K, bool> {
 		  public:
 		    typedef MapBase<K, bool> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Gives back \c false.
 		    Value operator[](const Key&) const { return false; }
 		  };
 		  /// Returns a \c FalseMap class
 		  /// This function just returns a \c FalseMap class.
 		  /// \relates FalseMap
 		  template<typename K>
 		  inline FalseMap<K> falseMap() {
 		    return FalseMap<K>();
+		  }
 		  /// @}
 		  /// \addtogroup map_adaptors
 		  /// @{
 		  /// Logical 'and' of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the logical
 		  /// 'and' of the values of the two given maps.
 		  /// Its \c Key type is inherited from \c M1 and its \c Value type is
 		  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   AndMap<M1,M2> am(m1,m2);
 		  /// \endcode
 		  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the andMap()
 		  /// function.
 		  ///
 		  /// \sa OrMap
 		  /// \sa NotMap, NotWriteMap
 		  template<typename M1, typename M2>
 		  class AndMap : public MapBase<typename M1::Key, bool> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    typedef MapBase<typename M1::Key, bool> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
 		  };
 		  /// Returns an \c AndMap class
 		  /// This function just returns an \c AndMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
 		  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]&&m2[x]</tt>.
 		  ///
 		  /// \relates AndMap
 		  template<typename M1, typename M2>
 		  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
 		    return AndMap<M1, M2>(m1,m2);
+		  }
 		  /// Logical 'or' of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the logical
 		  /// 'or' of the values of the two given maps.
 		  /// Its \c Key type is inherited from \c M1 and its \c Value type is
 		  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   OrMap<M1,M2> om(m1,m2);
 		  /// \endcode
 		  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the orMap()
 		  /// function.
 		  ///
 		  /// \sa AndMap
 		  /// \sa NotMap, NotWriteMap
 		  template<typename M1, typename M2>
 		  class OrMap : public MapBase<typename M1::Key, bool> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    typedef MapBase<typename M1::Key, bool> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
 		  };
 		  /// Returns an \c OrMap class
 		  /// This function just returns an \c OrMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
 		  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]||m2[x]</tt>.
 		  ///
 		  /// \relates OrMap
 		  template<typename M1, typename M2>
 		  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
 		    return OrMap<M1, M2>(m1,m2);
+		  }
 		  /// Logical 'not' of a map
 		  /// This \ref concepts::ReadMap "read-only map" returns the logical
 		  /// negation of the values of the given map.
 		  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
 		  ///
 		  /// The simplest way of using this map is through the notMap()
 		  /// function.
 		  ///
 		  /// \sa NotWriteMap
 		  template <typename M>
 		  class NotMap : public MapBase<typename M::Key, bool> {
 		    const M &_m;
 		  public:
 		    typedef MapBase<typename M::Key, bool> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    NotMap(const M &m) : _m(m) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return !_m[k]; }
 		  };
 		  /// Logical 'not' of a map (read-write version)
 		  /// This \ref concepts::ReadWriteMap "read-write map" returns the
 		  /// logical negation of the values of the given map.
 		  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
 		  /// It makes also possible to write the map. When a value is set,
 		  /// the opposite value is set to the original map.
 		  ///
 		  /// The simplest way of using this map is through the notWriteMap()
 		  /// function.
 		  ///
 		  /// \sa NotMap
 		  template <typename M>
 		  class NotWriteMap : public MapBase<typename M::Key, bool> {
 		    M &_m;
 		  public:
 		    typedef MapBase<typename M::Key, bool> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    NotWriteMap(M &m) : _m(m) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return !_m[k]; }
 		    /// \e
 		    void set(const Key &k, bool v) { _m.set(k, !v); }
 		  };
 		  /// Returns a \c NotMap class
 		  /// This function just returns a \c NotMap class.
 		  ///
 		  /// For example, if \c m is a map with \c bool values, then
 		  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
 		  ///
 		  /// \relates NotMap
 		  template <typename M>
 		  inline NotMap<M> notMap(const M &m) {
 		    return NotMap<M>(m);
+		  }
 		  /// Returns a \c NotWriteMap class
 		  /// This function just returns a \c NotWriteMap class.
 		  ///
 		  /// For example, if \c m is a map with \c bool values, then
 		  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
 		  /// Moreover it makes also possible to write the map.
 		  ///
 		  /// \relates NotWriteMap
 		  template <typename M>
 		  inline NotWriteMap<M> notWriteMap(M &m) {
 		    return NotWriteMap<M>(m);
+		  }
 		  /// Combination of two maps using the \c == operator
 		  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
 		  /// the keys for which the corresponding values of the two maps are
 		  /// equal.
 		  /// Its \c Key type is inherited from \c M1 and its \c Value type is
 		  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   EqualMap<M1,M2> em(m1,m2);
 		  /// \endcode
 		  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the equalMap()
 		  /// function.
 		  ///
 		  /// \sa LessMap
 		  template<typename M1, typename M2>
 		  class EqualMap : public MapBase<typename M1::Key, bool> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    typedef MapBase<typename M1::Key, bool> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
 		  };
 		  /// Returns an \c EqualMap class
 		  /// This function just returns an \c EqualMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are maps with keys and values of
 		  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]==m2[x]</tt>.
 		  ///
 		  /// \relates EqualMap
 		  template<typename M1, typename M2>
 		  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
 		    return EqualMap<M1, M2>(m1,m2);
+		  }
 		  /// Combination of two maps using the \c < operator
 		  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
 		  /// the keys for which the corresponding value of the first map is
 		  /// less then the value of the second map.
 		  /// Its \c Key type is inherited from \c M1 and its \c Value type is
 		  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   LessMap<M1,M2> lm(m1,m2);
 		  /// \endcode
 		  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the lessMap()
 		  /// function.
 		  ///
 		  /// \sa EqualMap
 		  template<typename M1, typename M2>
 		  class LessMap : public MapBase<typename M1::Key, bool> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    typedef MapBase<typename M1::Key, bool> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
 		  };
 		  /// Returns an \c LessMap class
 		  /// This function just returns an \c LessMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are maps with keys and values of
 		  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]<m2[x]</tt>.
 		  ///
 		  /// \relates LessMap
 		  template<typename M1, typename M2>
 		  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
 		    return LessMap<M1, M2>(m1,m2);
+		  }
 		  namespace _maps_bits {
 		    template <typename _Iterator, typename Enable = void>
 		    struct IteratorTraits {
 		      typedef typename std::iterator_traits<_Iterator>::value_type Value;
 		    };
 		    template <typename _Iterator>
 		    struct IteratorTraits<_Iterator,
 		      typename exists<typename _Iterator::container_type>::type>
+		    {
 		      typedef typename _Iterator::container_type::value_type Value;
 		    };
+		  }
 		  /// @}
 		  /// \addtogroup maps
 		  /// @{
 		  /// \brief Writable bool map for logging each \c true assigned element
 		  ///
 		  /// A \ref concepts::WriteMap "writable" bool map for logging
 		  /// each \c true assigned element, i.e it copies subsequently each
 		  /// keys set to \c true to the given iterator.
 		  /// The most important usage of it is storing certain nodes or arcs
 		  /// that were marked \c true by an algorithm.
 		  ///
 		  /// There are several algorithms that provide solutions through bool
 		  /// maps and most of them assign \c true at most once for each key.
 		  /// In these cases it is a natural request to store each \c true
 		  /// assigned elements (in order of the assignment), which can be
 		  /// easily done with LoggerBoolMap.
 		  ///
 		  /// The simplest way of using this map is through the loggerBoolMap()
 		  /// function.
 		  ///
 		  /// \tparam It The type of the iterator.
 		  /// \tparam Ke The key type of the map. The default value set
 		  /// according to the iterator type should work in most cases.
 		  ///
 		  /// \note The container of the iterator must contain enough space
 		  /// for the elements or the iterator should be an inserter iterator.
 		#ifdef DOXYGEN
 		  template <typename It, typename Ke>
 		#else
 		  template <typename It,
 		            typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
 		#endif
 		  class LoggerBoolMap {
 		  public:
 		    typedef It Iterator;
 		    typedef Ke Key;
 		    typedef bool Value;
 		    /// Constructor
 		    LoggerBoolMap(Iterator it)
 		      : _begin(it), _end(it) {}
 		    /// Gives back the given iterator set for the first key
 		    Iterator begin() const {
 		      return _begin;
+		    }
 		    /// Gives back the the 'after the last' iterator
 		    Iterator end() const {
 		      return _end;
+		    }
 		    /// The set function of the map
 		    void set(const Key& key, Value value) {
 		      if (value) {
 		        *_end++ = key;
+		      }
+		    }
 		  private:
 		    Iterator _begin;
 		    Iterator _end;
 		  };
 		  /// Returns a \c LoggerBoolMap class
 		  /// This function just returns a \c LoggerBoolMap class.
 		  ///
 		  /// The most important usage of it is storing certain nodes or arcs
 		  /// that were marked \c true by an algorithm.
 		  /// For example it makes easier to store the nodes in the processing
 		  /// order of Dfs algorithm, as the following examples show.
 		  /// \code
 		  ///   std::vector<Node> v;
 		  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
 		  /// \endcode
 		  /// \code
 		  ///   std::vector<Node> v(countNodes(g));
 		  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
 		  /// \endcode
 		  ///
 		  /// \note The container of the iterator must contain enough space
 		  /// for the elements or the iterator should be an inserter iterator.
 		  ///
 		  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
 		  /// it cannot be used when a readable map is needed, for example as
 		  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
 		  ///
 		  /// \relates LoggerBoolMap
 		  template<typename Iterator>
 		  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
 		    return LoggerBoolMap<Iterator>(it);
+		  }
 		  /// @}
 		  /// \addtogroup graph_maps
 		  /// @{
 		  /// Provides an immutable and unique id for each item in the graph.
 		  /// The IdMap class provides a unique and immutable id for each item of the
 		  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
 		  /// different items (nodes) get different ids <li>\b immutable: the id of an
 		  /// item (node) does not change (even if you delete other nodes).  </ul>
 		  /// Through this map you get access (i.e. can read) the inner id values of
 		  /// the items stored in the graph. This map can be inverted with its member
 		  /// class \c InverseMap or with the \c operator() member.
 		  ///
 		  template <typename _Graph, typename _Item>
 		  class IdMap {
 		  public:
 		    typedef _Graph Graph;
 		    typedef int Value;
 		    typedef _Item Item;
 		    typedef _Item Key;
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor of the map.
 		    explicit IdMap(const Graph& graph) : _graph(&graph) {}
 		    /// \brief Gives back the \e id of the item.
 		    ///
 		    /// Gives back the immutable and unique \e id of the item.
 		    int operator[](const Item& item) const { return _graph->id(item);}
 		    /// \brief Gives back the item by its id.
 		    ///
 		    /// Gives back the item by its id.
 		    Item operator()(int id) { return _graph->fromId(id, Item()); }
 		  private:
 		    const Graph* _graph;
 		  public:
 		    /// \brief The class represents the inverse of its owner (IdMap).
 		    ///
 		    /// The class represents the inverse of its owner (IdMap).
 		    /// \see inverse()
 		    class InverseMap {
 		    public:
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor for creating an id-to-item map.
 		      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor for creating an id-to-item map.
 		      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
 		      /// \brief Gives back the given item from its id.
 		      ///
 		      /// Gives back the given item from its id.
 		      ///
 		      Item operator[](int id) const { return _graph->fromId(id, Item());}
 		    private:
 		      const Graph* _graph;
 		    };
 		    /// \brief Gives back the inverse of the map.
 		    ///
 		    /// Gives back the inverse of the IdMap.
 		    InverseMap inverse() const { return InverseMap(*_graph);}
 		  };
 		  /// \brief General invertable graph-map type.
 		  /// This type provides simple invertable graph-maps.
 		  /// The InvertableMap wraps an arbitrary ReadWriteMap
 		  /// and if a key is set to a new value then store it
 		  /// in the inverse map.
 		  ///
 		  /// The values of the map can be accessed
 		  /// with stl compatible forward iterator.
 		  ///
 		  /// \tparam _Graph The graph type.
 		  /// \tparam _Item The item type of the graph.
 		  /// \tparam _Value The value type of the map.
 		  ///
 		  /// \see IterableValueMap
 		  template <typename _Graph, typename _Item, typename _Value>
 		  class InvertableMap
 		    : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
 		  private:
 		    typedef typename ItemSetTraits<_Graph, _Item>::
 		    template Map<_Value>::Type Map;
 		    typedef _Graph Graph;
 		    typedef std::map<_Value, _Item> Container;
 		    Container _inv_map;
 		  public:
 		    /// The key type of InvertableMap (Node, Arc, Edge).
 		    typedef typename Map::Key Key;
 		    /// The value type of the InvertableMap.
 		    typedef typename Map::Value Value;
 		    /// \brief Constructor.
 		    ///
 		    /// Construct a new InvertableMap for the graph.
 		    ///
 		    explicit InvertableMap(const Graph& graph) : Map(graph) {}
 		    /// \brief Forward iterator for values.
 		    ///
 		    /// This iterator is an stl compatible forward
 		    /// iterator on the values of the map. The values can
 		    /// be accessed in the [beginValue, endValue) range.
 		    ///
 		    class ValueIterator
 		      : public std::iterator<std::forward_iterator_tag, Value> {
 		      friend class InvertableMap;
 		    private:
 		      ValueIterator(typename Container::const_iterator _it)
 		        : it(_it) {}
 		    public:
 		      ValueIterator() {}
 		      ValueIterator& operator++() { ++it; return *this; }
 		      ValueIterator operator++(int) {
 		        ValueIterator tmp(*this);
 		        operator++();
 		        return tmp;
+		      }
 		      const Value& operator*() const { return it->first; }
 		      const Value* operator->() const { return &(it->first); }
 		      bool operator==(ValueIterator jt) const { return it == jt.it; }
 		      bool operator!=(ValueIterator jt) const { return it != jt.it; }
 		    private:
 		      typename Container::const_iterator it;
 		    };
 		    /// \brief Returns an iterator to the first value.
 		    ///
 		    /// Returns an stl compatible iterator to the
 		    /// first value of the map. The values of the
 		    /// map can be accessed in the [beginValue, endValue)
 		    /// range.
 		    ValueIterator beginValue() const {
 		      return ValueIterator(_inv_map.begin());
+		    }
 		    /// \brief Returns an iterator after the last value.
 		    ///
 		    /// Returns an stl compatible iterator after the
 		    /// last value of the map. The values of the
 		    /// map can be accessed in the [beginValue, endValue)
 		    /// range.
 		    ValueIterator endValue() const {
 		      return ValueIterator(_inv_map.end());
+		    }
 		    /// \brief The setter function of the map.
 		    ///
 		    /// Sets the mapped value.
 		    void set(const Key& key, const Value& val) {
 		      Value oldval = Map::operator[](key);
 		      typename Container::iterator it = _inv_map.find(oldval);
 		      if (it != _inv_map.end() && it->second == key) {
 		        _inv_map.erase(it);
+		      }
 		      _inv_map.insert(make_pair(val, key));
 		      Map::set(key, val);
+		    }
 		    /// \brief The getter function of the map.
 		    ///
 		    /// It gives back the value associated with the key.
 		    typename MapTraits<Map>::ConstReturnValue
 		    operator[](const Key& key) const {
 		      return Map::operator[](key);
+		    }
 		    /// \brief Gives back the item by its value.
 		    ///
 		    /// Gives back the item by its value.
 		    Key operator()(const Value& key) const {
 		      typename Container::const_iterator it = _inv_map.find(key);
 		      return it != _inv_map.end() ? it->second : INVALID;
+		    }
 		  protected:
 		    /// \brief Erase the key from the map.
 		    ///
 		    /// Erase the key to the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void erase(const Key& key) {
 		      Value val = Map::operator[](key);
 		      typename Container::iterator it = _inv_map.find(val);
 		      if (it != _inv_map.end() && it->second == key) {
 		        _inv_map.erase(it);
+		      }
 		      Map::erase(key);
+		    }
 		    /// \brief Erase more keys from the map.
 		    ///
 		    /// Erase more keys from the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void erase(const std::vector<Key>& keys) {
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        Value val = Map::operator[](keys[i]);
 		        typename Container::iterator it = _inv_map.find(val);
 		        if (it != _inv_map.end() && it->second == keys[i]) {
 		          _inv_map.erase(it);
+		        }
+		      }
 		      Map::erase(keys);
+		    }
 		    /// \brief Clear the keys from the map and inverse map.
 		    ///
 		    /// Clear the keys from the map and inverse map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void clear() {
 		      _inv_map.clear();
 		      Map::clear();
+		    }
 		  public:
 		    /// \brief The inverse map type.
 		    ///
 		    /// The inverse of this map. The subscript operator of the map
 		    /// gives back always the item what was last assigned to the value.
 		    class InverseMap {
 		    public:
 		      /// \brief Constructor of the InverseMap.
 		      ///
 		      /// Constructor of the InverseMap.
 		      explicit InverseMap(const InvertableMap& inverted)
 		        : _inverted(inverted) {}
 		      /// The value type of the InverseMap.
 		      typedef typename InvertableMap::Key Value;
 		      /// The key type of the InverseMap.
 		      typedef typename InvertableMap::Value Key;
 		      /// \brief Subscript operator.
 		      ///
 		      /// Subscript operator. It gives back always the item
 		      /// what was last assigned to the value.
 		      Value operator[](const Key& key) const {
 		        return _inverted(key);
+		      }
 		    private:
 		      const InvertableMap& _inverted;
 		    };
 		    /// \brief It gives back the just readable inverse map.
 		    ///
 		    /// It gives back the just readable inverse map.
 		    InverseMap inverse() const {
 		      return InverseMap(*this);
+		    }
 		  };
 		  /// \brief Provides a mutable, continuous and unique descriptor for each
 		  /// item in the graph.
 		  ///
 		  /// The DescriptorMap class provides a unique and continuous (but mutable)
 		  /// descriptor (id) for each item of the same type (e.g. node) in the
 		  /// graph. This id is <ul><li>\b unique: different items (nodes) get
 		  /// different ids <li>\b continuous: the range of the ids is the set of
 		  /// integers between 0 and \c n-1, where \c n is the number of the items of
 		  /// this type (e.g. nodes) (so the id of a node can change if you delete an
 		  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
 		  /// with its member class \c InverseMap, or with the \c operator() member.
 		  ///
 		  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
 		  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
 		  /// Edge.
 		  template <typename _Graph, typename _Item>
 		  class DescriptorMap
 		    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
 		    typedef _Item Item;
 		    typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
 		  public:
 		    /// The graph class of DescriptorMap.
 		    typedef _Graph Graph;
 		    /// The key type of DescriptorMap (Node, Arc, Edge).
 		    typedef typename Map::Key Key;
 		    /// The value type of DescriptorMap.
 		    typedef typename Map::Value Value;
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor for descriptor map.
 		    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
 		      Item it;
 		      const typename Map::Notifier* nf = Map::notifier();
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        Map::set(it, _inv_map.size());
 		        _inv_map.push_back(it);
+		      }
+		    }
 		  protected:
 		    /// \brief Add a new key to the map.
 		    ///
 		    /// Add a new key to the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void add(const Item& item) {
 		      Map::add(item);
 		      Map::set(item, _inv_map.size());
 		      _inv_map.push_back(item);
+		    }
 		    /// \brief Add more new keys to the map.
 		    ///
 		    /// Add more new keys to the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void add(const std::vector<Item>& items) {
 		      Map::add(items);
 		      for (int i = 0; i < int(items.size()); ++i) {
 		        Map::set(items[i], _inv_map.size());
 		        _inv_map.push_back(items[i]);
+		      }
+		    }
 		    /// \brief Erase the key from the map.
 		    ///
 		    /// Erase the key from the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void erase(const Item& item) {
 		      Map::set(_inv_map.back(), Map::operator[](item));
 		      _inv_map[Map::operator[](item)] = _inv_map.back();
 		      _inv_map.pop_back();
 		      Map::erase(item);
+		    }
 		    /// \brief Erase more keys from the map.
 		    ///
 		    /// Erase more keys from the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void erase(const std::vector<Item>& items) {
 		      for (int i = 0; i < int(items.size()); ++i) {
 		        Map::set(_inv_map.back(), Map::operator[](items[i]));
 		        _inv_map[Map::operator[](items[i])] = _inv_map.back();
 		        _inv_map.pop_back();
+		      }
 		      Map::erase(items);
+		    }
 		    /// \brief Build the unique map.
 		    ///
 		    /// Build the unique map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void build() {
 		      Map::build();
 		      Item it;
 		      const typename Map::Notifier* nf = Map::notifier();
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        Map::set(it, _inv_map.size());
 		        _inv_map.push_back(it);
+		      }
+		    }
 		    /// \brief Clear the keys from the map.
 		    ///
 		    /// Clear the keys from the map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void clear() {
 		      _inv_map.clear();
 		      Map::clear();
+		    }
 		  public:
 		    /// \brief Returns the maximal value plus one.
 		    ///
 		    /// Returns the maximal value plus one in the map.
 		    unsigned int size() const {
 		      return _inv_map.size();
+		    }
 		    /// \brief Swaps the position of the two items in the map.
 		    ///
 		    /// Swaps the position of the two items in the map.
 		    void swap(const Item& p, const Item& q) {
 		      int pi = Map::operator[](p);
 		      int qi = Map::operator[](q);
 		      Map::set(p, qi);
 		      _inv_map[qi] = p;
 		      Map::set(q, pi);
 		      _inv_map[pi] = q;
+		    }
 		    /// \brief Gives back the \e descriptor of the item.
 		    ///
 		    /// Gives back the mutable and unique \e descriptor of the map.
 		    int operator[](const Item& item) const {
 		      return Map::operator[](item);
+		    }
 		    /// \brief Gives back the item by its descriptor.
 		    ///
 		    /// Gives back th item by its descriptor.
 		    Item operator()(int id) const {
 		      return _inv_map[id];
+		    }
 		  private:
 		    typedef std::vector<Item> Container;
 		    Container _inv_map;
 		  public:
 		    /// \brief The inverse map type of DescriptorMap.
 		    ///
 		    /// The inverse map type of DescriptorMap.
 		    class InverseMap {
 		    public:
 		      /// \brief Constructor of the InverseMap.
 		      ///
 		      /// Constructor of the InverseMap.
 		      explicit InverseMap(const DescriptorMap& inverted)
 		        : _inverted(inverted) {}
 		      /// The value type of the InverseMap.
 		      typedef typename DescriptorMap::Key Value;
 		      /// The key type of the InverseMap.
 		      typedef typename DescriptorMap::Value Key;
 		      /// \brief Subscript operator.
 		      ///
 		      /// Subscript operator. It gives back the item
 		      /// that the descriptor belongs to currently.
 		      Value operator[](const Key& key) const {
 		        return _inverted(key);
+		      }
 		      /// \brief Size of the map.
 		      ///
 		      /// Returns the size of the map.
 		      unsigned int size() const {
 		        return _inverted.size();
+		      }
 		    private:
 		      const DescriptorMap& _inverted;
 		    };
 		    /// \brief Gives back the inverse of the map.
 		    ///
 		    /// Gives back the inverse of the map.
 		    const InverseMap inverse() const {
 		      return InverseMap(*this);
+		    }
 		  };
 		  /// \brief Returns the source of the given arc.
 		  ///
 		  /// The SourceMap gives back the source Node of the given arc.
 		  /// \see TargetMap
 		  template <typename Digraph>
 		  class SourceMap {
 		  public:
 		    typedef typename Digraph::Node Value;
 		    typedef typename Digraph::Arc Key;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \param digraph The digraph that the map belongs to.
 		    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
 		    /// \brief The subscript operator.
 		    ///
 		    /// The subscript operator.
 		    /// \param arc The arc
 		    /// \return The source of the arc
 		    Value operator[](const Key& arc) const {
 		      return _digraph.source(arc);
+		    }
 		  private:
 		    const Digraph& _digraph;
 		  };
 		  /// \brief Returns a \c SourceMap class.
 		  ///
 		  /// This function just returns an \c SourceMap class.
 		  /// \relates SourceMap
 		  template <typename Digraph>
 		  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
 		    return SourceMap<Digraph>(digraph);
+		  }
 		  /// \brief Returns the target of the given arc.
 		  ///
 		  /// The TargetMap gives back the target Node of the given arc.
 		  /// \see SourceMap
 		  template <typename Digraph>
 		  class TargetMap {
 		  public:
 		    typedef typename Digraph::Node Value;
 		    typedef typename Digraph::Arc Key;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \param digraph The digraph that the map belongs to.
 		    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
 		    /// \brief The subscript operator.
 		    ///
 		    /// The subscript operator.
 		    /// \param e The arc
 		    /// \return The target of the arc
 		    Value operator[](const Key& e) const {
 		      return _digraph.target(e);
+		    }
 		  private:
 		    const Digraph& _digraph;
 		  };
 		  /// \brief Returns a \c TargetMap class.
 		  ///
 		  /// This function just returns a \c TargetMap class.
 		  /// \relates TargetMap
 		  template <typename Digraph>
 		  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
 		    return TargetMap<Digraph>(digraph);
+		  }
 		  /// \brief Returns the "forward" directed arc view of an edge.
 		  ///
 		  /// Returns the "forward" directed arc view of an edge.
 		  /// \see BackwardMap
 		  template <typename Graph>
 		  class ForwardMap {
 		  public:
 		    typedef typename Graph::Arc Value;
 		    typedef typename Graph::Edge Key;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \param graph The graph that the map belongs to.
 		    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
 		    /// \brief The subscript operator.
 		    ///
 		    /// The subscript operator.
 		    /// \param key An edge
 		    /// \return The "forward" directed arc view of edge
 		    Value operator[](const Key& key) const {
 		      return _graph.direct(key, true);
+		    }
 		  private:
 		    const Graph& _graph;
 		  };
 		  /// \brief Returns a \c ForwardMap class.
 		  ///
 		  /// This function just returns an \c ForwardMap class.
 		  /// \relates ForwardMap
 		  template <typename Graph>
 		  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
 		    return ForwardMap<Graph>(graph);
+		  }
 		  /// \brief Returns the "backward" directed arc view of an edge.
 		  ///
 		  /// Returns the "backward" directed arc view of an edge.
 		  /// \see ForwardMap
 		  template <typename Graph>
 		  class BackwardMap {
 		  public:
 		    typedef typename Graph::Arc Value;
 		    typedef typename Graph::Edge Key;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \param graph The graph that the map belongs to.
 		    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
 		    /// \brief The subscript operator.
 		    ///
 		    /// The subscript operator.
 		    /// \param key An edge
 		    /// \return The "backward" directed arc view of edge
 		    Value operator[](const Key& key) const {
 		      return _graph.direct(key, false);
+		    }
 		  private:
 		    const Graph& _graph;
 		  };
 		  /// \brief Returns a \c BackwardMap class
 		  /// This function just returns a \c BackwardMap class.
 		  /// \relates BackwardMap
 		  template <typename Graph>
 		  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
 		    return BackwardMap<Graph>(graph);
+		  }
 		  /// \brief Potential difference map
 		  ///
 		  /// If there is an potential map on the nodes then we
 		  /// can get an arc map as we get the substraction of the
 		  /// values of the target and source.
 		  template <typename Digraph, typename NodeMap>
 		  class PotentialDifferenceMap {
 		  public:
 		    typedef typename Digraph::Arc Key;
 		    typedef typename NodeMap::Value Value;
 		    /// \brief Constructor
 		    ///
 		    /// Contructor of the map
 		    explicit PotentialDifferenceMap(const Digraph& digraph,
 		                                    const NodeMap& potential)
 		      : _digraph(digraph), _potential(potential) {}
 		    /// \brief Const subscription operator
 		    ///
 		    /// Const subscription operator
 		    Value operator[](const Key& arc) const {
 		      return _potential[_digraph.target(arc)] -
 		        _potential[_digraph.source(arc)];
+		    }
 		  private:
 		    const Digraph& _digraph;
 		    const NodeMap& _potential;
 		  };
 		  /// \brief Returns a PotentialDifferenceMap.
 		  ///
 		  /// This function just returns a PotentialDifferenceMap.
 		  /// \relates PotentialDifferenceMap
 		  template <typename Digraph, typename NodeMap>
 		  PotentialDifferenceMap<Digraph, NodeMap>
 		  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
 		    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
+		  }
 		  /// \brief Map of the node in-degrees.
 		  ///
 		  /// This map returns the in-degree of a node. Once it is constructed,
 		  /// the degrees are stored in a standard NodeMap, so each query is done
 		  /// in constant time. On the other hand, the values are updated automatically
 		  /// whenever the digraph changes.
 		  ///
 		  /// \warning Besides addNode() and addArc(), a digraph structure may provide
 		  /// alternative ways to modify the digraph. The correct behavior of InDegMap
 		  /// is not guarantied if these additional features are used. For example
 		  /// the functions \ref ListDigraph::changeSource() "changeSource()",
 		  /// \ref ListDigraph::changeTarget() "changeTarget()" and
 		  /// \ref ListDigraph::reverseArc() "reverseArc()"
 		  /// of \ref ListDigraph will \e not update the degree values correctly.
 		  ///
 		  /// \sa OutDegMap
 		  template <typename _Digraph>
 		  class InDegMap
 		    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
 		      ::ItemNotifier::ObserverBase {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef int Value;
 		    typedef typename Digraph::Node Key;
 		    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
 		    ::ItemNotifier::ObserverBase Parent;
 		  private:
 		    class AutoNodeMap
 		      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
 		    public:
 		      typedef typename ItemSetTraits<Digraph, Key>::
 		      template Map<int>::Type Parent;
 		      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
 		      virtual void add(const Key& key) {
 		        Parent::add(key);
 		        Parent::set(key, 0);
+		      }
 		      virtual void add(const std::vector<Key>& keys) {
 		        Parent::add(keys);
 		        for (int i = 0; i < int(keys.size()); ++i) {
 		          Parent::set(keys[i], 0);
+		        }
+		      }
 		      virtual void build() {
 		        Parent::build();
 		        Key it;
 		        typename Parent::Notifier* nf = Parent::notifier();
 		        for (nf->first(it); it != INVALID; nf->next(it)) {
 		          Parent::set(it, 0);
+		        }
+		      }
 		    };
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor for creating in-degree map.
 		    explicit InDegMap(const Digraph& digraph)
 		      : _digraph(digraph), _deg(digraph) {
 		      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = countInArcs(_digraph, it);
+		      }
+		    }
 		    /// Gives back the in-degree of a Node.
 		    int operator[](const Key& key) const {
 		      return _deg[key];
+		    }
 		  protected:
 		    typedef typename Digraph::Arc Arc;
 		    virtual void add(const Arc& arc) {
 		      ++_deg[_digraph.target(arc)];
+		    }
 		    virtual void add(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        ++_deg[_digraph.target(arcs[i])];
+		      }
+		    }
 		    virtual void erase(const Arc& arc) {
 		      --_deg[_digraph.target(arc)];
+		    }
 		    virtual void erase(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        --_deg[_digraph.target(arcs[i])];
+		      }
+		    }
 		    virtual void build() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = countInArcs(_digraph, it);
+		      }
+		    }
 		    virtual void clear() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = 0;
+		      }
+		    }
 		  private:
 		    const Digraph& _digraph;
 		    AutoNodeMap _deg;
 		  };
 		  /// \brief Map of the node out-degrees.
 		  ///
 		  /// This map returns the out-degree of a node. Once it is constructed,
 		  /// the degrees are stored in a standard NodeMap, so each query is done
 		  /// in constant time. On the other hand, the values are updated automatically
 		  /// whenever the digraph changes.
 		  ///
 		  /// \warning Besides addNode() and addArc(), a digraph structure may provide
 		  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
 		  /// is not guarantied if these additional features are used. For example
 		  /// the functions \ref ListDigraph::changeSource() "changeSource()",
 		  /// \ref ListDigraph::changeTarget() "changeTarget()" and
 		  /// \ref ListDigraph::reverseArc() "reverseArc()"
 		  /// of \ref ListDigraph will \e not update the degree values correctly.
 		  ///
 		  /// \sa InDegMap
 		  template <typename _Digraph>
 		  class OutDegMap
 		    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
 		      ::ItemNotifier::ObserverBase {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef int Value;
 		    typedef typename Digraph::Node Key;
 		    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
 		    ::ItemNotifier::ObserverBase Parent;
 		  private:
 		    class AutoNodeMap
 		      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
 		    public:
 		      typedef typename ItemSetTraits<Digraph, Key>::
 		      template Map<int>::Type Parent;
 		      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
 		      virtual void add(const Key& key) {
 		        Parent::add(key);
 		        Parent::set(key, 0);
+		      }
 		      virtual void add(const std::vector<Key>& keys) {
 		        Parent::add(keys);
 		        for (int i = 0; i < int(keys.size()); ++i) {
 		          Parent::set(keys[i], 0);
+		        }
+		      }
 		      virtual void build() {
 		        Parent::build();
 		        Key it;
 		        typename Parent::Notifier* nf = Parent::notifier();
 		        for (nf->first(it); it != INVALID; nf->next(it)) {
 		          Parent::set(it, 0);
+		        }
+		      }
 		    };
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor for creating out-degree map.
 		    explicit OutDegMap(const Digraph& digraph)
 		      : _digraph(digraph), _deg(digraph) {
 		      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = countOutArcs(_digraph, it);
+		      }
+		    }
 		    /// Gives back the out-degree of a Node.
 		    int operator[](const Key& key) const {
 		      return _deg[key];
+		    }
 		  protected:
 		    typedef typename Digraph::Arc Arc;
 		    virtual void add(const Arc& arc) {
 		      ++_deg[_digraph.source(arc)];
+		    }
 		    virtual void add(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        ++_deg[_digraph.source(arcs[i])];
+		      }
+		    }
 		    virtual void erase(const Arc& arc) {
 		      --_deg[_digraph.source(arc)];
+		    }
 		    virtual void erase(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        --_deg[_digraph.source(arcs[i])];
+		      }
+		    }
 		    virtual void build() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = countOutArcs(_digraph, it);
+		      }
+		    }
 		    virtual void clear() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = 0;
+		      }
+		    }
 		  private:
 		    const Digraph& _digraph;
 		    AutoNodeMap _deg;
 		  };
 		  /// @}
+		}
 		#endif // LEMON_MAPS_H

0 comments (0 inline)

RhodeCode

Login to your account

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#ifndef LEMON_BITS_BASE_EXTENDER_H
20	20	#define LEMON_BITS_BASE_EXTENDER_H
21	21
22	22	#include <lemon/core.h>
23	23	#include <lemon/error.h>
24	24
25	25	#include <lemon/bits/map_extender.h>
26	26	#include <lemon/bits/default_map.h>
27	27
28	28	#include <lemon/concept_check.h>
29	29	#include <lemon/concepts/maps.h>
30	30
31		///\ingroup digraphbits
32		///\file
33		///\~~brief~~ ~~Extenders for the digraph types~~
	31	//\ingroup digraphbits
	32	//\file
	33	//\brief Extenders for the digraph types
34	34	namespace lemon {
35	35
36		/// \ingroup digraphbits
37		///
38		/// \~~brief~~ ~~BaseDigraph to BaseGraph extender~~
	36	// \ingroup digraphbits
	37	//
	38	// \brief BaseDigraph to BaseGraph extender
39	39	template <typename Base>
40	40	class UndirDigraphExtender : public Base {
41	41
42	42	public:
43	43
44	44	typedef Base Parent;
45	45	typedef typename Parent::Arc Edge;
46	46	typedef typename Parent::Node Node;
47	47
48	48	typedef True UndirectedTag;
49	49
50	50	class Arc : public Edge {
51	51	friend class UndirDigraphExtender;
52	52
53	53	protected:
54	54	bool forward;
55	55
56	56	Arc(const Edge &ue, bool _forward) :
57	57	Edge(ue), forward(_forward) {}
58	58
59	59	public:
60	60	Arc() {}
61	61
62	62	// Invalid arc constructor
63	63	Arc(Invalid i) : Edge(i), forward(true) {}
64	64
65	65	bool operator==(const Arc &that) const {
66	66	return forward==that.forward && Edge(*this)==Edge(that);
67	67	}
68	68	bool operator!=(const Arc &that) const {
69	69	return forward!=that.forward \|\| Edge(*this)!=Edge(that);
70	70	}
71	71	bool operator<(const Arc &that) const {
72	72	return forward<that.forward \|\|
73	73	(!(that.forward<forward) && Edge(*this)<Edge(that));
74	74	}
75	75	};
76	76
77		/// First node of the edge
	77	// First node of the edge
78	78	Node u(const Edge &e) const {
79	79	return Parent::source(e);
80	80	}
81	81
82		/// Source of the given arc
	82	// Source of the given arc
83	83	Node source(const Arc &e) const {
84	84	return e.forward ? Parent::source(e) : Parent::target(e);
85	85	}
86	86
87		/// Second node of the edge
	87	// Second node of the edge
88	88	Node v(const Edge &e) const {
89	89	return Parent::target(e);
90	90	}
91	91
92		/// Target of the given arc
	92	// Target of the given arc
93	93	Node target(const Arc &e) const {
94	94	return e.forward ? Parent::target(e) : Parent::source(e);
95	95	}
96	96
97		/// \brief Directed arc from an edge.
98		///
99		/// Returns a directed arc corresponding to the specified edge.
100		/// If the given bool is true, the first node of the given edge and
101		/// ~~the~~ ~~source node of the returned~~ arc ~~are~~ ~~the~~ ~~same~~.
	97	// \brief Directed arc from an edge.
	98	//
	99	// Returns a directed arc corresponding to the specified edge.
	100	// If the given bool is true, the first node of the given edge and
	101	// the source node of the returned arc are the same.
102	102	static Arc direct(const Edge &e, bool d) {
103	103	return Arc(e, d);
104	104	}
105	105
106		/// Returns whether the given directed arc has the same orientation
107		/// as the corresponding edge.
	106	// Returns whether the given directed arc has the same orientation
	107	// as the corresponding edge.
108	108	static bool direction(const Arc &a) { return a.forward; }
109	109
110	110	using Parent::first;
111	111	using Parent::next;
112	112
113	113	void first(Arc &e) const {
114	114	Parent::first(e);
115	115	e.forward=true;
116	116	}
117	117
118	118	void next(Arc &e) const {
119	119	if( e.forward ) {
120	120	e.forward = false;
121	121	}
122	122	else {
123	123	Parent::next(e);
124	124	e.forward = true;
125	125	}
126	126	}
127	127
128	128	void firstOut(Arc &e, const Node &n) const {
129	129	Parent::firstIn(e,n);
130	130	if( Edge(e) != INVALID ) {
131	131	e.forward = false;
132	132	}
133	133	else {
134	134	Parent::firstOut(e,n);
135	135	e.forward = true;
136	136	}
137	137	}
138	138	void nextOut(Arc &e) const {
139	139	if( ! e.forward ) {
140	140	Node n = Parent::target(e);
141	141	Parent::nextIn(e);
142	142	if( Edge(e) == INVALID ) {
143	143	Parent::firstOut(e, n);
144	144	e.forward = true;
145	145	}
146	146	}
147	147	else {
148	148	Parent::nextOut(e);
149	149	}
150	150	}
151	151
152	152	void firstIn(Arc &e, const Node &n) const {
153	153	Parent::firstOut(e,n);
154	154	if( Edge(e) != INVALID ) {
155	155	e.forward = false;
156	156	}
157	157	else {
158	158	Parent::firstIn(e,n);
159	159	e.forward = true;
160	160	}
161	161	}
162	162	void nextIn(Arc &e) const {
163	163	if( ! e.forward ) {
164	164	Node n = Parent::source(e);
165	165	Parent::nextOut(e);
166	166	if( Edge(e) == INVALID ) {
167	167	Parent::firstIn(e, n);
168	168	e.forward = true;
169	169	}
170	170	}
171	171	else {
172	172	Parent::nextIn(e);
173	173	}
174	174	}
175	175
176	176	void firstInc(Edge &e, bool &d, const Node &n) const {
177	177	d = true;
178	178	Parent::firstOut(e, n);
179	179	if (e != INVALID) return;
180	180	d = false;
181	181	Parent::firstIn(e, n);
182	182	}
183	183
184	184	void nextInc(Edge &e, bool &d) const {
185	185	if (d) {
186	186	Node s = Parent::source(e);
187	187	Parent::nextOut(e);
188	188	if (e != INVALID) return;
189	189	d = false;
190	190	Parent::firstIn(e, s);
191	191	} else {
192	192	Parent::nextIn(e);
193	193	}
194	194	}
195	195
196	196	Node nodeFromId(int ix) const {
197	197	return Parent::nodeFromId(ix);
198	198	}
199	199
200	200	Arc arcFromId(int ix) const {
201	201	return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
202	202	}
203	203
204	204	Edge edgeFromId(int ix) const {
205	205	return Parent::arcFromId(ix);
206	206	}
207	207
208	208	int id(const Node &n) const {
209	209	return Parent::id(n);
210	210	}
211	211
212	212	int id(const Edge &e) const {
213	213	return Parent::id(e);
214	214	}
215	215
216	216	int id(const Arc &e) const {
217	217	return 2 * Parent::id(e) + int(e.forward);
218	218	}
219	219
220	220	int maxNodeId() const {
221	221	return Parent::maxNodeId();
222	222	}
223	223
224	224	int maxArcId() const {
225	225	return 2 * Parent::maxArcId() + 1;
226	226	}
227	227
228	228	int maxEdgeId() const {
229	229	return Parent::maxArcId();
230	230	}
231	231
232	232	int arcNum() const {
233	233	return 2 * Parent::arcNum();
234	234	}
235	235
236	236	int edgeNum() const {
237	237	return Parent::arcNum();
238	238	}
239	239
240	240	Arc findArc(Node s, Node t, Arc p = INVALID) const {
241	241	if (p == INVALID) {
242	242	Edge arc = Parent::findArc(s, t);
243	243	if (arc != INVALID) return direct(arc, true);
244	244	arc = Parent::findArc(t, s);
245	245	if (arc != INVALID) return direct(arc, false);
246	246	} else if (direction(p)) {
247	247	Edge arc = Parent::findArc(s, t, p);
248	248	if (arc != INVALID) return direct(arc, true);
249	249	arc = Parent::findArc(t, s);
250	250	if (arc != INVALID) return direct(arc, false);
251	251	} else {
252	252	Edge arc = Parent::findArc(t, s, p);
253	253	if (arc != INVALID) return direct(arc, false);
254	254	}
255	255	return INVALID;
256	256	}
257	257
258	258	Edge findEdge(Node s, Node t, Edge p = INVALID) const {
259	259	if (s != t) {
260	260	if (p == INVALID) {
261	261	Edge arc = Parent::findArc(s, t);
262	262	if (arc != INVALID) return arc;
263	263	arc = Parent::findArc(t, s);
264	264	if (arc != INVALID) return arc;
265	265	} else if (Parent::s(p) == s) {
266	266	Edge arc = Parent::findArc(s, t, p);
267	267	if (arc != INVALID) return arc;
268	268	arc = Parent::findArc(t, s);
269	269	if (arc != INVALID) return arc;
270	270	} else {
271	271	Edge arc = Parent::findArc(t, s, p);
272	272	if (arc != INVALID) return arc;
273	273	}
274	274	} else {
275	275	return Parent::findArc(s, t, p);
276	276	}
277	277	return INVALID;
278	278	}
279	279	};
280	280
281	281	template <typename Base>
282	282	class BidirBpGraphExtender : public Base {
283	283	public:
284	284	typedef Base Parent;
285	285	typedef BidirBpGraphExtender Digraph;
286	286
287	287	typedef typename Parent::Node Node;
288	288	typedef typename Parent::Edge Edge;
289	289
290	290
291	291	using Parent::first;
292	292	using Parent::next;
293	293
294	294	using Parent::id;
295	295
296	296	class Red : public Node {
297	297	friend class BidirBpGraphExtender;
298	298	public:
299	299	Red() {}
300	300	Red(const Node& node) : Node(node) {
301	301	LEMON_DEBUG(Parent::red(node) \|\| node == INVALID,
302	302	typename Parent::NodeSetError());
303	303	}
304	304	Red& operator=(const Node& node) {
305	305	LEMON_DEBUG(Parent::red(node) \|\| node == INVALID,
306	306	typename Parent::NodeSetError());
307	307	Node::operator=(node);
308	308	return *this;
309	309	}
310	310	Red(Invalid) : Node(INVALID) {}
311	311	Red& operator=(Invalid) {
312	312	Node::operator=(INVALID);
313	313	return *this;
314	314	}
315	315	};
316	316
317	317	void first(Red& node) const {
318	318	Parent::firstRed(static_cast<Node&>(node));
319	319	}
320	320	void next(Red& node) const {
321	321	Parent::nextRed(static_cast<Node&>(node));
322	322	}
323	323
324	324	int id(const Red& node) const {
325	325	return Parent::redId(node);
326	326	}
327	327
328	328	class Blue : public Node {
329	329	friend class BidirBpGraphExtender;
330	330	public:
331	331	Blue() {}
332	332	Blue(const Node& node) : Node(node) {
333	333	LEMON_DEBUG(Parent::blue(node) \|\| node == INVALID,
334	334	typename Parent::NodeSetError());
335	335	}
336	336	Blue& operator=(const Node& node) {
337	337	LEMON_DEBUG(Parent::blue(node) \|\| node == INVALID,
338	338	typename Parent::NodeSetError());
339	339	Node::operator=(node);
340	340	return *this;
341	341	}
342	342	Blue(Invalid) : Node(INVALID) {}
343	343	Blue& operator=(Invalid) {
344	344	Node::operator=(INVALID);
345	345	return *this;
346	346	}
347	347	};
348	348
349	349	void first(Blue& node) const {
350	350	Parent::firstBlue(static_cast<Node&>(node));
351	351	}
352	352	void next(Blue& node) const {
353	353	Parent::nextBlue(static_cast<Node&>(node));
354	354	}
355	355
356	356	int id(const Blue& node) const {
357	357	return Parent::redId(node);
358	358	}
359	359
360	360	Node source(const Edge& arc) const {
361	361	return red(arc);
362	362	}
363	363	Node target(const Edge& arc) const {
364	364	return blue(arc);
365	365	}
366	366
367	367	void firstInc(Edge& arc, bool& dir, const Node& node) const {
368	368	if (Parent::red(node)) {
369	369	Parent::firstFromRed(arc, node);
370	370	dir = true;
371	371	} else {
372	372	Parent::firstFromBlue(arc, node);
373	373	dir = static_cast<Edge&>(arc) == INVALID;
374	374	}
375	375	}
376	376	void nextInc(Edge& arc, bool& dir) const {
377	377	if (dir) {
378	378	Parent::nextFromRed(arc);
379	379	} else {
380	380	Parent::nextFromBlue(arc);
381	381	if (arc == INVALID) dir = true;
382	382	}
383	383	}
384	384
385	385	class Arc : public Edge {
386	386	friend class BidirBpGraphExtender;
387	387	protected:
388	388	bool forward;
389	389
390	390	Arc(const Edge& arc, bool _forward)
391	391	: Edge(arc), forward(_forward) {}
392	392
393	393	public:
394	394	Arc() {}
395	395	Arc (Invalid) : Edge(INVALID), forward(true) {}
396	396	bool operator==(const Arc& i) const {
397	397	return Edge::operator==(i) && forward == i.forward;
398	398	}
399	399	bool operator!=(const Arc& i) const {
400	400	return Edge::operator!=(i) \|\| forward != i.forward;
401	401	}
402	402	bool operator<(const Arc& i) const {
403	403	return Edge::operator<(i) \|\|
404	404	(!(i.forward<forward) && Edge(*this)<Edge(i));
405	405	}
406	406	};
407	407
408	408	void first(Arc& arc) const {
409	409	Parent::first(static_cast<Edge&>(arc));
410	410	arc.forward = true;
411	411	}
412	412
413	413	void next(Arc& arc) const {
414	414	if (!arc.forward) {
415	415	Parent::next(static_cast<Edge&>(arc));
416	416	}
417	417	arc.forward = !arc.forward;
418	418	}
419	419
420	420	void firstOut(Arc& arc, const Node& node) const {
421	421	if (Parent::red(node)) {
422	422	Parent::firstFromRed(arc, node);
423	423	arc.forward = true;
424	424	} else {
425	425	Parent::firstFromBlue(arc, node);
426	426	arc.forward = static_cast<Edge&>(arc) == INVALID;
427	427	}
428	428	}
429	429	void nextOut(Arc& arc) const {
430	430	if (arc.forward) {
431	431	Parent::nextFromRed(arc);
432	432	} else {
433	433	Parent::nextFromBlue(arc);
434	434	arc.forward = static_cast<Edge&>(arc) == INVALID;
435	435	}
436	436	}
437	437
438	438	void firstIn(Arc& arc, const Node& node) const {
439	439	if (Parent::blue(node)) {
440	440	Parent::firstFromBlue(arc, node);
441	441	arc.forward = true;
442	442	} else {
443	443	Parent::firstFromRed(arc, node);
444	444	arc.forward = static_cast<Edge&>(arc) == INVALID;
445	445	}
446	446	}
447	447	void nextIn(Arc& arc) const {
448	448	if (arc.forward) {
449	449	Parent::nextFromBlue(arc);
450	450	} else {
451	451	Parent::nextFromRed(arc);
452	452	arc.forward = static_cast<Edge&>(arc) == INVALID;
453	453	}
454	454	}
455	455
456	456	Node source(const Arc& arc) const {
457	457	return arc.forward ? Parent::red(arc) : Parent::blue(arc);
458	458	}
459	459	Node target(const Arc& arc) const {
460	460	return arc.forward ? Parent::blue(arc) : Parent::red(arc);
461	461	}
462	462
463	463	int id(const Arc& arc) const {
464	464	return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
465	465	(arc.forward ? 0 : 1);
466	466	}
467	467	Arc arcFromId(int ix) const {
468	468	return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
469	469	}
470	470	int maxArcId() const {
471	471	return (Parent::maxEdgeId() << 1) + 1;
472	472	}
473	473
474	474	bool direction(const Arc& arc) const {
475	475	return arc.forward;
476	476	}
477	477
478	478	Arc direct(const Edge& arc, bool dir) const {
479	479	return Arc(arc, dir);
480	480	}
481	481
482	482	int arcNum() const {
483	483	return 2 * Parent::edgeNum();
484	484	}
485	485
486	486	int edgeNum() const {
487	487	return Parent::edgeNum();
488	488	}
489	489
490	490
491	491	};
492	492	}
493	493
494	494	#endif