Diff [32baeb8e5c8fc2cec7dd167588af17a1777b3c8b:10c9c3a35b8319389ac03a1371ae2a27916994ab] for / – LEMON

doc/groups.dox

-                      r663
+                      r735
 \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.
 */

lemon/concepts/digraph.h

-                      r580
+                      r734
     /// \brief Class describing the concept of directed graphs.
     ///
     /// This class describes the \ref concept "concept" of the
     /// immutable directed digraphs.
+    /// This class describes the common interface of all directed
+    /// graphs (digraphs).
     ///
+    /// Note that actual digraph implementation like @ref ListDigraph or
+    /// @ref SmartDigraph may have several additional functionality.
+    /// Like all concept classes, it only provides an interface
+    /// without any sensible implementation. So any general algorithm for
+    /// directed graphs should compile with this class, but it will not
+    /// run properly, of course.
+    /// An actual digraph implementation like \ref ListDigraph or
+    /// \ref SmartDigraph may have additional functionality.
     ///
     /// \sa concept
+    /// \sa Graph
     class Digraph {
     private:
+      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
+      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
+      ///
+      Digraph(const Digraph &) {};
+      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
+      ///\e not allowed. Use DigraphCopy() instead.
+      ///Assignment of \ref Digraph "Digraph"s to another ones are
+      ///\e not allowed.  Use DigraphCopy() instead.
+      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
+      Digraph(const Digraph &) {}
+      /// \brief Assignment of a digraph to another one is \e not allowed.
+      /// Use DigraphCopy instead.
       void operator=(const Digraph &) {}
     public:
+      ///\e
+      /// Defalult constructor.
+      /// Defalult constructor.
+      ///
+      /// Default constructor.
       Digraph() { }
+      /// Class for identifying a node of the digraph
+      /// The node type of the digraph
       /// This class identifies a node of the digraph. It also serves
       /// as a base class of the node iterators,
       /// thus they will convert to this type.
+      /// thus they convert to this type.
       class Node {
       public:
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Node() { }
         /// Copy constructor.
 …
         Node(const Node&) { }
         /// Invalid constructor \& conversion.
         /// This constructor initializes the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+        /// Initializes the object to be invalid.
         /// \sa Invalid for more details.
         Node(Invalid) { }
         /// Equality operator
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
         /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Node) const { return true; }
         /// Inequality operator
+        /// \sa operator==(Node n)
+        ///
+        /// Inequality operator.
         bool operator!=(Node) const { return true; }
         /// Artificial ordering operator.
+        /// To allow the use of digraph descriptors as key type in std::map or
+        /// similar associative container we require this.
+        ///
+        /// \note This operator only have to define some strict ordering of
+        /// the items; this order has nothing to do with the iteration
+        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the nodes; this order has nothing to do with the iteration
+        /// ordering of the nodes.
         bool operator<(Node) const { return false; }
+      };
+      /// This iterator goes through each node.
+      /// This iterator goes through each node.
+      };
+      /// Iterator class for the nodes.
+      /// This iterator goes through each node of the digraph.
       /// Its usage is quite simple, for example you can count the number
       /// of nodes in digraph \c g of type \c Digraph like this:
+      /// of nodes in a digraph \c g of type \c %Digraph like this:
       ///\code
       /// int count=0;
 …
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         NodeIt() { }
         /// Copy constructor.
 …
         ///
         NodeIt(const NodeIt& n) : Node(n) { }
         /// Invalid constructor \& conversion.
         /// Initialize the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+        /// Initializes the iterator to be invalid.
         /// \sa Invalid for more details.
         NodeIt(Invalid) { }
         /// Sets the iterator to the first node.
+        /// Sets the iterator to the first node of \c g.
+        ///
+        NodeIt(const Digraph&) { }
+        /// Node -> NodeIt conversion.
+        /// Sets the iterator to the node of \c the digraph pointed by
+        /// the trivial iterator.
+        /// This feature necessitates that each time we
+        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first node of the given digraph.
+        ///
+        explicit NodeIt(const Digraph&) { }
+        /// Sets the iterator to the given node.
+        /// Sets the iterator to the given node of the given digraph.
+        ///
         NodeIt(const Digraph&, const Node&) { }
         /// Next node.
 …
       /// Class for identifying an arc of the digraph
+      /// The arc type of the digraph
       /// This class identifies an arc of the digraph. It also serves
 …
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Arc() { }
         /// Copy constructor.
 …
         ///
         Arc(const Arc&) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the object to be invalid.
+        /// \sa Invalid for more details.
         Arc(Invalid) { }
         /// Equality operator
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
         /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Arc) const { return true; }
         /// Inequality operator
+        /// \sa operator==(Arc n)
+        ///
+        /// Inequality operator.
         bool operator!=(Arc) const { return true; }
         /// Artificial ordering operator.
+        /// To allow the use of digraph descriptors as key type in std::map or
+        /// similar associative container we require this.
+        ///
+        /// \note This operator only have to define some strict ordering of
+        /// the items; this order has nothing to do with the iteration
+        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the arcs; this order has nothing to do with the iteration
+        /// ordering of the arcs.
         bool operator<(Arc) const { return false; }
       };
       /// This iterator goes trough the outgoing arcs of a node.
+      /// Iterator class for the outgoing arcs of a node.
       /// This iterator goes trough the \e outgoing arcs of a certain node
 …
       /// Its usage is quite simple, for example you can count the number
       /// of outgoing arcs of a node \c n
       /// in digraph \c g of type \c Digraph as follows.
+      /// in a digraph \c g of type \c %Digraph as follows.
       ///\code
       /// int count=0;
       /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
       class OutArcIt : public Arc {
       public:
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         OutArcIt() { }
         /// Copy constructor.
 …
         ///
         OutArcIt(const OutArcIt& e) : Arc(e) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         OutArcIt(Invalid) { }
         /// This constructor sets the iterator to the first outgoing arc.
         /// This constructor sets the iterator to the first outgoing arc of
         /// the node.
+        /// Sets the iterator to the first outgoing arc.
+        /// Sets the iterator to the first outgoing arc of the given node.
+        ///
         OutArcIt(const Digraph&, const Node&) { }
+        /// Arc -> OutArcIt conversion
+        /// Sets the iterator to the value of the trivial iterator.
+        /// This feature necessitates that each time we
+        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+        /// Sets the iterator to the given arc of the given digraph.
+        ///
         OutArcIt(const Digraph&, const Arc&) { }
         ///Next outgoing arc
+        /// Next outgoing arc
         /// Assign the iterator to the next
 …
       };
       /// This iterator goes trough the incoming arcs of a node.
+      /// Iterator class for the incoming arcs of a node.
       /// This iterator goes trough the \e incoming arcs of a certain node
       /// of a digraph.
       /// Its usage is quite simple, for example you can count the number
       /// of outgoing arcs of a node \c n
       /// in digraph \c g of type \c Digraph as follows.
+      /// of incoming arcs of a node \c n
+      /// in a digraph \c g of type \c %Digraph as follows.
       ///\code
       /// int count=0;
       /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
       class InArcIt : public Arc {
       public:
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         InArcIt() { }
         /// Copy constructor.
 …
         ///
         InArcIt(const InArcIt& e) : Arc(e) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         InArcIt(Invalid) { }
         /// This constructor sets the iterator to first incoming arc.
         /// This constructor set the iterator to the first incoming arc of
         /// the node.
+        /// Sets the iterator to the first incoming arc.
+        /// Sets the iterator to the first incoming arc of the given node.
+        ///
         InArcIt(const Digraph&, const Node&) { }
+        /// Arc -> InArcIt conversion
+        /// Sets the iterator to the value of the trivial iterator \c e.
+        /// This feature necessitates that each time we
+        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+        /// Sets the iterator to the given arc of the given digraph.
+        ///
         InArcIt(const Digraph&, const Arc&) { }
         /// Next incoming arc
         /// Assign the iterator to the next inarc of the corresponding node.
         ///
+        /// Assign the iterator to the next
+        /// incoming arc of the corresponding node.
         InArcIt& operator++() { return *this; }
       };
+      /// This iterator goes through each arc.
+      /// This iterator goes through each arc of a digraph.
+      /// Iterator class for the arcs.
+      /// This iterator goes through each arc of the digraph.
       /// Its usage is quite simple, for example you can count the number
       /// of arcs in a digraph \c g of type \c Digraph as follows:
+      /// of arcs in a digraph \c g of type \c %Digraph as follows:
       ///\code
       /// int count=0;
       /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
+      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
       ///\endcode
       class ArcIt : public Arc {
 …
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         ArcIt() { }
         /// Copy constructor.
 …
         ///
         ArcIt(const ArcIt& e) : Arc(e) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         ArcIt(Invalid) { }
+        /// This constructor sets the iterator to the first arc.
+        /// This constructor sets the iterator to the first arc of \c g.
+        ///@param g the digraph
+        ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
+        /// Arc -> ArcIt conversion
+        /// Sets the iterator to the value of the trivial iterator \c e.
+        /// This feature necessitates that each time we
+        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first arc.
+        /// Sets the iterator to the first arc of the given digraph.
+        ///
+        explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
+        /// Sets the iterator to the given arc.
+        /// Sets the iterator to the given arc of the given digraph.
+        ///
         ArcIt(const Digraph&, const Arc&) { }
         ///Next arc
+        /// Next arc
         /// Assign the iterator to the next arc.
+        ///
         ArcIt& operator++() { return *this; }
       };
+      ///Gives back the target node of an arc.
+      ///Gives back the target node of an arc.
+      ///
+      /// \brief The source node of the arc.
+      ///
+      /// Returns the source node of the given arc.
+      Node source(Arc) const { return INVALID; }
+      /// \brief The target node of the arc.
+      ///
+      /// Returns the target node of the given arc.
       Node target(Arc) const { return INVALID; }
+      ///Gives back the source node of an arc.
+      ///Gives back the source node of an arc.
+      ///
+      Node source(Arc) const { return INVALID; }
+      /// \brief Returns the ID of the node.
+      /// \brief The ID of the node.
+      ///
+      /// Returns the ID of the given node.
       int id(Node) const { return -1; }
+      /// \brief Returns the ID of the arc.
+      /// \brief The ID of the arc.
+      ///
+      /// Returns the ID of the given arc.
       int id(Arc) const { return -1; }
+      /// \brief Returns the node with the given ID.
+      ///
+      /// \pre The argument should be a valid node ID in the graph.
+      /// \brief The node with the given ID.
+      ///
+      /// Returns the node with the given ID.
+      /// \pre The argument should be a valid node ID in the digraph.
       Node nodeFromId(int) const { return INVALID; }
+      /// \brief Returns the arc with the given ID.
+      ///
+      /// \pre The argument should be a valid arc ID in the graph.
+      /// \brief The arc with the given ID.
+      ///
+      /// Returns the arc with the given ID.
+      /// \pre The argument should be a valid arc ID in the digraph.
       Arc arcFromId(int) const { return INVALID; }
+      /// \brief Returns an upper bound on the node IDs.
+      /// \brief An upper bound on the node IDs.
+      ///
+      /// Returns an upper bound on the node IDs.
       int maxNodeId() const { return -1; }
+      /// \brief Returns an upper bound on the arc IDs.
+      /// \brief An upper bound on the arc IDs.
+      ///
+      /// Returns an upper bound on the arc IDs.
       int maxArcId() const { return -1; }
 …
       int maxId(Arc) const { return -1; }
+      /// \brief The opposite node on the arc.
+      ///
+      /// Returns the opposite node on the given arc.
+      Node oppositeNode(Node, Arc) const { return INVALID; }
       /// \brief The base node of the iterator.
       ///
       /// Gives back the base node of the iterator.
       /// It is always the target of the pointed arc.
       Node baseNode(const InArcIt&) const { return INVALID; }
+      /// Returns the base node of the given outgoing arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node baseNode(OutArcIt) const { return INVALID; }
       /// \brief The running node of the iterator.
       ///
       /// Gives back the running node of the iterator.
       /// It is always the source of the pointed arc.
       Node runningNode(const InArcIt&) const { return INVALID; }
+      /// Returns the running node of the given outgoing arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node runningNode(OutArcIt) const { return INVALID; }
       /// \brief The base node of the iterator.
       ///
       /// Gives back the base node of the iterator.
       /// It is always the source of the pointed arc.
       Node baseNode(const OutArcIt&) const { return INVALID; }
+      /// Returns the base node of the given incomming arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node baseNode(InArcIt) const { return INVALID; }
       /// \brief The running node of the iterator.
       ///
+      /// Gives back the running node of the iterator.
+      /// It is always the target of the pointed arc.
+      Node runningNode(const OutArcIt&) const { return INVALID; }
+      /// \brief The opposite node on the given arc.
+      ///
+      /// Gives back the opposite node on the given arc.
+      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
+      /// \brief Reference map of the nodes to type \c T.
+      ///
+      /// Reference map of the nodes to type \c T.
+      /// Returns the running node of the given incomming arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node runningNode(InArcIt) const { return INVALID; }
+      /// \brief Standard graph map type for the nodes.
+      ///
+      /// Standard graph map type for the nodes.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
       public:
         ///\e
         NodeMap(const Digraph&) { }
         ///\e
+        /// Constructor
+        explicit NodeMap(const Digraph&) { }
+        /// Constructor with given initial value
         NodeMap(const Digraph&, T) { }
 …
       };
+      /// \brief Reference map of the arcs to type \c T.
+      ///
+      /// Reference map of the arcs to type \c T.
+      /// \brief Standard graph map type for the arcs.
+      ///
+      /// Standard graph map type for the arcs.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
       public:
         ///\e
         ArcMap(const Digraph&) { }
         ///\e
+        /// Constructor
+        explicit ArcMap(const Digraph&) { }
+        /// Constructor with given initial value
         ArcMap(const Digraph&, T) { }
       private:
         ///Copy constructor

lemon/concepts/graph.h

-                      r657
+                      r734
 ///\ingroup graph_concepts
 ///\file
 ///\brief The concept of Undirected Graphs.
+///\brief The concept of undirected graphs.
 #ifndef LEMON_CONCEPTS_GRAPH_H
 …
 #include <lemon/concepts/graph_components.h>
+#include <lemon/concepts/maps.h>
+#include <lemon/concept_check.h>
 #include <lemon/core.h>
 …
     /// \ingroup graph_concepts
     ///
     /// \brief Class describing the concept of Undirected Graphs.
+    /// \brief Class describing the concept of undirected graphs.
     ///
     /// This class describes the common interface of all Undirected
     /// Graphs.
+    /// This class describes the common interface of all undirected
+    /// graphs.
     ///
     /// As all concept describing classes it provides only interface
     /// without any sensible implementation. So any algorithm for
     /// undirected graph should compile with this class, but it will not
+    /// Like all concept classes, it only provides an interface
+    /// without any sensible implementation. So any general algorithm for
+    /// undirected graphs should compile with this class, but it will not
     /// run properly, of course.
+    /// An actual graph implementation like \ref ListGraph or
+    /// \ref SmartGraph may have additional functionality.
     ///
+    /// The LEMON undirected graphs also fulfill the concept of
+    /// directed graphs (\ref lemon::concepts::Digraph "Digraph
+    /// Concept"). Each edges can be seen as two opposite
+    /// directed arc and consequently the undirected graph can be
+    /// seen as the direceted graph of these directed arcs. The
+    /// Graph has the Edge inner class for the edges and
+    /// the Arc type for the directed arcs. The Arc type is
+    /// convertible to Edge or inherited from it so from a directed
+    /// arc we can get the represented edge.
+    /// The undirected graphs also fulfill the concept of \ref Digraph
+    /// "directed graphs", since each edge can also be regarded as two
+    /// oppositely directed arcs.
+    /// Undirected graphs provide an Edge type for the undirected edges and
+    /// an Arc type for the directed arcs. The Arc type is convertible to
+    /// Edge or inherited from it, i.e. the corresponding edge can be
+    /// obtained from an arc.
+    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
+    /// and ArcMap classes can be used for the arcs (just like in digraphs).
+    /// Both InArcIt and OutArcIt iterates on the same edges but with
+    /// opposite direction. IncEdgeIt also iterates on the same edges
+    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
+    /// only to Edge.
     ///
+    /// In the sense of the LEMON each edge has a default
+    /// direction (it should be in every computer implementation,
+    /// because the order of edge's nodes defines an
+    /// orientation). With the default orientation we can define that
+    /// the directed arc is forward or backward directed. With the \c
+    /// direction() and \c direct() function we can get the direction
+    /// of the directed arc and we can direct an edge.
+    /// In LEMON, each undirected edge has an inherent orientation.
+    /// Thus it can defined if an arc is forward or backward oriented in
+    /// an undirected graph with respect to this default oriantation of
+    /// the represented edge.
+    /// With the direction() and direct() functions the direction
+    /// of an arc can be obtained and set, respectively.
     ///
+    /// The EdgeIt is an iterator for the edges. We can use
+    /// the EdgeMap to map values for the edges. The InArcIt and
+    /// OutArcIt iterates on the same edges but with opposite
+    /// direction. The IncEdgeIt iterates also on the same edges
+    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
+    /// to Edge.
+    /// Only nodes and edges can be added to or removed from an undirected
+    /// graph and the corresponding arcs are added or removed automatically.
+    ///
+    /// \sa Digraph
     class Graph {
+    private:
+      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
+      Graph(const Graph&) {}
+      /// \brief Assignment of a graph to another one is \e not allowed.
+      /// Use DigraphCopy instead.
+      void operator=(const Graph&) {}
     public:
+      /// \brief The undirected graph should be tagged by the
+      /// UndirectedTag.
+      ///
+      /// The undirected graph should be tagged by the UndirectedTag. This
+      /// tag helps the enable_if technics to make compile time
+      /// Default constructor.
+      Graph() {}
+      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
+      ///
+      /// Undirected graphs should be tagged with \c UndirectedTag.
+      ///
+      /// This tag helps the \c enable_if technics to make compile time
       /// specializations for undirected graphs.
       typedef True UndirectedTag;
+      /// \brief The base type of node iterators,
+      /// or in other words, the trivial node iterator.
+      ///
+      /// This is the base type of each node iterator,
+      /// thus each kind of node iterator converts to this.
+      /// More precisely each kind of node iterator should be inherited
+      /// from the trivial node iterator.
+      /// The node type of the graph
+      /// This class identifies a node of the graph. It also serves
+      /// as a base class of the node iterators,
+      /// thus they convert to this type.
       class Node {
       public:
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Node() { }
         /// Copy constructor.
 …
         Node(const Node&) { }
         /// Invalid constructor \& conversion.
         /// This constructor initializes the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+        /// Initializes the object to be invalid.
         /// \sa Invalid for more details.
         Node(Invalid) { }
         /// Equality operator
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
         /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Node) const { return true; }
         /// Inequality operator
+        /// \sa operator==(Node n)
+        ///
+        /// Inequality operator.
         bool operator!=(Node) const { return true; }
         /// Artificial ordering operator.
+        /// To allow the use of graph descriptors as key type in std::map or
+        /// similar associative container we require this.
+        ///
+        /// \note This operator only have to define some strict ordering of
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
         /// the items; this order has nothing to do with the iteration
         /// ordering of the items.
 …
       };
       /// This iterator goes through each node.
       /// This iterator goes through each node.
+      /// Iterator class for the nodes.
+      /// This iterator goes through each node of the graph.
       /// Its usage is quite simple, for example you can count the number
       /// of nodes in graph \c g of type \c Graph like this:
+      /// of nodes in a graph \c g of type \c %Graph like this:
       ///\code
       /// int count=0;
 …
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         NodeIt() { }
         /// Copy constructor.
 …
         ///
         NodeIt(const NodeIt& n) : Node(n) { }
         /// Invalid constructor \& conversion.
         /// Initialize the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+        /// Initializes the iterator to be invalid.
         /// \sa Invalid for more details.
         NodeIt(Invalid) { }
         /// Sets the iterator to the first node.
+        /// Sets the iterator to the first node of \c g.
+        ///
+        NodeIt(const Graph&) { }
+        /// Node -> NodeIt conversion.
+        /// Sets the iterator to the node of \c the graph pointed by
+        /// the trivial iterator.
+        /// This feature necessitates that each time we
+        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first node of the given digraph.
+        ///
+        explicit NodeIt(const Graph&) { }
+        /// Sets the iterator to the given node.
+        /// Sets the iterator to the given node of the given digraph.
+        ///
         NodeIt(const Graph&, const Node&) { }
         /// Next node.
 …
+      /// The base type of the edge iterators.
+      /// The base type of the edge iterators.
+      ///
+      /// The edge type of the graph
+      /// This class identifies an edge of the graph. It also serves
+      /// as a base class of the edge iterators,
+      /// thus they will convert to this type.
       class Edge {
       public:
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Edge() { }
         /// Copy constructor.
 …
         ///
         Edge(const Edge&) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the object to be invalid.
+        /// \sa Invalid for more details.
         Edge(Invalid) { }
         /// Equality operator
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
         /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Edge) const { return true; }
         /// Inequality operator
+        /// \sa operator==(Edge n)
+        ///
+        /// Inequality operator.
         bool operator!=(Edge) const { return true; }
         /// Artificial ordering operator.
+        /// To allow the use of graph descriptors as key type in std::map or
+        /// similar associative container we require this.
+        ///
+        /// \note This operator only have to define some strict ordering of
+        /// the items; this order has nothing to do with the iteration
+        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the edges; this order has nothing to do with the iteration
+        /// ordering of the edges.
         bool operator<(Edge) const { return false; }
       };
       /// This iterator goes through each edge.
       /// This iterator goes through each edge of a graph.
+      /// Iterator class for the edges.
+      /// This iterator goes through each edge of the graph.
       /// Its usage is quite simple, for example you can count the number
       /// of edges in a graph \c g of type \c Graph as follows:
+      /// of edges in a graph \c g of type \c %Graph as follows:
       ///\code
       /// int count=0;
 …
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         EdgeIt() { }
         /// Copy constructor.
 …
         ///
         EdgeIt(const EdgeIt& e) : Edge(e) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         EdgeIt(Invalid) { }
+        /// This constructor sets the iterator to the first edge.
+        /// This constructor sets the iterator to the first edge.
+        EdgeIt(const Graph&) { }
+        /// Edge -> EdgeIt conversion
+        /// Sets the iterator to the value of the trivial iterator.
+        /// This feature necessitates that each time we
+        /// iterate the edge-set, the iteration order is the
+        /// same.
+        /// Sets the iterator to the first edge.
+        /// Sets the iterator to the first edge of the given graph.
+        ///
+        explicit EdgeIt(const Graph&) { }
+        /// Sets the iterator to the given edge.
+        /// Sets the iterator to the given edge of the given graph.
+        ///
         EdgeIt(const Graph&, const Edge&) { }
         /// Next edge
         /// Assign the iterator to the next edge.
+        ///
         EdgeIt& operator++() { return *this; }
       };
+      /// \brief This iterator goes trough the incident undirected
+      /// arcs of a node.
+      ///
+      /// This iterator goes trough the incident edges
+      /// of a certain node of a graph. You should assume that the
+      /// loop arcs will be iterated twice.
+      ///
+      /// Iterator class for the incident edges of a node.
+      /// This iterator goes trough the incident undirected edges
+      /// of a certain node of a graph.
       /// Its usage is quite simple, for example you can compute the
       /// degree (i.e. count the number of incident arcs of a node \c n
       /// in graph \c g of type \c Graph as follows.
+      /// degree (i.e. the number of incident edges) of a node \c n
+      /// in a graph \c g of type \c %Graph as follows.
       ///
       ///\code
 …
       /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
       ///\endcode
+      ///
+      /// \warning Loop edges will be iterated twice.
       class IncEdgeIt : public Edge {
       public:
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         IncEdgeIt() { }
         /// Copy constructor.
 …
         ///
         IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         IncEdgeIt(Invalid) { }
         /// This constructor sets the iterator to first incident arc.
         /// This constructor set the iterator to the first incident arc of
         /// the node.
+        /// Sets the iterator to the first incident edge.
+        /// Sets the iterator to the first incident edge of the given node.
+        ///
         IncEdgeIt(const Graph&, const Node&) { }
+        /// Edge -> IncEdgeIt conversion
+        /// Sets the iterator to the value of the trivial iterator \c e.
+        /// This feature necessitates that each time we
+        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given edge.
+        /// Sets the iterator to the given edge of the given graph.
+        ///
         IncEdgeIt(const Graph&, const Edge&) { }
         /// Next incident arc
         /// Assign the iterator to the next incident arc
+        /// Next incident edge
+        /// Assign the iterator to the next incident edge
         /// of the corresponding node.
         IncEdgeIt& operator++() { return *this; }
       };
       /// The directed arc type.
       /// The directed arc type. It can be converted to the
       /// edge or it should be inherited from the undirected
       /// edge.
+      /// The arc type of the graph
+      /// This class identifies a directed arc of the graph. It also serves
+      /// as a base class of the arc iterators,
+      /// thus they will convert to this type.
       class Arc {
       public:
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Arc() { }
         /// Copy constructor.
 …
         ///
         Arc(const Arc&) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the object to be invalid.
+        /// \sa Invalid for more details.
         Arc(Invalid) { }
         /// Equality operator
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
         /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Arc) const { return true; }
         /// Inequality operator
+        /// \sa operator==(Arc n)
+        ///
+        /// Inequality operator.
         bool operator!=(Arc) const { return true; }
         /// Artificial ordering operator.
+        /// To allow the use of graph descriptors as key type in std::map or
+        /// similar associative container we require this.
+        ///
+        /// \note This operator only have to define some strict ordering of
+        /// the items; this order has nothing to do with the iteration
+        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the arcs; this order has nothing to do with the iteration
+        /// ordering of the arcs.
         bool operator<(Arc) const { return false; }
+        /// Converison to Edge
+        /// Converison to \c Edge
+        /// Converison to \c Edge.
+        ///
         operator Edge() const { return Edge(); }
       };
+      /// This iterator goes through each directed arc.
+      /// This iterator goes through each arc of a graph.
+      /// Iterator class for the arcs.
+      /// This iterator goes through each directed arc of the graph.
       /// Its usage is quite simple, for example you can count the number
       /// of arcs in a graph \c g of type \c Graph as follows:
+      /// of arcs in a graph \c g of type \c %Graph as follows:
       ///\code
       /// int count=0;
       /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
+      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
       ///\endcode
       class ArcIt : public Arc {
 …
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         ArcIt() { }
         /// Copy constructor.
 …
         ///
         ArcIt(const ArcIt& e) : Arc(e) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         ArcIt(Invalid) { }
+        /// This constructor sets the iterator to the first arc.
+        /// This constructor sets the iterator to the first arc of \c g.
+        ///@param g the graph
+        ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
+        /// Arc -> ArcIt conversion
+        /// Sets the iterator to the value of the trivial iterator \c e.
+        /// This feature necessitates that each time we
+        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first arc.
+        /// Sets the iterator to the first arc of the given graph.
+        ///
+        explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
+        /// Sets the iterator to the given arc.
+        /// Sets the iterator to the given arc of the given graph.
+        ///
         ArcIt(const Graph&, const Arc&) { }
         ///Next arc
+        /// Next arc
         /// Assign the iterator to the next arc.
+        ///
         ArcIt& operator++() { return *this; }
       };
       /// This iterator goes trough the outgoing directed arcs of a node.
       /// This iterator goes trough the \e outgoing arcs of a certain node
       /// of a graph.
+      /// Iterator class for the outgoing arcs of a node.
+      /// This iterator goes trough the \e outgoing directed arcs of a
+      /// certain node of a graph.
       /// Its usage is quite simple, for example you can count the number
       /// of outgoing arcs of a node \c n
       /// in graph \c g of type \c Graph as follows.
+      /// in a graph \c g of type \c %Graph as follows.
       ///\code
       /// int count=0;
       /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
       class OutArcIt : public Arc {
       public:
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         OutArcIt() { }
         /// Copy constructor.
 …
         ///
         OutArcIt(const OutArcIt& e) : Arc(e) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         OutArcIt(Invalid) { }
+        /// This constructor sets the iterator to the first outgoing arc.
+        /// This constructor sets the iterator to the first outgoing arc of
+        /// the node.
+        ///@param n the node
+        ///@param g the graph
+        /// Sets the iterator to the first outgoing arc.
+        /// Sets the iterator to the first outgoing arc of the given node.
+        ///
         OutArcIt(const Graph& n, const Node& g) {
           ignore_unused_variable_warning(n);
           ignore_unused_variable_warning(g);
+        }
+        /// Arc -> OutArcIt conversion
+        /// Sets the iterator to the value of the trivial iterator.
+        /// This feature necessitates that each time we
+        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+        /// Sets the iterator to the given arc of the given graph.
+        ///
         OutArcIt(const Graph&, const Arc&) { }
         ///Next outgoing arc
+        /// Next outgoing arc
         /// Assign the iterator to the next
 …
       };
       /// This iterator goes trough the incoming directed arcs of a node.
       /// This iterator goes trough the \e incoming arcs of a certain node
       /// of a graph.
+      /// Iterator class for the incoming arcs of a node.
+      /// This iterator goes trough the \e incoming directed arcs of a
+      /// certain node of a graph.
       /// Its usage is quite simple, for example you can count the number
       /// of outgoing arcs of a node \c n
       /// in graph \c g of type \c Graph as follows.
+      /// of incoming arcs of a node \c n
+      /// in a graph \c g of type \c %Graph as follows.
       ///\code
       /// int count=0;
       /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
       class InArcIt : public Arc {
       public:
         /// Default constructor
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         InArcIt() { }
         /// Copy constructor.
 …
         ///
         InArcIt(const InArcIt& e) : Arc(e) { }
         /// Initialize the iterator to be invalid.
         /// Initialize the iterator to be invalid.
         ///
+        /// %Invalid constructor \& conversion.
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         InArcIt(Invalid) { }
+        /// This constructor sets the iterator to first incoming arc.
+        /// This constructor set the iterator to the first incoming arc of
+        /// the node.
+        ///@param n the node
+        ///@param g the graph
+        /// Sets the iterator to the first incoming arc.
+        /// Sets the iterator to the first incoming arc of the given node.
+        ///
         InArcIt(const Graph& g, const Node& n) {
           ignore_unused_variable_warning(n);
           ignore_unused_variable_warning(g);
+        }
+        /// Arc -> InArcIt conversion
+        /// Sets the iterator to the value of the trivial iterator \c e.
+        /// This feature necessitates that each time we
+        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+        /// Sets the iterator to the given arc of the given graph.
+        ///
         InArcIt(const Graph&, const Arc&) { }
         /// Next incoming arc
         /// Assign the iterator to the next inarc of the corresponding node.
         ///
+        /// Assign the iterator to the next
+        /// incoming arc of the corresponding node.
         InArcIt& operator++() { return *this; }
       };
+      /// \brief Reference map of the nodes to type \c T.
+      ///
+      /// Reference map of the nodes to type \c T.
+      /// \brief Standard graph map type for the nodes.
+      ///
+      /// Standard graph map type for the nodes.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class NodeMap : public ReferenceMap<Node, T, T&, const T&>
 …
       public:
         ///\e
         NodeMap(const Graph&) { }
         ///\e
+        /// Constructor
+        explicit NodeMap(const Graph&) { }
+        /// Constructor with given initial value
         NodeMap(const Graph&, T) { }
 …
       };
+      /// \brief Reference map of the arcs to type \c T.
+      ///
+      /// Reference map of the arcs to type \c T.
+      /// \brief Standard graph map type for the arcs.
+      ///
+      /// Standard graph map type for the arcs.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
 …
       public:
         ///\e
         ArcMap(const Graph&) { }
         ///\e
+        /// Constructor
+        explicit ArcMap(const Graph&) { }
+        /// Constructor with given initial value
         ArcMap(const Graph&, T) { }
       private:
         ///Copy constructor
 …
       };
+      /// Reference map of the edges to type \c T.
+      /// Reference map of the edges to type \c T.
+      /// \brief Standard graph map type for the edges.
+      ///
+      /// Standard graph map type for the edges.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
 …
       public:
         ///\e
         EdgeMap(const Graph&) { }
         ///\e
+        /// Constructor
+        explicit EdgeMap(const Graph&) { }
+        /// Constructor with given initial value
         EdgeMap(const Graph&, T) { }
       private:
         ///Copy constructor
 …
       };
+      /// \brief Direct the given edge.
+      ///
+      /// Direct the given edge. The returned arc source
+      /// will be the given node.
+      Arc direct(const Edge&, const Node&) const {
+        return INVALID;
+      }
+      /// \brief Direct the given edge.
+      ///
+      /// Direct the given edge. The returned arc
+      /// represents the given edge and the direction comes
+      /// from the bool parameter. The source of the edge and
+      /// the directed arc is the same when the given bool is true.
+      Arc direct(const Edge&, bool) const {
+        return INVALID;
+      }
+      /// \brief Returns true if the arc has default orientation.
+      ///
+      /// Returns whether the given directed arc is same orientation as
+      /// the corresponding edge's default orientation.
+      bool direction(Arc) const { return true; }
+      /// \brief Returns the opposite directed arc.
+      ///
+      /// Returns the opposite directed arc.
+      Arc oppositeArc(Arc) const { return INVALID; }
+      /// \brief Opposite node on an arc
+      ///
+      /// \return The opposite of the given node on the given edge.
+      Node oppositeNode(Node, Edge) const { return INVALID; }
+      /// \brief First node of the edge.
+      ///
+      /// \return The first node of the given edge.
+      ///
+      /// Naturally edges don't have direction and thus
+      /// don't have source and target node. However we use \c u() and \c v()
+      /// methods to query the two nodes of the arc. The direction of the
+      /// arc which arises this way is called the inherent direction of the
+      /// edge, and is used to define the "default" direction
+      /// of the directed versions of the arcs.
+      /// \brief The first node of the edge.
+      ///
+      /// Returns the first node of the given edge.
+      ///
+      /// Edges don't have source and target nodes, however methods
+      /// u() and v() are used to query the two end-nodes of an edge.
+      /// The orientation of an edge that arises this way is called
+      /// the inherent direction, it is used to define the default
+      /// direction for the corresponding arcs.
       /// \sa v()
       /// \sa direction()
       Node u(Edge) const { return INVALID; }
+      /// \brief Second node of the edge.
+      ///
+      /// \return The second node of the given edge.
+      ///
+      /// Naturally edges don't have direction and thus
+      /// don't have source and target node. However we use \c u() and \c v()
+      /// methods to query the two nodes of the arc. The direction of the
+      /// arc which arises this way is called the inherent direction of the
+      /// edge, and is used to define the "default" direction
+      /// of the directed versions of the arcs.
+      /// \brief The second node of the edge.
+      ///
+      /// Returns the second node of the given edge.
+      ///
+      /// Edges don't have source and target nodes, however methods
+      /// u() and v() are used to query the two end-nodes of an edge.
+      /// The orientation of an edge that arises this way is called
+      /// the inherent direction, it is used to define the default
+      /// direction for the corresponding arcs.
       /// \sa u()
       /// \sa direction()
       Node v(Edge) const { return INVALID; }
+      /// \brief Source node of the directed arc.
+      /// \brief The source node of the arc.
+      ///
+      /// Returns the source node of the given arc.
       Node source(Arc) const { return INVALID; }
+      /// \brief Target node of the directed arc.
+      /// \brief The target node of the arc.
+      ///
+      /// Returns the target node of the given arc.
       Node target(Arc) const { return INVALID; }
+      /// \brief Returns the id of the node.
+      /// \brief The ID of the node.
+      ///
+      /// Returns the ID of the given node.
       int id(Node) const { return -1; }
+      /// \brief Returns the id of the edge.
+      /// \brief The ID of the edge.
+      ///
+      /// Returns the ID of the given edge.
       int id(Edge) const { return -1; }
+      /// \brief Returns the id of the arc.
+      /// \brief The ID of the arc.
+      ///
+      /// Returns the ID of the given arc.
       int id(Arc) const { return -1; }
+      /// \brief Returns the node with the given id.
+      ///
+      /// \pre The argument should be a valid node id in the graph.
+      /// \brief The node with the given ID.
+      ///
+      /// Returns the node with the given ID.
+      /// \pre The argument should be a valid node ID in the graph.
       Node nodeFromId(int) const { return INVALID; }
+      /// \brief Returns the edge with the given id.
+      ///
+      /// \pre The argument should be a valid edge id in the graph.
+      /// \brief The edge with the given ID.
+      ///
+      /// Returns the edge with the given ID.
+      /// \pre The argument should be a valid edge ID in the graph.
       Edge edgeFromId(int) const { return INVALID; }
+      /// \brief Returns the arc with the given id.
+      ///
+      /// \pre The argument should be a valid arc id in the graph.
+      /// \brief The arc with the given ID.
+      ///
+      /// Returns the arc with the given ID.
+      /// \pre The argument should be a valid arc ID in the graph.
       Arc arcFromId(int) const { return INVALID; }
+      /// \brief Returns an upper bound on the node IDs.
+      /// \brief An upper bound on the node IDs.
+      ///
+      /// Returns an upper bound on the node IDs.
       int maxNodeId() const { return -1; }
+      /// \brief Returns an upper bound on the edge IDs.
+      /// \brief An upper bound on the edge IDs.
+      ///
+      /// Returns an upper bound on the edge IDs.
       int maxEdgeId() const { return -1; }
+      /// \brief Returns an upper bound on the arc IDs.
+      /// \brief An upper bound on the arc IDs.
+      ///
+      /// Returns an upper bound on the arc IDs.
       int maxArcId() const { return -1; }
+      /// \brief The direction of the arc.
+      ///
+      /// Returns \c true if the direction of the given arc is the same as
+      /// the inherent orientation of the represented edge.
+      bool direction(Arc) const { return true; }
+      /// \brief Direct the edge.
+      ///
+      /// Direct the given edge. The returned arc
+      /// represents the given edge and its direction comes
+      /// from the bool parameter. If it is \c true, then the direction
+      /// of the arc is the same as the inherent orientation of the edge.
+      Arc direct(Edge, bool) const {
+        return INVALID;
+      }
+      /// \brief Direct the edge.
+      ///
+      /// Direct the given edge. The returned arc represents the given
+      /// edge and its source node is the given node.
+      Arc direct(Edge, Node) const {
+        return INVALID;
+      }
+      /// \brief The oppositely directed arc.
+      ///
+      /// Returns the oppositely directed arc representing the same edge.
+      Arc oppositeArc(Arc) const { return INVALID; }
+      /// \brief The opposite node on the edge.
+      ///
+      /// Returns the opposite node on the given edge.
+      Node oppositeNode(Node, Edge) const { return INVALID; }
       void first(Node&) const {}
 …
       int maxId(Arc) const { return -1; }
+      /// \brief Base node of the iterator
+      ///
+      /// Returns the base node (the source in this case) of the iterator
+      Node baseNode(OutArcIt e) const {
+        return source(e);
+      }
+      /// \brief Running node of the iterator
+      ///
+      /// Returns the running node (the target in this case) of the
+      /// iterator
+      Node runningNode(OutArcIt e) const {
+        return target(e);
+      }
+      /// \brief Base node of the iterator
+      ///
+      /// Returns the base node (the target in this case) of the iterator
+      Node baseNode(InArcIt e) const {
+        return target(e);
+      }
+      /// \brief Running node of the iterator
+      ///
+      /// Returns the running node (the source in this case) of the
+      /// iterator
+      Node runningNode(InArcIt e) const {
+        return source(e);
+      }
+      /// \brief Base node of the iterator
+      ///
+      /// Returns the base node of the iterator
+      Node baseNode(IncEdgeIt) const {
+        return INVALID;
+      }
+      /// \brief Running node of the iterator
+      ///
+      /// Returns the running node of the iterator
+      Node runningNode(IncEdgeIt) const {
+        return INVALID;
+      }
+      /// \brief The base node of the iterator.
+      ///
+      /// Returns the base node of the given incident edge iterator.
+      Node baseNode(IncEdgeIt) const { return INVALID; }
+      /// \brief The running node of the iterator.
+      ///
+      /// Returns the running node of the given incident edge iterator.
+      Node runningNode(IncEdgeIt) const { return INVALID; }
+      /// \brief The base node of the iterator.
+      ///
+      /// Returns the base node of the given outgoing arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node baseNode(OutArcIt) const { return INVALID; }
+      /// \brief The running node of the iterator.
+      ///
+      /// Returns the running node of the given outgoing arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node runningNode(OutArcIt) const { return INVALID; }
+      /// \brief The base node of the iterator.
+      ///
+      /// Returns the base node of the given incomming arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node baseNode(InArcIt) const { return INVALID; }
+      /// \brief The running node of the iterator.
+      ///
+      /// Returns the running node of the given incomming arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node runningNode(InArcIt) const { return INVALID; }
       template <typename _Graph>

lemon/concepts/graph_components.h

r666	r734
93	93	/// associative containers (e.g. \c std::map).
94	94	///
95		/// \note This operator only have to define some strict ordering of
	95	/// \note This operator only has to define some strict ordering of
96	96	/// the items; this order has nothing to do with the iteration
97	97	/// ordering of the items.

lemon/full_graph.h

-                      r617
+                      r735
 ///\ingroup graphs
 ///\file
 ///\brief FullGraph and FullDigraph classes.
+///\brief FullDigraph and FullGraph classes.
 namespace lemon {
 …
   /// \ingroup graphs
   ///
+  /// \brief A full digraph 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.
+  ///
+  /// This class fully conforms to the \ref concepts::Digraph
+  /// "Digraph concept".
+  ///
+  /// The \c FullDigraph and \c FullGraph classes are very similar,
+  /// \brief A directed full graph class.
+  ///
+  /// 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 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.
+  ///
+  /// \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
 …
   public:
+    /// \brief Constructor
+    /// \brief Default constructor.
+    ///
+    /// Default constructor. The number of nodes and arcs will be zero.
     FullDigraph() { construct(0); }
 …
     /// \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) {
 …
     /// \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 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.
+  ///
+  /// This class fully conforms to the \ref concepts::Graph "Graph concept".
+  ///
+  /// The \c FullGraph and \c FullDigraph classes are very similar,
+  /// but there are two differences. While the \c FullDigraph class
+  /// 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 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 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
 …
   public:
+    /// \brief Constructor
+    /// \brief Default constructor.
+    ///
+    /// Default constructor. The number of nodes and edges will be zero.
     FullGraph() { construct(0); }
 …
     /// \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) {
 …
     /// \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.
     ///
     /// Returns the edge connects the given nodes.
     Edge edge(const Node& u, const Node& v) const {
+    /// \brief Returns the edge connecting the given nodes.
+    ///
+    /// Returns the edge connecting the given nodes.
+    Edge edge(Node u, Node v) const {
       return Parent::edge(u, v);
+    }

lemon/grid_graph.h

-                      r617
+                      r735
   /// \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
 …
   ///\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>.
+    ///
+    /// 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 \ref dim2::Point
+    /// "dim2::Point<int>".
     class IndexMap {
     public:
 …
       /// \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);
 …
       /// \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);
 …
       /// \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);
 …
     /// \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
+    ///
+    /// 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.
+    /// \brief Resizes the graph
+    ///
+    /// 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();
 …
+    }
     /// \brief Gives back the column index of the node.
+    /// \brief The column index of the node.
     ///
     /// Gives back the column index of the node.
 …
+    }
     /// \brief Gives back the row index of the node.
+    /// \brief The row index of the node.
     ///
     /// Gives back the row index of the node.
 …
+    }
     /// \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.
 …
+    }
     /// \brief Gives back the number of the columns.
+    /// \brief The number of the columns.
     ///
     /// Gives back the number of the columns.
 …
+    }
     /// \brief Gives back the number of the rows.
+    /// \brief The number of the rows.
     ///
     /// Gives back the number of the rows.
 …
+    }
     /// \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
 …
+    }
     /// \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
 …
+    }
     /// \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
 …
+    }
     /// \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

lemon/hypercube_graph.h

-                      r617
+                      r737
   /// \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, however
+  /// the structure can be resized using resize().
+  ///
+  /// 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;
 …
     /// Constructs a hypercube graph with \c dim dimensions.
     HypercubeGraph(int dim) { construct(dim); }
+    /// \brief Resizes the graph
+    ///
+    /// 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 dim) {
+      Parent::notifier(Arc()).clear();
+      Parent::notifier(Edge()).clear();
+      Parent::notifier(Node()).clear();
+      construct(dim);
+      Parent::notifier(Node()).build();
+      Parent::notifier(Edge()).build();
+      Parent::notifier(Arc()).build();
+    }
     /// \brief The number of dimensions.
 …
     ///
     /// 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);
 …
     ///
     /// 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);

lemon/list_graph.h

-                      r739
+                      r741
 ///\ingroup graphs
 ///\file
 ///\brief ListDigraph, ListGraph classes.
+///\brief ListDigraph and ListGraph classes.
 #include <lemon/core.h>
 …
 namespace lemon {
+  class ListDigraph;
   class ListDigraphBase {
 …
     class Node {
       friend class ListDigraphBase;
+      friend class ListDigraph;
     protected:
 …
     class Arc {
       friend class ListDigraphBase;
+      friend class ListDigraph;
     protected:
 …
   ///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:
 …
     ///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.
+    ///
+    /// \warning A Node pointing to a removed item
+    /// could become valid again later if new nodes are
+    /// added to 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 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.
+    ///
+    /// \warning An Arc pointing to a removed item
+    /// could become valid again later if new nodes are
+    /// added to 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 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 of \c a to \c n
+    ///
+    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
+    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
+    ///invalidated.
+    /// Change the target node of an arc
+    /// This function changes the target node of the given arc \c a to \c n.
+    ///
+    ///\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
 …
       Parent::changeTarget(a,n);
+    }
+    /// Change the source of \c a to \c n
+    /// Change the source of \c a to \c n
+    ///
+    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
+    ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are
+    ///invalidated.
+    /// Change the source node of an arc
+    /// This function changes the source node of the given arc \c a to \c n.
+    ///
+    ///\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
 …
+    }
     /// Invert the direction of an arc.
     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
     ///invalidated.
+    /// Reverse the direction of an arc.
+    /// 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);
+    }
+    /// 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); };
+    void reverseArc(Arc a) {
+      Node t=target(a);
+      changeTarget(a,source(a));
+      changeSource(a,t);
+    }
     ///Contract two nodes.
+    ///This function contracts two nodes.
+    ///Node \p b will be removed but instead of deleting
+    ///incident arcs, they will be joined to \p a.
+    ///The last parameter \p r controls whether to remove loops. \c true
+    ///means that loops will be removed.
+    ///
+    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
+    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
+    ///may be invalidated.
+    ///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 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.
+    ///
+    ///\warning This functionality cannot be used in conjunction with the
+    ///\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();
+      for(OutArcIt e(*this,n);e!=INVALID;) {
+        OutArcIt f=e;
+        ++f;
+        changeSource(e,b);
+        e=f;
+      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);
 …
     ///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.
+    ///
+    ///\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
 …
     /// 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:
 …
       ///
       /// 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),
 …
       /// \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&).
+      ///
+      /// \warning This method invalidates the snapshot, i.e. repeated
+      /// restoring is not supported unless you call save() again.
       void restore() {
         detach();
 …
+      }
       /// \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();
 …
     typedef ListGraphBase Graph;
-    class Node;
-    class Arc;
-    class Edge;
     class Node {
 …
       bool operator<(const Arc& arc) const {return id < arc.id;}
     };
     ListGraphBase()
 …
   ///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:
 …
     /// \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);
+    }
+    /// \brief Erase a node from the graph.
+    ///
+    /// Erase a node from the graph.
+    ///
+    void erase(const Node& n) { Parent::erase(n); }
+    /// \brief Erase an edge from the graph.
+    ///
+    /// Erase an edge from the graph.
+    ///
+    void erase(const Edge& e) { Parent::erase(e); }
+    Edge addEdge(Node u, Node v) {
+      return Parent::addEdge(u, v);
+    }
+    ///\brief 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.
+    ///
+    /// 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.
+    ///
+    /// \warning A Node pointing to a removed item
+    /// could become valid again later if new nodes are
+    /// 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 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.
+    ///
+    /// \warning An Arc pointing to a removed item
+    /// could become valid again later if new edges are
+    /// 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 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.
+    ///
+    /// \warning A Edge pointing to a removed item
+    /// could become valid again later if new edges are
+    /// added to the graph.
+    bool valid(Edge e) const { return Parent::valid(e); }
+    /// \brief Change the end \c u of \c e to \c n
+    ///
+    /// This function changes the end \c u of \c e to node \c n.
+    ///
+    ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
+    ///changed edge are invalidated and if the changed node is the
+    ///base node of an iterator then this iterator is also
+    ///invalidated.
+    /// \brief Change the first node of an edge.
+    ///
+    /// This function changes the first node of the given edge \c e to \c n.
+    ///
+    ///\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
 …
       Parent::changeU(e,n);
+    }
+    /// \brief Change the end \c v of \c e to \c n
+    ///
+    /// This function changes the end \c v of \c e to \c n.
+    ///
+    ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
+    ///valid, however <tt>ArcIt</tt>s and if the changed node is the
+    ///base node of an iterator then this iterator is invalidated.
+    /// \brief Change the second node of an edge.
+    ///
+    /// This function changes the second node of the given edge \c e to \c n.
+    ///
+    ///\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
 …
       Parent::changeV(e,n);
+    }
     /// \brief Contract two nodes.
     ///
+    /// This function contracts two nodes.
+    /// Node \p b will be removed but instead of deleting
+    /// its neighboring arcs, they will be joined to \p a.
+    /// The last parameter \p r controls whether to remove loops. \c true
+    /// means that loops will be removed.
+    ///
+    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
+    /// valid.
+    /// 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 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
 …
+    }
+    ///Clear the graph.
+    ///This function erases all nodes and arcs from the graph.
+    ///
+    void clear() {
+      Parent::clear();
+    }
+    /// Reserve memory for nodes.
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveEdge()
+    void reserveNode(int n) { nodes.reserve(n); };
+    /// Reserve memory for edges.
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveNode()
+    void reserveEdge(int m) { arcs.reserve(2 * m); };
     /// \brief Class to make a snapshot of the graph and restore
 …
     /// 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:
 …
       ///
       /// 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),
 …
       /// \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&).
+      ///
+      /// \warning This method invalidates the snapshot, i.e. repeated
+      /// restoring is not supported unless you call save() again.
       void restore() {
         detach();
 …
+      }
       /// \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();

lemon/smart_graph.h

-                      r617
+                      r736
   class SmartDigraph;
+  ///Base of SmartDigraph
+  ///Base of SmartDigraph
+  ///
   class SmartDigraphBase {
   protected:
 …
   ///\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 &) {}
 …
     ///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.
 …
+    }
+    ///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:
 …
   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 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 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.
+    ///
+    ///\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.
+    ///restore() function. This is the only way for deleting nodes and/or
+    ///arcs from a SmartDigraph structure.
+    ///
+    ///\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
+    {
 …
       ///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()
+      {
 …
   /// \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 &) {}
 …
     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();
+    }
+    /// Reserve memory for nodes.
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveEdge()
+    void reserveNode(int n) { nodes.reserve(n); };
+    /// Reserve memory for edges.
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveNode()
+    void reserveEdge(int m) { arcs.reserve(2 * m); };
   public:
 …
   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 restrore to 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.
+    ///
+    ///\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.
+    ///Class to make a snapshot of the graph and to restore it later.
+    ///Class to make a snapshot of the graph and to restore it later.
+    ///
+    ///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 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 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
+    {
 …
       ///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);
+      }
+      ///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().
+        gr.saveSnapshot(*this);
+      }
+      ///Undo the changes until the last snapshot.
+      ///This function undos the changes until the last snapshot
+      ///created by save() or Snapshot(SmartGraph&).
       void restore()
+      {

test/digraph_test.cc

-                      r440
+                      r740
   checkGraphArcList(G, 0);
+  G.reserveNode(3);
+  G.reserveArc(4);
   Node
     n1 = G.addNode(),
 …
   snapshot.restore();
+  snapshot.save(G);
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 4);
+  G.addArc(G.addNode(), G.addNode());
+  snapshot.restore();
   checkGraphNodeList(G, 4);
 …
   typedef FullDigraph Digraph;
   DIGRAPH_TYPEDEFS(Digraph);
   Digraph G(num);
+  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
+  G.resize(num);
+  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
   checkGraphNodeList(G, num);

test/graph_test.cc

-                      r440
+                      r740
   checkGraphArcList(G, 0);
+  G.reserveNode(3);
+  G.reserveEdge(3);
   Node
     n1 = G.addNode(),
 …
   snapshot.restore();
+  snapshot.save(G);
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 3);
+  checkGraphArcList(G, 6);
+  G.addEdge(G.addNode(), G.addNode());
+  snapshot.restore();
   checkGraphNodeList(G, 4);
 …
   Graph G(num);
+  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
+        "Wrong size");
+  G.resize(num);
+  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
+        "Wrong size");
   checkGraphNodeList(G, num);
   checkGraphEdgeList(G, num * (num - 1) / 2);
 …
   check(G.height() == height, "Wrong row number");
+  G.resize(width, height);
+  check(G.width() == width, "Wrong column number");
+  check(G.height() == height, "Wrong row number");
   for (int i = 0; i < width; ++i) {
     for (int j = 0; j < height; ++j) {
 …
   HypercubeGraph G(dim);
+  check(G.dimension() == dim, "Wrong dimension");
+  G.resize(dim);
+  check(G.dimension() == dim, "Wrong dimension");
   checkGraphNodeList(G, 1 << dim);
   checkGraphEdgeList(G, dim * (1 << (dim-1)));

Context Navigation

Changes in / [739:32baeb8e5c8f:741:10c9c3a35b83] in lemon-main

Legend:

doc/groups.dox

lemon/concepts/digraph.h

lemon/concepts/graph.h

lemon/concepts/graph_components.h

lemon/full_graph.h

lemon/grid_graph.h

lemon/hypercube_graph.h

lemon/list_graph.h

lemon/smart_graph.h

test/digraph_test.cc

test/graph_test.cc

Download in other formats: