Index: doc/groups.dox
===================================================================
 doc/groups.dox (revision 710)
+++ doc/groups.dox (revision 782)
@@ 637,6 +637,6 @@
\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.
*/
Index: lemon/concepts/digraph.h
===================================================================
 lemon/concepts/digraph.h (revision 627)
+++ lemon/concepts/digraph.h (revision 781)
@@ 36,44 +36,38 @@
/// \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.
@@ 83,38 +77,37 @@
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;
@@ 125,6 +118,6 @@
/// 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.
@@ 133,20 +126,18 @@
///
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 arcset, 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.
@@ 158,5 +149,5 @@
 /// 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
@@ 167,6 +158,6 @@
/// 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.
@@ 175,32 +166,32 @@
///
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
@@ 208,16 +199,15 @@
/// 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.
@@ 226,21 +216,20 @@
///
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 arcset, 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
@@ 249,22 +238,21 @@
};
 /// 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.
@@ 273,34 +261,34 @@
///
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 arcset, 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 {
@@ 308,6 +296,6 @@
/// 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.
@@ 316,56 +304,66 @@
///
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 arcset, 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; }
@@ 393,43 +391,44 @@
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 NodeMap : public ReferenceMap {
public:
 ///\e
 NodeMap(const Digraph&) { }
 ///\e
+ /// Constructor
+ explicit NodeMap(const Digraph&) { }
+ /// Constructor with given initial value
NodeMap(const Digraph&, T) { }
@@ 446,15 +445,17 @@
};
 /// \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 ArcMap : public ReferenceMap {
public:
 ///\e
 ArcMap(const Digraph&) { }
 ///\e
+ /// Constructor
+ explicit ArcMap(const Digraph&) { }
+ /// Constructor with given initial value
ArcMap(const Digraph&, T) { }
+
private:
///Copy constructor
Index: lemon/concepts/graph.h
===================================================================
 lemon/concepts/graph.h (revision 704)
+++ lemon/concepts/graph.h (revision 781)
@@ 19,5 +19,5 @@
///\ingroup graph_concepts
///\file
///\brief The concept of Undirected Graphs.
+///\brief The concept of undirected graphs.
#ifndef LEMON_CONCEPTS_GRAPH_H
@@ 25,4 +25,6 @@
#include
+#include
+#include
#include
@@ 32,61 +34,72 @@
/// \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.
@@ 96,27 +109,27 @@
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.
@@ 125,9 +138,9 @@
};
 /// 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;
@@ 138,6 +151,6 @@
/// 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.
@@ 146,20 +159,18 @@
///
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 arcset, 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.
@@ 171,14 +182,15 @@
 /// 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.
@@ 187,36 +199,36 @@
///
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;
@@ 227,6 +239,6 @@
/// 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.
@@ 235,36 +247,33 @@
///
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 edgeset, 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
@@ 272,10 +281,12 @@
/// 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.
@@ 284,38 +295,37 @@
///
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 arcset, 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.
@@ 324,41 +334,45 @@
///
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 {
@@ 366,6 +380,6 @@
/// 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.
@@ 374,44 +388,43 @@
///
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 arcset, 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.
@@ 420,26 +433,23 @@
///
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 arcset, 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
@@ 448,22 +458,21 @@
};
 /// 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.
@@ 472,35 +481,33 @@
///
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 arcset, 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 NodeMap : public ReferenceMap
@@ 508,7 +515,7 @@
public:
 ///\e
 NodeMap(const Graph&) { }
 ///\e
+ /// Constructor
+ explicit NodeMap(const Graph&) { }
+ /// Constructor with given initial value
NodeMap(const Graph&, T) { }
@@ 525,7 +532,8 @@
};
 /// \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 ArcMap : public ReferenceMap
@@ 533,8 +541,9 @@
public:
 ///\e
 ArcMap(const Graph&) { }
 ///\e
+ /// Constructor
+ explicit ArcMap(const Graph&) { }
+ /// Constructor with given initial value
ArcMap(const Graph&, T) { }
+
private:
///Copy constructor
@@ 549,7 +558,8 @@
};
 /// 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 EdgeMap : public ReferenceMap
@@ 557,8 +567,9 @@
public:
 ///\e
 EdgeMap(const Graph&) { }
 ///\e
+ /// Constructor
+ explicit EdgeMap(const Graph&) { }
+ /// Constructor with given initial value
EdgeMap(const Graph&, T) { }
+
private:
///Copy constructor
@@ 573,104 +584,121 @@
};
 /// \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 endnodes 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 endnodes 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 {}
@@ 706,45 +734,37 @@
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
Index: lemon/concepts/graph_components.h
===================================================================
 lemon/concepts/graph_components.h (revision 713)
+++ lemon/concepts/graph_components.h (revision 781)
@@ 93,5 +93,5 @@
/// associative containers (e.g. \c std::map).
///
 /// \note This operator only have to define some strict ordering of
+ /// \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.
Index: lemon/full_graph.h
===================================================================
 lemon/full_graph.h (revision 664)
+++ lemon/full_graph.h (revision 782)
@@ 25,5 +25,5 @@
///\ingroup graphs
///\file
///\brief FullGraph and FullDigraph classes.
+///\brief FullDigraph and FullGraph classes.
namespace lemon {
@@ 149,22 +149,24 @@
/// \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
@@ 174,5 +176,7 @@
public:
 /// \brief Constructor
+ /// \brief Default constructor.
+ ///
+ /// Default constructor. The number of nodes and arcs will be zero.
FullDigraph() { construct(0); }
@@ 185,6 +189,6 @@
/// \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) {
@@ 198,7 +202,7 @@
/// \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
 /// [0..nodeNum()1].
+ /// Returns the node with the given index. Since this structure is
+ /// completely static, the nodes can be indexed with integers from
+ /// the range [0..nodeNum()1].
/// \sa index()
Node operator()(int ix) const { return Parent::operator()(ix); }
@@ 206,14 +210,14 @@
/// \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
 /// [0..nodeNum()1].
 /// \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 [0..nodeNum()1].
+ /// \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);
}
@@ 521,19 +525,21 @@
/// \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(n1)/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 n(n1)/2.
+ /// 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
@@ 543,5 +549,7 @@
public:
 /// \brief Constructor
+ /// \brief Default constructor.
+ ///
+ /// Default constructor. The number of nodes and edges will be zero.
FullGraph() { construct(0); }
@@ 554,6 +562,6 @@
/// \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) {
@@ 569,7 +577,7 @@
/// \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
 /// [0..nodeNum()1].
+ /// Returns the node with the given index. Since this structure is
+ /// completely static, the nodes can be indexed with integers from
+ /// the range [0..nodeNum()1].
/// \sa index()
Node operator()(int ix) const { return Parent::operator()(ix); }
@@ 577,21 +585,21 @@
/// \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
 /// [0..nodeNum()1].
 /// \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 [0..nodeNum()1].
+ /// \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);
}
Index: lemon/grid_graph.h
===================================================================
 lemon/grid_graph.h (revision 664)
+++ lemon/grid_graph.h (revision 782)
@@ 471,15 +471,19 @@
/// \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 [0..width()1] and j is in the range
+ /// [0..height()1]. 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 bottomleft 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
@@ 497,6 +501,7 @@
///\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;
@@ 504,7 +509,9 @@
public:
 /// \brief Map to get the indices of the nodes as dim2::Point.
 ///
 /// Map to get the indices of the nodes as dim2::Point.
+ /// \brief Map to get the indices of the nodes as \ref dim2::Point
+ /// "dim2::Point".
+ ///
+ /// Map to get the indices of the nodes as \ref dim2::Point
+ /// "dim2::Point".
class IndexMap {
public:
@@ 515,11 +522,7 @@
/// \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);
@@ 541,11 +544,7 @@
/// \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);
@@ 567,11 +566,7 @@
/// \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);
@@ 584,13 +579,12 @@
/// \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();
@@ 610,5 +604,5 @@
}
 /// \brief Gives back the column index of the node.
+ /// \brief The column index of the node.
///
/// Gives back the column index of the node.
@@ 617,5 +611,5 @@
}
 /// \brief Gives back the row index of the node.
+ /// \brief The row index of the node.
///
/// Gives back the row index of the node.
@@ 624,5 +618,5 @@
}
 /// \brief Gives back the position of the node.
+ /// \brief The position of the node.
///
/// Gives back the position of the node, ie. the (col,row) pair.
@@ 631,5 +625,5 @@
}
 /// \brief Gives back the number of the columns.
+ /// \brief The number of the columns.
///
/// Gives back the number of the columns.
@@ 638,5 +632,5 @@
}
 /// \brief Gives back the number of the rows.
+ /// \brief The number of the rows.
///
/// Gives back the number of the rows.
@@ 645,5 +639,5 @@
}
 /// \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
@@ 653,5 +647,5 @@
}
 /// \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
@@ 661,5 +655,5 @@
}
 /// \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
@@ 669,5 +663,5 @@
}
 /// \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
Index: lemon/hypercube_graph.h
===================================================================
 lemon/hypercube_graph.h (revision 664)
+++ lemon/hypercube_graph.h (revision 784)
@@ 283,15 +283,19 @@
/// \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;
@@ 303,4 +307,19 @@
/// 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.
@@ 321,5 +340,5 @@
///
/// Gives back the dimension id of the given edge.
 /// It is in the [0..dim1] range.
+ /// It is in the range [0..dim1].
int dimension(Edge edge) const {
return Parent::dimension(edge);
@@ 329,5 +348,5 @@
///
/// Gives back the dimension id of the given arc.
 /// It is in the [0..dim1] range.
+ /// It is in the range [0..dim1].
int dimension(Arc arc) const {
return Parent::dimension(arc);
Index: lemon/list_graph.h
===================================================================
 lemon/list_graph.h (revision 786)
+++ lemon/list_graph.h (revision 787)
@@ 22,5 +22,5 @@
///\ingroup graphs
///\file
///\brief ListDigraph, ListGraph classes.
+///\brief ListDigraph and ListGraph classes.
#include
@@ 32,4 +32,6 @@
namespace lemon {
+
+ class ListDigraph;
class ListDigraphBase {
@@ 63,4 +65,5 @@
class Node {
friend class ListDigraphBase;
+ friend class ListDigraph;
protected:
@@ 78,4 +81,5 @@
class Arc {
friend class ListDigraphBase;
+ friend class ListDigraph;
protected:
@@ 117,18 +121,18 @@
int n;
for(n = first_node;
 n != 1 && nodes[n].first_out == 1;
+ n!=1 && nodes[n].first_in == 1;
n = nodes[n].next) {}
 arc.id = (n == 1) ? 1 : nodes[n].first_out;
+ arc.id = (n == 1) ? 1 : nodes[n].first_in;
}
void next(Arc& arc) const {
 if (arcs[arc.id].next_out != 1) {
 arc.id = arcs[arc.id].next_out;
+ if (arcs[arc.id].next_in != 1) {
+ arc.id = arcs[arc.id].next_in;
} else {
int n;
 for(n = nodes[arcs[arc.id].source].next;
 n != 1 && nodes[n].first_out == 1;
+ for(n = nodes[arcs[arc.id].target].next;
+ n!=1 && nodes[n].first_in == 1;
n = nodes[n].next) {}
 arc.id = (n == 1) ? 1 : nodes[n].first_out;
+ arc.id = (n == 1) ? 1 : nodes[n].first_in;
}
}
@@ 312,29 +316,23 @@
///A general directed graph structure.
 ///\ref ListDigraph is a simple and fast directed graph
 ///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:
@@ 348,5 +346,5 @@
///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(); }
@@ 354,8 +352,8 @@
///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);
}
@@ 363,41 +361,36 @@
///\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 ArcIts and OutArcIts referencing
 ///the changed arc remain valid. However InArcIts 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
@@ 406,11 +399,10 @@
Parent::changeTarget(a,n);
}
 /// Change the source of \c a to \c n

 /// Change the source of \c a to \c n
 ///
 ///\note The InArcIts referencing the changed arc remain
 ///valid. However the ArcIts and OutArcIts 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
@@ 420,92 +412,74 @@
}
 /// Invert the direction of an arc.

 ///\note The ArcIts referencing the changed arc remain
 ///valid. However OutArcIts and InArcIts 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 ArcIts referencing a moved arc remain
 ///valid. However InArcIts and OutArcIts
 ///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 ArcIts referencing a moved arc remain
 ///valid. However InArcIts and OutArcIts 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);
@@ 515,18 +489,49 @@
///Split an arc.
 ///This function splits an arc. First a new node \c b is added to
 ///the digraph, then the original arc is retargeted 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
@@ 538,7 +543,13 @@
/// 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:
@@ 710,5 +721,5 @@
///
/// 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),
@@ 717,30 +728,31 @@
/// \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();
@@ 756,7 +768,7 @@
}
 /// \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();
@@ 795,8 +807,4 @@
typedef ListGraphBase Graph;

 class Node;
 class Arc;
 class Edge;
class Node {
@@ 848,6 +856,4 @@
bool operator<(const Arc& arc) const {return id < arc.id;}
};


ListGraphBase()
@@ 1165,29 +1171,23 @@
///A general undirected graph structure.
 ///\ref ListGraph is a simple and fast undirected graph
 ///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:
@@ 1202,5 +1202,5 @@
/// \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(); }
@@ 1208,57 +1208,53 @@
/// \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 EdgeIts and ArcIts 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
@@ 1267,11 +1263,12 @@
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 EdgeIts referencing the changed edge remain
 ///valid, however ArcIts 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
@@ 1280,14 +1277,18 @@
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 ArcIts 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
@@ 1308,4 +1309,31 @@
}
+ ///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
@@ 1317,7 +1345,13 @@
/// 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 endnodes 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:
@@ 1489,5 +1523,5 @@
///
/// 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),
@@ 1496,30 +1530,31 @@
/// \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();
@@ 1535,7 +1570,7 @@
}
 /// \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();
Index: lemon/smart_graph.h
===================================================================
 lemon/smart_graph.h (revision 664)
+++ lemon/smart_graph.h (revision 783)
@@ 33,8 +33,5 @@
class SmartDigraph;
 ///Base of SmartDigraph

 ///Base of SmartDigraph
 ///
+
class SmartDigraphBase {
protected:
@@ 188,26 +185,24 @@
///\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 it does support only limited (only stacklike)
 ///node and arc deletions.
 ///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 &) {}
@@ 222,77 +217,47 @@
///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 Arcs
 ///referencing a moved arc remain
 ///valid. However InArc's and OutArc's
 ///may be invalidated.
+ ///\note All iterators remain valid.
+ ///
///\warning This functionality cannot be used together with the Snapshot
///feature.
@@ 309,4 +274,32 @@
}
+ ///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:
@@ 333,18 +326,21 @@
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
{
@@ 358,12 +354,11 @@
///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();
@@ 372,12 +367,9 @@
///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();
@@ 386,9 +378,6 @@
///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()
{
@@ 622,27 +611,24 @@
/// \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 it does support only limited (only stacklike)
 /// node and arc deletions.
 /// 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 &) {}
@@ 655,53 +641,74 @@
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:
@@ 743,19 +750,20 @@
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
{
@@ 769,34 +777,28 @@
///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()
{
Index: test/digraph_test.cc
===================================================================
 test/digraph_test.cc (revision 463)
+++ test/digraph_test.cc (revision 787)
@@ 36,4 +36,7 @@
checkGraphArcList(G, 0);
+ G.reserveNode(3);
+ G.reserveArc(4);
+
Node
n1 = G.addNode(),
@@ 284,4 +287,12 @@
snapshot.restore();
+ snapshot.save(G);
+
+ checkGraphNodeList(G, 4);
+ checkGraphArcList(G, 4);
+
+ G.addArc(G.addNode(), G.addNode());
+
+ snapshot.restore();
checkGraphNodeList(G, 4);
@@ 376,5 +387,10 @@
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);
Index: test/graph_test.cc
===================================================================
 test/graph_test.cc (revision 463)
+++ test/graph_test.cc (revision 787)
@@ 39,4 +39,7 @@
checkGraphArcList(G, 0);
+ G.reserveNode(3);
+ G.reserveEdge(3);
+
Node
n1 = G.addNode(),
@@ 257,4 +260,13 @@
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);
@@ 268,4 +280,11 @@
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);
@@ 412,4 +431,8 @@
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) {
@@ 487,4 +510,9 @@
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 << (dim1)));