LEMON/LEMON-official Changeset - r1078:c59bdcc8e33e

Repositories » LEMON » LEMON-official

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

Changeset - r1078:c59bdcc8e33e

« 1077:8276e0

1079:a1d8d1 »

r1078:c59bdcc8e33e

Fri, 05 Aug 2011 00:17:29

[Not Reviewed]

0 comments (0 inline)

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

Unify sources

0 24 0

r1.0.7 1.0

24 files changed:

doc/dirs.dox

doc/groups.dox

doc/lgf.dox

lemon/base.cc

lemon/bits/default_map.h

lemon/bits/map_extender.h

lemon/bits/path_dump.h

lemon/bits/windows.cc

lemon/core.h

lemon/dfs.h

lemon/graph_to_eps.h

lemon/lgf_reader.h

lemon/lgf_writer.h

lemon/list_graph.h

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

↑ Collapse diff ↑

doc/dirs.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
+		 * Copyright (C) 2003-2011
 		 * 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.
+		 *
 		 */
 		/**
 		\dir demo
 		\brief A collection of demo applications.
 		This directory contains several simple demo applications, mainly
 		for educational purposes.
 		*/
 		/**
 		\dir doc
 		\brief Auxiliary (and the whole generated) documentation.
 		This directory contains some auxiliary pages and the whole generated
 		documentation.
 		*/
 		/**
 		\dir test
 		\brief Test programs.
 		This directory contains several test programs that check the consistency
 		of the code.
 		*/
 		/**
 		\dir tools
 		\brief Some useful executables.
 		This directory contains the sources of some useful complete executables.
 		*/
 		/**
 		\dir lemon
 		\brief Base include directory of LEMON.
 		This is the base directory of LEMON includes, so each include file must be
 		prefixed with this, e.g.
 		\code
 		#include<lemon/list_graph.h>
 		#include<lemon/dijkstra.h>
 		\endcode
 		*/
 		/**
 		\dir concepts
 		\brief Concept descriptors and checking classes.
 		This directory contains the concept descriptors and concept checking tools.
 		For more information see the \ref concept "Concepts" module.
 		*/
 		/**
 		\dir bits
 		\brief Auxiliary tools for implementation.
-		This directory contains some auxiliary classes for implementing graphs,
 		This directory contains some auxiliary classes for implementing graphs,
 		maps and some other classes.
 		As a user you typically don't have to deal with these files.
 		*/

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
+		 * Copyright (C) 2003-2011
 		 * 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.
 		You are free to use the graph structure that fit your requirements
 		the best, most graph algorithms and auxiliary data structures can be used
 		with any graph structure.
 		<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		@defgroup 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 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 graphToEps() function.
 		\code
 		  Color nodeColor(int deg) {
 		    if (deg >= 2) {
 		      return Color(0.5, 0.0, 0.5);
 		    } else if (deg == 1) {
 		      return Color(1.0, 0.5, 1.0);
 		    } else {
 		      return Color(0.0, 0.0, 0.0);
+		    }
+		  }
 		  Digraph::NodeMap<int> degree_map(graph);
 		  graphToEps(graph, "graph.eps")
 		    .coords(coords).scaleToA4().undirected()
 		    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
 		    .run();
 		\endcode
 		The \c functorToMap() function makes an \c int to \c Color map from the
 		\c nodeColor() function. The \c composeMap() compose the \c degree_map
 		and the previously created map. The composed map is a proper function to
 		get the color of each node.
 		The usage with class type algorithms is little bit harder. In this
 		case the function type map adaptors can not be used, because the
 		function map adaptors give back temporary objects.
 		\code
 		  Digraph graph;
 		  typedef Digraph::ArcMap<double> DoubleArcMap;
 		  DoubleArcMap length(graph);
 		  DoubleArcMap speed(graph);
 		  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
 		  TimeMap time(length, speed);
 		  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 		  dijkstra.run(source, target);
 		\endcode
 		We have a length map and a maximum speed map on the arcs of a digraph.
 		The minimum time to pass the arc can be calculated as the division of
 		the two maps which can be done implicitly with the \c DivMap template
 		class. We use the implicit minimum time map as the length map of the
 		\c Dijkstra algorithm.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief %Path structures implemented in LEMON.
 		This group describes the path structures implemented in LEMON.
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
 		\sa lemon::concepts::Path
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group describes some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group describes the several algorithms
 		implemented in LEMON.
 		This group describes the several algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
 		This group describes the common graph search algorithms like
 		Breadth-First Search (BFS) and Depth-First Search (DFS).
 		*/
 		/**
 		@defgroup shortest_path Shortest Path Algorithms
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
 		This group describes the algorithms for finding shortest paths in graphs.
 		*/
 		/**
 		@defgroup 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 utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
 		This group describes some simple basic graph utilities.
 		*/
 		/**
 		@defgroup misc Miscellaneous Tools
 		@ingroup utils
 		\brief Tools for development, debugging and testing.
 		This group describes several useful tools for development,
 		debugging and testing.
 		*/
 		/**
 		@defgroup timecount Time Measuring and Counting
 		@ingroup misc
 		\brief Simple tools for measuring the performance of algorithms.
 		This group describes simple tools for measuring the performance
 		of algorithms.
 		*/
 		/**
 		@defgroup 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
 		and the encapsulated postscript (EPS) format.
 		postscript (EPS) format.
 		*/
 		/**
 		@defgroup lemon_io LEMON Input-Output
 		@ingroup io_group
 		\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
 		@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.
 		*/
 		/**
 		@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.
 		*/

doc/lgf.dox

Show inline comments

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

lemon/base.cc

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
+		 * Copyright (C) 2003-2011
 		 * 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.
+		 *
 		 */
 		///\file
 		///\brief Some basic non-inline functions and static global data.
 		#include<lemon/tolerance.h>
 		#include<lemon/core.h>
 		namespace lemon {
 		  float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
 		  double Tolerance<double>::def_epsilon = 1e-10;
 		  long double Tolerance<long double>::def_epsilon = 1e-14;
 		#ifndef LEMON_ONLY_TEMPLATES
 		  const Invalid INVALID = Invalid();
 		#endif
 		} //namespace lemon

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
+		 * Copyright (C) 2003-2011
 		 * 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/config.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.
 		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 LEMON_HAVE_LONG_LONG
 		  // 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
 		  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/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
+		 * Copyright (C) 2003-2011
 		 * 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.
 		namespace lemon {
 		  // \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() : map(NULL) {}
 		      MapIt(Invalid i) : Parent(i), map(NULL) {}
 		      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() : map(NULL) {}
 		      ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
 		      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() : map(NULL) {}
 		      ItemIt(Invalid i) : Parent(i), map(NULL) {}
 		      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.
 		  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() : map(NULL) {}
 		      MapIt(Invalid i) : Parent(i), map(NULL) { }
 		      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() : map(NULL) {}
 		      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
 		      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() : map(NULL) {}
 		      ItemIt(Invalid i) : Parent(i), map(NULL) { }
 		      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/path_dump.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
+		 * Copyright (C) 2003-2011
 		 * 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_PRED_MAP_PATH_H
 		#define LEMON_BITS_PRED_MAP_PATH_H
 		namespace lemon {
 		  template <typename _Digraph, typename _PredMap>
 		  class PredMapPath {
 		  public:
 		    typedef True RevPathTag;
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef _PredMap PredMap;
 		    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
 		                typename Digraph::Node _target)
 		      : digraph(_digraph), predMap(_predMap), target(_target) {}
 		    int length() const {
 		      int len = 0;
 		      typename Digraph::Node node = target;
 		      typename Digraph::Arc arc;
 		      while ((arc = predMap[node]) != INVALID) {
 		        node = digraph.source(arc);
 		        ++len;
+		      }
 		      return len;
+		    }
 		    bool empty() const {
 		      return predMap[target] == INVALID;
+		    }
 		    class RevArcIt {
 		    public:
 		      RevArcIt() {}
 		      RevArcIt(Invalid) : path(0), current(INVALID) {}
 		      RevArcIt(const PredMapPath& _path)
 		        : path(&_path), current(_path.target) {
 		        if (path->predMap[current] == INVALID) current = INVALID;
+		      }
 		      operator const typename Digraph::Arc() const {
 		        return path->predMap[current];
+		      }
 		      RevArcIt& operator++() {
 		        current = path->digraph.source(path->predMap[current]);
 		        if (path->predMap[current] == INVALID) current = INVALID;
 		        return *this;
+		      }
 		      bool operator==(const RevArcIt& e) const {
 		        return current == e.current;
+		      }
 		      bool operator!=(const RevArcIt& e) const {
 		        return current != e.current;
+		      }
 		      bool operator<(const RevArcIt& e) const {
 		        return current < e.current;
+		      }
 		    private:
 		      const PredMapPath* path;
 		      typename Digraph::Node current;
 		    };
 		  private:
 		    const Digraph& digraph;
 		    const PredMap& predMap;
 		    typename Digraph::Node target;
 		  };
 		  template <typename _Digraph, typename _PredMatrixMap>
 		  class PredMatrixMapPath {
 		  public:
 		    typedef True RevPathTag;
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef _PredMatrixMap PredMatrixMap;
 		    PredMatrixMapPath(const Digraph& _digraph,
 		                      const PredMatrixMap& _predMatrixMap,
 		                      typename Digraph::Node _source,
 		                      typename Digraph::Node _target)
 		      : digraph(_digraph), predMatrixMap(_predMatrixMap),
 		        source(_source), target(_target) {}
 		    int length() const {
 		      int len = 0;
 		      typename Digraph::Node node = target;
 		      typename Digraph::Arc arc;
 		      while ((arc = predMatrixMap(source, node)) != INVALID) {
 		        node = digraph.source(arc);
 		        ++len;
+		      }
 		      return len;
+		    }
 		    bool empty() const {
 		      return predMatrixMap(source, target) == INVALID;
+		    }
 		    class RevArcIt {
 		    public:
 		      RevArcIt() {}
 		      RevArcIt(Invalid) : path(0), current(INVALID) {}
 		      RevArcIt(const PredMatrixMapPath& _path)
 		        : path(&_path), current(_path.target) {
 		        if (path->predMatrixMap(path->source, current) == INVALID)
 		          current = INVALID;
+		      }
 		      operator const typename Digraph::Arc() const {
 		        return path->predMatrixMap(path->source, current);
+		      }
 		      RevArcIt& operator++() {
 		        current =
 		          path->digraph.source(path->predMatrixMap(path->source, current));
 		        if (path->predMatrixMap(path->source, current) == INVALID)
 		          current = INVALID;
 		        return *this;
+		      }
 		      bool operator==(const RevArcIt& e) const {
 		        return current == e.current;
+		      }
 		      bool operator!=(const RevArcIt& e) const {
 		        return current != e.current;
+		      }
 		      bool operator<(const RevArcIt& e) const {
 		        return current < e.current;
+		      }
 		    private:
 		      const PredMatrixMapPath* path;
 		      typename Digraph::Node current;
 		    };
 		  private:
 		    const Digraph& digraph;
 		    const PredMatrixMap& predMatrixMap;
 		    typename Digraph::Node source;
 		    typename Digraph::Node target;
 		  };
+		}
 		#endif

lemon/bits/windows.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2009
+		 * Copyright (C) 2003-2011
 		 * 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.
+		 *
 		 */
 		///\file
 		///\brief Some basic non-inline functions and static global data.
 		#include<lemon/bits/windows.h>
 		#ifdef WIN32
 		#ifndef WIN32_LEAN_AND_MEAN
 		#define WIN32_LEAN_AND_MEAN
 		#endif
 		#ifndef NOMINMAX
 		#define NOMINMAX
 		#endif
 		#ifdef UNICODE
 		#undef UNICODE
 		#endif
 		#include <windows.h>
 		#ifdef LOCALE_INVARIANT
 		#define MY_LOCALE LOCALE_INVARIANT
 		#else
 		#define MY_LOCALE LOCALE_NEUTRAL
 		#endif
 		#else
 		#include <unistd.h>
 		#include <ctime>
 		#include <sys/times.h>
 		#include <sys/time.h>
 		#endif
 		#include <cmath>
 		#include <sstream>
 		namespace lemon {
 		  namespace bits {
 		    void getWinProcTimes(double &rtime,
 		                         double &utime, double &stime,
 		                         double &cutime, double &cstime)
+		    {
 		#ifdef WIN32
 		      static const double ch = 4294967296.0e-7;
 		      static const double cl = 1.0e-7;
 		      FILETIME system;
 		      GetSystemTimeAsFileTime(&system);
 		      rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime;
 		      FILETIME create, exit, kernel, user;
 		      if (GetProcessTimes(GetCurrentProcess(),&create, &exit, &kernel, &user)) {
 		        utime = ch * user.dwHighDateTime + cl * user.dwLowDateTime;
 		        stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime;
 		        cutime = 0;
 		        cstime = 0;
 		      } else {
 		        rtime = 0;
 		        utime = 0;
 		        stime = 0;
 		        cutime = 0;
 		        cstime = 0;
+		      }
 		#else
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      rtime=tv.tv_sec+double(tv.tv_usec)/1e6;
 		      tms ts;
 		      double tck=sysconf(_SC_CLK_TCK);
 		      times(&ts);
 		      utime=ts.tms_utime/tck;
 		      stime=ts.tms_stime/tck;
 		      cutime=ts.tms_cutime/tck;
 		      cstime=ts.tms_cstime/tck;
 		#endif
+		    }
 		    std::string getWinFormattedDate()
+		    {
 		      std::ostringstream os;
 		#ifdef WIN32
 		      SYSTEMTIME time;
 		      GetSystemTime(&time);
 		      char buf1[11], buf2[9], buf3[5];
-			  if (GetDateFormat(MY_LOCALE, 0, &time,
+		          if (GetDateFormat(MY_LOCALE, 0, &time,
 		                        ("ddd MMM dd"), buf1, 11) &&
 		          GetTimeFormat(MY_LOCALE, 0, &time,
 		                        ("HH':'mm':'ss"), buf2, 9) &&
 		          GetDateFormat(MY_LOCALE, 0, &time,
 		                        ("yyyy"), buf3, 5)) {
 		        os << buf1 << ' ' << buf2 << ' ' << buf3;
+		      }
 		      else os << "unknown";
 		#else
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      char cbuf[26];
 		      ctime_r(&tv.tv_sec,cbuf);
 		      os << cbuf;
 		#endif
 		      return os.str();
+		    }
 		    int getWinRndSeed()
+		    {
 		#ifdef WIN32
 		      FILETIME time;
 		      GetSystemTimeAsFileTime(&time);
 		      return GetCurrentProcessId() + time.dwHighDateTime + time.dwLowDateTime;
 		#else
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      return getpid() + tv.tv_sec + tv.tv_usec;
 		#endif
+		    }
+		  }
+		}

lemon/core.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
+		 * Copyright (C) 2003-2011
 		 * 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_CORE_H
 		#define LEMON_CORE_H
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/config.h>
 		#include <lemon/bits/enable_if.h>
 		#include <lemon/bits/traits.h>
 		#include <lemon/assert.h>
 		///\file
 		///\brief LEMON core utilities.
 		///
 		///This header file contains core utilities for LEMON.
 		///It is automatically included by all graph types, therefore it usually
 		///do not have to be included directly.
 		namespace lemon {
 		  /// \brief Dummy type to make it easier to create invalid iterators.
 		  ///
 		  /// Dummy type to make it easier to create invalid iterators.
 		  /// See \ref INVALID for the usage.
 		  struct Invalid {
 		  public:
 		    bool operator==(Invalid) { return true;  }
 		    bool operator!=(Invalid) { return false; }
 		    bool operator< (Invalid) { return false; }
 		  };
 		  /// \brief Invalid iterators.
 		  ///
 		  /// \ref Invalid is a global type that converts to each iterator
 		  /// in such a way that the value of the target iterator will be invalid.
 		#ifdef LEMON_ONLY_TEMPLATES
 		  const Invalid INVALID = Invalid();
 		#else
 		  extern const Invalid INVALID;
 		#endif
 		  /// \addtogroup gutils
 		  /// @{
 		  ///Create convenience typedefs for the digraph types and iterators
 		  ///This \c \#define creates convenient type definitions for the following
 		  ///types of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
 		  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
 		  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
 		  ///
 		  ///\note If the graph type is a dependent type, ie. the graph type depend
 		  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
 		  ///macro.
 		#define DIGRAPH_TYPEDEFS(Digraph)                                       \
 		  typedef Digraph::Node Node;                                           \
 		  typedef Digraph::NodeIt NodeIt;                                       \
 		  typedef Digraph::Arc Arc;                                             \
 		  typedef Digraph::ArcIt ArcIt;                                         \
 		  typedef Digraph::InArcIt InArcIt;                                     \
 		  typedef Digraph::OutArcIt OutArcIt;                                   \
 		  typedef Digraph::NodeMap<bool> BoolNodeMap;                           \
 		  typedef Digraph::NodeMap<int> IntNodeMap;                             \
 		  typedef Digraph::NodeMap<double> DoubleNodeMap;                       \
 		  typedef Digraph::ArcMap<bool> BoolArcMap;                             \
 		  typedef Digraph::ArcMap<int> IntArcMap;                               \
 		  typedef Digraph::ArcMap<double> DoubleArcMap
 		  ///Create convenience typedefs for the digraph types and iterators
 		  ///\see DIGRAPH_TYPEDEFS
 		  ///
 		  ///\note Use this macro, if the graph type is a dependent type,
 		  ///ie. the graph type depend on a template parameter.
 		#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \
 		  typedef typename Digraph::Node Node;                                  \
 		  typedef typename Digraph::NodeIt NodeIt;                              \
 		  typedef typename Digraph::Arc Arc;                                    \
 		  typedef typename Digraph::ArcIt ArcIt;                                \
 		  typedef typename Digraph::InArcIt InArcIt;                            \
 		  typedef typename Digraph::OutArcIt OutArcIt;                          \
 		  typedef typename Digraph::template NodeMap<bool> BoolNodeMap;         \
 		  typedef typename Digraph::template NodeMap<int> IntNodeMap;           \
 		  typedef typename Digraph::template NodeMap<double> DoubleNodeMap;     \
 		  typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \
 		  typedef typename Digraph::template ArcMap<int> IntArcMap;             \
 		  typedef typename Digraph::template ArcMap<double> DoubleArcMap
 		  ///Create convenience typedefs for the graph types and iterators
 		  ///This \c \#define creates the same convenient type definitions as defined
 		  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
 		  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
 		  ///\c DoubleEdgeMap.
 		  ///
 		  ///\note If the graph type is a dependent type, ie. the graph type depend
 		  ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
 		  ///macro.
 		#define GRAPH_TYPEDEFS(Graph)                                           \
 		  DIGRAPH_TYPEDEFS(Graph);                                              \
 		  typedef Graph::Edge Edge;                                             \
 		  typedef Graph::EdgeIt EdgeIt;                                         \
 		  typedef Graph::IncEdgeIt IncEdgeIt;                                   \
 		  typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \
 		  typedef Graph::EdgeMap<int> IntEdgeMap;                               \
 		  typedef Graph::EdgeMap<double> DoubleEdgeMap
 		  ///Create convenience typedefs for the graph types and iterators
 		  ///\see GRAPH_TYPEDEFS
 		  ///
 		  ///\note Use this macro, if the graph type is a dependent type,
 		  ///ie. the graph type depend on a template parameter.
 		#define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \
 		  typedef typename Graph::Edge Edge;                                    \
 		  typedef typename Graph::EdgeIt EdgeIt;                                \
 		  typedef typename Graph::IncEdgeIt IncEdgeIt;                          \
 		  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \
 		  typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \
 		  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
 		  /// \brief Function to count the items in a graph.
 		  ///
 		  /// This function counts the items (nodes, arcs etc.) in a graph.
 		  /// The complexity of the function is linear because
 		  /// it iterates on all of the items.
 		  template <typename Graph, typename Item>
 		  inline int countItems(const Graph& g) {
 		    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
 		    int num = 0;
 		    for (ItemIt it(g); it != INVALID; ++it) {
 		      ++num;
+		    }
 		    return num;
+		  }
 		  // Node counting:
 		  namespace _core_bits {
 		    template <typename Graph, typename Enable = void>
 		    struct CountNodesSelector {
 		      static int count(const Graph &g) {
 		        return countItems<Graph, typename Graph::Node>(g);
+		      }
 		    };
 		    template <typename Graph>
 		    struct CountNodesSelector<
 		      Graph, typename
 		      enable_if<typename Graph::NodeNumTag, void>::type>
+		    {
 		      static int count(const Graph &g) {
 		        return g.nodeNum();
+		      }
 		    };
+		  }
 		  /// \brief Function to count the nodes in the graph.
 		  ///
 		  /// This function counts the nodes in the graph.
 		  /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
 		  /// graph structures it is specialized to run in <em>O</em>(1).
 		  ///
 		  /// \note If the graph contains a \c nodeNum() member function and a
 		  /// \c NodeNumTag tag then this function calls directly the member
 		  /// function to query the cardinality of the node set.
 		  template <typename Graph>
 		  inline int countNodes(const Graph& g) {
 		    return _core_bits::CountNodesSelector<Graph>::count(g);
+		  }
 		  // Arc counting:
 		  namespace _core_bits {
 		    template <typename Graph, typename Enable = void>
 		    struct CountArcsSelector {
 		      static int count(const Graph &g) {
 		        return countItems<Graph, typename Graph::Arc>(g);
+		      }
 		    };
 		    template <typename Graph>
 		    struct CountArcsSelector<
 		      Graph,
 		      typename enable_if<typename Graph::ArcNumTag, void>::type>
+		    {
 		      static int count(const Graph &g) {
 		        return g.arcNum();
+		      }
 		    };
+		  }
 		  /// \brief Function to count the arcs in the graph.
 		  ///
 		  /// This function counts the arcs in the graph.
 		  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
 		  /// graph structures it is specialized to run in <em>O</em>(1).
 		  ///
 		  /// \note If the graph contains a \c arcNum() member function and a
 		  /// \c ArcNumTag tag then this function calls directly the member
 		  /// function to query the cardinality of the arc set.
 		  template <typename Graph>
 		  inline int countArcs(const Graph& g) {
 		    return _core_bits::CountArcsSelector<Graph>::count(g);
+		  }
 		  // Edge counting:
 		  namespace _core_bits {
 		    template <typename Graph, typename Enable = void>
 		    struct CountEdgesSelector {
 		      static int count(const Graph &g) {
 		        return countItems<Graph, typename Graph::Edge>(g);
+		      }
 		    };
 		    template <typename Graph>
 		    struct CountEdgesSelector<
 		      Graph,
 		      typename enable_if<typename Graph::EdgeNumTag, void>::type>
+		    {
 		      static int count(const Graph &g) {
 		        return g.edgeNum();
+		      }
 		    };
+		  }
 		  /// \brief Function to count the edges in the graph.
 		  ///
 		  /// This function counts the edges in the graph.
 		  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
 		  /// graph structures it is specialized to run in <em>O</em>(1).
 		  ///
 		  /// \note If the graph contains a \c edgeNum() member function and a
 		  /// \c EdgeNumTag tag then this function calls directly the member
 		  /// function to query the cardinality of the edge set.
 		  template <typename Graph>
 		  inline int countEdges(const Graph& g) {
 		    return _core_bits::CountEdgesSelector<Graph>::count(g);
+		  }
 		  template <typename Graph, typename DegIt>
 		  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
 		    int num = 0;
 		    for (DegIt it(_g, _n); it != INVALID; ++it) {
 		      ++num;
+		    }
 		    return num;
+		  }
 		  /// \brief Function to count the number of the out-arcs from node \c n.
 		  ///
 		  /// This function counts the number of the out-arcs from node \c n
 		  /// in the graph \c g.
 		  template <typename Graph>
 		  inline int countOutArcs(const Graph& g,  const typename Graph::Node& n) {
 		    return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
+		  }
 		  /// \brief Function to count the number of the in-arcs to node \c n.
 		  ///
 		  /// This function counts the number of the in-arcs to node \c n
 		  /// in the graph \c g.
 		  template <typename Graph>
 		  inline int countInArcs(const Graph& g,  const typename Graph::Node& n) {
 		    return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
+		  }
 		  /// \brief Function to count the number of the inc-edges to node \c n.
 		  ///
 		  /// This function counts the number of the inc-edges to node \c n
 		  /// in the undirected graph \c g.
 		  template <typename Graph>
 		  inline int countIncEdges(const Graph& g,  const typename Graph::Node& n) {
 		    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
+		  }
 		  namespace _core_bits {
 		    template <typename Digraph, typename Item, typename RefMap>
 		    class MapCopyBase {
 		    public:
 		      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
 		      virtual ~MapCopyBase() {}
 		    };
 		    template <typename Digraph, typename Item, typename RefMap,
 		              typename FromMap, typename ToMap>
 		    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
 		    public:
 		      MapCopy(const FromMap& map, ToMap& tmap)
 		        : _map(map), _tmap(tmap) {}
 		      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
 		        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
 		        for (ItemIt it(digraph); it != INVALID; ++it) {
 		          _tmap.set(refMap[it], _map[it]);
+		        }
+		      }
 		    private:
 		      const FromMap& _map;
 		      ToMap& _tmap;
 		    };
 		    template <typename Digraph, typename Item, typename RefMap, typename It>
 		    class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
 		    public:
 		      ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
 		      virtual void copy(const Digraph&, const RefMap& refMap) {
 		        _it = refMap[_item];
+		      }
 		    private:
 		      Item _item;
 		      It& _it;
 		    };
 		    template <typename Digraph, typename Item, typename RefMap, typename Ref>
 		    class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
 		    public:
 		      RefCopy(Ref& map) : _map(map) {}
 		      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
 		        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
 		        for (ItemIt it(digraph); it != INVALID; ++it) {
 		          _map.set(it, refMap[it]);
+		        }
+		      }
 		    private:
 		      Ref& _map;
 		    };
 		    template <typename Digraph, typename Item, typename RefMap,
 		              typename CrossRef>
 		    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
 		    public:
 		      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
 		      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
 		        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
 		        for (ItemIt it(digraph); it != INVALID; ++it) {
 		          _cmap.set(refMap[it], it);
+		        }
+		      }
 		    private:
 		      CrossRef& _cmap;
 		    };
 		    template <typename Digraph, typename Enable = void>
 		    struct DigraphCopySelector {
 		      template <typename From, typename NodeRefMap, typename ArcRefMap>
 		      static void copy(const From& from, Digraph &to,
 		                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
 		        to.clear();
 		        for (typename From::NodeIt it(from); it != INVALID; ++it) {
 		          nodeRefMap[it] = to.addNode();
+		        }
 		        for (typename From::ArcIt it(from); it != INVALID; ++it) {
 		          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
 		                                    nodeRefMap[from.target(it)]);
+		        }
+		      }
 		    };
 		    template <typename Digraph>
 		    struct DigraphCopySelector<
 		      Digraph,
 		      typename enable_if<typename Digraph::BuildTag, void>::type>
+		    {
 		      template <typename From, typename NodeRefMap, typename ArcRefMap>
 		      static void copy(const From& from, Digraph &to,
 		                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
 		        to.build(from, nodeRefMap, arcRefMap);
+		      }
 		    };
 		    template <typename Graph, typename Enable = void>
 		    struct GraphCopySelector {
 		      template <typename From, typename NodeRefMap, typename EdgeRefMap>
 		      static void copy(const From& from, Graph &to,
 		                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
 		        to.clear();
 		        for (typename From::NodeIt it(from); it != INVALID; ++it) {
 		          nodeRefMap[it] = to.addNode();
+		        }
 		        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
 		          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
 		                                      nodeRefMap[from.v(it)]);
+		        }
+		      }
 		    };
 		    template <typename Graph>
 		    struct GraphCopySelector<
 		      Graph,
 		      typename enable_if<typename Graph::BuildTag, void>::type>
+		    {
 		      template <typename From, typename NodeRefMap, typename EdgeRefMap>
 		      static void copy(const From& from, Graph &to,
 		                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
 		        to.build(from, nodeRefMap, edgeRefMap);
+		      }
 		    };
+		  }
 		  /// \brief Class to copy a digraph.
 		  ///
 		  /// Class to copy a digraph to another digraph (duplicate a digraph). The
 		  /// simplest way of using it is through the \c digraphCopy() function.
 		  ///
 		  /// This class not only make a copy of a digraph, but it can create
 		  /// references and cross references between the nodes and arcs of
 		  /// the two digraphs, and it can copy maps to use with the newly created
 		  /// digraph.
 		  ///
 		  /// To make a copy from a digraph, first an instance of DigraphCopy
 		  /// should be created, then the data belongs to the digraph should
 		  /// assigned to copy. In the end, the \c run() member should be
 		  /// called.
 		  ///
 		  /// The next code copies a digraph with several data:
 		  ///\code
 		  ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
 		  ///  // Create references for the nodes
 		  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
 		  ///  cg.nodeRef(nr);
 		  ///  // Create cross references (inverse) for the arcs
 		  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
 		  ///  cg.arcCrossRef(acr);
 		  ///  // Copy an arc map
 		  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
 		  ///  NewGraph::ArcMap<double> namap(new_graph);
 		  ///  cg.arcMap(oamap, namap);
 		  ///  // Copy a node
 		  ///  OrigGraph::Node on;
 		  ///  NewGraph::Node nn;
 		  ///  cg.node(on, nn);
 		  ///  // Execute copying
 		  ///  cg.run();
 		  ///\endcode
 		  template <typename From, typename To>
 		  class DigraphCopy {
 		  private:
 		    typedef typename From::Node Node;
 		    typedef typename From::NodeIt NodeIt;
 		    typedef typename From::Arc Arc;
 		    typedef typename From::ArcIt ArcIt;
 		    typedef typename To::Node TNode;
 		    typedef typename To::Arc TArc;
 		    typedef typename From::template NodeMap<TNode> NodeRefMap;
 		    typedef typename From::template ArcMap<TArc> ArcRefMap;
 		  public:
 		    /// \brief Constructor of DigraphCopy.
 		    ///
 		    /// Constructor of DigraphCopy for copying the content of the
 		    /// \c from digraph into the \c to digraph.
 		    DigraphCopy(const From& from, To& to)
 		      : _from(from), _to(to) {}
 		    /// \brief Destructor of DigraphCopy
 		    ///
 		    /// Destructor of DigraphCopy.
 		    ~DigraphCopy() {
 		      for (int i = 0; i < int(_node_maps.size()); ++i) {
 		        delete _node_maps[i];
+		      }
 		      for (int i = 0; i < int(_arc_maps.size()); ++i) {
 		        delete _arc_maps[i];
+		      }
+		    }
 		    /// \brief Copy the node references into the given map.
 		    ///
 		    /// This function copies the node references into the given map.
 		    /// The parameter should be a map, whose key type is the Node type of
 		    /// the source digraph, while the value type is the Node type of the
 		    /// destination digraph.

lemon/dfs.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
+		 * Copyright (C) 2003-2011
 		 * 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_DFS_H
 		#define LEMON_DFS_H
 		///\ingroup search
 		///\file
 		///\brief DFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///Default traits class of Dfs class.
 		  ///Default traits class of Dfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
 		    ///This function instantiates a ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a ReachedMap.
 		    ///This function instantiates a ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a DistMap.
 		    ///This function instantiates a DistMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///DistMap.
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%DFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %DFS algorithm.
 		  ///
 		  ///There is also a \ref dfs() "function-type interface" for the DFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default value is \ref ListDigraph. The value of GR is not used
 		  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
 		  ///\tparam TR Traits class to set various data types used by the algorithm.
 		  ///The default traits class is
 		  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
 		  ///See \ref DfsDefaultTraits for the documentation of
 		  ///a Dfs traits class.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=DfsDefaultTraits<GR> >
 		#endif
 		  class Dfs {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The traits class.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::OutArcIt> _stack;
 		    int _stack_head;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Dfs() {}
 		  public:
 		    typedef Dfs Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///PredMap type.
 		    template <class T>
 		    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 		      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "DistMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///DistMap type.
 		    template <class T>
 		    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///ReachedMap type.
 		    template <class T>
 		    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ProcessedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type.
 		    template <class T>
 		    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap :
 		      public Dfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param g The digraph the algorithm runs on.
 		    Dfs(const Digraph &g) :
 		      G(&g),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _reached(NULL), local_reached(false),
 		      _processed(NULL), local_processed(false)
 		    { }
 		    ///Destructor.
 		    ~Dfs()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_reached) delete _reached;
 		      if(local_processed) delete _processed;
+		    }
 		    ///Sets the map that stores the predecessor arcs.
 		    ///Sets the map that stores the predecessor arcs.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are reached.
 		    ///Sets the map that indicates which nodes are reached.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &reachedMap(ReachedMap &m)
+		    {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are processed.
 		    ///Sets the map that indicates which nodes are processed.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &processedMap(ProcessedMap &m)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
+		      }
 		      _processed = &m;
 		      return *this;
+		    }
 		    ///Sets the map that stores the distances of the nodes.
 		    ///Sets the map that stores the distances of the nodes calculated by
 		    ///the algorithm.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destructor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Dfs &distMap(DistMap &m)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;
+		    }
 		  public:
 		    ///\name Execution control
 		    ///The simplest way to execute the algorithm is to use
 		    ///one of the member functions called \ref lemon::Dfs::run() "run()".
 		    ///\n
 		    ///If you need more control on the execution, first you must call
 		    ///\ref lemon::Dfs::init() "init()", then you can add a source node
 		    ///with \ref lemon::Dfs::addSource() "addSource()".
 		    ///Finally \ref lemon::Dfs::start() "start()" will perform the
 		    ///actual path computation.
 		    ///@{
 		    ///Initializes the internal data structures.
 		    ///Initializes the internal data structures.
 		    ///
 		    void init()
+		    {
 		      create_maps();
 		      _stack.resize(countNodes(*G));
 		      _stack_head=-1;
 		      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 		        _pred->set(u,INVALID);
 		        _reached->set(u,false);
 		        _processed->set(u,false);
+		      }
+		    }
 		    ///Adds a new source node.
 		    ///Adds a new source node to the set of nodes to be processed.
 		    ///
 		    ///\pre The stack must be empty. (Otherwise the algorithm gives
 		    ///false results.)
 		    ///
 		    ///\warning Distances will be wrong (or at least strange) in case of
 		    ///multiple sources.
 		    void addSource(Node s)
+		    {
 		      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
 		      if(!(*_reached)[s])
+		        {
 		          _reached->set(s,true);
 		          _pred->set(s,INVALID);
 		          OutArcIt e(*G,s);
 		          if(e!=INVALID) {
 		            _stack[++_stack_head]=e;
 		            _dist->set(s,_stack_head);
+		          }
 		          else {
 		            _processed->set(s,true);
 		            _dist->set(s,0);
+		          }
+		        }
+		    }
 		    ///Processes the next arc.
 		    ///Processes the next arc.
 		    ///
 		    ///\return The processed arc.
 		    ///
 		    ///\pre The stack must not be empty.
 		    Arc processNextArc()
+		    {
 		      Node m;
 		      Arc e=_stack[_stack_head];
 		      if(!(*_reached)[m=G->target(e)]) {
 		        _pred->set(m,e);
 		        _reached->set(m,true);
 		        ++_stack_head;
 		        _stack[_stack_head] = OutArcIt(*G, m);
 		        _dist->set(m,_stack_head);
+		      }
 		      else {
 		        m=G->source(e);
 		        ++_stack[_stack_head];
+		      }
 		      while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
 		        _processed->set(m,true);
 		        --_stack_head;
 		        if(_stack_head>=0) {
 		          m=G->source(_stack[_stack_head]);
 		          ++_stack[_stack_head];
+		        }
+		      }
 		      return e;
+		    }
 		    ///Next arc to be processed.
 		    ///Next arc to be processed.
 		    ///
 		    ///\return The next arc to be processed or \c INVALID if the stack
 		    ///is empty.
 		    OutArcIt nextArc() const
+		    {
 		      return _stack_head>=0?_stack[_stack_head]:INVALID;
+		    }
 		    ///\brief Returns \c false if there are nodes
 		    ///to be processed.
 		    ///
 		    ///Returns \c false if there are nodes
 		    ///to be processed in the queue (stack).
 		    bool emptyQueue() const { return _stack_head<0; }
 		    ///Returns the number of the nodes to be processed.

lemon/graph_to_eps.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
+		 * Copyright (C) 2003-2011
 		 * 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_GRAPH_TO_EPS_H
 		#define LEMON_GRAPH_TO_EPS_H
 		#include<iostream>
 		#include<fstream>
 		#include<sstream>
 		#include<algorithm>
 		#include<vector>
 		#ifndef WIN32
 		#include<sys/time.h>
 		#include<ctime>
 		#else
 		#include<lemon/bits/windows.h>
 		#endif
 		#include<lemon/math.h>
 		#include<lemon/core.h>
 		#include<lemon/dim2.h>
 		#include<lemon/maps.h>
 		#include<lemon/color.h>
 		#include<lemon/bits/bezier.h>
 		#include<lemon/error.h>
 		///\ingroup eps_io
 		///\file
 		///\brief A well configurable tool for visualizing graphs
 		namespace lemon {
 		  namespace _graph_to_eps_bits {
 		    template<class MT>
 		    class _NegY {
 		    public:
 		      typedef typename MT::Key Key;
 		      typedef typename MT::Value Value;
 		      const MT &map;
 		      int yscale;
 		      _NegY(const MT &m,bool b) : map(m), yscale(1-b*2) {}
 		      Value operator[](Key n) { return Value(map[n].x,map[n].y*yscale);}
 		    };
+		  }
 		///Default traits class of GraphToEps
 		///Default traits class of \ref GraphToEps.
 		///
 		///\c G is the type of the underlying graph.
 		template<class G>
 		struct DefaultGraphToEpsTraits
+		{
 		  typedef G Graph;
 		  typedef typename Graph::Node Node;
 		  typedef typename Graph::NodeIt NodeIt;
 		  typedef typename Graph::Arc Arc;
 		  typedef typename Graph::ArcIt ArcIt;
 		  typedef typename Graph::InArcIt InArcIt;
 		  typedef typename Graph::OutArcIt OutArcIt;
 		  const Graph &g;
 		  std::ostream& os;
 		  typedef ConstMap<typename Graph::Node,dim2::Point<double> > CoordsMapType;
 		  CoordsMapType _coords;
 		  ConstMap<typename Graph::Node,double > _nodeSizes;
 		  ConstMap<typename Graph::Node,int > _nodeShapes;
 		  ConstMap<typename Graph::Node,Color > _nodeColors;
 		  ConstMap<typename Graph::Arc,Color > _arcColors;
 		  ConstMap<typename Graph::Arc,double > _arcWidths;
 		  double _arcWidthScale;
 		  double _nodeScale;
 		  double _xBorder, _yBorder;
 		  double _scale;
 		  double _nodeBorderQuotient;
 		  bool _drawArrows;
 		  double _arrowLength, _arrowWidth;
 		  bool _showNodes, _showArcs;
 		  bool _enableParallel;
 		  double _parArcDist;
 		  bool _showNodeText;
 		  ConstMap<typename Graph::Node,bool > _nodeTexts;
 		  double _nodeTextSize;
 		  bool _showNodePsText;
 		  ConstMap<typename Graph::Node,bool > _nodePsTexts;
 		  char *_nodePsTextsPreamble;
 		  bool _undirected;
 		  bool _pleaseRemoveOsStream;
 		  bool _scaleToA4;
 		  std::string _title;
 		  std::string _copyright;
 		  enum NodeTextColorType
 		    { DIST_COL=0, DIST_BW=1, CUST_COL=2, SAME_COL=3 } _nodeTextColorType;
 		  ConstMap<typename Graph::Node,Color > _nodeTextColors;
 		  bool _autoNodeScale;
 		  bool _autoArcWidthScale;
 		  bool _absoluteNodeSizes;
 		  bool _absoluteArcWidths;
 		  bool _negY;
 		  bool _preScale;
 		  ///Constructor
 		  ///Constructor
 		  ///\param _g  Reference to the graph to be printed.
 		  ///\param _os Reference to the output stream.
 		  ///\param _os Reference to the output stream.
 		  ///By default it is <tt>std::cout</tt>.
 		  ///\param _pros If it is \c true, then the \c ostream referenced by \c _os
 		  ///will be explicitly deallocated by the destructor.
 		  DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,
 		                          bool _pros=false) :
 		    g(_g), os(_os),
 		    _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0),
 		    _nodeColors(WHITE), _arcColors(BLACK),
 		    _arcWidths(1.0), _arcWidthScale(0.003),
 		    _nodeScale(.01), _xBorder(10), _yBorder(10), _scale(1.0),
 		    _nodeBorderQuotient(.1),
 		    _drawArrows(false), _arrowLength(1), _arrowWidth(0.3),
 		    _showNodes(true), _showArcs(true),
 		    _enableParallel(false), _parArcDist(1),
 		    _showNodeText(false), _nodeTexts(false), _nodeTextSize(1),
 		    _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0),
 		    _undirected(lemon::UndirectedTagIndicator<G>::value),
 		    _pleaseRemoveOsStream(_pros), _scaleToA4(false),
 		    _nodeTextColorType(SAME_COL), _nodeTextColors(BLACK),
 		    _autoNodeScale(false),
 		    _autoArcWidthScale(false),
 		    _absoluteNodeSizes(false),
 		    _absoluteArcWidths(false),
 		    _negY(false),
 		    _preScale(true)
 		  {}
 		};
 		///Auxiliary class to implement the named parameters of \ref graphToEps()
 		///Auxiliary class to implement the named parameters of \ref graphToEps().
 		///
 		///For detailed examples see the \ref graph_to_eps_demo.cc demo file.
 		template<class T> class GraphToEps : public T
+		{
 		  // Can't believe it is required by the C++ standard
 		  using T::g;
 		  using T::os;
 		  using T::_coords;
 		  using T::_nodeSizes;
 		  using T::_nodeShapes;
 		  using T::_nodeColors;
 		  using T::_arcColors;
 		  using T::_arcWidths;
 		  using T::_arcWidthScale;
 		  using T::_nodeScale;
 		  using T::_xBorder;
 		  using T::_yBorder;
 		  using T::_scale;
 		  using T::_nodeBorderQuotient;
 		  using T::_drawArrows;
 		  using T::_arrowLength;
 		  using T::_arrowWidth;
 		  using T::_showNodes;
 		  using T::_showArcs;
 		  using T::_enableParallel;
 		  using T::_parArcDist;
 		  using T::_showNodeText;
 		  using T::_nodeTexts;
 		  using T::_nodeTextSize;
 		  using T::_showNodePsText;
 		  using T::_nodePsTexts;
 		  using T::_nodePsTextsPreamble;
 		  using T::_undirected;
 		  using T::_pleaseRemoveOsStream;
 		  using T::_scaleToA4;
 		  using T::_title;
 		  using T::_copyright;
 		  using T::NodeTextColorType;
 		  using T::CUST_COL;
 		  using T::DIST_COL;
 		  using T::DIST_BW;
 		  using T::_nodeTextColorType;
 		  using T::_nodeTextColors;
 		  using T::_autoNodeScale;
 		  using T::_autoArcWidthScale;
 		  using T::_absoluteNodeSizes;
 		  using T::_absoluteArcWidths;
 		  using T::_negY;
 		  using T::_preScale;
 		  // dradnats ++C eht yb deriuqer si ti eveileb t'naC
 		  typedef typename T::Graph Graph;
 		  typedef typename Graph::Node Node;
 		  typedef typename Graph::NodeIt NodeIt;
 		  typedef typename Graph::Arc Arc;
 		  typedef typename Graph::ArcIt ArcIt;
 		  typedef typename Graph::InArcIt InArcIt;
 		  typedef typename Graph::OutArcIt OutArcIt;
 		  static const int INTERPOL_PREC;
 		  static const double A4HEIGHT;
 		  static const double A4WIDTH;
 		  static const double A4BORDER;
 		  bool dontPrint;
 		public:
 		  ///Node shapes
 		  ///Node shapes.
 		  ///
 		  enum NodeShapes {
 		    /// = 0
 		    ///\image html nodeshape_0.png
 		    ///\image latex nodeshape_0.eps "CIRCLE shape (0)" width=2cm
 		    CIRCLE=0,
 		    /// = 1
 		    ///\image html nodeshape_1.png
 		    ///\image latex nodeshape_1.eps "SQUARE shape (1)" width=2cm
 		    ///
 		    SQUARE=1,
 		    /// = 2
 		    ///\image html nodeshape_2.png
 		    ///\image latex nodeshape_2.eps "DIAMOND shape (2)" width=2cm
 		    ///
 		    DIAMOND=2,
 		    /// = 3
 		    ///\image html nodeshape_3.png
 		    ///\image latex nodeshape_2.eps "MALE shape (4)" width=2cm
 		    ///
 		    MALE=3,
 		    /// = 4
 		    ///\image html nodeshape_4.png
 		    ///\image latex nodeshape_2.eps "FEMALE shape (4)" width=2cm
 		    ///
 		    FEMALE=4
 		  };
 		private:
 		  class arcLess {
 		    const Graph &g;
 		  public:
 		    arcLess(const Graph &_g) : g(_g) {}
 		    bool operator()(Arc a,Arc b) const
+		    {
 		      Node ai=std::min(g.source(a),g.target(a));
 		      Node aa=std::max(g.source(a),g.target(a));
 		      Node bi=std::min(g.source(b),g.target(b));
 		      Node ba=std::max(g.source(b),g.target(b));
 		      return ai<bi ||
 		        (ai==bi && (aa < ba ||
 		                    (aa==ba && ai==g.source(a) && bi==g.target(b))));
+		    }
 		  };
 		  bool isParallel(Arc e,Arc f) const
+		  {
 		    return (g.source(e)==g.source(f)&&
 		            g.target(e)==g.target(f)) ||
 		      (g.source(e)==g.target(f)&&
 		       g.target(e)==g.source(f));
+		  }
 		  template<class TT>
 		  static std::string psOut(const dim2::Point<TT> &p)
+		    {
 		      std::ostringstream os;
 		      os << p.x << ' ' << p.y;
 		      return os.str();
+		    }
 		  static std::string psOut(const Color &c)
+		    {
 		      std::ostringstream os;
 		      os << c.red() << ' ' << c.green() << ' ' << c.blue();
 		      return os.str();
+		    }
 		public:
 		  GraphToEps(const T &t) : T(t), dontPrint(false) {};
 		  template<class X> struct CoordsTraits : public T {
 		  typedef X CoordsMapType;
 		    const X &_coords;
 		    CoordsTraits(const T &t,const X &x) : T(t), _coords(x) {}
 		  };
 		  ///Sets the map of the node coordinates
 		  ///Sets the map of the node coordinates.
 		  ///\param x must be a node map with \ref dim2::Point "dim2::Point<double>" or
 		  ///\ref dim2::Point "dim2::Point<int>" values.
 		  template<class X> GraphToEps<CoordsTraits<X> > coords(const X &x) {
 		    dontPrint=true;
 		    return GraphToEps<CoordsTraits<X> >(CoordsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeSizesTraits : public T {
 		    const X &_nodeSizes;
 		    NodeSizesTraits(const T &t,const X &x) : T(t), _nodeSizes(x) {}
 		  };
 		  ///Sets the map of the node sizes
 		  ///Sets the map of the node sizes.
 		  ///\param x must be a node map with \c double (or convertible) values.
 		  template<class X> GraphToEps<NodeSizesTraits<X> > nodeSizes(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeSizesTraits<X> >(NodeSizesTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeShapesTraits : public T {
 		    const X &_nodeShapes;
 		    NodeShapesTraits(const T &t,const X &x) : T(t), _nodeShapes(x) {}
 		  };
 		  ///Sets the map of the node shapes
 		  ///Sets the map of the node shapes.
 		  ///The available shape values
 		  ///can be found in \ref NodeShapes "enum NodeShapes".
 		  ///\param x must be a node map with \c int (or convertible) values.
 		  ///\sa NodeShapes
 		  template<class X> GraphToEps<NodeShapesTraits<X> > nodeShapes(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeShapesTraits<X> >(NodeShapesTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeTextsTraits : public T {
 		    const X &_nodeTexts;
 		    NodeTextsTraits(const T &t,const X &x) : T(t), _nodeTexts(x) {}
 		  };
 		  ///Sets the text printed on the nodes
 		  ///Sets the text printed on the nodes.
 		  ///\param x must be a node map with type that can be pushed to a standard
 		  ///\c ostream.
 		  template<class X> GraphToEps<NodeTextsTraits<X> > nodeTexts(const X &x)
+		  {
 		    dontPrint=true;
 		    _showNodeText=true;
 		    return GraphToEps<NodeTextsTraits<X> >(NodeTextsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodePsTextsTraits : public T {
 		    const X &_nodePsTexts;
 		    NodePsTextsTraits(const T &t,const X &x) : T(t), _nodePsTexts(x) {}
 		  };
 		  ///Inserts a PostScript block to the nodes
 		  ///With this command it is possible to insert a verbatim PostScript
 		  ///block to the nodes.
 		  ///The PS current point will be moved to the center of the node before
 		  ///the PostScript block inserted.
 		  ///
 		  ///Before and after the block a newline character is inserted so you
 		  ///don't have to bother with the separators.
 		  ///
 		  ///\param x must be a node map with type that can be pushed to a standard
 		  ///\c ostream.
 		  ///
 		  ///\sa nodePsTextsPreamble()
 		  template<class X> GraphToEps<NodePsTextsTraits<X> > nodePsTexts(const X &x)
+		  {
 		    dontPrint=true;
 		    _showNodePsText=true;
 		    return GraphToEps<NodePsTextsTraits<X> >(NodePsTextsTraits<X>(*this,x));
+		  }
 		  template<class X> struct ArcWidthsTraits : public T {
 		    const X &_arcWidths;
 		    ArcWidthsTraits(const T &t,const X &x) : T(t), _arcWidths(x) {}
 		  };
 		  ///Sets the map of the arc widths
 		  ///Sets the map of the arc widths.
 		  ///\param x must be an arc map with \c double (or convertible) values.
 		  template<class X> GraphToEps<ArcWidthsTraits<X> > arcWidths(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<ArcWidthsTraits<X> >(ArcWidthsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeColorsTraits : public T {
 		    const X &_nodeColors;
 		    NodeColorsTraits(const T &t,const X &x) : T(t), _nodeColors(x) {}
 		  };
 		  ///Sets the map of the node colors
 		  ///Sets the map of the node colors.
 		  ///\param x must be a node map with \ref Color values.
 		  ///
 		  ///\sa Palette
 		  template<class X> GraphToEps<NodeColorsTraits<X> >
 		  nodeColors(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<NodeColorsTraits<X> >(NodeColorsTraits<X>(*this,x));
+		  }
 		  template<class X> struct NodeTextColorsTraits : public T {
 		    const X &_nodeTextColors;
 		    NodeTextColorsTraits(const T &t,const X &x) : T(t), _nodeTextColors(x) {}
 		  };
 		  ///Sets the map of the node text colors
 		  ///Sets the map of the node text colors.
 		  ///\param x must be a node map with \ref Color values.
 		  ///
 		  ///\sa Palette
 		  template<class X> GraphToEps<NodeTextColorsTraits<X> >
 		  nodeTextColors(const X &x)
+		  {
 		    dontPrint=true;
 		    _nodeTextColorType=CUST_COL;
 		    return GraphToEps<NodeTextColorsTraits<X> >
 		      (NodeTextColorsTraits<X>(*this,x));
+		  }
 		  template<class X> struct ArcColorsTraits : public T {
 		    const X &_arcColors;
 		    ArcColorsTraits(const T &t,const X &x) : T(t), _arcColors(x) {}
 		  };
 		  ///Sets the map of the arc colors
 		  ///Sets the map of the arc colors.
 		  ///\param x must be an arc map with \ref Color values.
 		  ///
 		  ///\sa Palette
 		  template<class X> GraphToEps<ArcColorsTraits<X> >
 		  arcColors(const X &x)
+		  {
 		    dontPrint=true;
 		    return GraphToEps<ArcColorsTraits<X> >(ArcColorsTraits<X>(*this,x));
+		  }
 		  ///Sets a global scale factor for node sizes
 		  ///Sets a global scale factor for node sizes.
 		  ///
 		  /// If nodeSizes() is not given, this function simply sets the node
 		  /// sizes to \c d.  If nodeSizes() is given, but
 		  /// autoNodeScale() is not, then the node size given by
 		  /// nodeSizes() will be multiplied by the value \c d.
 		  /// If both nodeSizes() and autoNodeScale() are used, then the
 		  /// node sizes will be scaled in such a way that the greatest size will be
 		  /// equal to \c d.
 		  /// \sa nodeSizes()
 		  /// \sa autoNodeScale()
 		  GraphToEps<T> &nodeScale(double d=.01) {_nodeScale=d;return *this;}
 		  ///Turns on/off the automatic node size scaling.
 		  ///Turns on/off the automatic node size scaling.
 		  ///
 		  ///\sa nodeScale()
 		  ///
 		  GraphToEps<T> &autoNodeScale(bool b=true) {
 		    _autoNodeScale=b;return *this;
+		  }
 		  ///Turns on/off the absolutematic node size scaling.
 		  ///Turns on/off the absolutematic node size scaling.
 		  ///
 		  ///\sa nodeScale()
 		  ///
 		  GraphToEps<T> &absoluteNodeSizes(bool b=true) {
 		    _absoluteNodeSizes=b;return *this;
+		  }
 		  ///Negates the Y coordinates.
 		  GraphToEps<T> &negateY(bool b=true) {
 		    _negY=b;return *this;
+		  }
 		  ///Turn on/off pre-scaling

lemon/lgf_reader.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2011
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup lemon_io
 		///\file
 		///\brief \ref lgf-format "LEMON Graph Format" reader.
 		#ifndef LEMON_LGF_READER_H
 		#define LEMON_LGF_READER_H
 		#include <iostream>
 		#include <fstream>
 		#include <sstream>
 		#include <set>
 		#include <map>
 		#include <lemon/core.h>
 		#include <lemon/lgf_writer.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		namespace lemon {
 		  namespace _reader_bits {
 		    template <typename Value>
 		    struct DefaultConverter {
 		      Value operator()(const std::string& str) {
 		        std::istringstream is(str);
 		        Value value;
 		        if (!(is >> value)) {
 		          throw FormatError("Cannot read token");
+		        }
 		        char c;
 		        if (is >> std::ws >> c) {
 		          throw FormatError("Remaining characters in token");
+		        }
 		        return value;
+		      }
 		    };
 		    template <>
 		    struct DefaultConverter<std::string> {
 		      std::string operator()(const std::string& str) {
 		        return str;
+		      }
 		    };
 		    template <typename _Item>
 		    class MapStorageBase {
 		    public:
 		      typedef _Item Item;
 		    public:
 		      MapStorageBase() {}
 		      virtual ~MapStorageBase() {}
 		      virtual void set(const Item& item, const std::string& value) = 0;
 		    };
 		    template <typename _Item, typename _Map,
 		              typename _Converter = DefaultConverter<typename _Map::Value> >
 		    class MapStorage : public MapStorageBase<_Item> {
 		    public:
 		      typedef _Map Map;
 		      typedef _Converter Converter;
 		      typedef _Item Item;
 		    private:
 		      Map& _map;
 		      Converter _converter;
 		    public:
 		      MapStorage(Map& map, const Converter& converter = Converter())
 		        : _map(map), _converter(converter) {}
 		      virtual ~MapStorage() {}
 		      virtual void set(const Item& item ,const std::string& value) {
 		        _map.set(item, _converter(value));
+		      }
 		    };
 		    template <typename _Graph, bool _dir, typename _Map,
 		              typename _Converter = DefaultConverter<typename _Map::Value> >
 		    class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
 		    public:
 		      typedef _Map Map;
 		      typedef _Converter Converter;
 		      typedef _Graph Graph;
 		      typedef typename Graph::Edge Item;
 		      static const bool dir = _dir;
 		    private:
 		      const Graph& _graph;
 		      Map& _map;
 		      Converter _converter;
 		    public:
 		      GraphArcMapStorage(const Graph& graph, Map& map,
 		                         const Converter& converter = Converter())
 		        : _graph(graph), _map(map), _converter(converter) {}
 		      virtual ~GraphArcMapStorage() {}
 		      virtual void set(const Item& item ,const std::string& value) {
 		        _map.set(_graph.direct(item, dir), _converter(value));
+		      }
 		    };
 		    class ValueStorageBase {
 		    public:
 		      ValueStorageBase() {}
 		      virtual ~ValueStorageBase() {}
 		      virtual void set(const std::string&) = 0;
 		    };
 		    template <typename _Value, typename _Converter = DefaultConverter<_Value> >
 		    class ValueStorage : public ValueStorageBase {
 		    public:
 		      typedef _Value Value;
 		      typedef _Converter Converter;
 		    private:
 		      Value& _value;
 		      Converter _converter;
 		    public:
 		      ValueStorage(Value& value, const Converter& converter = Converter())
 		        : _value(value), _converter(converter) {}
 		      virtual void set(const std::string& value) {
 		        _value = _converter(value);
+		      }
 		    };
 		    template <typename Value>
 		    struct MapLookUpConverter {
 		      const std::map<std::string, Value>& _map;
 		      MapLookUpConverter(const std::map<std::string, Value>& map)
 		        : _map(map) {}
 		      Value operator()(const std::string& str) {
 		        typename std::map<std::string, Value>::const_iterator it =
 		          _map.find(str);
 		        if (it == _map.end()) {
 		          std::ostringstream msg;
 		          msg << "Item not found: " << str;
 		          throw FormatError(msg.str());
+		        }
 		        return it->second;
+		      }
 		    };
 		    template <typename Graph>
 		    struct GraphArcLookUpConverter {
 		      const Graph& _graph;
 		      const std::map<std::string, typename Graph::Edge>& _map;
 		      GraphArcLookUpConverter(const Graph& graph,
 		                              const std::map<std::string,
 		                                             typename Graph::Edge>& map)
 		        : _graph(graph), _map(map) {}
 		      typename Graph::Arc operator()(const std::string& str) {
 		        if (str.empty() || (str[0] != '+' && str[0] != '-')) {
 		          throw FormatError("Item must start with '+' or '-'");
+		        }
 		        typename std::map<std::string, typename Graph::Edge>
 		          ::const_iterator it = _map.find(str.substr(1));
 		        if (it == _map.end()) {
 		          throw FormatError("Item not found");
+		        }
 		        return _graph.direct(it->second, str[0] == '+');
+		      }
 		    };
 		    inline bool isWhiteSpace(char c) {
 		      return c == ' ' || c == '\t' || c == '\v' ||
 		        c == '\n' || c == '\r' || c == '\f';
+		    }
 		    inline bool isOct(char c) {
 		      return '0' <= c && c <='7';
+		    }
 		    inline int valueOct(char c) {
 		      LEMON_ASSERT(isOct(c), "The character is not octal.");
 		      return c - '0';
+		    }
 		    inline bool isHex(char c) {
 		      return ('0' <= c && c <= '9') ||
 		        ('a' <= c && c <= 'z') ||
 		        ('A' <= c && c <= 'Z');
+		    }
 		    inline int valueHex(char c) {
 		      LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
 		      if ('0' <= c && c <= '9') return c - '0';
 		      if ('a' <= c && c <= 'z') return c - 'a' + 10;
 		      return c - 'A' + 10;
+		    }
 		    inline bool isIdentifierFirstChar(char c) {
 		      return ('a' <= c && c <= 'z') ||
 		        ('A' <= c && c <= 'Z') || c == '_';
+		    }
 		    inline bool isIdentifierChar(char c) {
 		      return isIdentifierFirstChar(c) ||
 		        ('0' <= c && c <= '9');
+		    }
 		    inline char readEscape(std::istream& is) {
 		      char c;
 		      if (!is.get(c))
 		        throw FormatError("Escape format error");
 		      switch (c) {
 		      case '\\':
 		        return '\\';
 		      case '\"':
 		        return '\"';
 		      case '\'':
 		        return '\'';
 		      case '\?':
 		        return '\?';
 		      case 'a':
 		        return '\a';
 		      case 'b':
 		        return '\b';
 		      case 'f':
 		        return '\f';
 		      case 'n':
 		        return '\n';
 		      case 'r':
 		        return '\r';
 		      case 't':
 		        return '\t';
 		      case 'v':
 		        return '\v';
 		      case 'x':
+		        {
 		          int code;
 		          if (!is.get(c) || !isHex(c))
 		            throw FormatError("Escape format error");
 		          else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
 		          else code = code * 16 + valueHex(c);
 		          return code;
+		        }
 		      default:
+		        {
 		          int code;
 		          if (!isOct(c))
 		            throw FormatError("Escape format error");
 		          else if (code = valueOct(c), !is.get(c) || !isOct(c))
 		            is.putback(c);
 		          else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
 		            is.putback(c);
 		          else code = code * 8 + valueOct(c);
 		          return code;
+		        }
+		      }
+		    }
 		    inline std::istream& readToken(std::istream& is, std::string& str) {
 		      std::ostringstream os;
 		      char c;
 		      is >> std::ws;
 		      if (!is.get(c))
 		        return is;
 		      if (c == '\"') {
 		        while (is.get(c) && c != '\"') {
 		          if (c == '\\')
 		            c = readEscape(is);
 		          os << c;
+		        }
 		        if (!is)
 		          throw FormatError("Quoted format error");
 		      } else {
 		        is.putback(c);
 		        while (is.get(c) && !isWhiteSpace(c)) {
 		          if (c == '\\')
 		            c = readEscape(is);
 		          os << c;
+		        }
 		        if (!is) {
 		          is.clear();
 		        } else {
 		          is.putback(c);
+		        }
+		      }
 		      str = os.str();
 		      return is;
+		    }
 		    class Section {
 		    public:
 		      virtual ~Section() {}
 		      virtual void process(std::istream& is, int& line_num) = 0;
 		    };
 		    template <typename Functor>
 		    class LineSection : public Section {
 		    private:
 		      Functor _functor;
 		    public:
 		      LineSection(const Functor& functor) : _functor(functor) {}
 		      virtual ~LineSection() {}
 		      virtual void process(std::istream& is, int& line_num) {
 		        char c;
 		        std::string line;
 		        while (is.get(c) && c != '@') {
 		          if (c == '\n') {
 		            ++line_num;
 		          } else if (c == '#') {
 		            getline(is, line);
 		            ++line_num;
 		          } else if (!isWhiteSpace(c)) {
 		            is.putback(c);
 		            getline(is, line);
 		            _functor(line);
 		            ++line_num;
+		          }
+		        }
 		        if (is) is.putback(c);
 		        else if (is.eof()) is.clear();
+		      }
 		    };
 		    template <typename Functor>
 		    class StreamSection : public Section {
 		    private:
 		      Functor _functor;
 		    public:
 		      StreamSection(const Functor& functor) : _functor(functor) {}
 		      virtual ~StreamSection() {}
 		      virtual void process(std::istream& is, int& line_num) {
 		        _functor(is, line_num);
 		        char c;
 		        std::string line;
 		        while (is.get(c) && c != '@') {
 		          if (c == '\n') {
 		            ++line_num;
 		          } else if (!isWhiteSpace(c)) {
 		            getline(is, line);
 		            ++line_num;
+		          }
+		        }
 		        if (is) is.putback(c);
 		        else if (is.eof()) is.clear();
+		      }
 		    };
+		  }
 		  template <typename Digraph>
 		  class DigraphReader;
 		  template <typename Digraph>
-		  DigraphReader<Digraph> digraphReader(Digraph& digraph,
 		  DigraphReader<Digraph> digraphReader(Digraph& digraph,
 		                                       std::istream& is = std::cin);
 		  template <typename Digraph>
 		  DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn);
 		  template <typename Digraph>
 		  DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn);
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief \ref lgf-format "LGF" reader for directed graphs
 		  ///
 		  /// This utility reads an \ref lgf-format "LGF" file.
 		  ///
 		  /// The reading method does a batch processing. The user creates a
 		  /// reader object, then various reading rules can be added to the
 		  /// reader, and eventually the reading is executed with the \c run()
 		  /// member function. A map reading rule can be added to the reader
 		  /// with the \c nodeMap() or \c arcMap() members. An optional
 		  /// converter parameter can also be added as a standard functor
 		  /// converting from \c std::string to the value type of the map. If it
 		  /// is set, it will determine how the tokens in the file should be
 		  /// converted to the value type of the map. If the functor is not set,
 		  /// then a default conversion will be used. One map can be read into
 		  /// multiple map objects at the same time. The \c attribute(), \c
 		  /// node() and \c arc() functions are used to add attribute reading
 		  /// rules.
 		  ///
 		  ///\code
 		  /// DigraphReader<Digraph>(digraph, std::cin).
 		  ///   nodeMap("coordinates", coord_map).
 		  ///   arcMap("capacity", cap_map).
 		  ///   node("source", src).
 		  ///   node("target", trg).
 		  ///   attribute("caption", caption).
 		  ///   run();
 		  ///\endcode
 		  ///
 		  /// By default the reader uses the first section in the file of the
 		  /// proper type. If a section has an optional name, then it can be
 		  /// selected for reading by giving an optional name parameter to the
 		  /// \c nodes(), \c arcs() or \c attributes() functions.
 		  ///
 		  /// The \c useNodes() and \c useArcs() functions are used to tell the reader
 		  /// that the nodes or arcs should not be constructed (added to the
 		  /// graph) during the reading, but instead the label map of the items
 		  /// are given as a parameter of these functions. An
 		  /// application of these functions is multipass reading, which is
 		  /// important if two \c \@arcs sections must be read from the
 		  /// file. In this case the first phase would read the node set and one
 		  /// of the arc sets, while the second phase would read the second arc
 		  /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
 		  /// The previously read label node map should be passed to the \c
 		  /// useNodes() functions. Another application of multipass reading when
 		  /// paths are given as a node map or an arc map.
 		  /// It is impossible to read this in
 		  /// a single pass, because the arcs are not constructed when the node
 		  /// maps are read.
 		  template <typename _Digraph>
 		  class DigraphReader {
 		  public:
 		    typedef _Digraph Digraph;
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  private:
 		    std::istream* _is;
 		    bool local_is;
 		    std::string _filename;
 		    Digraph& _digraph;
 		    std::string _nodes_caption;
 		    std::string _arcs_caption;
 		    std::string _attributes_caption;
 		    typedef std::map<std::string, Node> NodeIndex;
 		    NodeIndex _node_index;
 		    typedef std::map<std::string, Arc> ArcIndex;
 		    ArcIndex _arc_index;
 		    typedef std::vector<std::pair<std::string,
 		      _reader_bits::MapStorageBase<Node>*> > NodeMaps;
 		    NodeMaps _node_maps;
 		    typedef std::vector<std::pair<std::string,
 		      _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
 		    ArcMaps _arc_maps;
 		    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
 		      Attributes;
 		    Attributes _attributes;
 		    bool _use_nodes;
 		    bool _use_arcs;
 		    bool _skip_nodes;
 		    bool _skip_arcs;
 		    int line_num;
 		    std::istringstream line;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph reader, which reads from the given
 		    /// input stream.
 		    DigraphReader(Digraph& digraph, std::istream& is = std::cin)
 		      : _is(&is), local_is(false), _digraph(digraph),
 		        _use_nodes(false), _use_arcs(false),
 		        _skip_nodes(false), _skip_arcs(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph reader, which reads from the given
 		    /// file.
 		    DigraphReader(Digraph& digraph, const std::string& fn)
 		      : _is(new std::ifstream(fn.c_str())), local_is(true),
 		        _filename(fn), _digraph(digraph),
 		        _use_nodes(false), _use_arcs(false),
 		        _skip_nodes(false), _skip_arcs(false) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph reader, which reads from the given
 		    /// file.
 		    DigraphReader(Digraph& digraph, const char* fn)
 		      : _is(new std::ifstream(fn)), local_is(true),
 		        _filename(fn), _digraph(digraph),
 		        _use_nodes(false), _use_arcs(false),
 		        _skip_nodes(false), _skip_arcs(false) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~DigraphReader() {
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename ArcMaps::iterator it = _arc_maps.begin();
 		           it != _arc_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_is) {
 		        delete _is;
+		      }
+		    }
 		  private:
 		    template <typename DGR>
 		    friend DigraphReader<DGR> digraphReader(DGR& digraph, std::istream& is);
 		    template <typename DGR>
-		    friend DigraphReader<DGR> digraphReader(DGR& digraph,
 		    friend DigraphReader<DGR> digraphReader(DGR& digraph,
 		                                            const std::string& fn);
 		    template <typename DGR>
 		    friend DigraphReader<DGR> digraphReader(DGR& digraph, const char *fn);
 		    DigraphReader(DigraphReader& other)
 		      : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
 		        _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),
 		        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
 		      other._is = 0;
 		      other.local_is = false;
 		      _node_index.swap(other._node_index);
 		      _arc_index.swap(other._arc_index);
 		      _node_maps.swap(other._node_maps);
 		      _arc_maps.swap(other._arc_maps);
 		      _attributes.swap(other._attributes);
 		      _nodes_caption = other._nodes_caption;
 		      _arcs_caption = other._arcs_caption;
 		      _attributes_caption = other._attributes_caption;
+		    }
 		    DigraphReader& operator=(const DigraphReader&);
 		  public:
 		    /// \name Reading rules
 		    /// @{
 		    /// \brief Node map reading rule
 		    ///
 		    /// Add a node map reading rule to the reader.
 		    template <typename Map>
 		    DigraphReader& nodeMap(const std::string& caption, Map& map) {
 		      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Node>* storage =
 		        new _reader_bits::MapStorage<Node, Map>(map);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node map reading rule
 		    ///
 		    /// Add a node map reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Map, typename Converter>
 		    DigraphReader& nodeMap(const std::string& caption, Map& map,
 		                           const Converter& converter = Converter()) {
 		      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Node>* storage =
 		        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map reading rule
 		    ///
 		    /// Add an arc map reading rule to the reader.
 		    template <typename Map>
 		    DigraphReader& arcMap(const std::string& caption, Map& map) {
 		      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Arc>* storage =
 		        new _reader_bits::MapStorage<Arc, Map>(map);
 		      _arc_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map reading rule
 		    ///
 		    /// Add an arc map reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Map, typename Converter>
 		    DigraphReader& arcMap(const std::string& caption, Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Arc>* storage =
 		        new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
 		      _arc_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute reading rule
 		    ///
 		    /// Add an attribute reading rule to the reader.
 		    template <typename Value>
 		    DigraphReader& attribute(const std::string& caption, Value& value) {
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Value>(value);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute reading rule
 		    ///
 		    /// Add an attribute reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Value, typename Converter>
 		    DigraphReader& attribute(const std::string& caption, Value& value,
 		                             const Converter& converter = Converter()) {
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node reading rule
 		    ///
 		    /// Add a node reading rule to reader.
 		    DigraphReader& node(const std::string& caption, Node& node) {
 		      typedef _reader_bits::MapLookUpConverter<Node> Converter;
 		      Converter converter(_node_index);
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc reading rule
 		    ///
 		    /// Add an arc reading rule to reader.
 		    DigraphReader& arc(const std::string& caption, Arc& arc) {
 		      typedef _reader_bits::MapLookUpConverter<Arc> Converter;
 		      Converter converter(_arc_index);
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Select section by name
 		    /// @{
 		    /// \brief Set \c \@nodes section to be read
 		    ///
 		    /// Set \c \@nodes section to be read
 		    DigraphReader& nodes(const std::string& caption) {
 		      _nodes_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Set \c \@arcs section to be read
 		    ///
 		    /// Set \c \@arcs section to be read
 		    DigraphReader& arcs(const std::string& caption) {
 		      _arcs_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Set \c \@attributes section to be read
 		    ///
 		    /// Set \c \@attributes section to be read
 		    DigraphReader& attributes(const std::string& caption) {
 		      _attributes_caption = caption;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Using previously constructed node or arc set
 		    /// @{
 		    /// \brief Use previously constructed node set
 		    ///
 		    /// Use previously constructed node set, and specify the node
 		    /// label map.
 		    template <typename Map>
 		    DigraphReader& useNodes(const Map& map) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
 		      _use_nodes = true;
 		      _writer_bits::DefaultConverter<typename Map::Value> converter;
 		      for (NodeIt n(_digraph); n != INVALID; ++n) {
 		        _node_index.insert(std::make_pair(converter(map[n]), n));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed node set
 		    ///
 		    /// Use previously constructed node set, and specify the node
 		    /// label map and a functor which converts the label map values to
 		    /// \c std::string.
 		    template <typename Map, typename Converter>
 		    DigraphReader& useNodes(const Map& map,
 		                            const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
 		      _use_nodes = true;
 		      for (NodeIt n(_digraph); n != INVALID; ++n) {
 		        _node_index.insert(std::make_pair(converter(map[n]), n));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed arc set
 		    ///
 		    /// Use previously constructed arc set, and specify the arc
 		    /// label map.
 		    template <typename Map>
 		    DigraphReader& useArcs(const Map& map) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
 		      _use_arcs = true;
 		      _writer_bits::DefaultConverter<typename Map::Value> converter;
 		      for (ArcIt a(_digraph); a != INVALID; ++a) {
 		        _arc_index.insert(std::make_pair(converter(map[a]), a));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed arc set
 		    ///
 		    /// Use previously constructed arc set, and specify the arc
 		    /// label map and a functor which converts the label map values to
 		    /// \c std::string.
 		    template <typename Map, typename Converter>
 		    DigraphReader& useArcs(const Map& map,
 		                           const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
 		      _use_arcs = true;
 		      for (ArcIt a(_digraph); a != INVALID; ++a) {
 		        _arc_index.insert(std::make_pair(converter(map[a]), a));
+		      }
 		      return *this;
+		    }
 		    /// \brief Skips the reading of node section
 		    ///
 		    /// Omit the reading of the node section. This implies that each node
 		    /// map reading rule will be abandoned, and the nodes of the graph
 		    /// will not be constructed, which usually cause that the arc set
 		    /// could not be read due to lack of node name resolving.
 		    /// Therefore \c skipArcs() function should also be used, or
 		    /// \c useNodes() should be used to specify the label of the nodes.
 		    DigraphReader& skipNodes() {
 		      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
 		      _skip_nodes = true;
 		      return *this;
+		    }
 		    /// \brief Skips the reading of arc section
 		    ///
 		    /// Omit the reading of the arc section. This implies that each arc
 		    /// map reading rule will be abandoned, and the arcs of the graph
 		    /// will not be constructed.
 		    DigraphReader& skipArcs() {
 		      LEMON_ASSERT(!_skip_arcs, "Skip arcs already set");
 		      _skip_arcs = true;
 		      return *this;
+		    }
 		    /// @}
 		  private:
 		    bool readLine() {
 		      std::string str;
 		      while(++line_num, std::getline(*_is, str)) {
 		        line.clear(); line.str(str);
 		        char c;
 		        if (line >> std::ws >> c && c != '#') {
 		          line.putback(c);
 		          return true;
+		        }
+		      }
 		      return false;
+		    }
 		    bool readSuccess() {
 		      return static_cast<bool>(*_is);
+		    }
 		    void skipSection() {
 		      char c;
 		      while (readSuccess() && line >> c && c != '@') {
 		        readLine();
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
+		    }
 		    void readNodes() {
 		      std::vector<int> map_index(_node_maps.size());
 		      int map_num, label_index;
 		      char c;
 		      if (!readLine() || !(line >> c) || c == '@') {
 		        if (readSuccess() && line) line.putback(c);
 		        if (!_node_maps.empty())
 		          throw FormatError("Cannot find map names");
 		        return;
+		      }
 		      line.putback(c);
+		      {
 		        std::map<std::string, int> maps;
 		        std::string map;
 		        int index = 0;
 		        while (_reader_bits::readToken(line, map)) {
 		          if (maps.find(map) != maps.end()) {
 		            std::ostringstream msg;
 		            msg << "Multiple occurence of node map: " << map;
 		            throw FormatError(msg.str());
+		          }
 		          maps.insert(std::make_pair(map, index));
 		          ++index;
+		        }
 		        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
 		          std::map<std::string, int>::iterator jt =
 		            maps.find(_node_maps[i].first);
 		          if (jt == maps.end()) {
 		            std::ostringstream msg;
 		            msg << "Map not found: " << _node_maps[i].first;
 		            throw FormatError(msg.str());
+		          }
 		          map_index[i] = jt->second;
+		        }
+		        {
 		          std::map<std::string, int>::iterator jt = maps.find("label");
 		          if (jt != maps.end()) {
 		            label_index = jt->second;
 		          } else {
 		            label_index = -1;
+		          }
+		        }
 		        map_num = maps.size();
+		      }
 		      while (readLine() && line >> c && c != '@') {
 		        line.putback(c);
 		        std::vector<std::string> tokens(map_num);
 		        for (int i = 0; i < map_num; ++i) {
 		          if (!_reader_bits::readToken(line, tokens[i])) {
 		            std::ostringstream msg;
 		            msg << "Column not found (" << i + 1 << ")";
 		            throw FormatError(msg.str());
+		          }
+		        }
 		        if (line >> std::ws >> c)
 		          throw FormatError("Extra character at the end of line");
 		        Node n;
 		        if (!_use_nodes) {
 		          n = _digraph.addNode();
 		          if (label_index != -1)
 		            _node_index.insert(std::make_pair(tokens[label_index], n));
 		        } else {
 		          if (label_index == -1)
 		            throw FormatError("Label map not found");
 		          typename std::map<std::string, Node>::iterator it =
 		            _node_index.find(tokens[label_index]);
 		          if (it == _node_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Node with label not found: " << tokens[label_index];
 		            throw FormatError(msg.str());
+		          }
 		          n = it->second;
+		        }
 		        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
 		          _node_maps[i].second->set(n, tokens[map_index[i]]);
+		        }
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
+		    }
 		    void readArcs() {
 		      std::vector<int> map_index(_arc_maps.size());
 		      int map_num, label_index;
 		      char c;
 		      if (!readLine() || !(line >> c) || c == '@') {
 		        if (readSuccess() && line) line.putback(c);
 		        if (!_arc_maps.empty())
 		          throw FormatError("Cannot find map names");
 		        return;
+		      }
 		      line.putback(c);
+		      {
 		        std::map<std::string, int> maps;
 		        std::string map;
 		        int index = 0;
 		        while (_reader_bits::readToken(line, map)) {
 		          if(map == "-") {
 		              if(index!=0)
 		                throw FormatError("'-' is not allowed as a map name");
 		              else if (line >> std::ws >> c)
 		                throw FormatError("Extra character at the end of line");
 		              else break;
+		            }
 		          if (maps.find(map) != maps.end()) {
 		            std::ostringstream msg;
 		            msg << "Multiple occurence of arc map: " << map;
 		            throw FormatError(msg.str());
+		          }
 		          maps.insert(std::make_pair(map, index));
 		          ++index;
+		        }
 		        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
 		          std::map<std::string, int>::iterator jt =
 		            maps.find(_arc_maps[i].first);
 		          if (jt == maps.end()) {
 		            std::ostringstream msg;
 		            msg << "Map not found: " << _arc_maps[i].first;
 		            throw FormatError(msg.str());
+		          }
 		          map_index[i] = jt->second;
+		        }
+		        {
 		          std::map<std::string, int>::iterator jt = maps.find("label");
 		          if (jt != maps.end()) {
 		            label_index = jt->second;
 		          } else {
 		            label_index = -1;
+		          }
+		        }
 		        map_num = maps.size();
+		      }
 		      while (readLine() && line >> c && c != '@') {
 		        line.putback(c);
 		        std::string source_token;
 		        std::string target_token;
 		        if (!_reader_bits::readToken(line, source_token))
 		          throw FormatError("Source not found");
 		        if (!_reader_bits::readToken(line, target_token))
 		          throw FormatError("Target not found");
 		        std::vector<std::string> tokens(map_num);
 		        for (int i = 0; i < map_num; ++i) {
 		          if (!_reader_bits::readToken(line, tokens[i])) {
 		            std::ostringstream msg;
 		            msg << "Column not found (" << i + 1 << ")";
 		            throw FormatError(msg.str());
+		          }
+		        }
 		        if (line >> std::ws >> c)
 		          throw FormatError("Extra character at the end of line");
 		        Arc a;
 		        if (!_use_arcs) {
 		          typename NodeIndex::iterator it;
 		          it = _node_index.find(source_token);
 		          if (it == _node_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Item not found: " << source_token;
 		            throw FormatError(msg.str());
+		          }
 		          Node source = it->second;
 		          it = _node_index.find(target_token);
 		          if (it == _node_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Item not found: " << target_token;
 		            throw FormatError(msg.str());
+		          }
 		          Node target = it->second;
 		          a = _digraph.addArc(source, target);
 		          if (label_index != -1)
 		            _arc_index.insert(std::make_pair(tokens[label_index], a));
 		        } else {
 		          if (label_index == -1)
 		            throw FormatError("Label map not found");
 		          typename std::map<std::string, Arc>::iterator it =
 		            _arc_index.find(tokens[label_index]);
 		          if (it == _arc_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Arc with label not found: " << tokens[label_index];
 		            throw FormatError(msg.str());
+		          }
 		          a = it->second;
+		        }
 		        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
 		          _arc_maps[i].second->set(a, tokens[map_index[i]]);
+		        }
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
+		    }
 		    void readAttributes() {
 		      std::set<std::string> read_attr;
 		      char c;
 		      while (readLine() && line >> c && c != '@') {
 		        line.putback(c);
 		        std::string attr, token;
 		        if (!_reader_bits::readToken(line, attr))
 		          throw FormatError("Attribute name not found");
 		        if (!_reader_bits::readToken(line, token))
 		          throw FormatError("Attribute value not found");
 		        if (line >> c)
 		          throw FormatError("Extra character at the end of line");
+		        {
 		          std::set<std::string>::iterator it = read_attr.find(attr);
 		          if (it != read_attr.end()) {
 		            std::ostringstream msg;
 		            msg << "Multiple occurence of attribute: " << attr;
 		            throw FormatError(msg.str());
+		          }
 		          read_attr.insert(attr);
+		        }
+		        {
 		          typename Attributes::iterator it = _attributes.lower_bound(attr);
 		          while (it != _attributes.end() && it->first == attr) {
 		            it->second->set(token);
 		            ++it;
+		          }
+		        }
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        if (read_attr.find(it->first) == read_attr.end()) {
 		          std::ostringstream msg;
 		          msg << "Attribute not found: " << it->first;
 		          throw FormatError(msg.str());
+		        }
+		      }
+		    }
 		  public:
 		    /// \name Execution of the reader
 		    /// @{
 		    /// \brief Start the batch processing
 		    ///
 		    /// This function starts the batch processing
 		    void run() {
 		      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
 		      bool nodes_done = _skip_nodes;
 		      bool arcs_done = _skip_arcs;
 		      bool attributes_done = false;
 		      line_num = 0;
 		      readLine();
 		      skipSection();
 		      while (readSuccess()) {
 		        try {
 		          char c;
 		          std::string section, caption;
 		          line >> c;
 		          _reader_bits::readToken(line, section);
 		          _reader_bits::readToken(line, caption);
 		          if (line >> c)
 		            throw FormatError("Extra character at the end of line");
 		          if (section == "nodes" && !nodes_done) {
 		            if (_nodes_caption.empty() || _nodes_caption == caption) {
 		              readNodes();
 		              nodes_done = true;
+		            }
 		          } else if ((section == "arcs" || section == "edges") &&
 		                     !arcs_done) {
 		            if (_arcs_caption.empty() || _arcs_caption == caption) {
 		              readArcs();
 		              arcs_done = true;
+		            }
 		          } else if (section == "attributes" && !attributes_done) {
 		            if (_attributes_caption.empty() || _attributes_caption == caption) {
 		              readAttributes();
 		              attributes_done = true;
+		            }
 		          } else {
 		            readLine();
 		            skipSection();
+		          }
 		        } catch (FormatError& error) {
 		          error.line(line_num);
 		          error.file(_filename);
 		          throw;
+		        }
+		      }
 		      if (!nodes_done) {
 		        throw FormatError("Section @nodes not found");
+		      }
 		      if (!arcs_done) {
 		        throw FormatError("Section @arcs not found");
+		      }
 		      if (!attributes_done && !_attributes.empty()) {
 		        throw FormatError("Section @attributes not found");
+		      }
+		    }
 		    /// @}
 		  };
 		  /// \brief Return a \ref DigraphReader class
 		  ///
 		  /// This function just returns a \ref DigraphReader class.
 		  /// \relates DigraphReader
 		  template <typename Digraph>
 		  DigraphReader<Digraph> digraphReader(Digraph& digraph, std::istream& is) {
 		    DigraphReader<Digraph> tmp(digraph, is);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref DigraphReader class
 		  ///
 		  /// This function just returns a \ref DigraphReader class.
 		  /// \relates DigraphReader
 		  template <typename Digraph>
 		  DigraphReader<Digraph> digraphReader(Digraph& digraph,
 		                                       const std::string& fn) {
 		    DigraphReader<Digraph> tmp(digraph, fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref DigraphReader class
 		  ///
 		  /// This function just returns a \ref DigraphReader class.
 		  /// \relates DigraphReader
 		  template <typename Digraph>
 		  DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) {
 		    DigraphReader<Digraph> tmp(digraph, fn);
 		    return tmp;
+		  }
 		  template <typename Graph>
 		  class GraphReader;
 		  template <typename Graph>
-		  GraphReader<Graph> graphReader(Graph& graph,
 		  GraphReader<Graph> graphReader(Graph& graph,
 		                                 std::istream& is = std::cin);
 		  template <typename Graph>
 		  GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
 		  template <typename Graph>
 		  GraphReader<Graph> graphReader(Graph& graph, const char *fn);
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief \ref lgf-format "LGF" reader for undirected graphs
 		  ///
 		  /// This utility reads an \ref lgf-format "LGF" file.
 		  ///
 		  /// It can be used almost the same way as \c DigraphReader.
 		  /// The only difference is that this class can handle edges and
 		  /// edge maps as well as arcs and arc maps.
 		  ///
 		  /// The columns in the \c \@edges (or \c \@arcs) section are the
 		  /// edge maps. However, if there are two maps with the same name
 		  /// prefixed with \c '+' and \c '-', then these can be read into an
 		  /// arc map.  Similarly, an attribute can be read into an arc, if
 		  /// it's value is an edge label prefixed with \c '+' or \c '-'.
 		  template <typename _Graph>
 		  class GraphReader {
 		  public:
 		    typedef _Graph Graph;
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  private:
 		    std::istream* _is;
 		    bool local_is;
 		    std::string _filename;
 		    Graph& _graph;
 		    std::string _nodes_caption;
 		    std::string _edges_caption;
 		    std::string _attributes_caption;
 		    typedef std::map<std::string, Node> NodeIndex;
 		    NodeIndex _node_index;
 		    typedef std::map<std::string, Edge> EdgeIndex;
 		    EdgeIndex _edge_index;
 		    typedef std::vector<std::pair<std::string,
 		      _reader_bits::MapStorageBase<Node>*> > NodeMaps;
 		    NodeMaps _node_maps;
 		    typedef std::vector<std::pair<std::string,
 		      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
 		    EdgeMaps _edge_maps;
 		    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
 		      Attributes;
 		    Attributes _attributes;
 		    bool _use_nodes;
 		    bool _use_edges;
 		    bool _skip_nodes;
 		    bool _skip_edges;
 		    int line_num;
 		    std::istringstream line;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct an undirected graph reader, which reads from the given
 		    /// input stream.
 		    GraphReader(Graph& graph, std::istream& is = std::cin)
 		      : _is(&is), local_is(false), _graph(graph),
 		        _use_nodes(false), _use_edges(false),
 		        _skip_nodes(false), _skip_edges(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct an undirected graph reader, which reads from the given
 		    /// file.
 		    GraphReader(Graph& graph, const std::string& fn)
 		      : _is(new std::ifstream(fn.c_str())), local_is(true),
 		        _filename(fn), _graph(graph),
 		        _use_nodes(false), _use_edges(false),
 		        _skip_nodes(false), _skip_edges(false) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct an undirected graph reader, which reads from the given
 		    /// file.
 		    GraphReader(Graph& graph, const char* fn)
 		      : _is(new std::ifstream(fn)), local_is(true),
 		        _filename(fn), _graph(graph),
 		        _use_nodes(false), _use_edges(false),
 		        _skip_nodes(false), _skip_edges(false) {
 		      if (!(*_is)) {
 		        delete _is;
 		        throw IoError("Cannot open file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~GraphReader() {
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		           it != _edge_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_is) {
 		        delete _is;
+		      }
+		    }
 		  private:
 		    template <typename GR>
 		    friend GraphReader<GR> graphReader(GR& graph, std::istream& is);
 		    template <typename GR>
-		    friend GraphReader<GR> graphReader(GR& graph, const std::string& fn);
 		    friend GraphReader<GR> graphReader(GR& graph, const std::string& fn);
 		    template <typename GR>
 		    friend GraphReader<GR> graphReader(GR& graph, const char *fn);
 		    GraphReader(GraphReader& other)
 		      : _is(other._is), local_is(other.local_is), _graph(other._graph),
 		        _use_nodes(other._use_nodes), _use_edges(other._use_edges),
 		        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
 		      other._is = 0;
 		      other.local_is = false;
 		      _node_index.swap(other._node_index);
 		      _edge_index.swap(other._edge_index);
 		      _node_maps.swap(other._node_maps);
 		      _edge_maps.swap(other._edge_maps);
 		      _attributes.swap(other._attributes);
 		      _nodes_caption = other._nodes_caption;
 		      _edges_caption = other._edges_caption;
 		      _attributes_caption = other._attributes_caption;
+		    }
 		    GraphReader& operator=(const GraphReader&);
 		  public:
 		    /// \name Reading rules
 		    /// @{
 		    /// \brief Node map reading rule
 		    ///
 		    /// Add a node map reading rule to the reader.
 		    template <typename Map>
 		    GraphReader& nodeMap(const std::string& caption, Map& map) {
 		      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Node>* storage =
 		        new _reader_bits::MapStorage<Node, Map>(map);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node map reading rule
 		    ///
 		    /// Add a node map reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Map, typename Converter>
 		    GraphReader& nodeMap(const std::string& caption, Map& map,
 		                           const Converter& converter = Converter()) {
 		      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Node>* storage =
 		        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge map reading rule
 		    ///
 		    /// Add an edge map reading rule to the reader.
 		    template <typename Map>
 		    GraphReader& edgeMap(const std::string& caption, Map& map) {
 		      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Edge>* storage =
 		        new _reader_bits::MapStorage<Edge, Map>(map);
 		      _edge_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge map reading rule
 		    ///
 		    /// Add an edge map reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Map, typename Converter>
 		    GraphReader& edgeMap(const std::string& caption, Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Edge>* storage =
 		        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
 		      _edge_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map reading rule
 		    ///
 		    /// Add an arc map reading rule to the reader.
 		    template <typename Map>
 		    GraphReader& arcMap(const std::string& caption, Map& map) {
 		      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Edge>* forward_storage =
 		        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
 		      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
 		      _reader_bits::MapStorageBase<Edge>* backward_storage =
 		        new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
 		      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
 		      return *this;
+		    }
 		    /// \brief Arc map reading rule
 		    ///
 		    /// Add an arc map reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Map, typename Converter>
 		    GraphReader& arcMap(const std::string& caption, Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
 		      _reader_bits::MapStorageBase<Edge>* forward_storage =
 		        new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
 		        (_graph, map, converter);
 		      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
 		      _reader_bits::MapStorageBase<Edge>* backward_storage =
 		        new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
 		        (_graph, map, converter);
 		      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
 		      return *this;
+		    }
 		    /// \brief Attribute reading rule
 		    ///
 		    /// Add an attribute reading rule to the reader.
 		    template <typename Value>
 		    GraphReader& attribute(const std::string& caption, Value& value) {
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Value>(value);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute reading rule
 		    ///
 		    /// Add an attribute reading rule with specialized converter to the
 		    /// reader.
 		    template <typename Value, typename Converter>
 		    GraphReader& attribute(const std::string& caption, Value& value,
 		                             const Converter& converter = Converter()) {
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node reading rule
 		    ///
 		    /// Add a node reading rule to reader.
 		    GraphReader& node(const std::string& caption, Node& node) {
 		      typedef _reader_bits::MapLookUpConverter<Node> Converter;
 		      Converter converter(_node_index);
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge reading rule
 		    ///
 		    /// Add an edge reading rule to reader.
 		    GraphReader& edge(const std::string& caption, Edge& edge) {
 		      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
 		      Converter converter(_edge_index);
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc reading rule
 		    ///
 		    /// Add an arc reading rule to reader.
 		    GraphReader& arc(const std::string& caption, Arc& arc) {
 		      typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
 		      Converter converter(_graph, _edge_index);
 		      _reader_bits::ValueStorageBase* storage =
 		        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
 		      _attributes.insert(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Select section by name
 		    /// @{
 		    /// \brief Set \c \@nodes section to be read
 		    ///
 		    /// Set \c \@nodes section to be read.
 		    GraphReader& nodes(const std::string& caption) {
 		      _nodes_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Set \c \@edges section to be read
 		    ///
 		    /// Set \c \@edges section to be read.
 		    GraphReader& edges(const std::string& caption) {
 		      _edges_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Set \c \@attributes section to be read
 		    ///
 		    /// Set \c \@attributes section to be read.
 		    GraphReader& attributes(const std::string& caption) {
 		      _attributes_caption = caption;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Using previously constructed node or edge set
 		    /// @{
 		    /// \brief Use previously constructed node set
 		    ///
 		    /// Use previously constructed node set, and specify the node
 		    /// label map.
 		    template <typename Map>
 		    GraphReader& useNodes(const Map& map) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
 		      _use_nodes = true;
 		      _writer_bits::DefaultConverter<typename Map::Value> converter;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _node_index.insert(std::make_pair(converter(map[n]), n));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed node set
 		    ///
 		    /// Use previously constructed node set, and specify the node
 		    /// label map and a functor which converts the label map values to
 		    /// \c std::string.
 		    template <typename Map, typename Converter>
 		    GraphReader& useNodes(const Map& map,
 		                            const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
 		      _use_nodes = true;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _node_index.insert(std::make_pair(converter(map[n]), n));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed edge set
 		    ///
 		    /// Use previously constructed edge set, and specify the edge
 		    /// label map.
 		    template <typename Map>
 		    GraphReader& useEdges(const Map& map) {
 		      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
 		      _use_edges = true;
 		      _writer_bits::DefaultConverter<typename Map::Value> converter;
 		      for (EdgeIt a(_graph); a != INVALID; ++a) {
 		        _edge_index.insert(std::make_pair(converter(map[a]), a));
+		      }
 		      return *this;
+		    }
 		    /// \brief Use previously constructed edge set
 		    ///
 		    /// Use previously constructed edge set, and specify the edge
 		    /// label map and a functor which converts the label map values to
 		    /// \c std::string.
 		    template <typename Map, typename Converter>
 		    GraphReader& useEdges(const Map& map,
 		                            const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
 		      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
 		      _use_edges = true;
 		      for (EdgeIt a(_graph); a != INVALID; ++a) {
 		        _edge_index.insert(std::make_pair(converter(map[a]), a));
+		      }
 		      return *this;
+		    }
 		    /// \brief Skip the reading of node section
 		    ///
 		    /// Omit the reading of the node section. This implies that each node
 		    /// map reading rule will be abandoned, and the nodes of the graph
 		    /// will not be constructed, which usually cause that the edge set
 		    /// could not be read due to lack of node name
 		    /// could not be read due to lack of node name resolving.
 		    /// Therefore \c skipEdges() function should also be used, or
 		    /// \c useNodes() should be used to specify the label of the nodes.
 		    GraphReader& skipNodes() {
 		      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
 		      _skip_nodes = true;
 		      return *this;
+		    }
 		    /// \brief Skip the reading of edge section
 		    ///
 		    /// Omit the reading of the edge section. This implies that each edge
 		    /// map reading rule will be abandoned, and the edges of the graph
 		    /// will not be constructed.
 		    GraphReader& skipEdges() {
 		      LEMON_ASSERT(!_skip_edges, "Skip edges already set");
 		      _skip_edges = true;
 		      return *this;
+		    }
 		    /// @}
 		  private:
 		    bool readLine() {
 		      std::string str;
 		      while(++line_num, std::getline(*_is, str)) {
 		        line.clear(); line.str(str);
 		        char c;
 		        if (line >> std::ws >> c && c != '#') {
 		          line.putback(c);
 		          return true;
+		        }
+		      }
 		      return false;
+		    }
 		    bool readSuccess() {
 		      return static_cast<bool>(*_is);
+		    }
 		    void skipSection() {
 		      char c;
 		      while (readSuccess() && line >> c && c != '@') {
 		        readLine();
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
+		    }
 		    void readNodes() {
 		      std::vector<int> map_index(_node_maps.size());
 		      int map_num, label_index;
 		      char c;
 		      if (!readLine() || !(line >> c) || c == '@') {
 		        if (readSuccess() && line) line.putback(c);
 		        if (!_node_maps.empty())
 		          throw FormatError("Cannot find map names");
 		        return;
+		      }
 		      line.putback(c);
+		      {
 		        std::map<std::string, int> maps;
 		        std::string map;
 		        int index = 0;
 		        while (_reader_bits::readToken(line, map)) {
 		          if (maps.find(map) != maps.end()) {
 		            std::ostringstream msg;
 		            msg << "Multiple occurence of node map: " << map;
 		            throw FormatError(msg.str());
+		          }
 		          maps.insert(std::make_pair(map, index));
 		          ++index;
+		        }
 		        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
 		          std::map<std::string, int>::iterator jt =
 		            maps.find(_node_maps[i].first);
 		          if (jt == maps.end()) {
 		            std::ostringstream msg;
 		            msg << "Map not found: " << _node_maps[i].first;
 		            throw FormatError(msg.str());
+		          }
 		          map_index[i] = jt->second;
+		        }
+		        {
 		          std::map<std::string, int>::iterator jt = maps.find("label");
 		          if (jt != maps.end()) {
 		            label_index = jt->second;
 		          } else {
 		            label_index = -1;
+		          }
+		        }
 		        map_num = maps.size();
+		      }
 		      while (readLine() && line >> c && c != '@') {
 		        line.putback(c);
 		        std::vector<std::string> tokens(map_num);
 		        for (int i = 0; i < map_num; ++i) {
 		          if (!_reader_bits::readToken(line, tokens[i])) {
 		            std::ostringstream msg;
 		            msg << "Column not found (" << i + 1 << ")";
 		            throw FormatError(msg.str());
+		          }
+		        }
 		        if (line >> std::ws >> c)
 		          throw FormatError("Extra character at the end of line");
 		        Node n;
 		        if (!_use_nodes) {
 		          n = _graph.addNode();
 		          if (label_index != -1)
 		            _node_index.insert(std::make_pair(tokens[label_index], n));
 		        } else {
 		          if (label_index == -1)
 		            throw FormatError("Label map not found");
 		          typename std::map<std::string, Node>::iterator it =
 		            _node_index.find(tokens[label_index]);
 		          if (it == _node_index.end()) {
 		            std::ostringstream msg;
 		            msg << "Node with label not found: " << tokens[label_index];
 		            throw FormatError(msg.str());
+		          }
 		          n = it->second;
+		        }
 		        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
 		          _node_maps[i].second->set(n, tokens[map_index[i]]);
+		        }
+		      }
 		      if (readSuccess()) {
 		        line.putback(c);
+		      }
+		    }
 		    void readEdges() {
 		      std::vector<int> map_index(_edge_maps.size());
 		      int map_num, label_index;
 		      char c;
 		      if (!readLine() || !(line >> c) || c == '@') {
 		        if (readSuccess() && line) line.putback(c);
 		        if (!_edge_maps.empty())
 		          throw FormatError("Cannot find map names");
 		        return;
+		      }
 		      line.putback(c);
+		      {
 		        std::map<std::string, int> maps;
 		        std::string map;
 		        int index = 0;
 		        while (_reader_bits::readToken(line, map)) {
 		          if(map == "-") {
 		              if(index!=0)
 		                throw FormatError("'-' is not allowed as a map name");
 		              else if (line >> std::ws >> c)
 		                throw FormatError("Extra character at the end of line");
 		              else break;
+		            }
 		          if (maps.find(map) != maps.end()) {
 		            std::ostringstream msg;
 		            msg << "Multiple occurence of edge map: " << map;
 		            throw FormatError(msg.str());
+		          }
 		          maps.insert(std::make_pair(map, index));
 		          ++index;
+		        }
 		        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
 		          std::map<std::string, int>::iterator jt =
 		            maps.find(_edge_maps[i].first);
 		          if (jt == maps.end()) {
 		            std::ostringstream msg;
 		            msg << "Map not found: " << _edge_maps[i].first;
 		            throw FormatError(msg.str());
+		          }
 		          map_index[i] = jt->second;
+		        }
+		        {
 		          std::map<std::string, int>::iterator jt = maps.find("label");
 		          if (jt != maps.end()) {
 		            label_index = jt->second;
 		          } else {
 		            label_index = -1;
+		          }
+		        }
 		        map_num = maps.size();
+		      }
 		      while (readLine() && line >> c && c != '@') {
 		        line.putback(c);
 		        std::string source_token;
 		        std::string target_token;
 		        if (!_reader_bits::readToken(line, source_token))
 		          throw FormatError("Node u not found");
 		        if (!_reader_bits::readToken(line, target_token))
 		          throw FormatError("Node v not found");
 		        std::vector<std::string> tokens(map_num);
 		        for (int i = 0; i < map_num; ++i) {
 		          if (!_reader_bits::readToken(line, tokens[i])) {
 		            std::ostringstream msg;
 		            msg << "Column not found (" << i + 1 << ")";
 		            throw FormatError(msg.str());
+		          }
+		        }
 		        if (line >> std::ws >> c)
 		          throw FormatError("Extra character at the end of line");
 		        Edge e;
 		        if (!_use_edges) {
 		          typename NodeIndex::iterator it;

lemon/lgf_writer.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2011
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup lemon_io
 		///\file
 		///\brief \ref lgf-format "LEMON Graph Format" writer.
 		#ifndef LEMON_LGF_WRITER_H
 		#define LEMON_LGF_WRITER_H
 		#include <iostream>
 		#include <fstream>
 		#include <sstream>
 		#include <algorithm>
 		#include <vector>
 		#include <functional>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		namespace lemon {
 		  namespace _writer_bits {
 		    template <typename Value>
 		    struct DefaultConverter {
 		      std::string operator()(const Value& value) {
 		        std::ostringstream os;
 		        os << value;
 		        return os.str();
+		      }
 		    };
 		    template <typename T>
 		    bool operator<(const T&, const T&) {
 		      throw FormatError("Label map is not comparable");
+		    }
 		    template <typename _Map>
 		    class MapLess {
 		    public:
 		      typedef _Map Map;
 		      typedef typename Map::Key Item;
 		    private:
 		      const Map& _map;
 		    public:
 		      MapLess(const Map& map) : _map(map) {}
 		      bool operator()(const Item& left, const Item& right) {
 		        return _map[left] < _map[right];
+		      }
 		    };
 		    template <typename _Graph, bool _dir, typename _Map>
 		    class GraphArcMapLess {
 		    public:
 		      typedef _Map Map;
 		      typedef _Graph Graph;
 		      typedef typename Graph::Edge Item;
 		    private:
 		      const Graph& _graph;
 		      const Map& _map;
 		    public:
 		      GraphArcMapLess(const Graph& graph, const Map& map)
 		        : _graph(graph), _map(map) {}
 		      bool operator()(const Item& left, const Item& right) {
 		        return _map[_graph.direct(left, _dir)] <
 		          _map[_graph.direct(right, _dir)];
+		      }
 		    };
 		    template <typename _Item>
 		    class MapStorageBase {
 		    public:
 		      typedef _Item Item;
 		    public:
 		      MapStorageBase() {}
 		      virtual ~MapStorageBase() {}
 		      virtual std::string get(const Item& item) = 0;
 		      virtual void sort(std::vector<Item>&) = 0;
 		    };
 		    template <typename _Item, typename _Map,
 		              typename _Converter = DefaultConverter<typename _Map::Value> >
 		    class MapStorage : public MapStorageBase<_Item> {
 		    public:
 		      typedef _Map Map;
 		      typedef _Converter Converter;
 		      typedef _Item Item;
 		    private:
 		      const Map& _map;
 		      Converter _converter;
 		    public:
 		      MapStorage(const Map& map, const Converter& converter = Converter())
 		        : _map(map), _converter(converter) {}
 		      virtual ~MapStorage() {}
 		      virtual std::string get(const Item& item) {
 		        return _converter(_map[item]);
+		      }
 		      virtual void sort(std::vector<Item>& items) {
 		        MapLess<Map> less(_map);
 		        std::sort(items.begin(), items.end(), less);
+		      }
 		    };
 		    template <typename _Graph, bool _dir, typename _Map,
 		              typename _Converter = DefaultConverter<typename _Map::Value> >
 		    class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
 		    public:
 		      typedef _Map Map;
 		      typedef _Converter Converter;
 		      typedef _Graph Graph;
 		      typedef typename Graph::Edge Item;
 		      static const bool dir = _dir;
 		    private:
 		      const Graph& _graph;
 		      const Map& _map;
 		      Converter _converter;
 		    public:
 		      GraphArcMapStorage(const Graph& graph, const Map& map,
 		                         const Converter& converter = Converter())
 		        : _graph(graph), _map(map), _converter(converter) {}
 		      virtual ~GraphArcMapStorage() {}
 		      virtual std::string get(const Item& item) {
 		        return _converter(_map[_graph.direct(item, dir)]);
+		      }
 		      virtual void sort(std::vector<Item>& items) {
 		        GraphArcMapLess<Graph, dir, Map> less(_graph, _map);
 		        std::sort(items.begin(), items.end(), less);
+		      }
 		    };
 		    class ValueStorageBase {
 		    public:
 		      ValueStorageBase() {}
 		      virtual ~ValueStorageBase() {}
 		      virtual std::string get() = 0;
 		    };
 		    template <typename _Value, typename _Converter = DefaultConverter<_Value> >
 		    class ValueStorage : public ValueStorageBase {
 		    public:
 		      typedef _Value Value;
 		      typedef _Converter Converter;
 		    private:
 		      const Value& _value;
 		      Converter _converter;
 		    public:
 		      ValueStorage(const Value& value, const Converter& converter = Converter())
 		        : _value(value), _converter(converter) {}
 		      virtual std::string get() {
 		        return _converter(_value);
+		      }
 		    };
 		    template <typename Value>
 		    struct MapLookUpConverter {
 		      const std::map<Value, std::string>& _map;
 		      MapLookUpConverter(const std::map<Value, std::string>& map)
 		        : _map(map) {}
 		      std::string operator()(const Value& str) {
 		        typename std::map<Value, std::string>::const_iterator it =
 		          _map.find(str);
 		        if (it == _map.end()) {
 		          throw FormatError("Item not found");
+		        }
 		        return it->second;
+		      }
 		    };
 		    template <typename Graph>
 		    struct GraphArcLookUpConverter {
 		      const Graph& _graph;
 		      const std::map<typename Graph::Edge, std::string>& _map;
 		      GraphArcLookUpConverter(const Graph& graph,
 		                              const std::map<typename Graph::Edge,
 		                                             std::string>& map)
 		        : _graph(graph), _map(map) {}
 		      std::string operator()(const typename Graph::Arc& val) {
 		        typename std::map<typename Graph::Edge, std::string>
 		          ::const_iterator it = _map.find(val);
 		        if (it == _map.end()) {
 		          throw FormatError("Item not found");
+		        }
 		        return (_graph.direction(val) ? '+' : '-') + it->second;
+		      }
 		    };
 		    inline bool isWhiteSpace(char c) {
 		      return c == ' ' || c == '\t' || c == '\v' ||
 		        c == '\n' || c == '\r' || c == '\f';
+		    }
 		    inline bool isEscaped(char c) {
 		      return c == '\\' || c == '\"' || c == '\'' ||
 		        c == '\a' || c == '\b';
+		    }
 		    inline static void writeEscape(std::ostream& os, char c) {
 		      switch (c) {
 		      case '\\':
 		        os << "\\\\";
 		        return;
 		      case '\"':
 		        os << "\\\"";
 		        return;
 		      case '\a':
 		        os << "\\a";
 		        return;
 		      case '\b':
 		        os << "\\b";
 		        return;
 		      case '\f':
 		        os << "\\f";
 		        return;
 		      case '\r':
 		        os << "\\r";
 		        return;
 		      case '\n':
 		        os << "\\n";
 		        return;
 		      case '\t':
 		        os << "\\t";
 		        return;
 		      case '\v':
 		        os << "\\v";
 		        return;
 		      default:
 		        if (c < 0x20) {
 		          std::ios::fmtflags flags = os.flags();
 		          os << '\\' << std::oct << static_cast<int>(c);
 		          os.flags(flags);
 		        } else {
 		          os << c;
+		        }
 		        return;
+		      }
+		    }
 		    inline bool requireEscape(const std::string& str) {
 		      if (str.empty() || str[0] == '@') return true;
 		      std::istringstream is(str);
 		      char c;
 		      while (is.get(c)) {
 		        if (isWhiteSpace(c) || isEscaped(c)) {
 		          return true;
+		        }
+		      }
 		      return false;
+		    }
 		    inline std::ostream& writeToken(std::ostream& os, const std::string& str) {
 		      if (requireEscape(str)) {
 		        os << '\"';
 		        for (std::string::const_iterator it = str.begin();
 		             it != str.end(); ++it) {
 		          writeEscape(os, *it);
+		        }
 		        os << '\"';
 		      } else {
 		        os << str;
+		      }
 		      return os;
+		    }
 		    class Section {
 		    public:
 		      virtual ~Section() {}
 		      virtual void process(std::ostream& os) = 0;
 		    };
 		    template <typename Functor>
 		    class LineSection : public Section {
 		    private:
 		      Functor _functor;
 		    public:
 		      LineSection(const Functor& functor) : _functor(functor) {}
 		      virtual ~LineSection() {}
 		      virtual void process(std::ostream& os) {
 		        std::string line;
 		        while (!(line = _functor()).empty()) os << line << std::endl;
+		      }
 		    };
 		    template <typename Functor>
 		    class StreamSection : public Section {
 		    private:
 		      Functor _functor;
 		    public:
 		      StreamSection(const Functor& functor) : _functor(functor) {}
 		      virtual ~StreamSection() {}
 		      virtual void process(std::ostream& os) {
 		        _functor(os);
+		      }
 		    };
+		  }
 		  template <typename Digraph>
 		  class DigraphWriter;
 		  template <typename Digraph>
 		  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
 		                                       std::ostream& os = std::cout);
 		  template <typename Digraph>
 		  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
 		                                       const std::string& fn);
 		  template <typename Digraph>
 		  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
 		                                       const char* fn);
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief \ref lgf-format "LGF" writer for directed graphs
 		  ///
 		  /// This utility writes an \ref lgf-format "LGF" file.
 		  ///
 		  /// The writing method does a batch processing. The user creates a
 		  /// writer object, then various writing rules can be added to the
 		  /// writer, and eventually the writing is executed with the \c run()
 		  /// member function. A map writing rule can be added to the writer
 		  /// with the \c nodeMap() or \c arcMap() members. An optional
 		  /// converter parameter can also be added as a standard functor
 		  /// converting from the value type of the map to \c std::string. If it
 		  /// is set, it will determine how the value type of the map is written to
 		  /// the output stream. If the functor is not set, then a default
 		  /// conversion will be used. The \c attribute(), \c node() and \c
 		  /// arc() functions are used to add attribute writing rules.
 		  ///
 		  ///\code
 		  /// DigraphWriter<Digraph>(digraph, std::cout).
 		  ///   nodeMap("coordinates", coord_map).
 		  ///   nodeMap("size", size).
 		  ///   nodeMap("title", title).
 		  ///   arcMap("capacity", cap_map).
 		  ///   node("source", src).
 		  ///   node("target", trg).
 		  ///   attribute("caption", caption).
 		  ///   run();
 		  ///\endcode
 		  ///
 		  ///
 		  /// By default, the writer does not write additional captions to the
 		  /// sections, but they can be give as an optional parameter of
 		  /// the \c nodes(), \c arcs() or \c
 		  /// attributes() functions.
 		  ///
 		  /// The \c skipNodes() and \c skipArcs() functions forbid the
 		  /// writing of the sections. If two arc sections should be written
 		  /// to the output, it can be done in two passes, the first pass
 		  /// writes the node section and the first arc section, then the
 		  /// second pass skips the node section and writes just the arc
 		  /// section to the stream. The output stream can be retrieved with
 		  /// the \c ostream() function, hence the second pass can append its
 		  /// output to the output of the first pass.
 		  template <typename _Digraph>
 		  class DigraphWriter {
 		  public:
 		    typedef _Digraph Digraph;
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  private:
 		    std::ostream* _os;
 		    bool local_os;
 		    const Digraph& _digraph;
 		    std::string _nodes_caption;
 		    std::string _arcs_caption;
 		    std::string _attributes_caption;
 		    typedef std::map<Node, std::string> NodeIndex;
 		    NodeIndex _node_index;
 		    typedef std::map<Arc, std::string> ArcIndex;
 		    ArcIndex _arc_index;
 		    typedef std::vector<std::pair<std::string,
 		      _writer_bits::MapStorageBase<Node>* > > NodeMaps;
 		    NodeMaps _node_maps;
 		    typedef std::vector<std::pair<std::string,
 		      _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
 		    ArcMaps _arc_maps;
 		    typedef std::vector<std::pair<std::string,
 		      _writer_bits::ValueStorageBase*> > Attributes;
 		    Attributes _attributes;
 		    bool _skip_nodes;
 		    bool _skip_arcs;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output stream.
 		    DigraphWriter(const Digraph& digraph, std::ostream& os = std::cout)
 		      : _os(&os), local_os(false), _digraph(digraph),
 		        _skip_nodes(false), _skip_arcs(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output file.
 		    DigraphWriter(const Digraph& digraph, const std::string& fn)
 		      : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
 		        _skip_nodes(false), _skip_arcs(false) {
 		      if (!(*_os)) {
 		        delete _os;
 		        throw IoError("Cannot write file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output file.
 		    DigraphWriter(const Digraph& digraph, const char* fn)
 		      : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
 		        _skip_nodes(false), _skip_arcs(false) {
 		      if (!(*_os)) {
 		        delete _os;
 		        throw IoError("Cannot write file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~DigraphWriter() {
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename ArcMaps::iterator it = _arc_maps.begin();
 		           it != _arc_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_os) {
 		        delete _os;
+		      }
+		    }
 		  private:
 		    template <typename DGR>
-		    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
 		    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
 		                                            std::ostream& os);
 		    template <typename DGR>
 		    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
 		                                            const std::string& fn);
 		    template <typename DGR>
 		    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
 		                                            const char *fn);
 		    DigraphWriter(DigraphWriter& other)
 		      : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
 		        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
 		      other._os = 0;
 		      other.local_os = false;
 		      _node_index.swap(other._node_index);
 		      _arc_index.swap(other._arc_index);
 		      _node_maps.swap(other._node_maps);
 		      _arc_maps.swap(other._arc_maps);
 		      _attributes.swap(other._attributes);
 		      _nodes_caption = other._nodes_caption;
 		      _arcs_caption = other._arcs_caption;
 		      _attributes_caption = other._attributes_caption;
+		    }
 		    DigraphWriter& operator=(const DigraphWriter&);
 		  public:
 		    /// \name Writing rules
 		    /// @{
 		    /// \brief Node map writing rule
 		    ///
 		    /// Add a node map writing rule to the writer.
 		    template <typename Map>
 		    DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Node>* storage =
 		        new _writer_bits::MapStorage<Node, Map>(map);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node map writing rule
 		    ///
 		    /// Add a node map writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Map, typename Converter>
 		    DigraphWriter& nodeMap(const std::string& caption, const Map& map,
 		                           const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Node>* storage =
 		        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map writing rule
 		    ///
 		    /// Add an arc map writing rule to the writer.
 		    template <typename Map>
 		    DigraphWriter& arcMap(const std::string& caption, const Map& map) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Arc>* storage =
 		        new _writer_bits::MapStorage<Arc, Map>(map);
 		      _arc_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map writing rule
 		    ///
 		    /// Add an arc map writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Map, typename Converter>
 		    DigraphWriter& arcMap(const std::string& caption, const Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Arc>* storage =
 		        new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
 		      _arc_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute writing rule
 		    ///
 		    /// Add an attribute writing rule to the writer.
 		    template <typename Value>
 		    DigraphWriter& attribute(const std::string& caption, const Value& value) {
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Value>(value);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute writing rule
 		    ///
 		    /// Add an attribute writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Value, typename Converter>
 		    DigraphWriter& attribute(const std::string& caption, const Value& value,
 		                             const Converter& converter = Converter()) {
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node writing rule
 		    ///
 		    /// Add a node writing rule to the writer.
 		    DigraphWriter& node(const std::string& caption, const Node& node) {
 		      typedef _writer_bits::MapLookUpConverter<Node> Converter;
 		      Converter converter(_node_index);
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc writing rule
 		    ///
 		    /// Add an arc writing rule to writer.
 		    DigraphWriter& arc(const std::string& caption, const Arc& arc) {
 		      typedef _writer_bits::MapLookUpConverter<Arc> Converter;
 		      Converter converter(_arc_index);
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \name Section captions
 		    /// @{
 		    /// \brief Add an additional caption to the \c \@nodes section
 		    ///
 		    /// Add an additional caption to the \c \@nodes section.
 		    DigraphWriter& nodes(const std::string& caption) {
 		      _nodes_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Add an additional caption to the \c \@arcs section
 		    ///
 		    /// Add an additional caption to the \c \@arcs section.
 		    DigraphWriter& arcs(const std::string& caption) {
 		      _arcs_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Add an additional caption to the \c \@attributes section
 		    ///
 		    /// Add an additional caption to the \c \@attributes section.
 		    DigraphWriter& attributes(const std::string& caption) {
 		      _attributes_caption = caption;
 		      return *this;
+		    }
 		    /// \name Skipping section
 		    /// @{
 		    /// \brief Skip writing the node set
 		    ///
 		    /// The \c \@nodes section will not be written to the stream.
 		    DigraphWriter& skipNodes() {
 		      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
 		      _skip_nodes = true;
 		      return *this;
+		    }
 		    /// \brief Skip writing arc set
 		    ///
 		    /// The \c \@arcs section will not be written to the stream.
 		    DigraphWriter& skipArcs() {
 		      LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
 		      _skip_arcs = true;
 		      return *this;
+		    }
 		    /// @}
 		  private:
 		    void writeNodes() {
 		      _writer_bits::MapStorageBase<Node>* label = 0;
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      *_os << "@nodes";
 		      if (!_nodes_caption.empty()) {
 		        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
+		      }
 		      *_os << std::endl;
 		      if (label == 0) {
 		        *_os << "label" << '\t';
+		      }
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << '\t';
+		      }
 		      *_os << std::endl;
 		      std::vector<Node> nodes;
 		      for (NodeIt n(_digraph); n != INVALID; ++n) {
 		        nodes.push_back(n);
+		      }
 		      if (label == 0) {
 		        IdMap<Digraph, Node> id_map(_digraph);
 		        _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
 		        std::sort(nodes.begin(), nodes.end(), id_less);
 		      } else {
 		        label->sort(nodes);
+		      }
 		      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
 		        Node n = nodes[i];
 		        if (label == 0) {
 		          std::ostringstream os;
 		          os << _digraph.id(n);
 		          _writer_bits::writeToken(*_os, os.str());
 		          *_os << '\t';
 		          _node_index.insert(std::make_pair(n, os.str()));
+		        }
 		        for (typename NodeMaps::iterator it = _node_maps.begin();
 		             it != _node_maps.end(); ++it) {
 		          std::string value = it->second->get(n);
 		          _writer_bits::writeToken(*_os, value);
 		          if (it->first == "label") {
 		            _node_index.insert(std::make_pair(n, value));
+		          }
 		          *_os << '\t';
+		        }
 		        *_os << std::endl;
+		      }
+		    }
 		    void createNodeIndex() {
 		      _writer_bits::MapStorageBase<Node>* label = 0;
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      if (label == 0) {
 		        for (NodeIt n(_digraph); n != INVALID; ++n) {
 		          std::ostringstream os;
 		          os << _digraph.id(n);
 		          _node_index.insert(std::make_pair(n, os.str()));
+		        }
 		      } else {
 		        for (NodeIt n(_digraph); n != INVALID; ++n) {
 		          std::string value = label->get(n);
 		          _node_index.insert(std::make_pair(n, value));
+		        }
+		      }
+		    }
 		    void writeArcs() {
 		      _writer_bits::MapStorageBase<Arc>* label = 0;
 		      for (typename ArcMaps::iterator it = _arc_maps.begin();
 		           it != _arc_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      *_os << "@arcs";
 		      if (!_arcs_caption.empty()) {
 		        _writer_bits::writeToken(*_os << ' ', _arcs_caption);
+		      }
 		      *_os << std::endl;
 		      *_os << '\t' << '\t';
 		      if (label == 0) {
 		        *_os << "label" << '\t';
+		      }
 		      for (typename ArcMaps::iterator it = _arc_maps.begin();
 		           it != _arc_maps.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << '\t';
+		      }
 		      *_os << std::endl;
 		      std::vector<Arc> arcs;
 		      for (ArcIt n(_digraph); n != INVALID; ++n) {
 		        arcs.push_back(n);
+		      }
 		      if (label == 0) {
 		        IdMap<Digraph, Arc> id_map(_digraph);
 		        _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
 		        std::sort(arcs.begin(), arcs.end(), id_less);
 		      } else {
 		        label->sort(arcs);
+		      }
 		      for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
 		        Arc a = arcs[i];
 		        _writer_bits::writeToken(*_os, _node_index.
 		                                 find(_digraph.source(a))->second);
 		        *_os << '\t';
 		        _writer_bits::writeToken(*_os, _node_index.
 		                                 find(_digraph.target(a))->second);
 		        *_os << '\t';
 		        if (label == 0) {
 		          std::ostringstream os;
 		          os << _digraph.id(a);
 		          _writer_bits::writeToken(*_os, os.str());
 		          *_os << '\t';
 		          _arc_index.insert(std::make_pair(a, os.str()));
+		        }
 		        for (typename ArcMaps::iterator it = _arc_maps.begin();
 		             it != _arc_maps.end(); ++it) {
 		          std::string value = it->second->get(a);
 		          _writer_bits::writeToken(*_os, value);
 		          if (it->first == "label") {
 		            _arc_index.insert(std::make_pair(a, value));
+		          }
 		          *_os << '\t';
+		        }
 		        *_os << std::endl;
+		      }
+		    }
 		    void createArcIndex() {
 		      _writer_bits::MapStorageBase<Arc>* label = 0;
 		      for (typename ArcMaps::iterator it = _arc_maps.begin();
 		           it != _arc_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      if (label == 0) {
 		        for (ArcIt a(_digraph); a != INVALID; ++a) {
 		          std::ostringstream os;
 		          os << _digraph.id(a);
 		          _arc_index.insert(std::make_pair(a, os.str()));
+		        }
 		      } else {
 		        for (ArcIt a(_digraph); a != INVALID; ++a) {
 		          std::string value = label->get(a);
 		          _arc_index.insert(std::make_pair(a, value));
+		        }
+		      }
+		    }
 		    void writeAttributes() {
 		      if (_attributes.empty()) return;
 		      *_os << "@attributes";
 		      if (!_attributes_caption.empty()) {
 		        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
+		      }
 		      *_os << std::endl;
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << ' ';
 		        _writer_bits::writeToken(*_os, it->second->get());
 		        *_os << std::endl;
+		      }
+		    }
 		  public:
 		    /// \name Execution of the writer
 		    /// @{
 		    /// \brief Start the batch processing
 		    ///
 		    /// This function starts the batch processing.
 		    void run() {
 		      if (!_skip_nodes) {
 		        writeNodes();
 		      } else {
 		        createNodeIndex();
+		      }
 		      if (!_skip_arcs) {
 		        writeArcs();
 		      } else {
 		        createArcIndex();
+		      }
 		      writeAttributes();
+		    }
 		    /// \brief Give back the stream of the writer
 		    ///
 		    /// Give back the stream of the writer.
 		    std::ostream& ostream() {
 		      return *_os;
+		    }
 		    /// @}
 		  };
 		  /// \brief Return a \ref DigraphWriter class
 		  ///
 		  /// This function just returns a \ref DigraphWriter class.
 		  /// \relates DigraphWriter
 		  template <typename Digraph>
 		  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
 		                                       std::ostream& os) {
 		    DigraphWriter<Digraph> tmp(digraph, os);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref DigraphWriter class
 		  ///
 		  /// This function just returns a \ref DigraphWriter class.
 		  /// \relates DigraphWriter
 		  template <typename Digraph>
 		  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
 		                                       const std::string& fn) {
 		    DigraphWriter<Digraph> tmp(digraph, fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref DigraphWriter class
 		  ///
 		  /// This function just returns a \ref DigraphWriter class.
 		  /// \relates DigraphWriter
 		  template <typename Digraph>
 		  DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
 		                                       const char* fn) {
 		    DigraphWriter<Digraph> tmp(digraph, fn);
 		    return tmp;
+		  }
 		  template <typename Graph>
 		  class GraphWriter;
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph,
 		                                 std::ostream& os = std::cout);
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn);
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn);
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief \ref lgf-format "LGF" writer for directed graphs
 		  ///
 		  /// This utility writes an \ref lgf-format "LGF" file.
 		  ///
 		  /// It can be used almost the same way as \c DigraphWriter.
 		  /// The only difference is that this class can handle edges and
 		  /// edge maps as well as arcs and arc maps.
 		  ///
 		  /// The arc maps are written into the file as two columns, the
 		  /// caption of the columns are the name of the map prefixed with \c
 		  /// '+' and \c '-'. The arcs are written into the \c \@attributes
 		  /// section as a \c '+' or a \c '-' prefix (depends on the direction
 		  /// of the arc) and the label of corresponding edge.
 		  template <typename _Graph>
 		  class GraphWriter {
 		  public:
 		    typedef _Graph Graph;
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		  private:
 		    std::ostream* _os;
 		    bool local_os;
 		    const Graph& _graph;
 		    std::string _nodes_caption;
 		    std::string _edges_caption;
 		    std::string _attributes_caption;
 		    typedef std::map<Node, std::string> NodeIndex;
 		    NodeIndex _node_index;
 		    typedef std::map<Edge, std::string> EdgeIndex;
 		    EdgeIndex _edge_index;
 		    typedef std::vector<std::pair<std::string,
 		      _writer_bits::MapStorageBase<Node>* > > NodeMaps;
 		    NodeMaps _node_maps;
 		    typedef std::vector<std::pair<std::string,
 		      _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
 		    EdgeMaps _edge_maps;
 		    typedef std::vector<std::pair<std::string,
 		      _writer_bits::ValueStorageBase*> > Attributes;
 		    Attributes _attributes;
 		    bool _skip_nodes;
 		    bool _skip_edges;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output stream.
 		    GraphWriter(const Graph& graph, std::ostream& os = std::cout)
 		      : _os(&os), local_os(false), _graph(graph),
 		        _skip_nodes(false), _skip_edges(false) {}
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output file.
 		    GraphWriter(const Graph& graph, const std::string& fn)
 		      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
 		        _skip_nodes(false), _skip_edges(false) {
 		      if (!(*_os)) {
 		        delete _os;
 		        throw IoError("Cannot write file", fn);
+		      }
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Construct a directed graph writer, which writes to the given
 		    /// output file.
 		    GraphWriter(const Graph& graph, const char* fn)
 		      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
 		        _skip_nodes(false), _skip_edges(false) {
 		      if (!(*_os)) {
 		        delete _os;
 		        throw IoError("Cannot write file", fn);
+		      }
+		    }
 		    /// \brief Destructor
 		    ~GraphWriter() {
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		           it != _edge_maps.end(); ++it) {
 		        delete it->second;
+		      }
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        delete it->second;
+		      }
 		      if (local_os) {
 		        delete _os;
+		      }
+		    }
 		  private:
 		    template <typename GR>
 		    friend GraphWriter<GR> graphWriter(const GR& graph,
 		                                       std::ostream& os);
 		    template <typename GR>
 		    friend GraphWriter<GR> graphWriter(const GR& graph,
 		                                       const std::string& fn);
 		    template <typename GR>
 		    friend GraphWriter<GR> graphWriter(const GR& graph,
 		                                       const char *fn);
 		    GraphWriter(GraphWriter& other)
 		      : _os(other._os), local_os(other.local_os), _graph(other._graph),
 		        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
 		      other._os = 0;
 		      other.local_os = false;
 		      _node_index.swap(other._node_index);
 		      _edge_index.swap(other._edge_index);
 		      _node_maps.swap(other._node_maps);
 		      _edge_maps.swap(other._edge_maps);
 		      _attributes.swap(other._attributes);
 		      _nodes_caption = other._nodes_caption;
 		      _edges_caption = other._edges_caption;
 		      _attributes_caption = other._attributes_caption;
+		    }
 		    GraphWriter& operator=(const GraphWriter&);
 		  public:
 		    /// \name Writing rules
 		    /// @{
 		    /// \brief Node map writing rule
 		    ///
 		    /// Add a node map writing rule to the writer.
 		    template <typename Map>
 		    GraphWriter& nodeMap(const std::string& caption, const Map& map) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Node>* storage =
 		        new _writer_bits::MapStorage<Node, Map>(map);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node map writing rule
 		    ///
 		    /// Add a node map writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Map, typename Converter>
 		    GraphWriter& nodeMap(const std::string& caption, const Map& map,
 		                           const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Node>* storage =
 		        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
 		      _node_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge map writing rule
 		    ///
 		    /// Add an edge map writing rule to the writer.
 		    template <typename Map>
 		    GraphWriter& edgeMap(const std::string& caption, const Map& map) {
 		      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Edge>* storage =
 		        new _writer_bits::MapStorage<Edge, Map>(map);
 		      _edge_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge map writing rule
 		    ///
 		    /// Add an edge map writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Map, typename Converter>
 		    GraphWriter& edgeMap(const std::string& caption, const Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Edge>* storage =
 		        new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
 		      _edge_maps.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc map writing rule
 		    ///
 		    /// Add an arc map writing rule to the writer.
 		    template <typename Map>
 		    GraphWriter& arcMap(const std::string& caption, const Map& map) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Edge>* forward_storage =
 		        new _writer_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
 		      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
 		      _writer_bits::MapStorageBase<Edge>* backward_storage =
 		        new _writer_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
 		      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
 		      return *this;
+		    }
 		    /// \brief Arc map writing rule
 		    ///
 		    /// Add an arc map writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Map, typename Converter>
 		    GraphWriter& arcMap(const std::string& caption, const Map& map,
 		                          const Converter& converter = Converter()) {
 		      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
 		      _writer_bits::MapStorageBase<Edge>* forward_storage =
 		        new _writer_bits::GraphArcMapStorage<Graph, true, Map, Converter>
 		        (_graph, map, converter);
 		      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
 		      _writer_bits::MapStorageBase<Edge>* backward_storage =
 		        new _writer_bits::GraphArcMapStorage<Graph, false, Map, Converter>
 		        (_graph, map, converter);
 		      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
 		      return *this;
+		    }
 		    /// \brief Attribute writing rule
 		    ///
 		    /// Add an attribute writing rule to the writer.
 		    template <typename Value>
 		    GraphWriter& attribute(const std::string& caption, const Value& value) {
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Value>(value);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Attribute writing rule
 		    ///
 		    /// Add an attribute writing rule with specialized converter to the
 		    /// writer.
 		    template <typename Value, typename Converter>
 		    GraphWriter& attribute(const std::string& caption, const Value& value,
 		                             const Converter& converter = Converter()) {
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Node writing rule
 		    ///
 		    /// Add a node writing rule to the writer.
 		    GraphWriter& node(const std::string& caption, const Node& node) {
 		      typedef _writer_bits::MapLookUpConverter<Node> Converter;
 		      Converter converter(_node_index);
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Edge writing rule
 		    ///
 		    /// Add an edge writing rule to writer.
 		    GraphWriter& edge(const std::string& caption, const Edge& edge) {
 		      typedef _writer_bits::MapLookUpConverter<Edge> Converter;
 		      Converter converter(_edge_index);
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \brief Arc writing rule
 		    ///
 		    /// Add an arc writing rule to writer.
 		    GraphWriter& arc(const std::string& caption, const Arc& arc) {
 		      typedef _writer_bits::GraphArcLookUpConverter<Graph> Converter;
 		      Converter converter(_graph, _edge_index);
 		      _writer_bits::ValueStorageBase* storage =
 		        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
 		      _attributes.push_back(std::make_pair(caption, storage));
 		      return *this;
+		    }
 		    /// \name Section captions
 		    /// @{
 		    /// \brief Add an additional caption to the \c \@nodes section
 		    ///
 		    /// Add an additional caption to the \c \@nodes section.
 		    GraphWriter& nodes(const std::string& caption) {
 		      _nodes_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Add an additional caption to the \c \@arcs section
 		    ///
 		    /// Add an additional caption to the \c \@arcs section.
 		    GraphWriter& edges(const std::string& caption) {
 		      _edges_caption = caption;
 		      return *this;
+		    }
 		    /// \brief Add an additional caption to the \c \@attributes section
 		    ///
 		    /// Add an additional caption to the \c \@attributes section.
 		    GraphWriter& attributes(const std::string& caption) {
 		      _attributes_caption = caption;
 		      return *this;
+		    }
 		    /// \name Skipping section
 		    /// @{
 		    /// \brief Skip writing the node set
 		    ///
 		    /// The \c \@nodes section will not be written to the stream.
 		    GraphWriter& skipNodes() {
 		      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
 		      _skip_nodes = true;
 		      return *this;
+		    }
 		    /// \brief Skip writing edge set
 		    ///
 		    /// The \c \@edges section will not be written to the stream.
 		    GraphWriter& skipEdges() {
 		      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
 		      _skip_edges = true;
 		      return *this;
+		    }
 		    /// @}
 		  private:
 		    void writeNodes() {
 		      _writer_bits::MapStorageBase<Node>* label = 0;
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      *_os << "@nodes";
 		      if (!_nodes_caption.empty()) {
 		        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
+		      }
 		      *_os << std::endl;
 		      if (label == 0) {
 		        *_os << "label" << '\t';
+		      }
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << '\t';
+		      }
 		      *_os << std::endl;
 		      std::vector<Node> nodes;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        nodes.push_back(n);
+		      }
 		      if (label == 0) {
 		        IdMap<Graph, Node> id_map(_graph);
 		        _writer_bits::MapLess<IdMap<Graph, Node> > id_less(id_map);
 		        std::sort(nodes.begin(), nodes.end(), id_less);
 		      } else {
 		        label->sort(nodes);
+		      }
 		      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
 		        Node n = nodes[i];
 		        if (label == 0) {
 		          std::ostringstream os;
 		          os << _graph.id(n);
 		          _writer_bits::writeToken(*_os, os.str());
 		          *_os << '\t';
 		          _node_index.insert(std::make_pair(n, os.str()));
+		        }
 		        for (typename NodeMaps::iterator it = _node_maps.begin();
 		             it != _node_maps.end(); ++it) {
 		          std::string value = it->second->get(n);
 		          _writer_bits::writeToken(*_os, value);
 		          if (it->first == "label") {
 		            _node_index.insert(std::make_pair(n, value));
+		          }
 		          *_os << '\t';
+		        }
 		        *_os << std::endl;
+		      }
+		    }
 		    void createNodeIndex() {
 		      _writer_bits::MapStorageBase<Node>* label = 0;
 		      for (typename NodeMaps::iterator it = _node_maps.begin();
 		           it != _node_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      if (label == 0) {
 		        for (NodeIt n(_graph); n != INVALID; ++n) {
 		          std::ostringstream os;
 		          os << _graph.id(n);
 		          _node_index.insert(std::make_pair(n, os.str()));
+		        }
 		      } else {
 		        for (NodeIt n(_graph); n != INVALID; ++n) {
 		          std::string value = label->get(n);
 		          _node_index.insert(std::make_pair(n, value));
+		        }
+		      }
+		    }
 		    void writeEdges() {
 		      _writer_bits::MapStorageBase<Edge>* label = 0;
 		      for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		           it != _edge_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      *_os << "@edges";
 		      if (!_edges_caption.empty()) {
 		        _writer_bits::writeToken(*_os << ' ', _edges_caption);
+		      }
 		      *_os << std::endl;
 		      *_os << '\t' << '\t';
 		      if (label == 0) {
 		        *_os << "label" << '\t';
+		      }
 		      for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		           it != _edge_maps.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << '\t';
+		      }
 		      *_os << std::endl;
 		      std::vector<Edge> edges;
 		      for (EdgeIt n(_graph); n != INVALID; ++n) {
 		        edges.push_back(n);
+		      }
 		      if (label == 0) {
 		        IdMap<Graph, Edge> id_map(_graph);
 		        _writer_bits::MapLess<IdMap<Graph, Edge> > id_less(id_map);
 		        std::sort(edges.begin(), edges.end(), id_less);
 		      } else {
 		        label->sort(edges);
+		      }
 		      for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
 		        Edge e = edges[i];
 		        _writer_bits::writeToken(*_os, _node_index.
 		                                 find(_graph.u(e))->second);
 		        *_os << '\t';
 		        _writer_bits::writeToken(*_os, _node_index.
 		                                 find(_graph.v(e))->second);
 		        *_os << '\t';
 		        if (label == 0) {
 		          std::ostringstream os;
 		          os << _graph.id(e);
 		          _writer_bits::writeToken(*_os, os.str());
 		          *_os << '\t';
 		          _edge_index.insert(std::make_pair(e, os.str()));
+		        }
 		        for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		             it != _edge_maps.end(); ++it) {
 		          std::string value = it->second->get(e);
 		          _writer_bits::writeToken(*_os, value);
 		          if (it->first == "label") {
 		            _edge_index.insert(std::make_pair(e, value));
+		          }
 		          *_os << '\t';
+		        }
 		        *_os << std::endl;
+		      }
+		    }
 		    void createEdgeIndex() {
 		      _writer_bits::MapStorageBase<Edge>* label = 0;
 		      for (typename EdgeMaps::iterator it = _edge_maps.begin();
 		           it != _edge_maps.end(); ++it) {
 		        if (it->first == "label") {
 		          label = it->second;
 		          break;
+		        }
+		      }
 		      if (label == 0) {
 		        for (EdgeIt e(_graph); e != INVALID; ++e) {
 		          std::ostringstream os;
 		          os << _graph.id(e);
 		          _edge_index.insert(std::make_pair(e, os.str()));
+		        }
 		      } else {
 		        for (EdgeIt e(_graph); e != INVALID; ++e) {
 		          std::string value = label->get(e);
 		          _edge_index.insert(std::make_pair(e, value));
+		        }
+		      }
+		    }
 		    void writeAttributes() {
 		      if (_attributes.empty()) return;
 		      *_os << "@attributes";
 		      if (!_attributes_caption.empty()) {
 		        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
+		      }
 		      *_os << std::endl;
 		      for (typename Attributes::iterator it = _attributes.begin();
 		           it != _attributes.end(); ++it) {
 		        _writer_bits::writeToken(*_os, it->first) << ' ';
 		        _writer_bits::writeToken(*_os, it->second->get());
 		        *_os << std::endl;
+		      }
+		    }
 		  public:
 		    /// \name Execution of the writer
 		    /// @{
 		    /// \brief Start the batch processing
 		    ///
 		    /// This function starts the batch processing.
 		    void run() {
 		      if (!_skip_nodes) {
 		        writeNodes();
 		      } else {
 		        createNodeIndex();
+		      }
 		      if (!_skip_edges) {
 		        writeEdges();
 		      } else {
 		        createEdgeIndex();
+		      }
 		      writeAttributes();
+		    }
 		    /// \brief Give back the stream of the writer
 		    ///
 		    /// Give back the stream of the writer
 		    std::ostream& ostream() {
 		      return *_os;
+		    }
 		    /// @}
 		  };
 		  /// \brief Return a \ref GraphWriter class
 		  ///
 		  /// This function just returns a \ref GraphWriter class.
 		  /// \relates GraphWriter
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph,
 		                                 std::ostream& os) {
 		    GraphWriter<Graph> tmp(graph, os);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref GraphWriter class
 		  ///
 		  /// This function just returns a \ref GraphWriter class.
 		  /// \relates GraphWriter
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn) {
 		    GraphWriter<Graph> tmp(graph, fn);
 		    return tmp;
+		  }
 		  /// \brief Return a \ref GraphWriter class
 		  ///
 		  /// This function just returns a \ref GraphWriter class.
 		  /// \relates GraphWriter
 		  template <typename Graph>
 		  GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn) {
 		    GraphWriter<Graph> tmp(graph, fn);
 		    return tmp;
+		  }
 		  class SectionWriter;
 		  SectionWriter sectionWriter(std::istream& is);
 		  SectionWriter sectionWriter(const std::string& fn);
 		  SectionWriter sectionWriter(const char* fn);
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief Section writer class
 		  ///
 		  /// In the \ref lgf-format "LGF" file extra sections can be placed,
 		  /// which contain any data in arbitrary format. Such sections can be
 		  /// written with this class. A writing rule can be added to the
 		  /// class with two different functions. With the \c sectionLines()
 		  /// function a generator can write the section line-by-line, while
 		  /// with the \c sectionStream() member the section can be written to
 		  /// an output stream.
 		  class SectionWriter {
 		  private:
 		    std::ostream* _os;
 		    bool local_os;
 		    typedef std::vector<std::pair<std::string, _writer_bits::Section*> >
 		    Sections;
 		    Sections _sections;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Construct a section writer, which writes to the given output
 		    /// stream.
 		    SectionWriter(std::ostream& os)

lemon/list_graph.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2011
 		 * 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_LIST_GRAPH_H
 		#define LEMON_LIST_GRAPH_H
 		///\ingroup graphs
 		///\file
 		///\brief ListDigraph, ListGraph classes.
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/bits/graph_extender.h>
 		#include <vector>
 		#include <list>
 		namespace lemon {
 		  class ListDigraphBase {
 		  protected:
 		    struct NodeT {
 		      int first_in, first_out;
 		      int prev, next;
 		    };
 		    struct ArcT {
 		      int target, source;
 		      int prev_in, prev_out;
 		      int next_in, next_out;
 		    };
 		    std::vector<NodeT> nodes;
 		    int first_node;
 		    int first_free_node;
 		    std::vector<ArcT> arcs;
 		    int first_free_arc;
 		  public:
 		    typedef ListDigraphBase Digraph;
 		    class Node {
 		      friend class ListDigraphBase;
 		    protected:
 		      int id;
 		      explicit Node(int pid) { id = pid;}
 		    public:
 		      Node() {}
 		      Node (Invalid) { id = -1; }
 		      bool operator==(const Node& node) const {return id == node.id;}
 		      bool operator!=(const Node& node) const {return id != node.id;}
 		      bool operator<(const Node& node) const {return id < node.id;}
 		    };
 		    class Arc {
 		      friend class ListDigraphBase;
 		    protected:
 		      int id;
 		      explicit Arc(int pid) { id = pid;}
 		    public:
 		      Arc() {}
 		      Arc (Invalid) { id = -1; }
 		      bool operator==(const Arc& arc) const {return id == arc.id;}
 		      bool operator!=(const Arc& arc) const {return id != arc.id;}
 		      bool operator<(const Arc& arc) const {return id < arc.id;}
 		    };
 		    ListDigraphBase()
 		      : nodes(), first_node(-1),
 		        first_free_node(-1), arcs(), first_free_arc(-1) {}
 		    int maxNodeId() const { return nodes.size()-1; }
 		    int maxArcId() const { return arcs.size()-1; }
 		    Node source(Arc e) const { return Node(arcs[e.id].source); }
 		    Node target(Arc e) const { return Node(arcs[e.id].target); }
 		    void first(Node& node) const {
 		      node.id = first_node;
+		    }
 		    void next(Node& node) const {
 		      node.id = nodes[node.id].next;
+		    }
 		    void first(Arc& arc) const {
 		      int n;
 		      for(n = first_node;
 		          n!=-1 && nodes[n].first_in == -1;
 		          n = nodes[n].next) {}
 		      arc.id = (n == -1) ? -1 : nodes[n].first_in;
+		    }
 		    void next(Arc& arc) const {
 		      if (arcs[arc.id].next_in != -1) {
 		        arc.id = arcs[arc.id].next_in;
 		      } else {
 		        int n;
 		        for(n = nodes[arcs[arc.id].target].next;
 		            n!=-1 && nodes[n].first_in == -1;
 		            n = nodes[n].next) {}
 		        arc.id = (n == -1) ? -1 : nodes[n].first_in;
+		      }
+		    }
 		    void firstOut(Arc &e, const Node& v) const {
 		      e.id = nodes[v.id].first_out;
+		    }
 		    void nextOut(Arc &e) const {
 		      e.id=arcs[e.id].next_out;
+		    }
 		    void firstIn(Arc &e, const Node& v) const {
 		      e.id = nodes[v.id].first_in;
+		    }
 		    void nextIn(Arc &e) const {
 		      e.id=arcs[e.id].next_in;
+		    }
 		    static int id(Node v) { return v.id; }
 		    static int id(Arc e) { return e.id; }
 		    static Node nodeFromId(int id) { return Node(id);}
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    bool valid(Node n) const {
 		      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
 		        nodes[n.id].prev != -2;
+		    }
 		    bool valid(Arc a) const {
 		      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
 		        arcs[a.id].prev_in != -2;
+		    }
 		    Node addNode() {
 		      int n;
 		      if(first_free_node==-1) {
 		        n = nodes.size();
 		        nodes.push_back(NodeT());
 		      } else {
 		        n = first_free_node;
 		        first_free_node = nodes[n].next;
+		      }
 		      nodes[n].next = first_node;
 		      if(first_node != -1) nodes[first_node].prev = n;
 		      first_node = n;
 		      nodes[n].prev = -1;
 		      nodes[n].first_in = nodes[n].first_out = -1;
 		      return Node(n);
+		    }
 		    Arc addArc(Node u, Node v) {
 		      int n;
 		      if (first_free_arc == -1) {
 		        n = arcs.size();
 		        arcs.push_back(ArcT());
 		      } else {
 		        n = first_free_arc;
 		        first_free_arc = arcs[n].next_in;
+		      }
 		      arcs[n].source = u.id;
 		      arcs[n].target = v.id;
 		      arcs[n].next_out = nodes[u.id].first_out;
 		      if(nodes[u.id].first_out != -1) {
 		        arcs[nodes[u.id].first_out].prev_out = n;
+		      }
 		      arcs[n].next_in = nodes[v.id].first_in;
 		      if(nodes[v.id].first_in != -1) {
 		        arcs[nodes[v.id].first_in].prev_in = n;
+		      }
 		      arcs[n].prev_in = arcs[n].prev_out = -1;
 		      nodes[u.id].first_out = nodes[v.id].first_in = n;
 		      return Arc(n);
+		    }
 		    void erase(const Node& node) {
 		      int n = node.id;
 		      if(nodes[n].next != -1) {
 		        nodes[nodes[n].next].prev = nodes[n].prev;
+		      }
 		      if(nodes[n].prev != -1) {
 		        nodes[nodes[n].prev].next = nodes[n].next;
 		      } else {
 		        first_node = nodes[n].next;
+		      }
 		      nodes[n].next = first_free_node;
 		      first_free_node = n;
 		      nodes[n].prev = -2;
+		    }
 		    void erase(const Arc& arc) {
 		      int n = arc.id;
 		      if(arcs[n].next_in!=-1) {
 		        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
+		      }
 		      if(arcs[n].prev_in!=-1) {
 		        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
 		      } else {
 		        nodes[arcs[n].target].first_in = arcs[n].next_in;
+		      }
 		      if(arcs[n].next_out!=-1) {
 		        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+		      }
 		      if(arcs[n].prev_out!=-1) {
 		        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 		      } else {
 		        nodes[arcs[n].source].first_out = arcs[n].next_out;
+		      }
 		      arcs[n].next_in = first_free_arc;
 		      first_free_arc = n;
 		      arcs[n].prev_in = -2;
+		    }
 		    void clear() {
 		      arcs.clear();
 		      nodes.clear();
 		      first_node = first_free_node = first_free_arc = -1;
+		    }
 		  protected:
 		    void changeTarget(Arc e, Node n)
+		    {
 		      if(arcs[e.id].next_in != -1)
 		        arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
 		      if(arcs[e.id].prev_in != -1)
 		        arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
 		      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
 		      if (nodes[n.id].first_in != -1) {
 		        arcs[nodes[n.id].first_in].prev_in = e.id;
+		      }
 		      arcs[e.id].target = n.id;
 		      arcs[e.id].prev_in = -1;
 		      arcs[e.id].next_in = nodes[n.id].first_in;
 		      nodes[n.id].first_in = e.id;
+		    }
 		    void changeSource(Arc e, Node n)
+		    {
 		      if(arcs[e.id].next_out != -1)
 		        arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
 		      if(arcs[e.id].prev_out != -1)
 		        arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
 		      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
 		      if (nodes[n.id].first_out != -1) {
 		        arcs[nodes[n.id].first_out].prev_out = e.id;
+		      }
 		      arcs[e.id].source = n.id;
 		      arcs[e.id].prev_out = -1;
 		      arcs[e.id].next_out = nodes[n.id].first_out;
 		      nodes[n.id].first_out = e.id;
+		    }
 		  };
 		  typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
 		  /// \addtogroup graphs
 		  /// @{
 		  ///A general directed graph structure.
 		  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
 		  ///implementation based on static linked lists that are stored in
 		  ///\c std::vector structures.
 		  ///
 		  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
 		  ///also provides several useful additional functionalities.
 		  ///Most of the member functions and nested classes are documented
 		  ///only in the concept class.
 		  ///
 		  ///An important extra feature of this digraph implementation is that
 		  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
 		  ///
 		  ///\sa concepts::Digraph
 		  class ListDigraph : public ExtendedListDigraphBase {
 		  private:
 		    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 		    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 		    ///
 		    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
 		    ///\brief Assignment of ListDigraph to another one is \e not allowed.
 		    ///Use copyDigraph() instead.
 		    ///Assignment of ListDigraph to another one is \e not allowed.
 		    ///Use copyDigraph() instead.
 		    void operator=(const ListDigraph &) {}
 		  public:
 		    typedef ExtendedListDigraphBase Parent;
 		    /// Constructor
 		    /// Constructor.
 		    ///
 		    ListDigraph() {}
 		    ///Add a new node to the digraph.
 		    ///Add a new node to the digraph.
 		    ///\return the new node.
 		    Node addNode() { return Parent::addNode(); }
 		    ///Add a new arc to the digraph.
 		    ///Add a new arc to the digraph with source node \c s
 		    ///and target node \c t.
 		    ///\return the new arc.
 		    Arc addArc(const Node& s, const Node& t) {
 		      return Parent::addArc(s, t);
+		    }
 		    ///\brief Erase a node from the digraph.
 		    ///
 		    ///Erase a node from the digraph.
 		    ///
 		    void erase(const Node& n) { Parent::erase(n); }
 		    ///\brief Erase an arc from the digraph.
 		    ///
 		    ///Erase an arc from the digraph.
 		    ///
 		    void erase(const Arc& a) { Parent::erase(a); }
 		    /// Node validity check
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    ///
 		    /// \warning A Node pointing to a removed item
 		    /// could become valid again later if new nodes are
 		    /// added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// Arc validity check
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning An Arc pointing to a removed item
 		    /// could become valid again later if new nodes are
 		    /// added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    /// Change the target of \c a to \c n
 		    /// Change the target of \c a to \c n
 		    ///
 		    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
 		    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void changeTarget(Arc a, Node n) {
 		      Parent::changeTarget(a,n);
+		    }
 		    /// Change the source of \c a to \c n
 		    /// Change the source of \c a to \c n
 		    ///
 		    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
 		    ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void changeSource(Arc a, Node n) {
 		      Parent::changeSource(a,n);
+		    }
 		    /// Invert the direction of an arc.
 		    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
 		    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void reverseArc(Arc e) {
 		      Node t=target(e);
 		      changeTarget(e,source(e));
 		      changeSource(e,t);
+		    }
 		    /// Reserve memory for nodes.
 		    /// Using this function it is possible to avoid the superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be very large (e.g. it will contain millions of nodes and/or arcs)
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveArc
 		    void reserveNode(int n) { nodes.reserve(n); };
 		    /// Reserve memory for arcs.
 		    /// Using this function it is possible to avoid the superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be very large (e.g. it will contain millions of nodes and/or arcs)
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveNode
 		    void reserveArc(int m) { arcs.reserve(m); };
 		    ///Contract two nodes.
 		    ///This function contracts two nodes.
 		    ///Node \p b will be removed but instead of deleting
 		    ///incident arcs, they will be joined to \p a.
 		    ///The last parameter \p r controls whether to remove loops. \c true
 		    ///means that loops will be removed.
 		    ///
 		    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
 		    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
 		    ///may be invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void contract(Node a, Node b, bool r = true)
+		    {
 		      for(OutArcIt e(*this,b);e!=INVALID;) {
 		        OutArcIt f=e;
 		        ++f;
 		        if(r && target(e)==a) erase(e);
 		        else changeSource(e,a);
 		        e=f;
+		      }
 		      for(InArcIt e(*this,b);e!=INVALID;) {
 		        InArcIt f=e;
 		        ++f;
 		        if(r && source(e)==a) erase(e);
 		        else changeTarget(e,a);
 		        e=f;
+		      }
 		      erase(b);
+		    }
 		    ///Split a node.
 		    ///This function splits a node. First a new node is added to the digraph,
 		    ///then the source of each outgoing arc of \c n is moved to this new node.
 		    ///If \c connect is \c true (this is the default value), then a new arc
 		    ///from \c n to the newly created node is also added.
 		    ///\return The newly created node.
 		    ///
 		    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
 		    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
 		    ///be invalidated.
 		    ///
 		    ///\warning This functionality cannot be used in conjunction with the
 		    ///Snapshot feature.
 		    Node split(Node n, bool connect = true) {
 		      Node b = addNode();
 		      for(OutArcIt e(*this,n);e!=INVALID;) {
 		        OutArcIt f=e;
 		        ++f;
 		        changeSource(e,b);
 		        e=f;
+		      }
 		      if (connect) addArc(n,b);
 		      return b;
+		    }
 		    ///Split an arc.
 		    ///This function splits an arc. First a new node \c b is added to
 		    ///the digraph, then the original arc is re-targeted to \c
 		    ///b. Finally an arc from \c b to the original target is added.
 		    ///
 		    ///\return The newly created node.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    Node split(Arc e) {
 		      Node b = addNode();
 		      addArc(b,target(e));
 		      changeTarget(e,b);
 		      return b;
+		    }
 		    /// \brief Class to make a snapshot of the digraph and restore
 		    /// it later.
 		    ///
 		    /// Class to make a snapshot of the digraph and restore it later.
 		    ///
 		    /// The newly added nodes and arcs can be removed using the
 		    /// restore() function.
 		    ///
 		    /// \warning Arc and node deletions and other modifications (e.g.
 		    /// contracting, splitting, reversing arcs or nodes) cannot be
 		    /// restored. These events invalidate the snapshot.
 		    class Snapshot {
 		    protected:
 		      typedef Parent::NodeNotifier NodeNotifier;
 		      class NodeObserverProxy : public NodeNotifier::ObserverBase {
 		      public:
 		        NodeObserverProxy(Snapshot& _snapshot)
 		          : snapshot(_snapshot) {}
 		        using NodeNotifier::ObserverBase::attach;
 		        using NodeNotifier::ObserverBase::detach;
 		        using NodeNotifier::ObserverBase::attached;
 		      protected:
 		        virtual void add(const Node& node) {
 		          snapshot.addNode(node);
+		        }
 		        virtual void add(const std::vector<Node>& nodes) {
 		          for (int i = nodes.size() - 1; i >= 0; ++i) {
 		            snapshot.addNode(nodes[i]);
+		          }
+		        }
 		        virtual void erase(const Node& node) {
 		          snapshot.eraseNode(node);
+		        }
 		        virtual void erase(const std::vector<Node>& nodes) {
 		          for (int i = 0; i < int(nodes.size()); ++i) {
 		            snapshot.eraseNode(nodes[i]);
+		          }
+		        }
 		        virtual void build() {
 		          Node node;
 		          std::vector<Node> nodes;
 		          for (notifier()->first(node); node != INVALID;
 		               notifier()->next(node)) {
 		            nodes.push_back(node);
+		          }
 		          for (int i = nodes.size() - 1; i >= 0; --i) {
 		            snapshot.addNode(nodes[i]);
+		          }
+		        }
 		        virtual void clear() {
 		          Node node;
 		          for (notifier()->first(node); node != INVALID;
 		               notifier()->next(node)) {
 		            snapshot.eraseNode(node);
+		          }
+		        }
 		        Snapshot& snapshot;
 		      };
 		      class ArcObserverProxy : public ArcNotifier::ObserverBase {
 		      public:
 		        ArcObserverProxy(Snapshot& _snapshot)
 		          : snapshot(_snapshot) {}
 		        using ArcNotifier::ObserverBase::attach;
 		        using ArcNotifier::ObserverBase::detach;
 		        using ArcNotifier::ObserverBase::attached;
 		      protected:
 		        virtual void add(const Arc& arc) {
 		          snapshot.addArc(arc);
+		        }
 		        virtual void add(const std::vector<Arc>& arcs) {
 		          for (int i = arcs.size() - 1; i >= 0; ++i) {
 		            snapshot.addArc(arcs[i]);
+		          }
+		        }
 		        virtual void erase(const Arc& arc) {
 		          snapshot.eraseArc(arc);
+		        }
 		        virtual void erase(const std::vector<Arc>& arcs) {
 		          for (int i = 0; i < int(arcs.size()); ++i) {
 		            snapshot.eraseArc(arcs[i]);
+		          }
+		        }
 		        virtual void build() {
 		          Arc arc;
 		          std::vector<Arc> arcs;
 		          for (notifier()->first(arc); arc != INVALID;
 		               notifier()->next(arc)) {
 		            arcs.push_back(arc);
+		          }
 		          for (int i = arcs.size() - 1; i >= 0; --i) {
 		            snapshot.addArc(arcs[i]);
+		          }
+		        }
 		        virtual void clear() {
 		          Arc arc;
 		          for (notifier()->first(arc); arc != INVALID;
 		               notifier()->next(arc)) {
 		            snapshot.eraseArc(arc);
+		          }
+		        }
 		        Snapshot& snapshot;
 		      };
 		      ListDigraph *digraph;
 		      NodeObserverProxy node_observer_proxy;
 		      ArcObserverProxy arc_observer_proxy;
 		      std::list<Node> added_nodes;
 		      std::list<Arc> added_arcs;
 		      void addNode(const Node& node) {
 		        added_nodes.push_front(node);
+		      }
 		      void eraseNode(const Node& node) {
 		        std::list<Node>::iterator it =
 		          std::find(added_nodes.begin(), added_nodes.end(), node);
 		        if (it == added_nodes.end()) {
 		          clear();
 		          arc_observer_proxy.detach();
 		          throw NodeNotifier::ImmediateDetach();
 		        } else {
 		          added_nodes.erase(it);
+		        }
+		      }
 		      void addArc(const Arc& arc) {
 		        added_arcs.push_front(arc);
+		      }
 		      void eraseArc(const Arc& arc) {
 		        std::list<Arc>::iterator it =
 		          std::find(added_arcs.begin(), added_arcs.end(), arc);
 		        if (it == added_arcs.end()) {
 		          clear();
 		          node_observer_proxy.detach();
 		          throw ArcNotifier::ImmediateDetach();
 		        } else {
 		          added_arcs.erase(it);
+		        }
+		      }
 		      void attach(ListDigraph &_digraph) {
 		        digraph = &_digraph;
 		        node_observer_proxy.attach(digraph->notifier(Node()));
 		        arc_observer_proxy.attach(digraph->notifier(Arc()));
+		      }
 		      void detach() {
 		        node_observer_proxy.detach();
 		        arc_observer_proxy.detach();
+		      }
 		      bool attached() const {
 		        return node_observer_proxy.attached();
+		      }
 		      void clear() {
 		        added_nodes.clear();
 		        added_arcs.clear();
+		      }
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
 		      /// To actually make a snapshot you must call save().
 		      Snapshot()
 		        : digraph(0), node_observer_proxy(*this),
 		          arc_observer_proxy(*this) {}
 		      /// \brief Constructor that immediately makes a snapshot.
 		      ///
 		      /// This constructor immediately makes a snapshot of the digraph.
 		      /// \param _digraph The digraph we make a snapshot of.
 		      Snapshot(ListDigraph &_digraph)
 		        : node_observer_proxy(*this),
 		          arc_observer_proxy(*this) {
 		        attach(_digraph);
+		      }
 		      /// \brief Make a snapshot.
 		      ///
 		      /// Make a snapshot of the digraph.
 		      ///
 		      /// This function can be called more than once. In case of a repeated
 		      /// call, the previous snapshot gets lost.
 		      /// \param _digraph The digraph we make the snapshot of.
 		      void save(ListDigraph &_digraph) {
 		        if (attached()) {
 		          detach();
 		          clear();
+		        }
 		        attach(_digraph);
+		      }
 		      /// \brief Undo the changes until the last snapshot.
 		      //
 		      /// Undo the changes until the last snapshot created by save().
 		      void restore() {
 		        detach();
 		        for(std::list<Arc>::iterator it = added_arcs.begin();
 		            it != added_arcs.end(); ++it) {
 		          digraph->erase(*it);
+		        }
 		        for(std::list<Node>::iterator it = added_nodes.begin();
 		            it != added_nodes.end(); ++it) {
 		          digraph->erase(*it);
+		        }
 		        clear();
+		      }
 		      /// \brief Gives back true when the snapshot is valid.
 		      ///
 		      /// Gives back true when the snapshot is valid.
 		      bool valid() const {
 		        return attached();
+		      }
 		    };
 		  };
 		  ///@}
 		  class ListGraphBase {
 		  protected:
 		    struct NodeT {
 		      int first_out;
 		      int prev, next;
 		    };
 		    struct ArcT {
 		      int target;
 		      int prev_out, next_out;
 		    };
 		    std::vector<NodeT> nodes;
 		    int first_node;
 		    int first_free_node;
 		    std::vector<ArcT> arcs;
 		    int first_free_arc;
 		  public:
 		    typedef ListGraphBase Digraph;
 		    class Node;
 		    class Arc;
 		    class Edge;
 		    class Node {
 		      friend class ListGraphBase;
 		    protected:
 		      int id;
 		      explicit Node(int pid) { id = pid;}
 		    public:
 		      Node() {}
 		      Node (Invalid) { id = -1; }
 		      bool operator==(const Node& node) const {return id == node.id;}
 		      bool operator!=(const Node& node) const {return id != node.id;}
 		      bool operator<(const Node& node) const {return id < node.id;}
 		    };
 		    class Edge {
 		      friend class ListGraphBase;
 		    protected:
 		      int id;
 		      explicit Edge(int pid) { id = pid;}
 		    public:
 		      Edge() {}
 		      Edge (Invalid) { id = -1; }
 		      bool operator==(const Edge& edge) const {return id == edge.id;}
 		      bool operator!=(const Edge& edge) const {return id != edge.id;}
 		      bool operator<(const Edge& edge) const {return id < edge.id;}
 		    };
 		    class Arc {
 		      friend class ListGraphBase;
 		    protected:
 		      int id;
 		      explicit Arc(int pid) { id = pid;}
 		    public:
 		      operator Edge() const {
 		        return id != -1 ? edgeFromId(id / 2) : INVALID;
 		      operator Edge() const {
 		        return id != -1 ? edgeFromId(id / 2) : INVALID;
+		      }
 		      Arc() {}
 		      Arc (Invalid) { id = -1; }
 		      bool operator==(const Arc& arc) const {return id == arc.id;}
 		      bool operator!=(const Arc& arc) const {return id != arc.id;}
 		      bool operator<(const Arc& arc) const {return id < arc.id;}
 		    };
 		    ListGraphBase()
 		      : nodes(), first_node(-1),
 		        first_free_node(-1), arcs(), first_free_arc(-1) {}
 		    int maxNodeId() const { return nodes.size()-1; }
 		    int maxEdgeId() const { return arcs.size() / 2 - 1; }
 		    int maxArcId() const { return arcs.size()-1; }
 		    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
 		    Node target(Arc e) const { return Node(arcs[e.id].target); }
 		    Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
 		    Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
 		    static bool direction(Arc e) {
 		      return (e.id & 1) == 1;
+		    }
 		    static Arc direct(Edge e, bool d) {
 		      return Arc(e.id * 2 + (d ? 1 : 0));
+		    }
 		    void first(Node& node) const {
 		      node.id = first_node;
+		    }
 		    void next(Node& node) const {
 		      node.id = nodes[node.id].next;
+		    }
 		    void first(Arc& e) const {
 		      int n = first_node;
 		      while (n != -1 && nodes[n].first_out == -1) {
 		        n = nodes[n].next;
+		      }
 		      e.id = (n == -1) ? -1 : nodes[n].first_out;
+		    }
 		    void next(Arc& e) const {
 		      if (arcs[e.id].next_out != -1) {
 		        e.id = arcs[e.id].next_out;
 		      } else {
 		        int n = nodes[arcs[e.id ^ 1].target].next;
 		        while(n != -1 && nodes[n].first_out == -1) {
 		          n = nodes[n].next;
+		        }
 		        e.id = (n == -1) ? -1 : nodes[n].first_out;
+		      }
+		    }
 		    void first(Edge& e) const {
 		      int n = first_node;
 		      while (n != -1) {
 		        e.id = nodes[n].first_out;
 		        while ((e.id & 1) != 1) {
 		          e.id = arcs[e.id].next_out;
+		        }
 		        if (e.id != -1) {
 		          e.id /= 2;
 		          return;
+		        }
 		        n = nodes[n].next;
+		      }
 		      e.id = -1;
+		    }
 		    void next(Edge& e) const {
 		      int n = arcs[e.id * 2].target;
 		      e.id = arcs[(e.id * 2) | 1].next_out;
 		      while ((e.id & 1) != 1) {
 		        e.id = arcs[e.id].next_out;
+		      }
 		      if (e.id != -1) {
 		        e.id /= 2;
 		        return;
+		      }
 		      n = nodes[n].next;
 		      while (n != -1) {
 		        e.id = nodes[n].first_out;
 		        while ((e.id & 1) != 1) {
 		          e.id = arcs[e.id].next_out;
+		        }
 		        if (e.id != -1) {
 		          e.id /= 2;
 		          return;
+		        }
 		        n = nodes[n].next;
+		      }
 		      e.id = -1;
+		    }
 		    void firstOut(Arc &e, const Node& v) const {
 		      e.id = nodes[v.id].first_out;
+		    }
 		    void nextOut(Arc &e) const {
 		      e.id = arcs[e.id].next_out;
+		    }
 		    void firstIn(Arc &e, const Node& v) const {
 		      e.id = ((nodes[v.id].first_out) ^ 1);
 		      if (e.id == -2) e.id = -1;
+		    }
 		    void nextIn(Arc &e) const {
 		      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
 		      if (e.id == -2) e.id = -1;
+		    }
 		    void firstInc(Edge &e, bool& d, const Node& v) const {
 		      int a = nodes[v.id].first_out;
 		      if (a != -1 ) {
 		        e.id = a / 2;
 		        d = ((a & 1) == 1);
 		      } else {
 		        e.id = -1;
 		        d = true;
+		      }
+		    }
 		    void nextInc(Edge &e, bool& d) const {
 		      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
 		      if (a != -1 ) {
 		        e.id = a / 2;
 		        d = ((a & 1) == 1);
 		      } else {
 		        e.id = -1;
 		        d = true;
+		      }
+		    }
 		    static int id(Node v) { return v.id; }
 		    static int id(Arc e) { return e.id; }
 		    static int id(Edge e) { return e.id; }
 		    static Node nodeFromId(int id) { return Node(id);}
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    static Edge edgeFromId(int id) { return Edge(id);}
 		    bool valid(Node n) const {
 		      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
 		        nodes[n.id].prev != -2;
+		    }
 		    bool valid(Arc a) const {
 		      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
 		        arcs[a.id].prev_out != -2;
+		    }
 		    bool valid(Edge e) const {
 		      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
 		        arcs[2 * e.id].prev_out != -2;
+		    }
 		    Node addNode() {
 		      int n;
 		      if(first_free_node==-1) {
 		        n = nodes.size();
 		        nodes.push_back(NodeT());
 		      } else {
 		        n = first_free_node;
 		        first_free_node = nodes[n].next;
+		      }
 		      nodes[n].next = first_node;
 		      if (first_node != -1) nodes[first_node].prev = n;
 		      first_node = n;
 		      nodes[n].prev = -1;
 		      nodes[n].first_out = -1;
 		      return Node(n);
+		    }
 		    Edge addEdge(Node u, Node v) {
 		      int n;
 		      if (first_free_arc == -1) {
 		        n = arcs.size();
 		        arcs.push_back(ArcT());
 		        arcs.push_back(ArcT());
 		      } else {
 		        n = first_free_arc;
 		        first_free_arc = arcs[n].next_out;
+		      }
 		      arcs[n].target = u.id;
 		      arcs[n | 1].target = v.id;
 		      arcs[n].next_out = nodes[v.id].first_out;
 		      if (nodes[v.id].first_out != -1) {
 		        arcs[nodes[v.id].first_out].prev_out = n;
+		      }
 		      arcs[n].prev_out = -1;
 		      nodes[v.id].first_out = n;
 		      arcs[n | 1].next_out = nodes[u.id].first_out;
 		      if (nodes[u.id].first_out != -1) {
 		        arcs[nodes[u.id].first_out].prev_out = (n | 1);
+		      }
 		      arcs[n | 1].prev_out = -1;
 		      nodes[u.id].first_out = (n | 1);
 		      return Edge(n / 2);
+		    }
 		    void erase(const Node& node) {
 		      int n = node.id;
 		      if(nodes[n].next != -1) {
 		        nodes[nodes[n].next].prev = nodes[n].prev;
+		      }
 		      if(nodes[n].prev != -1) {
 		        nodes[nodes[n].prev].next = nodes[n].next;
 		      } else {
 		        first_node = nodes[n].next;
+		      }
 		      nodes[n].next = first_free_node;
 		      first_free_node = n;
 		      nodes[n].prev = -2;
+		    }
 		    void erase(const Edge& edge) {
 		      int n = edge.id * 2;
 		      if (arcs[n].next_out != -1) {
 		        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+		      }
 		      if (arcs[n].prev_out != -1) {
 		        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 		      } else {
 		        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
+		      }
 		      if (arcs[n | 1].next_out != -1) {
 		        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
+		      }
 		      if (arcs[n | 1].prev_out != -1) {
 		        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
 		      } else {
 		        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
+		      }
 		      arcs[n].next_out = first_free_arc;
 		      first_free_arc = n;
 		      arcs[n].prev_out = -2;
 		      arcs[n | 1].prev_out = -2;
+		    }
 		    void clear() {
 		      arcs.clear();
 		      nodes.clear();
 		      first_node = first_free_node = first_free_arc = -1;
+		    }
 		  protected:
 		    void changeV(Edge e, Node n) {
 		      if(arcs[2 * e.id].next_out != -1) {
 		        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
+		      }
 		      if(arcs[2 * e.id].prev_out != -1) {
 		        arcs[arcs[2 * e.id].prev_out].next_out =
 		          arcs[2 * e.id].next_out;
 		      } else {
 		        nodes[arcs[(2 * e.id) | 1].target].first_out =
 		          arcs[2 * e.id].next_out;
+		      }
 		      if (nodes[n.id].first_out != -1) {
 		        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
+		      }
 		      arcs[(2 * e.id) | 1].target = n.id;
 		      arcs[2 * e.id].prev_out = -1;
 		      arcs[2 * e.id].next_out = nodes[n.id].first_out;
 		      nodes[n.id].first_out = 2 * e.id;
+		    }
 		    void changeU(Edge e, Node n) {
 		      if(arcs[(2 * e.id) | 1].next_out != -1) {
 		        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
 		          arcs[(2 * e.id) | 1].prev_out;
+		      }
 		      if(arcs[(2 * e.id) | 1].prev_out != -1) {
 		        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
 		          arcs[(2 * e.id) | 1].next_out;
 		      } else {
 		        nodes[arcs[2 * e.id].target].first_out =
 		          arcs[(2 * e.id) | 1].next_out;
+		      }
 		      if (nodes[n.id].first_out != -1) {
 		        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
+		      }
 		      arcs[2 * e.id].target = n.id;
 		      arcs[(2 * e.id) | 1].prev_out = -1;
 		      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
 		      nodes[n.id].first_out = ((2 * e.id) | 1);
+		    }
 		  };
 		  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
 		  /// \addtogroup graphs
 		  /// @{
 		  ///A general undirected graph structure.
 		  ///\ref ListGraph is a simple and fast <em>undirected graph</em>
 		  ///implementation based on static linked lists that are stored in
 		  ///\c std::vector structures.
 		  ///
 		  ///It conforms to the \ref concepts::Graph "Graph concept" and it
 		  ///also provides several useful additional functionalities.
 		  ///Most of the member functions and nested classes are documented
 		  ///only in the concept class.
 		  ///
 		  ///An important extra feature of this graph implementation is that
 		  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
 		  ///
 		  ///\sa concepts::Graph
 		  class ListGraph : public ExtendedListGraphBase {
 		  private:
 		    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
 		    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
 		    ///
 		    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
 		    ///\brief Assignment of ListGraph to another one is \e not allowed.
 		    ///Use copyGraph() instead.
 		    ///Assignment of ListGraph to another one is \e not allowed.
 		    ///Use copyGraph() instead.
 		    void operator=(const ListGraph &) {}
 		  public:
 		    /// Constructor
 		    /// Constructor.
 		    ///
 		    ListGraph() {}
 		    typedef ExtendedListGraphBase Parent;
 		    typedef Parent::OutArcIt IncEdgeIt;
 		    /// \brief Add a new node to the graph.
 		    ///
 		    /// Add a new node to the graph.
 		    /// \return the new node.
 		    Node addNode() { return Parent::addNode(); }
 		    /// \brief Add a new edge to the graph.
 		    ///
 		    /// Add a new edge to the graph with source node \c s
 		    /// and target node \c t.
 		    /// \return the new edge.
 		    Edge addEdge(const Node& s, const Node& t) {
 		      return Parent::addEdge(s, t);
+		    }
 		    /// \brief Erase a node from the graph.
 		    ///
 		    /// Erase a node from the graph.
 		    ///
 		    void erase(const Node& n) { Parent::erase(n); }
 		    /// \brief Erase an edge from the graph.
 		    ///
 		    /// Erase an edge from the graph.
 		    ///
 		    void erase(const Edge& e) { Parent::erase(e); }
 		    /// Node validity check
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    ///
 		    /// \warning A Node pointing to a removed item
 		    /// could become valid again later if new nodes are
 		    /// added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// Arc validity check
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning An Arc pointing to a removed item
 		    /// could become valid again later if new edges are
 		    /// added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    /// Edge validity check
 		    /// This function gives back true if the given edge is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning A Edge pointing to a removed item
 		    /// could become valid again later if new edges are
 		    /// added to the graph.
 		    bool valid(Edge e) const { return Parent::valid(e); }
 		    /// \brief Change the end \c u of \c e to \c n
 		    ///
 		    /// This function changes the end \c u of \c e to node \c n.
 		    ///
 		    ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
 		    ///changed edge are invalidated and if the changed node is the
 		    ///base node of an iterator then this iterator is also
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    void changeU(Edge e, Node n) {
 		      Parent::changeU(e,n);
+		    }
 		    /// \brief Change the end \c v of \c e to \c n
 		    ///
 		    /// This function changes the end \c v of \c e to \c n.
 		    ///
 		    ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
 		    ///valid, however <tt>ArcIt</tt>s and if the changed node is the
 		    ///base node of an iterator then this iterator is invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    void changeV(Edge e, Node n) {
 		      Parent::changeV(e,n);
+		    }
 		    /// \brief Contract two nodes.
 		    ///
 		    /// This function contracts two nodes.
 		    /// Node \p b will be removed but instead of deleting
 		    /// its neighboring arcs, they will be joined to \p a.
 		    /// The last parameter \p r controls whether to remove loops. \c true
 		    /// means that loops will be removed.
 		    ///
 		    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
 		    /// valid.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    void contract(Node a, Node b, bool r = true) {
 		      for(IncEdgeIt e(*this, b); e!=INVALID;) {
 		        IncEdgeIt f = e; ++f;
 		        if (r && runningNode(e) == a) {
 		          erase(e);
 		        } else if (u(e) == b) {
 		          changeU(e, a);
 		        } else {
 		          changeV(e, a);
+		        }
 		        e = f;
+		      }
 		      erase(b);
+		    }
 		    /// \brief Class to make a snapshot of the graph and restore
 		    /// it later.
 		    ///
 		    /// Class to make a snapshot of the graph and restore it later.
 		    ///
 		    /// The newly added nodes and edges can be removed
 		    /// using the restore() function.
 		    ///
 		    /// \warning Edge and node deletions and other modifications
 		    /// (e.g. changing nodes of edges, contracting nodes) cannot be
 		    /// restored. These events invalidate the snapshot.
 		    class Snapshot {
 		    protected:
 		      typedef Parent::NodeNotifier NodeNotifier;
 		      class NodeObserverProxy : public NodeNotifier::ObserverBase {
 		      public:
 		        NodeObserverProxy(Snapshot& _snapshot)
 		          : snapshot(_snapshot) {}
 		        using NodeNotifier::ObserverBase::attach;
 		        using NodeNotifier::ObserverBase::detach;
 		        using NodeNotifier::ObserverBase::attached;
 		      protected:
 		        virtual void add(const Node& node) {
 		          snapshot.addNode(node);
+		        }
 		        virtual void add(const std::vector<Node>& nodes) {
 		          for (int i = nodes.size() - 1; i >= 0; ++i) {
 		            snapshot.addNode(nodes[i]);
+		          }
+		        }
 		        virtual void erase(const Node& node) {
 		          snapshot.eraseNode(node);
+		        }
 		        virtual void erase(const std::vector<Node>& nodes) {

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

0 comments (0 inline)

RhodeCode

Login to your account

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

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