Index: doc/groups.dox
===================================================================
 doc/groups.dox (revision 663)
+++ doc/groups.dox (revision 735)
@@ 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/full_graph.h
===================================================================
 lemon/full_graph.h (revision 617)
+++ lemon/full_graph.h (revision 735)
@@ 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 617)
+++ lemon/grid_graph.h (revision 735)
@@ 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 617)
+++ lemon/hypercube_graph.h (revision 735)
@@ 283,15 +283,18 @@
/// \brief Hypercube graph class
///
 /// This class implements a special graph type. The nodes of the graph
 /// are indiced with integers with at most \c dim binary digits.
+ /// HypercubeGraph implements a special graph type. The nodes of the
+ /// graph are indexed with integers having at most \c dim binary digits.
/// Two nodes are connected in the graph if and only if their indices
/// differ only on one position in the binary form.
+ /// This class is completely static and it needs constant memory space.
+ /// Thus you can neither add nor delete nodes or edges.
+ ///
+ /// This type fully conforms to the \ref concepts::Graph "Graph concept".
+ /// Most of its member functions and nested classes are documented
+ /// only in the concept class.
///
/// \note The type of the indices is chosen to \c int for efficiency
/// reasons. Thus the maximum dimension of this implementation is 26
/// (assuming that the size of \c int is 32 bit).
 ///
 /// This graph type fully conforms to the \ref concepts::Graph
 /// "Graph concept".
class HypercubeGraph : public ExtendedHypercubeGraphBase {
typedef ExtendedHypercubeGraphBase Parent;
@@ 321,5 +324,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 +332,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 617)
+++ lemon/list_graph.h (revision 735)
@@ 22,5 +22,5 @@
///\ingroup graphs
///\file
///\brief ListDigraph, ListGraph classes.
+///\brief ListDigraph and ListGraph classes.
#include
@@ 312,29 +312,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 +342,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 +348,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 +357,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 +395,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,84 +408,68 @@
}
 /// 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 \c ArcIt and \c OutArcIt iterators referencing the outgoing
+ ///arcs of node \c n are invalidated. Other iterators remain valid.
+ ///
+ ///\warning This functionality cannot be used together with the
///Snapshot feature.
Node split(Node n, bool connect = true) {
@@ 515,18 +487,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 +541,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 +719,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 +726,28 @@
/// \brief Constructor that immediately makes a snapshot.
///
 /// This constructor immediately makes a snapshot of the digraph.
 /// \param _digraph The digraph we make a snapshot of.
 Snapshot(ListDigraph &_digraph)
+ /// This constructor immediately makes a snapshot of the given digraph.
+ Snapshot(ListDigraph &gr)
: node_observer_proxy(*this),
arc_observer_proxy(*this) {
 attach(_digraph);
+ attach(gr);
}
/// \brief Make a snapshot.
///
 /// Make a snapshot of the digraph.
 ///
 /// This function can be called more than once. In case of a repeated
+ /// This function makes a snapshot of the given digraph.
+ /// It can be called more than once. In case of a repeated
/// call, the previous snapshot gets lost.
 /// \param _digraph The digraph we make the snapshot of.
 void save(ListDigraph &_digraph) {
+ void save(ListDigraph &gr) {
if (attached()) {
detach();
clear();
}
 attach(_digraph);
+ attach(gr);
}
/// \brief Undo the changes until the last snapshot.
 //
 /// Undo the changes until the last snapshot created by save().
+ ///
+ /// This function undos the changes until the last snapshot
+ /// created by save() or Snapshot(ListDigraph&).
void restore() {
detach();
@@ 756,7 +763,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 +802,4 @@
typedef ListGraphBase Graph;

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


ListGraphBase()
@@ 1165,29 +1166,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 +1197,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 +1203,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 +1258,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 +1272,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 +1304,11 @@
}
+ ///Clear the graph.
+
+ ///This function erases all nodes and arcs from the graph.
+ ///
+ void clear() {
+ Parent::clear();
+ }
/// \brief Class to make a snapshot of the graph and restore
@@ 1317,7 +1320,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 +1498,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 +1505,28 @@
/// \brief Constructor that immediately makes a snapshot.
///
 /// This constructor immediately makes a snapshot of the graph.
 /// \param _graph The graph we make a snapshot of.
 Snapshot(ListGraph &_graph)
+ /// This constructor immediately makes a snapshot of the given graph.
+ Snapshot(ListGraph &gr)
: node_observer_proxy(*this),
edge_observer_proxy(*this) {
 attach(_graph);
+ attach(gr);
}
/// \brief Make a snapshot.
///
 /// Make a snapshot of the graph.
 ///
 /// This function can be called more than once. In case of a repeated
+ /// This function makes a snapshot of the given graph.
+ /// It can be called more than once. In case of a repeated
/// call, the previous snapshot gets lost.
 /// \param _graph The graph we make the snapshot of.
 void save(ListGraph &_graph) {
+ void save(ListGraph &gr) {
if (attached()) {
detach();
clear();
}
 attach(_graph);
+ attach(gr);
}
/// \brief Undo the changes until the last snapshot.
 //
 /// Undo the changes until the last snapshot created by save().
+ ///
+ /// This function undos the changes until the last snapshot
+ /// created by save() or Snapshot(ListGraph&).
void restore() {
detach();
@@ 1535,7 +1542,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 617)
+++ lemon/smart_graph.h (revision 735)
@@ 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,49 +641,50 @@
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() {
@@ 743,19 +730,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 +757,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()
{