LEMON/LEMON-main Changeset - r735:853fcddcf282

Repositories » LEMON » LEMON-main

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

Changeset - r735:853fcddcf282

« 734:bd72f8

736:2e20aa »

r735:853fcddcf282

Sun, 23 Aug 2009 11:09:22

[Not Reviewed]

0 comments (0 inline)

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

Doc improvements, fixes and unifications for graphs (#311)

0 6 0

default

6 files changed with 471 insertions and 477 deletions:

doc/groups.dox

lemon/full_graph.h

lemon/grid_graph.h

lemon/hypercube_graph.h

lemon/list_graph.h

217

210

lemon/smart_graph.h

148

166

↑ Collapse diff ↑

doc/groups.dox

Show inline comments

@@ -511,162 +511,162 @@
 		/**
 		@defgroup metah Metaheuristics
 		@ingroup gen_opt_group
 		\brief Metaheuristics for LEMON library.
 		This group contains some metaheuristic optimization tools.
 		*/
 		/**
 		@defgroup utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
 		This group contains some simple basic graph utilities.
 		*/
 		/**
 		@defgroup misc Miscellaneous Tools
 		@ingroup utils
 		\brief Tools for development, debugging and testing.
 		This group contains several useful tools for development,
 		debugging and testing.
 		*/
 		/**
 		@defgroup timecount Time Measuring and Counting
 		@ingroup misc
 		\brief Simple tools for measuring the performance of algorithms.
 		This group contains simple tools for measuring the performance
 		of algorithms.
 		*/
 		/**
 		@defgroup exceptions Exceptions
 		@ingroup utils
 		\brief Exceptions defined in LEMON.
 		This group contains the exceptions defined in LEMON.
 		*/
 		/**
 		@defgroup io_group Input-Output
 		\brief Graph Input-Output methods
 		This group contains the tools for importing and exporting graphs
 		and graph related data. Now it supports the \ref lgf-format
 		"LEMON Graph Format", the \c DIMACS format and the encapsulated
 		postscript (EPS) format.
 		*/
 		/**
 		@defgroup lemon_io LEMON Graph Format
 		@ingroup io_group
 		\brief Reading and writing LEMON Graph Format.
 		This group contains methods for reading and writing
 		\ref lgf-format "LEMON Graph Format".
 		*/
 		/**
 		@defgroup eps_io Postscript Exporting
 		@ingroup io_group
 		\brief General \c EPS drawer and graph exporter
 		This group contains general \c EPS drawing methods and special
 		graph exporting tools.
 		*/
 		/**
 		@defgroup dimacs_group DIMACS format
 		@ingroup io_group
 		\brief Read and write files in DIMACS format
 		Tools to read a digraph from or write it to a file in DIMACS format data.
 		*/
 		/**
 		@defgroup nauty_group NAUTY Format
 		@ingroup io_group
 		\brief Read \e Nauty format
 		Tool to read graphs from \e Nauty format data.
 		*/
 		/**
 		@defgroup concept Concepts
 		\brief Skeleton classes and concept checking classes
 		This group contains the data/algorithm skeletons and concept checking
 		classes implemented in LEMON.
 		The purpose of the classes in this group is fourfold.
 		- These classes contain the documentations of the %concepts. In order
 		  to avoid document multiplications, an implementation of a concept
 		  simply refers to the corresponding concept class.
 		- These classes declare every functions, <tt>typedef</tt>s etc. an
 		  implementation of the %concepts should provide, however completely
 		  without implementations and real data structures behind the
 		  interface. On the other hand they should provide nothing else. All
 		  the algorithms working on a data structure meeting a certain concept
 		  should compile with these classes. (Though it will not run properly,
 		  of course.) In this way it is easily to check if an algorithm
 		  doesn't use any extra feature of a certain implementation.
 		- The concept descriptor classes also provide a <em>checker class</em>
 		  that makes it possible to check whether a certain implementation of a
 		  concept indeed provides all the required features.
 		- Finally, They can serve as a skeleton of a new implementation of a concept.
 		*/
 		/**
 		@defgroup graph_concepts Graph Structure Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for graph structures
 		This group contains the skeletons and concept checking classes of LEMON's
 		graph structures and helper classes used to implement these.
 		This group contains the skeletons and concept checking classes of
 		graph structures.
 		*/
 		/**
 		@defgroup map_concepts Map Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for maps
 		This group contains the skeletons and concept checking classes of maps.
 		*/
 		/**
 		\anchor demoprograms
 		@defgroup demos Demo Programs
 		Some demo programs are listed here. Their full source codes can be found in
 		the \c demo subdirectory of the source tree.
 		In order to compile them, use the <tt>make demo</tt> or the
 		<tt>make check</tt> commands.
 		*/
 		/**
 		@defgroup tools Standalone Utility Applications
 		Some utility applications are listed here.
 		The standard compilation procedure (<tt>./configure;make</tt>) will compile
 		them, as well.
 		*/
+		}

lemon/full_graph.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_FULL_GRAPH_H
 		#define LEMON_FULL_GRAPH_H
 		#include <lemon/core.h>
 		#include <lemon/bits/graph_extender.h>
 		///\ingroup graphs
 		///\file
-		///\brief FullGraph and FullDigraph classes.
+		///\brief FullDigraph and FullGraph classes.
 		namespace lemon {
 		  class FullDigraphBase {
 		  public:
 		    typedef FullDigraphBase Digraph;
 		    class Node;
 		    class Arc;
 		  protected:
 		    int _node_num;
 		    int _arc_num;
 		    FullDigraphBase() {}
 		    void construct(int n) { _node_num = n; _arc_num = n * n; }
 		  public:
 		    typedef True NodeNumTag;
 		    typedef True ArcNumTag;
 		    Node operator()(int ix) const { return Node(ix); }
 		    int index(const Node& node) const { return node._id; }
 		    Arc arc(const Node& s, const Node& t) const {
 		      return Arc(s._id * _node_num + t._id);
+		    }
 		    int nodeNum() const { return _node_num; }
 		    int arcNum() const { return _arc_num; }
 		    int maxNodeId() const { return _node_num - 1; }
 		    int maxArcId() const { return _arc_num - 1; }
 		    Node source(Arc arc) const { return arc._id / _node_num; }
 		    Node target(Arc arc) const { return arc._id % _node_num; }
 		    static int id(Node node) { return node._id; }
 		    static int id(Arc arc) { return arc._id; }
 		    static Node nodeFromId(int id) { return Node(id);}
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    typedef True FindArcTag;
 		    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
 		      return prev == INVALID ? arc(s, t) : INVALID;
+		    }
 		    class Node {
 		      friend class FullDigraphBase;
 		    protected:
 		      int _id;
 		      Node(int id) : _id(id) {}
 		    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 FullDigraphBase;
 		    protected:
 		      int _id;  // _node_num * source + target;
 		      Arc(int id) : _id(id) {}
 		    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;}
 		    };
 		    void first(Node& node) const {
 		      node._id = _node_num - 1;
+		    }
 		    static void next(Node& node) {
 		      --node._id;
+		    }
 		    void first(Arc& arc) const {
 		      arc._id = _arc_num - 1;
+		    }
 		    static void next(Arc& arc) {
 		      --arc._id;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      arc._id = (node._id + 1) * _node_num - 1;
+		    }
 		    void nextOut(Arc& arc) const {
 		      if (arc._id % _node_num == 0) arc._id = 0;
 		      --arc._id;
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      arc._id = _arc_num + node._id - _node_num;
+		    }
 		    void nextIn(Arc& arc) const {
 		      arc._id -= _node_num;
 		      if (arc._id < 0) arc._id = -1;
+		    }
 		  };
 		  typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;
 		  /// \ingroup graphs
 		  ///
-		  /// \brief A full digraph class.
+		  /// \brief A directed full graph class.
 		  ///
 		  /// This is a simple and fast directed full graph implementation.
 		  /// From each node go arcs to each node (including the source node),
 		  /// therefore the number of the arcs in the digraph is the square of
 		  /// the node number. This digraph type is completely static, so you
 		  /// can neither add nor delete either arcs or nodes, and it needs
 		  /// constant space in memory.
 		  /// FullDigraph is a simple and fast implmenetation of directed full
 		  /// (complete) graphs. It contains an arc from each node to each node
 		  /// (including a loop for each node), therefore the number of arcs
 		  /// is the square of the number of nodes.
 		  /// This class is completely static and it needs constant memory space.
 		  /// Thus you can neither add nor delete nodes or arcs, however
 		  /// the structure can be resized using resize().
 		  ///
 		  /// This class fully conforms to the \ref concepts::Digraph
 		  /// "Digraph concept".
 		  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
 		  /// Most of its member functions and nested classes are documented
 		  /// only in the concept class.
 		  ///
-		  /// The \c FullDigraph and \c FullGraph classes are very similar,
+		  /// \note FullDigraph and FullGraph classes are very similar,
 		  /// but there are two differences. While this class conforms only
 		  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
 		  /// class conforms to the \ref concepts::Graph "Graph" concept,
 		  /// moreover \c FullGraph does not contain a loop arc for each
 		  /// node as \c FullDigraph does.
 		  /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
 		  /// conforms to the \ref concepts::Graph "Graph" concept,
 		  /// moreover FullGraph does not contain a loop for each
 		  /// node as this class does.
 		  ///
 		  /// \sa FullGraph
 		  class FullDigraph : public ExtendedFullDigraphBase {
 		    typedef ExtendedFullDigraphBase Parent;
 		  public:
-		    /// \brief Constructor
+		    /// \brief Default constructor.
 		    ///
 		    /// Default constructor. The number of nodes and arcs will be zero.
 		    FullDigraph() { construct(0); }
 		    /// \brief Constructor
 		    ///
 		    /// Constructor.
 		    /// \param n The number of the nodes.
 		    FullDigraph(int n) { construct(n); }
 		    /// \brief Resizes the digraph
 		    ///
 		    /// Resizes the digraph. The function will fully destroy and
 		    /// rebuild the digraph. This cause that the maps of the digraph will
 		    /// This function resizes the digraph. It fully destroys and
 		    /// rebuilds the structure, therefore the maps of the digraph will be
 		    /// reallocated automatically and the previous values will be lost.
 		    void resize(int n) {
 		      Parent::notifier(Arc()).clear();
 		      Parent::notifier(Node()).clear();
 		      construct(n);
 		      Parent::notifier(Node()).build();
 		      Parent::notifier(Arc()).build();
+		    }
 		    /// \brief Returns the node with the given index.
 		    ///
 		    /// Returns the node with the given index. Since it is a static
 		    /// digraph its nodes can be indexed with integers from the range
-		    /// <tt>[0..nodeNum()-1]</tt>.
+		    /// Returns the node with the given index. Since this structure is
 		    /// completely static, the nodes can be indexed with integers from
 		    /// the range <tt>[0..nodeNum()-1]</tt>.
 		    /// \sa index()
 		    Node operator()(int ix) const { return Parent::operator()(ix); }
 		    /// \brief Returns the index of the given node.
 		    ///
 		    /// Returns the index of the given node. Since it is a static
 		    /// digraph its nodes can be indexed with integers from the range
 		    /// <tt>[0..nodeNum()-1]</tt>.
 		    /// \sa operator()
-		    int index(const Node& node) const { return Parent::index(node); }
+		    /// Returns the index of the given node. Since this structure is
 		    /// completely static, the nodes can be indexed with integers from
 		    /// the range <tt>[0..nodeNum()-1]</tt>.
 		    /// \sa operator()()
 		    int index(Node node) const { return Parent::index(node); }
 		    /// \brief Returns the arc connecting the given nodes.
 		    ///
 		    /// Returns the arc connecting the given nodes.
-		    Arc arc(const Node& u, const Node& v) const {
 		    Arc arc(Node u, Node v) const {
 		      return Parent::arc(u, v);
+		    }
 		    /// \brief Number of nodes.
 		    int nodeNum() const { return Parent::nodeNum(); }
 		    /// \brief Number of arcs.
 		    int arcNum() const { return Parent::arcNum(); }
 		  };
 		  class FullGraphBase {
 		  public:
 		    typedef FullGraphBase Graph;
 		    class Node;
 		    class Arc;
 		    class Edge;
 		  protected:
 		    int _node_num;
 		    int _edge_num;
 		    FullGraphBase() {}
 		    void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
 		    int _uid(int e) const {
 		      int u = e / _node_num;
 		      int v = e % _node_num;
 		      return u < v ? u : _node_num - 2 - u;
+		    }
 		    int _vid(int e) const {
 		      int u = e / _node_num;
 		      int v = e % _node_num;
 		      return u < v ? v : _node_num - 1 - v;
+		    }
 		    void _uvid(int e, int& u, int& v) const {
 		      u = e / _node_num;
 		      v = e % _node_num;
 		      if  (u >= v) {
 		        u = _node_num - 2 - u;
 		        v = _node_num - 1 - v;
+		      }
+		    }
 		    void _stid(int a, int& s, int& t) const {
 		      if ((a & 1) == 1) {
 		        _uvid(a >> 1, s, t);
 		      } else {
 		        _uvid(a >> 1, t, s);
+		      }
+		    }
 		    int _eid(int u, int v) const {
 		      if (u < (_node_num - 1) / 2) {
 		        return u * _node_num + v;
 		      } else {
 		        return (_node_num - 1 - u) * _node_num - v - 1;
+		      }
+		    }
 		  public:
 		    Node operator()(int ix) const { return Node(ix); }
 		    int index(const Node& node) const { return node._id; }
 		    Edge edge(const Node& u, const Node& v) const {
 		      if (u._id < v._id) {
 		        return Edge(_eid(u._id, v._id));
 		      } else if (u._id != v._id) {
 		        return Edge(_eid(v._id, u._id));
 		      } else {
 		        return INVALID;
+		      }
+		    }
 		    Arc arc(const Node& s, const Node& t) const {
 		      if (s._id < t._id) {
 		        return Arc((_eid(s._id, t._id) << 1) | 1);
 		      } else if (s._id != t._id) {
 		        return Arc(_eid(t._id, s._id) << 1);
 		      } else {
 		        return INVALID;
+		      }
+		    }
 		    typedef True NodeNumTag;
 		    typedef True ArcNumTag;
 		    typedef True EdgeNumTag;
 		    int nodeNum() const { return _node_num; }
 		    int arcNum() const { return 2 * _edge_num; }
 		    int edgeNum() const { return _edge_num; }
 		    static int id(Node node) { return node._id; }
 		    static int id(Arc arc) { return arc._id; }
 		    static int id(Edge edge) { return edge._id; }
 		    int maxNodeId() const { return _node_num-1; }
 		    int maxArcId() const { return 2 * _edge_num-1; }
 		    int maxEdgeId() const { return _edge_num-1; }
 		    static Node nodeFromId(int id) { return Node(id);}
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    static Edge edgeFromId(int id) { return Edge(id);}
 		    Node u(Edge edge) const {
 		      return Node(_uid(edge._id));
+		    }
 		    Node v(Edge edge) const {
 		      return Node(_vid(edge._id));
+		    }
 		    Node source(Arc arc) const {
 		      return Node((arc._id & 1) == 1 ?
 		                  _uid(arc._id >> 1) : _vid(arc._id >> 1));
+		    }
 		    Node target(Arc arc) const {
 		      return Node((arc._id & 1) == 1 ?
 		                  _vid(arc._id >> 1) : _uid(arc._id >> 1));
+		    }
@@ -395,218 +399,222 @@
 		      Arc(int id) : _id(id) {}
 		    public:
 		      Arc() { }
 		      Arc (Invalid) { _id = -1; }
 		      operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -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;}
 		    };
 		    static bool direction(Arc arc) {
 		      return (arc._id & 1) == 1;
+		    }
 		    static Arc direct(Edge edge, bool dir) {
 		      return Arc((edge._id << 1) | (dir ? 1 : 0));
+		    }
 		    void first(Node& node) const {
 		      node._id = _node_num - 1;
+		    }
 		    static void next(Node& node) {
 		      --node._id;
+		    }
 		    void first(Arc& arc) const {
 		      arc._id = (_edge_num << 1) - 1;
+		    }
 		    static void next(Arc& arc) {
 		      --arc._id;
+		    }
 		    void first(Edge& edge) const {
 		      edge._id = _edge_num - 1;
+		    }
 		    static void next(Edge& edge) {
 		      --edge._id;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      int s = node._id, t = _node_num - 1;
 		      if (s < t) {
 		        arc._id = (_eid(s, t) << 1) | 1;
 		      } else {
 		        --t;
 		        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
+		      }
+		    }
 		    void nextOut(Arc& arc) const {
 		      int s, t;
 		      _stid(arc._id, s, t);
 		      --t;
 		      if (s < t) {
 		        arc._id = (_eid(s, t) << 1) | 1;
 		      } else {
 		        if (s == t) --t;
 		        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
+		      }
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      int s = _node_num - 1, t = node._id;
 		      if (s > t) {
 		        arc._id = (_eid(t, s) << 1);
 		      } else {
 		        --s;
 		        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
+		      }
+		    }
 		    void nextIn(Arc& arc) const {
 		      int s, t;
 		      _stid(arc._id, s, t);
 		      --s;
 		      if (s > t) {
 		        arc._id = (_eid(t, s) << 1);
 		      } else {
 		        if (s == t) --s;
 		        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
+		      }
+		    }
 		    void firstInc(Edge& edge, bool& dir, const Node& node) const {
 		      int u = node._id, v = _node_num - 1;
 		      if (u < v) {
 		        edge._id = _eid(u, v);
 		        dir = true;
 		      } else {
 		        --v;
 		        edge._id = (v != -1 ? _eid(v, u) : -1);
 		        dir = false;
+		      }
+		    }
 		    void nextInc(Edge& edge, bool& dir) const {
 		      int u, v;
 		      if (dir) {
 		        _uvid(edge._id, u, v);
 		        --v;
 		        if (u < v) {
 		          edge._id = _eid(u, v);
 		        } else {
 		          --v;
 		          edge._id = (v != -1 ? _eid(v, u) : -1);
 		          dir = false;
+		        }
 		      } else {
 		        _uvid(edge._id, v, u);
 		        --v;
 		        edge._id = (v != -1 ? _eid(v, u) : -1);
+		      }
+		    }
 		  };
 		  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
 		  /// \ingroup graphs
 		  ///
 		  /// \brief An undirected full graph class.
 		  ///
 		  /// This is a simple and fast undirected full graph
 		  /// implementation. From each node go edge to each other node,
 		  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
 		  /// This graph type is completely static, so you can neither
 		  /// add nor delete either edges or nodes, and it needs constant
 		  /// space in memory.
 		  /// FullGraph is a simple and fast implmenetation of undirected full
 		  /// (complete) graphs. It contains an edge between every distinct pair
 		  /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
 		  /// This class is completely static and it needs constant memory space.
 		  /// Thus you can neither add nor delete nodes or edges, however
 		  /// the structure can be resized using resize().
 		  ///
-		  /// This class fully conforms to the \ref concepts::Graph "Graph concept".
+		  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
 		  /// Most of its member functions and nested classes are documented
 		  /// only in the concept class.
 		  ///
 		  /// The \c FullGraph and \c FullDigraph classes are very similar,
 		  /// but there are two differences. While the \c FullDigraph class
 		  /// \note FullDigraph and FullGraph classes are very similar,
 		  /// but there are two differences. While FullDigraph
 		  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
 		  /// this class conforms to the \ref concepts::Graph "Graph" concept,
 		  /// moreover \c FullGraph does not contain a loop arc for each
 		  /// node as \c FullDigraph does.
 		  /// moreover this class does not contain a loop for each
 		  /// node as FullDigraph does.
 		  ///
 		  /// \sa FullDigraph
 		  class FullGraph : public ExtendedFullGraphBase {
 		    typedef ExtendedFullGraphBase Parent;
 		  public:
-		    /// \brief Constructor
+		    /// \brief Default constructor.
 		    ///
 		    /// Default constructor. The number of nodes and edges will be zero.
 		    FullGraph() { construct(0); }
 		    /// \brief Constructor
 		    ///
 		    /// Constructor.
 		    /// \param n The number of the nodes.
 		    FullGraph(int n) { construct(n); }
 		    /// \brief Resizes the graph
 		    ///
 		    /// Resizes the graph. The function will fully destroy and
 		    /// rebuild the graph. This cause that the maps of the graph will
 		    /// This function resizes the graph. It fully destroys and
 		    /// rebuilds the structure, therefore the maps of the graph will be
 		    /// reallocated automatically and the previous values will be lost.
 		    void resize(int n) {
 		      Parent::notifier(Arc()).clear();
 		      Parent::notifier(Edge()).clear();
 		      Parent::notifier(Node()).clear();
 		      construct(n);
 		      Parent::notifier(Node()).build();
 		      Parent::notifier(Edge()).build();
 		      Parent::notifier(Arc()).build();
+		    }
 		    /// \brief Returns the node with the given index.
 		    ///
 		    /// Returns the node with the given index. Since it is a static
 		    /// graph its nodes can be indexed with integers from the range
-		    /// <tt>[0..nodeNum()-1]</tt>.
+		    /// Returns the node with the given index. Since this structure is
 		    /// completely static, the nodes can be indexed with integers from
 		    /// the range <tt>[0..nodeNum()-1]</tt>.
 		    /// \sa index()
 		    Node operator()(int ix) const { return Parent::operator()(ix); }
 		    /// \brief Returns the index of the given node.
 		    ///
 		    /// Returns the index of the given node. Since it is a static
 		    /// graph its nodes can be indexed with integers from the range
 		    /// <tt>[0..nodeNum()-1]</tt>.
 		    /// \sa operator()
-		    int index(const Node& node) const { return Parent::index(node); }
+		    /// Returns the index of the given node. Since this structure is
 		    /// completely static, the nodes can be indexed with integers from
 		    /// the range <tt>[0..nodeNum()-1]</tt>.
 		    /// \sa operator()()
 		    int index(Node node) const { return Parent::index(node); }
 		    /// \brief Returns the arc connecting the given nodes.
 		    ///
 		    /// Returns the arc connecting the given nodes.
-		    Arc arc(const Node& s, const Node& t) const {
 		    Arc arc(Node s, Node t) const {
 		      return Parent::arc(s, t);
+		    }
-		    /// \brief Returns the edge connects the given nodes.
+		    /// \brief Returns the edge connecting the given nodes.
 		    ///
 		    /// Returns the edge connects the given nodes.
 		    Edge edge(const Node& u, const Node& v) const {
 		    /// Returns the edge connecting the given nodes.
 		    Edge edge(Node u, Node v) const {
 		      return Parent::edge(u, v);
+		    }
 		    /// \brief Number of nodes.
 		    int nodeNum() const { return Parent::nodeNum(); }
 		    /// \brief Number of arcs.
 		    int arcNum() const { return Parent::arcNum(); }
 		    /// \brief Number of edges.
 		    int edgeNum() const { return Parent::edgeNum(); }
 		  };
 		} //namespace lemon
 		#endif //LEMON_FULL_GRAPH_H

lemon/grid_graph.h

Show inline comments

@@ -345,359 +345,353 @@
+		        }
 		        if (nid >= _width) {
 		          arc._id = (nid - _width) << 1 | 1;
 		          return;
+		        }
 		      } else {
 		        if (nid >= _edge_limit) {
 		          nid = (nid - _edge_limit) % (_width - 1) +
 		            (nid - _edge_limit) / (_width - 1) * _width + 1;
 		          if (nid >= _width) {
 		            arc._id = (nid - _width) << 1 | 1;
 		            return;
+		          }
+		        }
+		      }
 		      arc._id = -1;
+		    }
 		    void firstInc(Edge& edge, bool& dir, const Node& node) const {
 		      if (node._id % _width < _width - 1) {
 		        edge._id = _edge_limit + node._id % _width +
 		          (node._id / _width) * (_width - 1);
 		        dir = true;
 		        return;
+		      }
 		      if (node._id < _node_num - _width) {
 		        edge._id = node._id;
 		        dir = true;
 		        return;
+		      }
 		      if (node._id % _width > 0) {
 		        edge._id = _edge_limit + node._id % _width +
 		          (node._id / _width) * (_width - 1) - 1;
 		        dir = false;
 		        return;
+		      }
 		      if (node._id >= _width) {
 		        edge._id = node._id - _width;
 		        dir = false;
 		        return;
+		      }
 		      edge._id = -1;
 		      dir = true;
+		    }
 		    void nextInc(Edge& edge, bool& dir) const {
 		      int nid = edge._id;
 		      if (dir) {
 		        if (nid >= _edge_limit) {
 		          nid = (nid - _edge_limit) % (_width - 1) +
 		            (nid - _edge_limit) / (_width - 1) * _width;
 		          if (nid < _node_num - _width) {
 		            edge._id = nid;
 		            return;
+		          }
+		        }
 		        if (nid % _width > 0) {
 		          edge._id = _edge_limit + nid % _width +
 		            (nid / _width) * (_width - 1) - 1;
 		          dir = false;
 		          return;
+		        }
 		        if (nid >= _width) {
 		          edge._id = nid - _width;
 		          dir = false;
 		          return;
+		        }
 		      } else {
 		        if (nid >= _edge_limit) {
 		          nid = (nid - _edge_limit) % (_width - 1) +
 		            (nid - _edge_limit) / (_width - 1) * _width + 1;
 		          if (nid >= _width) {
 		            edge._id = nid - _width;
 		            return;
+		          }
+		        }
+		      }
 		      edge._id = -1;
 		      dir = true;
+		    }
 		    Arc right(Node n) const {
 		      if (n._id % _width < _width - 1) {
 		        return Arc(((_edge_limit + n._id % _width +
 		                    (n._id / _width) * (_width - 1)) << 1) | 1);
 		      } else {
 		        return INVALID;
+		      }
+		    }
 		    Arc left(Node n) const {
 		      if (n._id % _width > 0) {
 		        return Arc((_edge_limit + n._id % _width +
 		                     (n._id / _width) * (_width - 1) - 1) << 1);
 		      } else {
 		        return INVALID;
+		      }
+		    }
 		    Arc up(Node n) const {
 		      if (n._id < _edge_limit) {
 		        return Arc((n._id << 1) | 1);
 		      } else {
 		        return INVALID;
+		      }
+		    }
 		    Arc down(Node n) const {
 		      if (n._id >= _width) {
 		        return Arc((n._id - _width) << 1);
 		      } else {
 		        return INVALID;
+		      }
+		    }
 		  private:
 		    int _width, _height;
 		    int _node_num, _edge_num;
 		    int _edge_limit;
 		  };
 		  typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
 		  /// \ingroup graphs
 		  ///
 		  /// \brief Grid graph class
 		  ///
 		  /// This class implements a special graph type. The nodes of the
 		  /// graph can be indexed by two integer \c (i,j) value where \c i is
 		  /// in the \c [0..width()-1] range and j is in the \c
 		  /// [0..height()-1] range.  Two nodes are connected in the graph if
 		  /// the indexes differ exactly on one position and exactly one is
 		  /// the difference. The nodes of the graph can be indexed by position
 		  /// with the \c operator()() function. The positions of the nodes can be
 		  /// get with \c pos(), \c col() and \c row() members. The outgoing
 		  /// GridGraph implements a special graph type. The nodes of the
 		  /// graph can be indexed by two integer values \c (i,j) where \c i is
 		  /// in the range <tt>[0..width()-1]</tt> and j is in the range
 		  /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if
 		  /// the indices differ exactly on one position and the difference is
 		  /// also exactly one. The nodes of the graph can be obtained by position
 		  /// using the \c operator()() function and the indices of the nodes can
 		  /// be obtained using \c pos(), \c col() and \c row() members. The outgoing
 		  /// arcs can be retrieved with the \c right(), \c up(), \c left()
 		  /// and \c down() functions, where the bottom-left corner is the
 		  /// origin.
 		  ///
 		  /// This class is completely static and it needs constant memory space.
 		  /// Thus you can neither add nor delete nodes or edges, however
 		  /// the structure can be resized using resize().
 		  ///
 		  /// \image html grid_graph.png
 		  /// \image latex grid_graph.eps "Grid graph" width=\textwidth
 		  ///
 		  /// A short example about the basic usage:
 		  ///\code
 		  /// GridGraph graph(rows, cols);
 		  /// GridGraph::NodeMap<int> val(graph);
 		  /// for (int i = 0; i < graph.width(); ++i) {
 		  ///   for (int j = 0; j < graph.height(); ++j) {
 		  ///     val[graph(i, j)] = i + j;
 		  ///   }
 		  /// }
 		  ///\endcode
 		  ///
 		  /// This graph type fully conforms to the \ref concepts::Graph
 		  /// "Graph concept".
 		  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
 		  /// Most of its member functions and nested classes are documented
 		  /// only in the concept class.
 		  class GridGraph : public ExtendedGridGraphBase {
 		    typedef ExtendedGridGraphBase Parent;
 		  public:
-		    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
+		    /// \brief Map to get the indices of the nodes as \ref dim2::Point
 		    /// "dim2::Point<int>".
 		    ///
-		    /// Map to get the indices of the nodes as dim2::Point<int>.
+		    /// Map to get the indices of the nodes as \ref dim2::Point
 		    /// "dim2::Point<int>".
 		    class IndexMap {
 		    public:
 		      /// \brief The key type of the map
 		      typedef GridGraph::Node Key;
 		      /// \brief The value type of the map
 		      typedef dim2::Point<int> Value;
 		      /// \brief Constructor
 		      ///
 		      /// Constructor
 		      IndexMap(const GridGraph& graph) : _graph(graph) {}
 		      /// \brief The subscript operator
 		      ///
 		      /// The subscript operator.
 		      Value operator[](Key key) const {
 		        return _graph.pos(key);
+		      }
 		    private:
 		      const GridGraph& _graph;
 		    };
 		    /// \brief Map to get the column of the nodes.
 		    ///
 		    /// Map to get the column of the nodes.
 		    class ColMap {
 		    public:
 		      /// \brief The key type of the map
 		      typedef GridGraph::Node Key;
 		      /// \brief The value type of the map
 		      typedef int Value;
 		      /// \brief Constructor
 		      ///
 		      /// Constructor
 		      ColMap(const GridGraph& graph) : _graph(graph) {}
 		      /// \brief The subscript operator
 		      ///
 		      /// The subscript operator.
 		      Value operator[](Key key) const {
 		        return _graph.col(key);
+		      }
 		    private:
 		      const GridGraph& _graph;
 		    };
 		    /// \brief Map to get the row of the nodes.
 		    ///
 		    /// Map to get the row of the nodes.
 		    class RowMap {
 		    public:
 		      /// \brief The key type of the map
 		      typedef GridGraph::Node Key;
 		      /// \brief The value type of the map
 		      typedef int Value;
 		      /// \brief Constructor
 		      ///
 		      /// Constructor
 		      RowMap(const GridGraph& graph) : _graph(graph) {}
 		      /// \brief The subscript operator
 		      ///
 		      /// The subscript operator.
 		      Value operator[](Key key) const {
 		        return _graph.row(key);
+		      }
 		    private:
 		      const GridGraph& _graph;
 		    };
 		    /// \brief Constructor
 		    ///
 		    /// Construct a grid graph with given size.
+		    /// Construct a grid graph with the given size.
 		    GridGraph(int width, int height) { construct(width, height); }
-		    /// \brief Resize the graph
+		    /// \brief Resizes the graph
 		    ///
 		    /// Resize the graph. The function will fully destroy and rebuild
 		    /// the graph.  This cause that the maps of the graph will
 		    /// reallocated automatically and the previous values will be
 		    /// lost.
 		    /// This function resizes the graph. It fully destroys and
 		    /// rebuilds the structure, therefore the maps of the graph will be
 		    /// reallocated automatically and the previous values will be lost.
 		    void resize(int width, int height) {
 		      Parent::notifier(Arc()).clear();
 		      Parent::notifier(Edge()).clear();
 		      Parent::notifier(Node()).clear();
 		      construct(width, height);
 		      Parent::notifier(Node()).build();
 		      Parent::notifier(Edge()).build();
 		      Parent::notifier(Arc()).build();
+		    }
 		    /// \brief The node on the given position.
 		    ///
 		    /// Gives back the node on the given position.
 		    Node operator()(int i, int j) const {
 		      return Parent::operator()(i, j);
+		    }
-		    /// \brief Gives back the column index of the node.
+		    /// \brief The column index of the node.
 		    ///
 		    /// Gives back the column index of the node.
 		    int col(Node n) const {
 		      return Parent::col(n);
+		    }
-		    /// \brief Gives back the row index of the node.
+		    /// \brief The row index of the node.
 		    ///
 		    /// Gives back the row index of the node.
 		    int row(Node n) const {
 		      return Parent::row(n);
+		    }
-		    /// \brief Gives back the position of the node.
+		    /// \brief The position of the node.
 		    ///
 		    /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
 		    dim2::Point<int> pos(Node n) const {
 		      return Parent::pos(n);
+		    }
-		    /// \brief Gives back the number of the columns.
+		    /// \brief The number of the columns.
 		    ///
 		    /// Gives back the number of the columns.
 		    int width() const {
 		      return Parent::width();
+		    }
-		    /// \brief Gives back the number of the rows.
+		    /// \brief The number of the rows.
 		    ///
 		    /// Gives back the number of the rows.
 		    int height() const {
 		      return Parent::height();
+		    }
-		    /// \brief Gives back the arc goes right from the node.
+		    /// \brief The arc goes right from the node.
 		    ///
 		    /// Gives back the arc goes right from the node. If there is not
 		    /// outgoing arc then it gives back INVALID.
 		    Arc right(Node n) const {
 		      return Parent::right(n);
+		    }
-		    /// \brief Gives back the arc goes left from the node.
+		    /// \brief The arc goes left from the node.
 		    ///
 		    /// Gives back the arc goes left from the node. If there is not
 		    /// outgoing arc then it gives back INVALID.
 		    Arc left(Node n) const {
 		      return Parent::left(n);
+		    }
-		    /// \brief Gives back the arc goes up from the node.
+		    /// \brief The arc goes up from the node.
 		    ///
 		    /// Gives back the arc goes up from the node. If there is not
 		    /// outgoing arc then it gives back INVALID.
 		    Arc up(Node n) const {
 		      return Parent::up(n);
+		    }
-		    /// \brief Gives back the arc goes down from the node.
+		    /// \brief The arc goes down from the node.
 		    ///
 		    /// Gives back the arc goes down from the node. If there is not
 		    /// outgoing arc then it gives back INVALID.
 		    Arc down(Node n) const {
 		      return Parent::down(n);
+		    }
 		    /// \brief Index map of the grid graph
 		    ///
 		    /// Just returns an IndexMap for the grid graph.
 		    IndexMap indexMap() const {
 		      return IndexMap(*this);
+		    }
 		    /// \brief Row map of the grid graph
 		    ///
 		    /// Just returns a RowMap for the grid graph.
 		    RowMap rowMap() const {
 		      return RowMap(*this);
+		    }
 		    /// \brief Column map of the grid graph
 		    ///
 		    /// Just returns a ColMap for the grid graph.
 		    ColMap colMap() const {
 		      return ColMap(*this);
+		    }
 		  };
+		}
 		#endif

lemon/hypercube_graph.h

Show inline comments

@@ -157,282 +157,285 @@
 		    public:
 		      Arc() {}
 		      Arc (Invalid) : _id(-1) {}
 		      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
 		      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;}
 		    };
 		    void first(Node& node) const {
 		      node._id = _node_num - 1;
+		    }
 		    static void next(Node& node) {
 		      --node._id;
+		    }
 		    void first(Edge& edge) const {
 		      edge._id = _edge_num - 1;
+		    }
 		    static void next(Edge& edge) {
 		      --edge._id;
+		    }
 		    void first(Arc& arc) const {
 		      arc._id = 2 * _edge_num - 1;
+		    }
 		    static void next(Arc& arc) {
 		      --arc._id;
+		    }
 		    void firstInc(Edge& edge, bool& dir, const Node& node) const {
 		      edge._id = node._id >> 1;
 		      dir = (node._id & 1) == 0;
+		    }
 		    void nextInc(Edge& edge, bool& dir) const {
 		      Node n = dir ? u(edge) : v(edge);
 		      int k = (edge._id >> (_dim-1)) + 1;
 		      if (k < _dim) {
 		        edge._id = (k << (_dim-1)) |
 		          ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
 		        dir = ((n._id >> k) & 1) == 0;
 		      } else {
 		        edge._id = -1;
 		        dir = true;
+		      }
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      arc._id = ((node._id >> 1) << 1) | (~node._id & 1);
+		    }
 		    void nextOut(Arc& arc) const {
 		      Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
 		      int k = (arc._id >> _dim) + 1;
 		      if (k < _dim) {
 		        arc._id = (k << (_dim-1)) |
 		          ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
 		        arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
 		      } else {
 		        arc._id = -1;
+		      }
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      arc._id = ((node._id >> 1) << 1) | (node._id & 1);
+		    }
 		    void nextIn(Arc& arc) const {
 		      Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
 		      int k = (arc._id >> _dim) + 1;
 		      if (k < _dim) {
 		        arc._id = (k << (_dim-1)) |
 		          ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
 		        arc._id = (arc._id << 1) | ((n._id >> k) & 1);
 		      } else {
 		        arc._id = -1;
+		      }
+		    }
 		    static bool direction(Arc arc) {
 		      return (arc._id & 1) == 1;
+		    }
 		    static Arc direct(Edge edge, bool dir) {
 		      return Arc((edge._id << 1) | (dir ? 1 : 0));
+		    }
 		    int dimension() const {
 		      return _dim;
+		    }
 		    bool projection(Node node, int n) const {
 		      return static_cast<bool>(node._id & (1 << n));
+		    }
 		    int dimension(Edge edge) const {
 		      return edge._id >> (_dim-1);
+		    }
 		    int dimension(Arc arc) const {
 		      return arc._id >> _dim;
+		    }
 		    int index(Node node) const {
 		      return node._id;
+		    }
 		    Node operator()(int ix) const {
 		      return Node(ix);
+		    }
 		  private:
 		    int _dim;
 		    int _node_num, _edge_num;
 		  };
 		  typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;
 		  /// \ingroup graphs
 		  ///
 		  /// \brief Hypercube graph class
 		  ///
 		  /// This class implements a special graph type. The nodes of the graph
 		  /// are indiced with integers with at most \c dim binary digits.
 		  /// HypercubeGraph implements a special graph type. The nodes of the
 		  /// graph are indexed with integers having at most \c dim binary digits.
 		  /// Two nodes are connected in the graph if and only if their indices
 		  /// differ only on one position in the binary form.
 		  /// This class is completely static and it needs constant memory space.
 		  /// Thus you can neither add nor delete nodes or edges.
 		  ///
 		  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
 		  /// Most of its member functions and nested classes are documented
 		  /// only in the concept class.
 		  ///
 		  /// \note The type of the indices is chosen to \c int for efficiency
 		  /// reasons. Thus the maximum dimension of this implementation is 26
 		  /// (assuming that the size of \c int is 32 bit).
 		  ///
 		  /// This graph type fully conforms to the \ref concepts::Graph
 		  /// "Graph concept".
 		  class HypercubeGraph : public ExtendedHypercubeGraphBase {
 		    typedef ExtendedHypercubeGraphBase Parent;
 		  public:
 		    /// \brief Constructs a hypercube graph with \c dim dimensions.
 		    ///
 		    /// Constructs a hypercube graph with \c dim dimensions.
 		    HypercubeGraph(int dim) { construct(dim); }
 		    /// \brief The number of dimensions.
 		    ///
 		    /// Gives back the number of dimensions.
 		    int dimension() const {
 		      return Parent::dimension();
+		    }
 		    /// \brief Returns \c true if the n'th bit of the node is one.
 		    ///
 		    /// Returns \c true if the n'th bit of the node is one.
 		    bool projection(Node node, int n) const {
 		      return Parent::projection(node, n);
+		    }
 		    /// \brief The dimension id of an edge.
 		    ///
 		    /// Gives back the dimension id of the given edge.
-		    /// It is in the [0..dim-1] range.
+		    /// It is in the range <tt>[0..dim-1]</tt>.
 		    int dimension(Edge edge) const {
 		      return Parent::dimension(edge);
+		    }
 		    /// \brief The dimension id of an arc.
 		    ///
 		    /// Gives back the dimension id of the given arc.
-		    /// It is in the [0..dim-1] range.
+		    /// It is in the range <tt>[0..dim-1]</tt>.
 		    int dimension(Arc arc) const {
 		      return Parent::dimension(arc);
+		    }
 		    /// \brief The index of a node.
 		    ///
 		    /// Gives back the index of the given node.
 		    /// The lower bits of the integer describes the node.
 		    int index(Node node) const {
 		      return Parent::index(node);
+		    }
 		    /// \brief Gives back a node by its index.
 		    ///
 		    /// Gives back a node by its index.
 		    Node operator()(int ix) const {
 		      return Parent::operator()(ix);
+		    }
 		    /// \brief Number of nodes.
 		    int nodeNum() const { return Parent::nodeNum(); }
 		    /// \brief Number of edges.
 		    int edgeNum() const { return Parent::edgeNum(); }
 		    /// \brief Number of arcs.
 		    int arcNum() const { return Parent::arcNum(); }
 		    /// \brief Linear combination map.
 		    ///
 		    /// This map makes possible to give back a linear combination
 		    /// for each node. It works like the \c std::accumulate function,
 		    /// so it accumulates the \c bf binary function with the \c fv first
 		    /// value. The map accumulates only on that positions (dimensions)
 		    /// where the index of the node is one. The values that have to be
 		    /// accumulated should be given by the \c begin and \c end iterators
 		    /// and the length of this range should be equal to the dimension
 		    /// number of the graph.
 		    ///
 		    ///\code
 		    /// const int DIM = 3;
 		    /// HypercubeGraph graph(DIM);
 		    /// dim2::Point<double> base[DIM];
 		    /// for (int k = 0; k < DIM; ++k) {
 		    ///   base[k].x = rnd();
 		    ///   base[k].y = rnd();
 		    /// }
 		    /// HypercubeGraph::HyperMap<dim2::Point<double> >
 		    ///   pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
 		    ///\endcode
 		    ///
 		    /// \see HypercubeGraph
 		    template <typename T, typename BF = std::plus<T> >
 		    class HyperMap {
 		    public:
 		      /// \brief The key type of the map
 		      typedef Node Key;
 		      /// \brief The value type of the map
 		      typedef T Value;
 		      /// \brief Constructor for HyperMap.
 		      ///
 		      /// Construct a HyperMap for the given graph. The values that have
 		      /// to be accumulated should be given by the \c begin and \c end
 		      /// iterators and the length of this range should be equal to the
 		      /// dimension number of the graph.
 		      ///
 		      /// This map accumulates the \c bf binary function with the \c fv
 		      /// first value on that positions (dimensions) where the index of
 		      /// the node is one.
 		      template <typename It>
 		      HyperMap(const Graph& graph, It begin, It end,
 		               T fv = 0, const BF& bf = BF())
 		        : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf)
+		      {
 		        LEMON_ASSERT(_values.size() == graph.dimension(),
 		                     "Wrong size of range");
+		      }
 		      /// \brief The partial accumulated value.
 		      ///
 		      /// Gives back the partial accumulated value.
 		      Value operator[](const Key& k) const {
 		        Value val = _first_value;
 		        int id = _graph.index(k);
 		        int n = 0;
 		        while (id != 0) {
 		          if (id & 1) {
 		            val = _bin_func(val, _values[n]);
+		          }
 		          id >>= 1;
 		          ++n;
+		        }
 		        return val;
+		      }
 		    private:
 		      const Graph& _graph;
 		      std::vector<T> _values;
 		      T _first_value;
 		      BF _bin_func;
 		    };
 		  };
+		}
 		#endif

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-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_LIST_GRAPH_H
 		#define LEMON_LIST_GRAPH_H
 		///\ingroup graphs
 		///\file
-		///\brief ListDigraph, ListGraph classes.
+		///\brief ListDigraph and 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; }
@@ -186,795 +186,796 @@
+		    }
 		    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
 		  ///\ref ListDigraph is a versatile and fast directed graph
 		  ///implementation based on 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
+		  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
 		  ///and it also provides several useful additional functionalities.
 		  ///Most of its member functions and nested classes are documented
 		  ///only in the concept class.
 		  ///
 		  ///\sa concepts::Digraph
+		  ///\sa ListGraph
 		  class ListDigraph : public ExtendedListDigraphBase {
 		    typedef ExtendedListDigraphBase Parent;
 		  private:
 		    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 		    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 		    ///
 		    /// Digraphs are \e not copy constructible. Use DigraphCopy 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.
+		    /// \brief Assignment of a digraph to another one is \e not allowed.
 		    /// Use DigraphCopy instead.
 		    void operator=(const ListDigraph &) {}
 		  public:
 		    /// Constructor
 		    /// Constructor.
 		    ///
 		    ListDigraph() {}
 		    ///Add a new node to the digraph.
-		    ///Add a new node to the digraph.
+		    ///This function adds 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
+		    ///This function adds 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) {
 		    Arc addArc(Node s, 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); }
+		    ///This function erases the given node from the digraph.
 		    void erase(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); }
+		    ///This function erases the given arc from the digraph.
 		    void erase(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.
 		    /// This function gives back \c true if the given node is valid,
 		    /// i.e. it is a real node of the digraph.
 		    ///
 		    /// \warning A Node pointing to a removed item
 		    /// could become valid again later if new nodes are
-		    /// added to the graph.
+		    /// \warning A removed node could become valid again if new nodes are
 		    /// added to the digraph.
 		    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.
 		    /// This function gives back \c true if the given arc is valid,
 		    /// i.e. it is a real arc of the digraph.
 		    ///
 		    /// \warning An Arc pointing to a removed item
 		    /// could become valid again later if new nodes are
-		    /// added to the graph.
+		    /// \warning A removed arc could become valid again if new arcs are
 		    /// added to the digraph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
-		    /// Change the target of \c a to \c n
+		    /// Change the target node of an arc
-		    /// Change the target of \c a to \c n
+		    /// This function changes the target node of the given arc \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.
+		    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
 		    ///arc remain valid, however \c InArcIt iterators 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 node of an arc
-		    /// Change the source of \c a to \c n
+		    /// This function changes the source node of the given arc \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.
+		    ///\note \c InArcIt iterators referencing the changed arc remain
 		    ///valid, however \c ArcIt and \c OutArcIt iterators 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.
+		    /// Reverse 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.
+		    /// This function reverses the direction of the given arc.
 		    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
 		    ///the changed arc 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);
 		    void reverseArc(Arc a) {
 		      Node t=target(a);
 		      changeTarget(a,source(a));
 		      changeSource(a,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.
+		    ///This function contracts the given two nodes.
 		    ///Node \c v is removed, but instead of deleting its
 		    ///incident arcs, they are joined to node \c u.
 		    ///If the last parameter \c r is \c true (this is the default value),
 		    ///then the newly created loops are 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.
+		    ///\note The moved arcs are joined to node \c u using changeSource()
 		    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
 		    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
 		    ///iterators are invalidated for the incomming arcs of \c v.
 		    ///Moreover all iterators referencing node \c v or the removed
 		    ///loops are also invalidated. Other iterators remain valid.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
-		    void contract(Node a, Node b, bool r = true)
+		    void contract(Node u, Node v, bool r = true)
+		    {
-		      for(OutArcIt e(*this,b);e!=INVALID;) {
+		      for(OutArcIt e(*this,v);e!=INVALID;) {
 		        OutArcIt f=e;
 		        ++f;
 		        if(r && target(e)==a) erase(e);
 		        else changeSource(e,a);
 		        if(r && target(e)==u) erase(e);
 		        else changeSource(e,u);
 		        e=f;
+		      }
-		      for(InArcIt e(*this,b);e!=INVALID;) {
+		      for(InArcIt e(*this,v);e!=INVALID;) {
 		        InArcIt f=e;
 		        ++f;
 		        if(r && source(e)==a) erase(e);
 		        else changeTarget(e,a);
 		        if(r && source(e)==u) erase(e);
 		        else changeTarget(e,u);
 		        e=f;
+		      }
-		      erase(b);
+		      erase(v);
+		    }
 		    ///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.
 		    ///This function splits the given node. First, a new node is added
 		    ///to the digraph, then the source of each outgoing arc of node \c n
 		    ///is moved to this new node.
 		    ///If the second parameter \c connect is \c true (this is the default
 		    ///value), then a new arc from node \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.
+		    ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing
 		    ///arcs of node \c n are invalidated. Other iterators remain valid.
 		    ///
-		    ///\warning This functionality cannot be used in conjunction with the
+		    ///\warning This functionality cannot be used together 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.
+		    ///This function splits the given arc. First, a new node \c v is
 		    ///added to the digraph, then the target node of the original arc
 		    ///is set to \c v. Finally, an arc from \c v to the original target
 		    ///is added.
 		    ///\return The newly created node.
 		    ///
-		    ///\return The newly created node.
+		    ///\note \c InArcIt iterators referencing the original arc are
 		    ///invalidated. Other iterators remain valid.
 		    ///
 		    ///\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;
+		    Node split(Arc a) {
 		      Node v = addNode();
 		      addArc(v,target(a));
 		      changeTarget(a,v);
 		      return v;
+		    }
 		    ///Clear the digraph.
 		    ///This function erases all nodes and arcs from the digraph.
 		    ///
 		    void clear() {
 		      Parent::clear();
+		    }
 		    /// Reserve memory for nodes.
 		    /// Using this function, it is possible to avoid superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be 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 superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be 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); };
 		    /// \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
 		    /// \note After a state is restored, you cannot restore a later state,
 		    /// i.e. you cannot add the removed nodes and arcs again using
 		    /// another Snapshot instance.
 		    ///
 		    /// \warning Node and arc deletions and other modifications (e.g.
 		    /// reversing, contracting, splitting arcs or nodes) cannot be
 		    /// restored. These events invalidate the snapshot.
 		    /// However the arcs and nodes that were added to the digraph after
 		    /// making the current snapshot can be removed without invalidating it.
 		    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().
+		      /// You have to call save() to actually make a snapshot.
 		      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)
+		      /// This constructor immediately makes a snapshot of the given digraph.
 		      Snapshot(ListDigraph &gr)
 		        : node_observer_proxy(*this),
 		          arc_observer_proxy(*this) {
-		        attach(_digraph);
+		        attach(gr);
+		      }
 		      /// \brief Make a snapshot.
 		      ///
 		      /// Make a snapshot of the digraph.
 		      ///
-		      /// This function can be called more than once. In case of a repeated
+		      /// This function makes a snapshot of the given digraph.
 		      /// It 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) {
 		      void save(ListDigraph &gr) {
 		        if (attached()) {
 		          detach();
 		          clear();
+		        }
-		        attach(_digraph);
+		        attach(gr);
+		      }
 		      /// \brief Undo the changes until the last snapshot.
 		      //
 		      /// Undo the changes until the last snapshot created by save().
 		      ///
 		      /// This function undos the changes until the last snapshot
 		      /// created by save() or Snapshot(ListDigraph&).
 		      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.
+		      /// \brief Returns \c true if the snapshot is valid.
 		      ///
-		      /// Gives back true when the snapshot is valid.
+		      /// This function returns \c true if 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 Graph;
 		    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;
+		      }
 		      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;
+		      }
+		    }
@@ -1039,512 +1040,518 @@
 		      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
 		  ///\ref ListGraph is a versatile and fast undirected graph
 		  ///implementation based on 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
+		  ///This type fully conforms to the \ref concepts::Graph "Graph concept"
 		  ///and it also provides several useful additional functionalities.
 		  ///Most of its member functions and nested classes are documented
 		  ///only in the concept class.
 		  ///
 		  ///\sa concepts::Graph
+		  ///\sa ListDigraph
 		  class ListGraph : public ExtendedListGraphBase {
 		    typedef ExtendedListGraphBase Parent;
 		  private:
 		    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
 		    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
 		    ///
 		    /// Graphs are \e not copy constructible. Use GraphCopy 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.
+		    /// \brief Assignment of a graph to another one is \e not allowed.
 		    /// Use GraphCopy instead.
 		    void operator=(const ListGraph &) {}
 		  public:
 		    /// Constructor
 		    /// Constructor.
 		    ///
 		    ListGraph() {}
 		    typedef Parent::OutArcIt IncEdgeIt;
 		    /// \brief Add a new node to the graph.
 		    ///
-		    /// Add a new node to the graph.
+		    /// This function adds 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.
 		    /// This function adds a new edge to the graph between nodes
 		    /// \c u and \c v with inherent orientation from node \c u to
 		    /// node \c v.
 		    /// \return The new edge.
 		    Edge addEdge(const Node& s, const Node& t) {
 		      return Parent::addEdge(s, t);
 		    Edge addEdge(Node u, Node v) {
 		      return Parent::addEdge(u, v);
+		    }
-		    /// \brief Erase a node from the graph.
 		    ///\brief Erase a node from the graph.
 		    ///
-		    /// Erase a node from the graph.
+		    /// This function erases the given node from the graph.
 		    void erase(Node n) { Parent::erase(n); }
 		    ///\brief Erase an edge 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); }
+		    /// This function erases the given edge from the graph.
 		    void erase(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.
 		    /// This function gives back \c true if the given node is valid,
 		    /// i.e. 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
 		    /// \warning A removed node could become valid again if new nodes are
 		    /// added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// Edge validity check
 		    /// This function gives back \c true if the given edge is valid,
 		    /// i.e. it is a real edge of the graph.
 		    ///
 		    /// \warning A removed edge could become valid again if new edges are
 		    /// added to the graph.
 		    bool valid(Edge e) const { return Parent::valid(e); }
 		    /// Arc validity check
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    /// This function gives back \c true if the given arc is valid,
 		    /// i.e. 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
 		    /// \warning A removed arc could become valid again 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.
 		    /// \brief Change the first node of an edge.
 		    ///
 		    /// \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 first node of the given edge \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.
 		    ///\note \c EdgeIt and \c ArcIt iterators referencing the
 		    ///changed edge are invalidated and all other iterators whose
 		    ///base node is the changed node are 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
+		    /// \brief Change the second node of an edge.
 		    ///
-		    /// This function changes the end \c v of \c e to \c n.
+		    /// This function changes the second node of the given edge \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.
+		    ///\note \c EdgeIt iterators referencing the changed edge remain
 		    ///valid, however \c ArcIt iterators referencing the changed edge and
 		    ///all other iterators whose base node is the changed node are also
 		    ///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.
+		    /// This function contracts the given two nodes.
 		    /// Node \c b is removed, but instead of deleting
 		    /// its incident edges, they are joined to node \c a.
 		    /// If the last parameter \c r is \c true (this is the default value),
 		    /// then the newly created loops are removed.
 		    ///
 		    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
 		    /// valid.
 		    /// \note The moved edges are joined to node \c a using changeU()
 		    /// or changeV(), thus all edge and arc iterators whose base node is
 		    /// \c b are invalidated.
 		    /// Moreover all iterators referencing node \c b or the removed
 		    /// loops are also invalidated. Other iterators 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);
+		    }
 		    ///Clear the graph.
 		    ///This function erases all nodes and arcs from the graph.
 		    ///
 		    void clear() {
 		      Parent::clear();
+		    }
 		    /// \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.
+		    /// \note After a state is restored, you cannot restore a later state,
 		    /// i.e. you cannot add the removed nodes and edges again using
 		    /// another Snapshot instance.
 		    ///
 		    /// \warning Node and edge deletions and other modifications
 		    /// (e.g. changing the end-nodes of edges or contracting nodes)
 		    /// cannot be restored. These events invalidate the snapshot.
 		    /// However the edges and nodes that were added to the graph after
 		    /// making the current snapshot can be removed without invalidating it.
 		    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 EdgeObserverProxy : public EdgeNotifier::ObserverBase {
 		      public:
 		        EdgeObserverProxy(Snapshot& _snapshot)
 		          : snapshot(_snapshot) {}
 		        using EdgeNotifier::ObserverBase::attach;
 		        using EdgeNotifier::ObserverBase::detach;
 		        using EdgeNotifier::ObserverBase::attached;
 		      protected:
 		        virtual void add(const Edge& edge) {
 		          snapshot.addEdge(edge);
+		        }
 		        virtual void add(const std::vector<Edge>& edges) {
 		          for (int i = edges.size() - 1; i >= 0; ++i) {
 		            snapshot.addEdge(edges[i]);
+		          }
+		        }
 		        virtual void erase(const Edge& edge) {
 		          snapshot.eraseEdge(edge);
+		        }
 		        virtual void erase(const std::vector<Edge>& edges) {
 		          for (int i = 0; i < int(edges.size()); ++i) {
 		            snapshot.eraseEdge(edges[i]);
+		          }
+		        }
 		        virtual void build() {
 		          Edge edge;
 		          std::vector<Edge> edges;
 		          for (notifier()->first(edge); edge != INVALID;
 		               notifier()->next(edge)) {
 		            edges.push_back(edge);
+		          }
 		          for (int i = edges.size() - 1; i >= 0; --i) {
 		            snapshot.addEdge(edges[i]);
+		          }
+		        }
 		        virtual void clear() {
 		          Edge edge;
 		          for (notifier()->first(edge); edge != INVALID;
 		               notifier()->next(edge)) {
 		            snapshot.eraseEdge(edge);
+		          }
+		        }
 		        Snapshot& snapshot;
 		      };
 		      ListGraph *graph;
 		      NodeObserverProxy node_observer_proxy;
 		      EdgeObserverProxy edge_observer_proxy;
 		      std::list<Node> added_nodes;
 		      std::list<Edge> added_edges;
 		      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();
 		          edge_observer_proxy.detach();
 		          throw NodeNotifier::ImmediateDetach();
 		        } else {
 		          added_nodes.erase(it);
+		        }
+		      }
 		      void addEdge(const Edge& edge) {
 		        added_edges.push_front(edge);
+		      }
 		      void eraseEdge(const Edge& edge) {
 		        std::list<Edge>::iterator it =
 		          std::find(added_edges.begin(), added_edges.end(), edge);
 		        if (it == added_edges.end()) {
 		          clear();
 		          node_observer_proxy.detach();
 		          throw EdgeNotifier::ImmediateDetach();
 		        } else {
 		          added_edges.erase(it);
+		        }
+		      }
 		      void attach(ListGraph &_graph) {
 		        graph = &_graph;
 		        node_observer_proxy.attach(graph->notifier(Node()));
 		        edge_observer_proxy.attach(graph->notifier(Edge()));
+		      }
 		      void detach() {
 		        node_observer_proxy.detach();
 		        edge_observer_proxy.detach();
+		      }
 		      bool attached() const {
 		        return node_observer_proxy.attached();
+		      }
 		      void clear() {
 		        added_nodes.clear();
 		        added_edges.clear();
+		      }
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
-		      /// To actually make a snapshot you must call save().
+		      /// You have to call save() to actually make a snapshot.
 		      Snapshot()
 		        : graph(0), node_observer_proxy(*this),
 		          edge_observer_proxy(*this) {}
 		      /// \brief Constructor that immediately makes a snapshot.
 		      ///
 		      /// This constructor immediately makes a snapshot of the graph.
 		      /// \param _graph The graph we make a snapshot of.
-		      Snapshot(ListGraph &_graph)
+		      /// This constructor immediately makes a snapshot of the given graph.
 		      Snapshot(ListGraph &gr)
 		        : node_observer_proxy(*this),
 		          edge_observer_proxy(*this) {
-		        attach(_graph);
+		        attach(gr);
+		      }
 		      /// \brief Make a snapshot.
 		      ///
 		      /// Make a snapshot of the graph.
 		      ///
-		      /// This function can be called more than once. In case of a repeated
+		      /// This function makes a snapshot of the given graph.
 		      /// It can be called more than once. In case of a repeated
 		      /// call, the previous snapshot gets lost.
 		      /// \param _graph The graph we make the snapshot of.
 		      void save(ListGraph &_graph) {
 		      void save(ListGraph &gr) {
 		        if (attached()) {
 		          detach();
 		          clear();
+		        }
-		        attach(_graph);
+		        attach(gr);
+		      }
 		      /// \brief Undo the changes until the last snapshot.
 		      //
 		      /// Undo the changes until the last snapshot created by save().
 		      ///
 		      /// This function undos the changes until the last snapshot
 		      /// created by save() or Snapshot(ListGraph&).
 		      void restore() {
 		        detach();
 		        for(std::list<Edge>::iterator it = added_edges.begin();
 		            it != added_edges.end(); ++it) {
 		          graph->erase(*it);
+		        }
 		        for(std::list<Node>::iterator it = added_nodes.begin();
 		            it != added_nodes.end(); ++it) {
 		          graph->erase(*it);
+		        }
 		        clear();
+		      }
-		      /// \brief Gives back true when the snapshot is valid.
+		      /// \brief Returns \c true if the snapshot is valid.
 		      ///
-		      /// Gives back true when the snapshot is valid.
+		      /// This function returns \c true if the snapshot is valid.
 		      bool valid() const {
 		        return attached();
+		      }
 		    };
 		  };
 		  /// @}
 		} //namespace lemon
 		#endif

lemon/smart_graph.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_SMART_GRAPH_H
 		#define LEMON_SMART_GRAPH_H
 		///\ingroup graphs
 		///\file
 		///\brief SmartDigraph and SmartGraph classes.
 		#include <vector>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/bits/graph_extender.h>
 		namespace lemon {
 		  class SmartDigraph;
 		  ///Base of SmartDigraph
 		  ///Base of SmartDigraph
 		  ///
 		  class SmartDigraphBase {
 		  protected:
 		    struct NodeT
+		    {
 		      int first_in, first_out;
 		      NodeT() {}
 		    };
 		    struct ArcT
+		    {
 		      int target, source, next_in, next_out;
 		      ArcT() {}
 		    };
 		    std::vector<NodeT> nodes;
 		    std::vector<ArcT> arcs;
 		  public:
 		    typedef SmartDigraphBase Digraph;
 		    class Node;
 		    class Arc;
 		  public:
 		    SmartDigraphBase() : nodes(), arcs() { }
 		    SmartDigraphBase(const SmartDigraphBase &_g)
 		      : nodes(_g.nodes), arcs(_g.arcs) { }
 		    typedef True NodeNumTag;
 		    typedef True ArcNumTag;
 		    int nodeNum() const { return nodes.size(); }
 		    int arcNum() const { return arcs.size(); }
 		    int maxNodeId() const { return nodes.size()-1; }
 		    int maxArcId() const { return arcs.size()-1; }
 		    Node addNode() {
 		      int n = nodes.size();
 		      nodes.push_back(NodeT());
 		      nodes[n].first_in = -1;
 		      nodes[n].first_out = -1;
 		      return Node(n);
+		    }
 		    Arc addArc(Node u, Node v) {
 		      int n = arcs.size();
 		      arcs.push_back(ArcT());
 		      arcs[n].source = u._id;
 		      arcs[n].target = v._id;
 		      arcs[n].next_out = nodes[u._id].first_out;
 		      arcs[n].next_in = nodes[v._id].first_in;
 		      nodes[u._id].first_out = nodes[v._id].first_in = n;
 		      return Arc(n);
+		    }
 		    void clear() {
 		      arcs.clear();
 		      nodes.clear();
+		    }
 		    Node source(Arc a) const { return Node(arcs[a._id].source); }
 		    Node target(Arc a) const { return Node(arcs[a._id].target); }
 		    static int id(Node v) { return v._id; }
 		    static int id(Arc a) { return a._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());
+		    }
 		    bool valid(Arc a) const {
 		      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
+		    }
 		    class Node {
 		      friend class SmartDigraphBase;
 		      friend class SmartDigraph;
 		    protected:
 		      int _id;
 		      explicit Node(int id) : _id(id) {}
 		    public:
 		      Node() {}
 		      Node (Invalid) : _id(-1) {}
 		      bool operator==(const Node i) const {return _id == i._id;}
 		      bool operator!=(const Node i) const {return _id != i._id;}
 		      bool operator<(const Node i) const {return _id < i._id;}
 		    };
 		    class Arc {
 		      friend class SmartDigraphBase;
 		      friend class SmartDigraph;
 		    protected:
 		      int _id;
 		      explicit Arc(int id) : _id(id) {}
 		    public:
 		      Arc() { }
 		      Arc (Invalid) : _id(-1) {}
 		      bool operator==(const Arc i) const {return _id == i._id;}
 		      bool operator!=(const Arc i) const {return _id != i._id;}
 		      bool operator<(const Arc i) const {return _id < i._id;}
 		    };
 		    void first(Node& node) const {
 		      node._id = nodes.size() - 1;
+		    }
 		    static void next(Node& node) {
 		      --node._id;
+		    }
 		    void first(Arc& arc) const {
 		      arc._id = arcs.size() - 1;
+		    }
 		    static void next(Arc& arc) {
 		      --arc._id;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      arc._id = nodes[node._id].first_out;
+		    }
 		    void nextOut(Arc& arc) const {
 		      arc._id = arcs[arc._id].next_out;
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      arc._id = nodes[node._id].first_in;
+		    }
 		    void nextIn(Arc& arc) const {
 		      arc._id = arcs[arc._id].next_in;
+		    }
 		  };
 		  typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
 		  ///\ingroup graphs
 		  ///
 		  ///\brief A smart directed graph class.
 		  ///
 		  ///This is a simple and fast digraph implementation.
 		  ///It is also quite memory efficient, but at the price
 		  ///that <b> it does support only limited (only stack-like)
 		  ///node and arc deletions</b>.
-		  ///It fully conforms to the \ref concepts::Digraph "Digraph concept".
+		  ///\ref SmartDigraph is a simple and fast digraph implementation.
 		  ///It is also quite memory efficient but at the price
 		  ///that it does not support node and arc deletion
 		  ///(except for the Snapshot feature).
 		  ///
-		  ///\sa concepts::Digraph.
+		  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
 		  ///and it also provides some additional functionalities.
 		  ///Most of its member functions and nested classes are documented
 		  ///only in the concept class.
 		  ///
 		  ///\sa concepts::Digraph
 		  ///\sa SmartGraph
 		  class SmartDigraph : public ExtendedSmartDigraphBase {
 		    typedef ExtendedSmartDigraphBase Parent;
 		  private:
 		    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
 		    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
 		    ///
+		    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
 		    SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
 		    ///\brief Assignment of SmartDigraph to another one is \e not allowed.
 		    ///Use DigraphCopy() instead.
 		    ///Assignment of SmartDigraph to another one is \e not allowed.
-		    ///Use DigraphCopy() instead.
+		    /// \brief Assignment of a digraph to another one is \e not allowed.
 		    /// Use DigraphCopy instead.
 		    void operator=(const SmartDigraph &) {}
 		  public:
 		    /// Constructor
 		    /// Constructor.
 		    ///
 		    SmartDigraph() {};
 		    ///Add a new node to the digraph.
 		    /// Add a new node to the digraph.
 		    /// \return The new node.
 		    ///This function adds 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
+		    ///This function adds 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) {
 		    Arc addArc(Node s, Node t) {
 		      return Parent::addArc(s, t);
+		    }
 		    /// \brief Using this it is possible to avoid the superfluous memory
 		    /// allocation.
 		    /// Using this 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); };
 		    /// \brief Using this it is possible to avoid the superfluous memory
 		    /// allocation.
 		    /// Using this 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); };
 		    /// \brief Node validity check
 		    ///
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    /// This function gives back \c true if the given node is valid,
 		    /// i.e. it is a real node of the digraph.
 		    ///
 		    /// \warning A removed node (using Snapshot) could become valid again
-		    /// when new nodes are added to the graph.
+		    /// if new nodes are added to the digraph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// \brief Arc validity check
 		    ///
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    /// This function gives back \c true if the given arc is valid,
 		    /// i.e. it is a real arc of the digraph.
 		    ///
 		    /// \warning A removed arc (using Snapshot) could become valid again
-		    /// when new arcs are added to the graph.
+		    /// if new arcs are added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    ///Clear the digraph.
 		    ///Erase all the nodes and arcs from the digraph.
 		    ///
 		    void clear() {
 		      Parent::clear();
+		    }
 		    ///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.
 		    ///This function splits the given node. First, a new node is added
 		    ///to the digraph, then the source of each outgoing arc of node \c n
 		    ///is moved to this new node.
 		    ///If the second parameter \c connect is \c true (this is the default
 		    ///value), then a new arc from node \c n to the newly created node
 		    ///is also added.
 		    ///\return The newly created node.
 		    ///
 		    ///\note The <tt>Arc</tt>s
 		    ///referencing a moved arc remain
 		    ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
 		    ///may be invalidated.
 		    ///\note All iterators remain valid.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    Node split(Node n, bool connect = true)
+		    {
 		      Node b = addNode();
 		      nodes[b._id].first_out=nodes[n._id].first_out;
 		      nodes[n._id].first_out=-1;
 		      for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
 		        arcs[i].source=b._id;
+		      }
 		      if(connect) addArc(n,b);
 		      return b;
+		    }
 		    ///Clear the digraph.
 		    ///This function erases all nodes and arcs from the digraph.
 		    ///
 		    void clear() {
 		      Parent::clear();
+		    }
 		    /// Reserve memory for nodes.
 		    /// Using this function, it is possible to avoid superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be 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 superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be 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); };
 		  public:
 		    class Snapshot;
 		  protected:
 		    void restoreSnapshot(const Snapshot &s)
+		    {
 		      while(s.arc_num<arcs.size()) {
 		        Arc arc = arcFromId(arcs.size()-1);
 		        Parent::notifier(Arc()).erase(arc);
 		        nodes[arcs.back().source].first_out=arcs.back().next_out;
 		        nodes[arcs.back().target].first_in=arcs.back().next_in;
 		        arcs.pop_back();
+		      }
 		      while(s.node_num<nodes.size()) {
 		        Node node = nodeFromId(nodes.size()-1);
 		        Parent::notifier(Node()).erase(node);
 		        nodes.pop_back();
+		      }
+		    }
 		  public:
-		    ///Class to make a snapshot of the digraph and to restrore to it later.
+		    ///Class to make a snapshot of the digraph and to restore it later.
-		    ///Class to make a snapshot of the digraph and to restrore to it later.
+		    ///Class to make a snapshot of the digraph and to restore it later.
 		    ///
 		    ///The newly added nodes and arcs can be removed using the
 		    ///restore() function.
 		    ///\note After you restore a state, you cannot restore
 		    ///a later state, in other word you cannot add again the arcs deleted
 		    ///by restore() using another one Snapshot instance.
 		    ///restore() function. This is the only way for deleting nodes and/or
 		    ///arcs from a SmartDigraph structure.
 		    ///
 		    ///\warning If you do not use correctly the snapshot that can cause
 		    ///either broken program, invalid state of the digraph, valid but
 		    ///not the restored digraph or no change. Because the runtime performance
 		    ///the validity of the snapshot is not stored.
 		    ///\note After a state is restored, you cannot restore a later state,
 		    ///i.e. you cannot add the removed nodes and arcs again using
 		    ///another Snapshot instance.
 		    ///
 		    ///\warning Node splitting cannot be restored.
 		    ///\warning The validity of the snapshot is not stored due to
 		    ///performance reasons. If you do not use the snapshot correctly,
 		    ///it can cause broken program, invalid or not restored state of
 		    ///the digraph or no change.
 		    class Snapshot
+		    {
 		      SmartDigraph *_graph;
 		    protected:
 		      friend class SmartDigraph;
 		      unsigned int node_num;
 		      unsigned int arc_num;
 		    public:
 		      ///Default constructor.
 		      ///Default constructor.
 		      ///To actually make a snapshot you must call save().
 		      ///
 		      ///You have to call save() to actually make a snapshot.
 		      Snapshot() : _graph(0) {}
 		      ///Constructor that immediately makes a snapshot
 		      ///This constructor immediately makes a snapshot of the digraph.
 		      ///\param graph The digraph we make a snapshot of.
-		      Snapshot(SmartDigraph &graph) : _graph(&graph) {
+		      ///This constructor immediately makes a snapshot of the given digraph.
 		      ///
 		      Snapshot(SmartDigraph &gr) : _graph(&gr) {
 		        node_num=_graph->nodes.size();
 		        arc_num=_graph->arcs.size();
+		      }
 		      ///Make a snapshot.
 		      ///Make a snapshot of the digraph.
 		      ///
-		      ///This function can be called more than once. In case of a repeated
+		      ///This function makes a snapshot of the given digraph.
 		      ///It can be called more than once. In case of a repeated
 		      ///call, the previous snapshot gets lost.
 		      ///\param graph The digraph we make the snapshot of.
 		      void save(SmartDigraph &graph)
+		      {
 		        _graph=&graph;
 		      void save(SmartDigraph &gr) {
 		        _graph=&gr;
 		        node_num=_graph->nodes.size();
 		        arc_num=_graph->arcs.size();
+		      }
 		      ///Undo the changes until a snapshot.
 		      ///Undo the changes until a snapshot created by save().
 		      ///
 		      ///\note After you restored a state, you cannot restore
 		      ///a later state, in other word you cannot add again the arcs deleted
-		      ///by restore().
+		      ///This function undos the changes until the last snapshot
 		      ///created by save() or Snapshot(SmartDigraph&).
 		      void restore()
+		      {
 		        _graph->restoreSnapshot(*this);
+		      }
 		    };
 		  };
 		  class SmartGraphBase {
 		  protected:
 		    struct NodeT {
 		      int first_out;
 		    };
 		    struct ArcT {
 		      int target;
 		      int next_out;
 		    };
 		    std::vector<NodeT> nodes;
 		    std::vector<ArcT> arcs;
 		    int first_free_arc;
 		  public:
 		    typedef SmartGraphBase Graph;
 		    class Node;
 		    class Arc;
 		    class Edge;
 		    class Node {
 		      friend class SmartGraphBase;
 		    protected:
 		      int _id;
 		      explicit Node(int id) { _id = id;}
 		    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 SmartGraphBase;
 		    protected:
 		      int _id;
 		      explicit Edge(int id) { _id = id;}
 		    public:
 		      Edge() {}
 		      Edge (Invalid) { _id = -1; }
 		      bool operator==(const Edge& arc) const {return _id == arc._id;}
 		      bool operator!=(const Edge& arc) const {return _id != arc._id;}
 		      bool operator<(const Edge& arc) const {return _id < arc._id;}
 		    };
 		    class Arc {
 		      friend class SmartGraphBase;
 		    protected:
 		      int _id;
 		      explicit Arc(int id) { _id = id;}
 		    public:
 		      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;}
 		    };
 		    SmartGraphBase()
 		      : nodes(), arcs() {}
 		    typedef True NodeNumTag;
 		    typedef True EdgeNumTag;
 		    typedef True ArcNumTag;
 		    int nodeNum() const { return nodes.size(); }
 		    int edgeNum() const { return arcs.size() / 2; }
 		    int arcNum() const { return arcs.size(); }
 		    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 = nodes.size() - 1;
+		    }
 		    void next(Node& node) const {
 		      --node._id;
+		    }
 		    void first(Arc& arc) const {
 		      arc._id = arcs.size() - 1;
+		    }
 		    void next(Arc& arc) const {
 		      --arc._id;
+		    }
 		    void first(Edge& arc) const {
 		      arc._id = arcs.size() / 2 - 1;
+		    }
 		    void next(Edge& arc) const {
 		      --arc._id;
+		    }
 		    void firstOut(Arc &arc, const Node& v) const {
 		      arc._id = nodes[v._id].first_out;
+		    }
 		    void nextOut(Arc &arc) const {
 		      arc._id = arcs[arc._id].next_out;
+		    }
 		    void firstIn(Arc &arc, const Node& v) const {
 		      arc._id = ((nodes[v._id].first_out) ^ 1);
 		      if (arc._id == -2) arc._id = -1;
+		    }
 		    void nextIn(Arc &arc) const {
 		      arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
 		      if (arc._id == -2) arc._id = -1;
+		    }
 		    void firstInc(Edge &arc, bool& d, const Node& v) const {
 		      int de = nodes[v._id].first_out;
 		      if (de != -1) {
 		        arc._id = de / 2;
 		        d = ((de & 1) == 1);
 		      } else {
 		        arc._id = -1;
 		        d = true;
+		      }
+		    }
 		    void nextInc(Edge &arc, bool& d) const {
 		      int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
 		      if (de != -1) {
 		        arc._id = de / 2;
 		        d = ((de & 1) == 1);
 		      } else {
 		        arc._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());
+		    }
 		    bool valid(Arc a) const {
 		      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
+		    }
 		    bool valid(Edge e) const {
 		      return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
+		    }
 		    Node addNode() {
 		      int n = nodes.size();
 		      nodes.push_back(NodeT());
 		      nodes[n].first_out = -1;
 		      return Node(n);
+		    }
 		    Edge addEdge(Node u, Node v) {
 		      int n = arcs.size();
 		      arcs.push_back(ArcT());
 		      arcs.push_back(ArcT());
 		      arcs[n].target = u._id;
 		      arcs[n | 1].target = v._id;
 		      arcs[n].next_out = nodes[v._id].first_out;
 		      nodes[v._id].first_out = n;
 		      arcs[n | 1].next_out = nodes[u._id].first_out;
 		      nodes[u._id].first_out = (n | 1);
 		      return Edge(n / 2);
+		    }
 		    void clear() {
 		      arcs.clear();
 		      nodes.clear();
+		    }
 		  };
 		  typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
 		  /// \ingroup graphs
 		  ///
 		  /// \brief A smart undirected graph class.
 		  ///
 		  /// This is a simple and fast graph implementation.
 		  /// It is also quite memory efficient, but at the price
 		  /// that <b> it does support only limited (only stack-like)
 		  /// node and arc deletions</b>.
-		  /// It fully conforms to the \ref concepts::Graph "Graph concept".
+		  /// \ref SmartGraph is a simple and fast graph implementation.
 		  /// It is also quite memory efficient but at the price
 		  /// that it does not support node and edge deletion
 		  /// (except for the Snapshot feature).
 		  ///
-		  /// \sa concepts::Graph.
+		  /// This type fully conforms to the \ref concepts::Graph "Graph concept"
 		  /// and it also provides some additional functionalities.
 		  /// Most of its member functions and nested classes are documented
 		  /// only in the concept class.
 		  ///
 		  /// \sa concepts::Graph
 		  /// \sa SmartDigraph
 		  class SmartGraph : public ExtendedSmartGraphBase {
 		    typedef ExtendedSmartGraphBase Parent;
 		  private:
 		    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
 		    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
 		    ///
+		    /// Graphs are \e not copy constructible. Use GraphCopy instead.
 		    SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
 		    ///\brief Assignment of SmartGraph to another one is \e not allowed.
 		    ///Use GraphCopy() instead.
 		    ///Assignment of SmartGraph to another one is \e not allowed.
 		    ///Use GraphCopy() instead.
 		    /// \brief Assignment of a graph to another one is \e not allowed.
 		    /// Use GraphCopy instead.
 		    void operator=(const SmartGraph &) {}
 		  public:
 		    /// Constructor
 		    /// Constructor.
 		    ///
 		    SmartGraph() {}
 		    ///Add a new node to the graph.
 		    /// Add a new node to the graph.
+		    /// \brief Add a new node to the graph.
 		    ///
 		    /// This function adds a new node to the graph.
 		    /// \return The new node.
 		    Node addNode() { return Parent::addNode(); }
 		    ///Add a new edge to the graph.
 		    ///Add a new edge to the graph with node \c s
 		    ///and \c t.
 		    ///\return The new edge.
 		    Edge addEdge(const Node& s, const Node& t) {
-		      return Parent::addEdge(s, t);
+		    /// \brief Add a new edge to the graph.
 		    ///
 		    /// This function adds a new edge to the graph between nodes
 		    /// \c u and \c v with inherent orientation from node \c u to
 		    /// node \c v.
 		    /// \return The new edge.
 		    Edge addEdge(Node u, Node v) {
 		      return Parent::addEdge(u, v);
+		    }
 		    /// \brief Node validity check
 		    ///
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    /// This function gives back \c true if the given node is valid,
 		    /// i.e. it is a real node of the graph.
 		    ///
 		    /// \warning A removed node (using Snapshot) could become valid again
-		    /// when new nodes are added to the graph.
+		    /// if new nodes are added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// \brief Edge validity check
 		    ///
 		    /// This function gives back \c true if the given edge is valid,
 		    /// i.e. it is a real edge of the graph.
 		    ///
 		    /// \warning A removed edge (using Snapshot) could become valid again
 		    /// if new edges are added to the graph.
 		    bool valid(Edge e) const { return Parent::valid(e); }
 		    /// \brief Arc validity check
 		    ///
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    /// This function gives back \c true if the given arc is valid,
 		    /// i.e. it is a real arc of the graph.
 		    ///
 		    /// \warning A removed arc (using Snapshot) could become valid again
-		    /// when new edges are added to the graph.
+		    /// if new edges are added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    /// \brief Edge validity check
 		    ///
 		    /// This function gives back true if the given edge is valid,
 		    /// ie. it is a real edge of the graph.
 		    ///
 		    /// \warning A removed edge (using Snapshot) could become valid again
 		    /// when new edges are added to the graph.
 		    bool valid(Edge e) const { return Parent::valid(e); }
 		    ///Clear the graph.
-		    ///Erase all the nodes and edges from the graph.
+		    ///This function erases all nodes and arcs from the graph.
 		    ///
 		    void clear() {
 		      Parent::clear();
+		    }
 		  public:
 		    class Snapshot;
 		  protected:
 		    void saveSnapshot(Snapshot &s)
+		    {
 		      s._graph = this;
 		      s.node_num = nodes.size();
 		      s.arc_num = arcs.size();
+		    }
 		    void restoreSnapshot(const Snapshot &s)
+		    {
 		      while(s.arc_num<arcs.size()) {
 		        int n=arcs.size()-1;
 		        Edge arc=edgeFromId(n/2);
 		        Parent::notifier(Edge()).erase(arc);
 		        std::vector<Arc> dir;
 		        dir.push_back(arcFromId(n));
 		        dir.push_back(arcFromId(n-1));
 		        Parent::notifier(Arc()).erase(dir);
 		        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
 		        nodes[arcs[n].target].first_out=arcs[n-1].next_out;
 		        arcs.pop_back();
 		        arcs.pop_back();
+		      }
 		      while(s.node_num<nodes.size()) {
 		        int n=nodes.size()-1;
 		        Node node = nodeFromId(n);
 		        Parent::notifier(Node()).erase(node);
 		        nodes.pop_back();
+		      }
+		    }
 		  public:
-		    ///Class to make a snapshot of the digraph and to restrore to it later.
+		    ///Class to make a snapshot of the graph and to restore it later.
-		    ///Class to make a snapshot of the digraph and to restrore to it later.
+		    ///Class to make a snapshot of the graph and to restore it later.
 		    ///
 		    ///The newly added nodes and arcs can be removed using the
 		    ///restore() function.
 		    ///The newly added nodes and edges can be removed using the
 		    ///restore() function. This is the only way for deleting nodes and/or
 		    ///edges from a SmartGraph structure.
 		    ///
 		    ///\note After you restore a state, you cannot restore
 		    ///a later state, in other word you cannot add again the arcs deleted
-		    ///by restore() using another one Snapshot instance.
+		    ///\note After a state is restored, you cannot restore a later state,
 		    ///i.e. you cannot add the removed nodes and edges again using
 		    ///another Snapshot instance.
 		    ///
 		    ///\warning If you do not use correctly the snapshot that can cause
 		    ///either broken program, invalid state of the digraph, valid but
 		    ///not the restored digraph or no change. Because the runtime performance
 		    ///the validity of the snapshot is not stored.
 		    ///\warning The validity of the snapshot is not stored due to
 		    ///performance reasons. If you do not use the snapshot correctly,
 		    ///it can cause broken program, invalid or not restored state of
 		    ///the graph or no change.
 		    class Snapshot
+		    {
 		      SmartGraph *_graph;
 		    protected:
 		      friend class SmartGraph;
 		      unsigned int node_num;
 		      unsigned int arc_num;
 		    public:
 		      ///Default constructor.
 		      ///Default constructor.
 		      ///To actually make a snapshot you must call save().
 		      ///
 		      ///You have to call save() to actually make a snapshot.
 		      Snapshot() : _graph(0) {}
 		      ///Constructor that immediately makes a snapshot
 		      ///This constructor immediately makes a snapshot of the digraph.
 		      ///\param graph The digraph we make a snapshot of.
 		      Snapshot(SmartGraph &graph) {
 		        graph.saveSnapshot(*this);
 		      /// This constructor immediately makes a snapshot of the given graph.
 		      ///
 		      Snapshot(SmartGraph &gr) {
 		        gr.saveSnapshot(*this);
+		      }
 		      ///Make a snapshot.
 		      ///Make a snapshot of the graph.
 		      ///
-		      ///This function can be called more than once. In case of a repeated
+		      ///This function makes a snapshot of the given graph.
 		      ///It can be called more than once. In case of a repeated
 		      ///call, the previous snapshot gets lost.
 		      ///\param graph The digraph we make the snapshot of.
 		      void save(SmartGraph &graph)
 		      void save(SmartGraph &gr)
+		      {
-		        graph.saveSnapshot(*this);
+		        gr.saveSnapshot(*this);
+		      }
-		      ///Undo the changes until a snapshot.
+		      ///Undo the changes until the last snapshot.
 		      ///Undo the changes until a snapshot created by save().
 		      ///
 		      ///\note After you restored a state, you cannot restore
 		      ///a later state, in other word you cannot add again the arcs deleted
-		      ///by restore().
+		      ///This function undos the changes until the last snapshot
 		      ///created by save() or Snapshot(SmartGraph&).
 		      void restore()
+		      {
 		        _graph->restoreSnapshot(*this);
+		      }
 		    };
 		  };
 		} //namespace lemon
 		#endif //LEMON_SMART_GRAPH_H

0 comments (0 inline)

RhodeCode

Login to your account