diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -636,8 +636,8 @@ @ingroup concept \brief Skeleton and concept checking classes for graph structures -This group contains the skeletons and concept checking classes of LEMON's -graph structures and helper classes used to implement these. +This group contains the skeletons and concept checking classes of +graph structures. */ /** diff --git a/lemon/full_graph.h b/lemon/full_graph.h --- a/lemon/full_graph.h +++ b/lemon/full_graph.h @@ -24,7 +24,7 @@ ///\ingroup graphs ///\file -///\brief FullGraph and FullDigraph classes. +///\brief FullDigraph and FullGraph classes. namespace lemon { @@ -148,24 +148,26 @@ /// \ingroup graphs /// - /// \brief A full digraph class. + /// \brief A directed full graph class. /// - /// This is a simple and fast directed full graph implementation. - /// From each node go arcs to each node (including the source node), - /// therefore the number of the arcs in the digraph is the square of - /// the node number. This digraph type is completely static, so you - /// can neither add nor delete either arcs or nodes, and it needs - /// constant space in memory. + /// FullDigraph is a simple and fast implmenetation of directed full + /// (complete) graphs. It contains an arc from each node to each node + /// (including a loop for each node), therefore the number of arcs + /// is the square of the number of nodes. + /// This class is completely static and it needs constant memory space. + /// Thus you can neither add nor delete nodes or arcs, however + /// the structure can be resized using resize(). /// - /// This class fully conforms to the \ref concepts::Digraph - /// "Digraph concept". + /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". + /// Most of its member functions and nested classes are documented + /// only in the concept class. /// - /// The \c FullDigraph and \c FullGraph classes are very similar, + /// \note FullDigraph and FullGraph classes are very similar, /// but there are two differences. While this class conforms only - /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph - /// class conforms to the \ref concepts::Graph "Graph" concept, - /// moreover \c FullGraph does not contain a loop arc for each - /// node as \c FullDigraph does. + /// to the \ref concepts::Digraph "Digraph" concept, FullGraph + /// conforms to the \ref concepts::Graph "Graph" concept, + /// moreover FullGraph does not contain a loop for each + /// node as this class does. /// /// \sa FullGraph class FullDigraph : public ExtendedFullDigraphBase { @@ -173,7 +175,9 @@ public: - /// \brief Constructor + /// \brief Default constructor. + /// + /// Default constructor. The number of nodes and arcs will be zero. FullDigraph() { construct(0); } /// \brief Constructor @@ -184,8 +188,8 @@ /// \brief Resizes the digraph /// - /// Resizes the digraph. The function will fully destroy and - /// rebuild the digraph. This cause that the maps of the digraph will + /// This function resizes the digraph. It fully destroys and + /// rebuilds the structure, therefore the maps of the digraph will be /// reallocated automatically and the previous values will be lost. void resize(int n) { Parent::notifier(Arc()).clear(); @@ -197,24 +201,24 @@ /// \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); } /// \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); } @@ -520,21 +524,23 @@ /// /// \brief An undirected full graph class. /// - /// This is a simple and fast undirected full graph - /// implementation. From each node go edge to each other node, - /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. - /// This graph type is completely static, so you can neither - /// add nor delete either edges or nodes, and it needs constant - /// space in memory. + /// FullGraph is a simple and fast implmenetation of undirected full + /// (complete) graphs. It contains an edge between every distinct pair + /// of nodes, therefore the number of edges is n(n-1)/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 class fully conforms to the \ref concepts::Graph "Graph concept". + /// This type fully conforms to the \ref concepts::Graph "Graph concept". + /// Most of its member functions and nested classes are documented + /// only in the concept class. /// - /// The \c FullGraph and \c FullDigraph classes are very similar, - /// but there are two differences. While the \c FullDigraph class + /// \note FullDigraph and FullGraph classes are very similar, + /// but there are two differences. While FullDigraph /// conforms only to the \ref concepts::Digraph "Digraph" concept, /// this class conforms to the \ref concepts::Graph "Graph" concept, - /// moreover \c FullGraph does not contain a loop arc for each - /// node as \c FullDigraph does. + /// moreover this class does not contain a loop for each + /// node as FullDigraph does. /// /// \sa FullDigraph class FullGraph : public ExtendedFullGraphBase { @@ -542,7 +548,9 @@ public: - /// \brief Constructor + /// \brief Default constructor. + /// + /// Default constructor. The number of nodes and edges will be zero. FullGraph() { construct(0); } /// \brief Constructor @@ -553,8 +561,8 @@ /// \brief Resizes the graph /// - /// Resizes the graph. The function will fully destroy and - /// rebuild the graph. This cause that the maps of the graph will + /// This function resizes the graph. It fully destroys and + /// rebuilds the structure, therefore the maps of the graph will be /// reallocated automatically and the previous values will be lost. void resize(int n) { Parent::notifier(Arc()).clear(); @@ -568,31 +576,31 @@ /// \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); } /// \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. + /// \brief Returns the edge connecting the given nodes. /// - /// Returns the edge connects the given nodes. - Edge edge(const Node& u, const Node& v) const { + /// Returns the edge connecting the given nodes. + Edge edge(Node u, Node v) const { return Parent::edge(u, v); } diff --git a/lemon/grid_graph.h b/lemon/grid_graph.h --- a/lemon/grid_graph.h +++ b/lemon/grid_graph.h @@ -470,18 +470,22 @@ /// /// \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 bottom-left corner is the /// origin. /// + /// This class is completely static and it needs constant memory space. + /// Thus you can neither add nor delete nodes or edges, however + /// the structure can be resized using resize(). + /// /// \image html grid_graph.png /// \image latex grid_graph.eps "Grid graph" width=\textwidth /// @@ -496,16 +500,19 @@ /// } ///\endcode /// - /// This graph type fully conforms to the \ref concepts::Graph - /// "Graph concept". + /// This type fully conforms to the \ref concepts::Graph "Graph concept". + /// Most of its member functions and nested classes are documented + /// only in the concept class. class GridGraph : public ExtendedGridGraphBase { typedef ExtendedGridGraphBase Parent; public: - /// \brief Map to get the indices of the nodes as dim2::Point. + /// \brief Map to get the indices of the nodes as \ref dim2::Point + /// "dim2::Point". /// - /// Map to get the indices of the nodes as dim2::Point. + /// Map to get the indices of the nodes as \ref dim2::Point + /// "dim2::Point". class IndexMap { public: /// \brief The key type of the map @@ -514,13 +521,9 @@ typedef dim2::Point Value; /// \brief Constructor - /// - /// Constructor IndexMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator - /// - /// The subscript operator. Value operator[](Key key) const { return _graph.pos(key); } @@ -540,13 +543,9 @@ typedef int Value; /// \brief Constructor - /// - /// Constructor ColMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator - /// - /// The subscript operator. Value operator[](Key key) const { return _graph.col(key); } @@ -566,13 +565,9 @@ typedef int Value; /// \brief Constructor - /// - /// Constructor RowMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator - /// - /// The subscript operator. Value operator[](Key key) const { return _graph.row(key); } @@ -583,15 +578,14 @@ /// \brief Constructor /// - /// Construct a grid graph with given size. + /// Construct a grid graph with the given size. GridGraph(int width, int height) { construct(width, height); } - /// \brief Resize the graph + /// \brief Resizes the graph /// - /// Resize the graph. The function will fully destroy and rebuild - /// the graph. This cause that the maps of the graph will - /// reallocated automatically and the previous values will be - /// lost. + /// This function resizes the graph. It fully destroys and + /// rebuilds the structure, therefore the maps of the graph will be + /// reallocated automatically and the previous values will be lost. void resize(int width, int height) { Parent::notifier(Arc()).clear(); Parent::notifier(Edge()).clear(); @@ -609,42 +603,42 @@ return Parent::operator()(i, j); } - /// \brief Gives back the column index of the node. + /// \brief The column index of the node. /// /// Gives back the column index of the node. int col(Node n) const { return Parent::col(n); } - /// \brief Gives back the row index of the node. + /// \brief The row index of the node. /// /// Gives back the row index of the node. int row(Node n) const { return Parent::row(n); } - /// \brief Gives back the position of the node. + /// \brief The position of the node. /// /// Gives back the position of the node, ie. the (col,row) pair. dim2::Point pos(Node n) const { return Parent::pos(n); } - /// \brief Gives back the number of the columns. + /// \brief The number of the columns. /// /// Gives back the number of the columns. int width() const { return Parent::width(); } - /// \brief Gives back the number of the rows. + /// \brief The number of the rows. /// /// Gives back the number of the rows. int height() const { return Parent::height(); } - /// \brief Gives back the arc goes right from the node. + /// \brief The arc goes right from the node. /// /// Gives back the arc goes right from the node. If there is not /// outgoing arc then it gives back INVALID. @@ -652,7 +646,7 @@ return Parent::right(n); } - /// \brief Gives back the arc goes left from the node. + /// \brief The arc goes left from the node. /// /// Gives back the arc goes left from the node. If there is not /// outgoing arc then it gives back INVALID. @@ -660,7 +654,7 @@ return Parent::left(n); } - /// \brief Gives back the arc goes up from the node. + /// \brief The arc goes up from the node. /// /// Gives back the arc goes up from the node. If there is not /// outgoing arc then it gives back INVALID. @@ -668,7 +662,7 @@ return Parent::up(n); } - /// \brief Gives back the arc goes down from the node. + /// \brief The arc goes down from the node. /// /// Gives back the arc goes down from the node. If there is not /// outgoing arc then it gives back INVALID. diff --git a/lemon/hypercube_graph.h b/lemon/hypercube_graph.h --- a/lemon/hypercube_graph.h +++ b/lemon/hypercube_graph.h @@ -282,17 +282,20 @@ /// /// \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; @@ -320,7 +323,7 @@ /// \brief The dimension id of an edge. /// /// Gives back the dimension id of the given edge. - /// It is in the [0..dim-1] range. + /// It is in the range [0..dim-1]. int dimension(Edge edge) const { return Parent::dimension(edge); } @@ -328,7 +331,7 @@ /// \brief The dimension id of an arc. /// /// Gives back the dimension id of the given arc. - /// It is in the [0..dim-1] range. + /// It is in the range [0..dim-1]. int dimension(Arc arc) const { return Parent::dimension(arc); } diff --git a/lemon/list_graph.h b/lemon/list_graph.h --- a/lemon/list_graph.h +++ b/lemon/list_graph.h @@ -21,7 +21,7 @@ ///\ingroup graphs ///\file -///\brief ListDigraph, ListGraph classes. +///\brief ListDigraph and ListGraph classes. #include #include @@ -311,31 +311,25 @@ ///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: @@ -347,71 +341,65 @@ ///Add a new node to the digraph. - ///Add a new node to the digraph. + ///This function adds a new node to the digraph. ///\return The new node. Node addNode() { return Parent::addNode(); } ///Add a new arc to the digraph. - ///Add a new arc to the digraph with source node \c s + ///This function adds a new arc to the digraph with source node \c s ///and target node \c t. ///\return The new arc. - Arc addArc(const Node& s, const Node& t) { + Arc addArc(Node s, Node t) { return Parent::addArc(s, t); } ///\brief Erase a node from the digraph. /// - ///Erase a node from the digraph. - /// - void erase(const Node& n) { Parent::erase(n); } + ///This function erases the given node from the digraph. + void erase(Node n) { Parent::erase(n); } ///\brief Erase an arc from the digraph. /// - ///Erase an arc from the digraph. - /// - void erase(const Arc& a) { Parent::erase(a); } + ///This function erases the given arc from the digraph. + void erase(Arc a) { Parent::erase(a); } /// Node validity check - /// This function gives back true if the given node is valid, - /// ie. it is a real node of the graph. + /// This function gives back \c true if the given node is valid, + /// i.e. it is a real node of the digraph. /// - /// \warning A Node pointing to a removed item - /// could become valid again later if new nodes are - /// added to the graph. + /// \warning A removed node could become valid again if new nodes are + /// added to the digraph. bool valid(Node n) const { return Parent::valid(n); } /// Arc validity check - /// This function gives back true if the given arc is valid, - /// ie. it is a real arc of the graph. + /// This function gives back \c true if the given arc is valid, + /// i.e. it is a real arc of the digraph. /// - /// \warning An Arc pointing to a removed item - /// could become valid again later if new nodes are - /// added to the graph. + /// \warning A removed arc could become valid again if new arcs are + /// added to the digraph. bool valid(Arc a) const { return Parent::valid(a); } - /// Change the target of \c a to \c n + /// Change the target node of an arc - /// Change the target of \c a to \c n + /// This function changes the target node of the given arc \c a to \c n. /// - ///\note The ArcIts and OutArcIts referencing - ///the changed arc remain valid. However InArcIts are - ///invalidated. + ///\note \c ArcIt and \c OutArcIt iterators referencing the changed + ///arc remain valid, however \c InArcIt iterators are invalidated. /// ///\warning This functionality cannot be used together with the Snapshot ///feature. void changeTarget(Arc a, Node n) { Parent::changeTarget(a,n); } - /// Change the source of \c a to \c n + /// Change the source node of an arc - /// Change the source of \c a to \c n + /// This function changes the source node of the given arc \c a to \c n. /// - ///\note The InArcIts referencing the changed arc remain - ///valid. However the ArcIts and OutArcIts are - ///invalidated. + ///\note \c InArcIt iterators referencing the changed arc remain + ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated. /// ///\warning This functionality cannot be used together with the Snapshot ///feature. @@ -419,86 +407,70 @@ Parent::changeSource(a,n); } - /// Invert the direction of an arc. + /// Reverse the direction of an arc. - ///\note The ArcIts referencing the changed arc remain - ///valid. However OutArcIts and InArcIts are - ///invalidated. + /// This function reverses the direction of the given arc. + ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing + ///the changed arc are invalidated. /// ///\warning This functionality cannot be used together with the Snapshot ///feature. - void reverseArc(Arc e) { - Node t=target(e); - changeTarget(e,source(e)); - changeSource(e,t); + void reverseArc(Arc a) { + Node t=target(a); + changeTarget(a,source(a)); + changeSource(a,t); } - /// Reserve memory for nodes. - - /// Using this function it is possible to avoid the superfluous memory - /// allocation: if you know that the digraph you want to build will - /// be very large (e.g. it will contain millions of nodes and/or arcs) - /// then it is worth reserving space for this amount before starting - /// to build the digraph. - /// \sa reserveArc - void reserveNode(int n) { nodes.reserve(n); }; - - /// Reserve memory for arcs. - - /// Using this function it is possible to avoid the superfluous memory - /// allocation: if you know that the digraph you want to build will - /// be very large (e.g. it will contain millions of nodes and/or arcs) - /// then it is worth reserving space for this amount before starting - /// to build the digraph. - /// \sa reserveNode - void reserveArc(int m) { arcs.reserve(m); }; - ///Contract two nodes. - ///This function contracts two nodes. - ///Node \p b will be removed but instead of deleting - ///incident arcs, they will be joined to \p a. - ///The last parameter \p r controls whether to remove loops. \c true - ///means that loops will be removed. + ///This function contracts the given two nodes. + ///Node \c v is removed, but instead of deleting its + ///incident arcs, they are joined to node \c u. + ///If the last parameter \c r is \c true (this is the default value), + ///then the newly created loops are removed. /// - ///\note The ArcIts referencing a moved arc remain - ///valid. However InArcIts and OutArcIts - ///may be invalidated. + ///\note The moved arcs are joined to node \c u using changeSource() + ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are + ///invalidated for the outgoing arcs of node \c v and \c InArcIt + ///iterators are invalidated for the incomming arcs of \c v. + ///Moreover all iterators referencing node \c v or the removed + ///loops are also invalidated. Other iterators remain valid. /// ///\warning This functionality cannot be used together with the Snapshot ///feature. - void contract(Node a, Node b, bool r = true) + void contract(Node u, Node v, bool r = true) { - for(OutArcIt e(*this,b);e!=INVALID;) { + for(OutArcIt e(*this,v);e!=INVALID;) { OutArcIt f=e; ++f; - if(r && target(e)==a) erase(e); - else changeSource(e,a); + if(r && target(e)==u) erase(e); + else changeSource(e,u); e=f; } - for(InArcIt e(*this,b);e!=INVALID;) { + for(InArcIt e(*this,v);e!=INVALID;) { InArcIt f=e; ++f; - if(r && source(e)==a) erase(e); - else changeTarget(e,a); + if(r && source(e)==u) erase(e); + else changeTarget(e,u); e=f; } - erase(b); + erase(v); } ///Split a node. - ///This function splits a node. First a new node is added to the digraph, - ///then the source of each outgoing arc of \c n is moved to this new node. - ///If \c connect is \c true (this is the default value), then a new arc - ///from \c n to the newly created node is also added. + ///This function splits the given node. First, a new node is added + ///to the digraph, then the source of each outgoing arc of node \c n + ///is moved to this new node. + ///If the second parameter \c connect is \c true (this is the default + ///value), then a new arc from node \c n to the newly created node + ///is also added. ///\return The newly created node. /// - ///\note The ArcIts referencing a moved arc remain - ///valid. However InArcIts and OutArcIts may - ///be invalidated. + ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing + ///arcs of node \c n are invalidated. Other iterators remain valid. /// - ///\warning This functionality cannot be used in conjunction with the + ///\warning This functionality cannot be used together with the ///Snapshot feature. Node split(Node n, bool connect = true) { Node b = addNode(); @@ -514,21 +486,52 @@ ///Split an arc. - ///This function splits an arc. First a new node \c b is added to - ///the digraph, then the original arc is re-targeted to \c - ///b. Finally an arc from \c b to the original target is added. + ///This function splits the given arc. First, a new node \c v is + ///added to the digraph, then the target node of the original arc + ///is set to \c v. Finally, an arc from \c v to the original target + ///is added. + ///\return The newly created node. /// - ///\return The newly created node. + ///\note \c InArcIt iterators referencing the original arc are + ///invalidated. Other iterators remain valid. /// ///\warning This functionality cannot be used together with the ///Snapshot feature. - Node split(Arc e) { - Node b = addNode(); - addArc(b,target(e)); - changeTarget(e,b); - return b; + Node split(Arc a) { + Node v = addNode(); + addArc(v,target(a)); + changeTarget(a,v); + return v; } + ///Clear the digraph. + + ///This function erases all nodes and arcs from the digraph. + /// + void clear() { + Parent::clear(); + } + + /// Reserve memory for nodes. + + /// Using this function, it is possible to avoid superfluous memory + /// allocation: if you know that the digraph you want to build will + /// be large (e.g. it will contain millions of nodes and/or arcs), + /// then it is worth reserving space for this amount before starting + /// to build the digraph. + /// \sa reserveArc() + void reserveNode(int n) { nodes.reserve(n); }; + + /// Reserve memory for arcs. + + /// Using this function, it is possible to avoid superfluous memory + /// allocation: if you know that the digraph you want to build will + /// be large (e.g. it will contain millions of nodes and/or arcs), + /// then it is worth reserving space for this amount before starting + /// to build the digraph. + /// \sa reserveNode() + void reserveArc(int m) { arcs.reserve(m); }; + /// \brief Class to make a snapshot of the digraph and restore /// it later. /// @@ -537,9 +540,15 @@ /// The newly added nodes and arcs can be removed using the /// restore() function. /// - /// \warning Arc and node deletions and other modifications (e.g. - /// contracting, splitting, reversing arcs or nodes) cannot be + /// \note After a state is restored, you cannot restore a later state, + /// i.e. you cannot add the removed nodes and arcs again using + /// another Snapshot instance. + /// + /// \warning Node and arc deletions and other modifications (e.g. + /// reversing, contracting, splitting arcs or nodes) cannot be /// restored. These events invalidate the snapshot. + /// However the arcs and nodes that were added to the digraph after + /// making the current snapshot can be removed without invalidating it. class Snapshot { protected: @@ -709,39 +718,37 @@ /// \brief Default constructor. /// /// Default constructor. - /// To actually make a snapshot you must call save(). + /// You have to call save() to actually make a snapshot. Snapshot() : digraph(0), node_observer_proxy(*this), arc_observer_proxy(*this) {} /// \brief Constructor that immediately makes a snapshot. /// - /// This constructor immediately makes a snapshot of the digraph. - /// \param _digraph The digraph we make a snapshot of. - Snapshot(ListDigraph &_digraph) + /// This constructor immediately makes a snapshot of the given digraph. + Snapshot(ListDigraph &gr) : node_observer_proxy(*this), arc_observer_proxy(*this) { - attach(_digraph); + attach(gr); } /// \brief Make a snapshot. /// - /// Make a snapshot of the digraph. - /// - /// This function can be called more than once. In case of a repeated + /// This function makes a snapshot of the given digraph. + /// It can be called more than once. In case of a repeated /// call, the previous snapshot gets lost. - /// \param _digraph The digraph we make the snapshot of. - void save(ListDigraph &_digraph) { + void save(ListDigraph &gr) { if (attached()) { detach(); clear(); } - attach(_digraph); + attach(gr); } /// \brief Undo the changes until the last snapshot. - // - /// Undo the changes until the last snapshot created by save(). + /// + /// This function undos the changes until the last snapshot + /// created by save() or Snapshot(ListDigraph&). void restore() { detach(); for(std::list::iterator it = added_arcs.begin(); @@ -755,9 +762,9 @@ clear(); } - /// \brief Gives back true when the snapshot is valid. + /// \brief Returns \c true if the snapshot is valid. /// - /// Gives back true when the snapshot is valid. + /// This function returns \c true if the snapshot is valid. bool valid() const { return attached(); } @@ -795,10 +802,6 @@ typedef ListGraphBase Graph; - class Node; - class Arc; - class Edge; - class Node { friend class ListGraphBase; protected: @@ -848,8 +851,6 @@ bool operator<(const Arc& arc) const {return id < arc.id;} }; - - ListGraphBase() : nodes(), first_node(-1), first_free_node(-1), arcs(), first_free_arc(-1) {} @@ -1164,31 +1165,25 @@ ///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: /// Constructor @@ -1201,94 +1196,95 @@ /// \brief Add a new node to the graph. /// - /// Add a new node to the graph. + /// This function adds a new node to the graph. /// \return The new node. Node addNode() { return Parent::addNode(); } /// \brief Add a new edge to the graph. /// - /// Add a new edge to the graph with source node \c s - /// and target node \c t. + /// This function adds a new edge to the graph between nodes + /// \c u and \c v with inherent orientation from node \c u to + /// node \c v. /// \return The new edge. - Edge addEdge(const Node& s, const Node& t) { - return Parent::addEdge(s, t); + Edge addEdge(Node u, Node v) { + return Parent::addEdge(u, v); } - /// \brief Erase a node from the graph. + ///\brief Erase a node from the graph. /// - /// Erase a node from the graph. + /// This function erases the given node from the graph. + void erase(Node n) { Parent::erase(n); } + + ///\brief Erase an edge from the graph. /// - void erase(const Node& n) { Parent::erase(n); } - - /// \brief Erase an edge from the graph. - /// - /// Erase an edge from the graph. - /// - void erase(const Edge& e) { Parent::erase(e); } + /// This function erases the given edge from the graph. + void erase(Edge e) { Parent::erase(e); } /// Node validity check - /// This function gives back true if the given node is valid, - /// ie. it is a real node of the graph. + /// This function gives back \c true if the given node is valid, + /// i.e. it is a real node of the graph. /// - /// \warning A Node pointing to a removed item - /// could become valid again later if new nodes are + /// \warning A removed node could become valid again if new nodes are /// added to the graph. bool valid(Node n) const { return Parent::valid(n); } + /// Edge validity check + + /// This function gives back \c true if the given edge is valid, + /// i.e. it is a real edge of the graph. + /// + /// \warning A removed edge could become valid again if new edges are + /// added to the graph. + bool valid(Edge e) const { return Parent::valid(e); } /// Arc validity check - /// This function gives back true if the given arc is valid, - /// ie. it is a real arc of the graph. + /// This function gives back \c true if the given arc is valid, + /// i.e. it is a real arc of the graph. /// - /// \warning An Arc pointing to a removed item - /// could become valid again later if new edges are + /// \warning A removed arc could become valid again if new edges are /// added to the graph. bool valid(Arc a) const { return Parent::valid(a); } - /// Edge validity check - /// This function gives back true if the given edge is valid, - /// ie. it is a real arc of the graph. + /// \brief Change the first node of an edge. /// - /// \warning A Edge pointing to a removed item - /// could become valid again later if new edges are - /// added to the graph. - bool valid(Edge e) const { return Parent::valid(e); } - /// \brief Change the end \c u of \c e to \c n + /// This function changes the first node of the given edge \c e to \c n. /// - /// This function changes the end \c u of \c e to node \c n. - /// - ///\note The 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. + ///\note \c EdgeIt and \c ArcIt iterators referencing the + ///changed edge are invalidated and all other iterators whose + ///base node is the changed node are also invalidated. /// ///\warning This functionality cannot be used together with the ///Snapshot feature. void changeU(Edge e, Node n) { Parent::changeU(e,n); } - /// \brief Change the end \c v of \c e to \c n + /// \brief Change the second node of an edge. /// - /// This function changes the end \c v of \c e to \c n. + /// This function changes the second node of the given edge \c e to \c n. /// - ///\note The 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. + ///\note \c EdgeIt iterators referencing the changed edge remain + ///valid, however \c ArcIt iterators referencing the changed edge and + ///all other iterators whose base node is the changed node are also + ///invalidated. /// ///\warning This functionality cannot be used together with the ///Snapshot feature. void changeV(Edge e, Node n) { Parent::changeV(e,n); } + /// \brief Contract two nodes. /// - /// This function contracts two nodes. - /// Node \p b will be removed but instead of deleting - /// its neighboring arcs, they will be joined to \p a. - /// The last parameter \p r controls whether to remove loops. \c true - /// means that loops will be removed. + /// This function contracts the given two nodes. + /// Node \c b is removed, but instead of deleting + /// its incident edges, they are joined to node \c a. + /// If the last parameter \c r is \c true (this is the default value), + /// then the newly created loops are removed. /// - /// \note The ArcIts referencing a moved arc remain - /// valid. + /// \note The moved edges are joined to node \c a using changeU() + /// or changeV(), thus all edge and arc iterators whose base node is + /// \c b are invalidated. + /// Moreover all iterators referencing node \c b or the removed + /// loops are also invalidated. Other iterators remain valid. /// ///\warning This functionality cannot be used together with the ///Snapshot feature. @@ -1307,6 +1303,13 @@ erase(b); } + ///Clear the graph. + + ///This function erases all nodes and arcs from the graph. + /// + void clear() { + Parent::clear(); + } /// \brief Class to make a snapshot of the graph and restore /// it later. @@ -1316,9 +1319,15 @@ /// The newly added nodes and edges can be removed /// using the restore() function. /// - /// \warning Edge and node deletions and other modifications - /// (e.g. changing nodes of edges, contracting nodes) cannot be - /// restored. These events invalidate the snapshot. + /// \note After a state is restored, you cannot restore a later state, + /// i.e. you cannot add the removed nodes and edges again using + /// another Snapshot instance. + /// + /// \warning Node and edge deletions and other modifications + /// (e.g. changing the end-nodes of edges or contracting nodes) + /// cannot be restored. These events invalidate the snapshot. + /// However the edges and nodes that were added to the graph after + /// making the current snapshot can be removed without invalidating it. class Snapshot { protected: @@ -1488,39 +1497,37 @@ /// \brief Default constructor. /// /// Default constructor. - /// To actually make a snapshot you must call save(). + /// You have to call save() to actually make a snapshot. Snapshot() : graph(0), node_observer_proxy(*this), edge_observer_proxy(*this) {} /// \brief Constructor that immediately makes a snapshot. /// - /// This constructor immediately makes a snapshot of the graph. - /// \param _graph The graph we make a snapshot of. - Snapshot(ListGraph &_graph) + /// This constructor immediately makes a snapshot of the given graph. + Snapshot(ListGraph &gr) : node_observer_proxy(*this), edge_observer_proxy(*this) { - attach(_graph); + attach(gr); } /// \brief Make a snapshot. /// - /// Make a snapshot of the graph. - /// - /// This function can be called more than once. In case of a repeated + /// This function makes a snapshot of the given graph. + /// It can be called more than once. In case of a repeated /// call, the previous snapshot gets lost. - /// \param _graph The graph we make the snapshot of. - void save(ListGraph &_graph) { + void save(ListGraph &gr) { if (attached()) { detach(); clear(); } - attach(_graph); + attach(gr); } /// \brief Undo the changes until the last snapshot. - // - /// Undo the changes until the last snapshot created by save(). + /// + /// This function undos the changes until the last snapshot + /// created by save() or Snapshot(ListGraph&). void restore() { detach(); for(std::list::iterator it = added_edges.begin(); @@ -1534,9 +1541,9 @@ clear(); } - /// \brief Gives back true when the snapshot is valid. + /// \brief Returns \c true if the snapshot is valid. /// - /// Gives back true when the snapshot is valid. + /// This function returns \c true if the snapshot is valid. bool valid() const { return attached(); } diff --git a/lemon/smart_graph.h b/lemon/smart_graph.h --- a/lemon/smart_graph.h +++ b/lemon/smart_graph.h @@ -32,10 +32,7 @@ namespace lemon { class SmartDigraph; - ///Base of SmartDigraph - ///Base of SmartDigraph - /// class SmartDigraphBase { protected: @@ -187,28 +184,26 @@ /// ///\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 stack-like) - ///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 &) {} public: @@ -221,79 +216,49 @@ ///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. Node split(Node n, bool connect = true) @@ -308,6 +273,34 @@ return b; } + ///Clear the digraph. + + ///This function erases all nodes and arcs from the digraph. + /// + void clear() { + Parent::clear(); + } + + /// Reserve memory for nodes. + + /// Using this function, it is possible to avoid superfluous memory + /// allocation: if you know that the digraph you want to build will + /// be large (e.g. it will contain millions of nodes and/or arcs), + /// then it is worth reserving space for this amount before starting + /// to build the digraph. + /// \sa reserveArc() + void reserveNode(int n) { nodes.reserve(n); }; + + /// Reserve memory for arcs. + + /// Using this function, it is possible to avoid superfluous memory + /// allocation: if you know that the digraph you want to build will + /// be large (e.g. it will contain millions of nodes and/or arcs), + /// then it is worth reserving space for this amount before starting + /// to build the digraph. + /// \sa reserveNode() + void reserveArc(int m) { arcs.reserve(m); }; + public: class Snapshot; @@ -332,20 +325,23 @@ public: - ///Class to make a snapshot of the digraph and to restrore to it later. + ///Class to make a snapshot of the digraph and to restore it later. - ///Class to make a snapshot of the digraph and to restrore to it later. + ///Class to make a snapshot of the digraph and to restore it later. /// ///The newly added nodes and arcs can be removed using the - ///restore() function. - ///\note After you restore a state, you cannot restore - ///a later state, in other word you cannot add again the arcs deleted - ///by restore() using another one Snapshot instance. + ///restore() function. This is the only way for deleting nodes and/or + ///arcs from a SmartDigraph structure. /// - ///\warning If you do not use correctly the snapshot that can cause - ///either broken program, invalid state of the digraph, valid but - ///not the restored digraph or no change. Because the runtime performance - ///the validity of the snapshot is not stored. + ///\note After a state is restored, you cannot restore a later state, + ///i.e. you cannot add the removed nodes and arcs again using + ///another Snapshot instance. + /// + ///\warning Node splitting cannot be restored. + ///\warning The validity of the snapshot is not stored due to + ///performance reasons. If you do not use the snapshot correctly, + ///it can cause broken program, invalid or not restored state of + ///the digraph or no change. class Snapshot { SmartDigraph *_graph; @@ -357,39 +353,32 @@ ///Default constructor. ///Default constructor. - ///To actually make a snapshot you must call save(). - /// + ///You have to call save() to actually make a snapshot. Snapshot() : _graph(0) {} ///Constructor that immediately makes a snapshot - ///This constructor immediately makes a snapshot of the digraph. - ///\param graph The digraph we make a snapshot of. - Snapshot(SmartDigraph &graph) : _graph(&graph) { + ///This constructor immediately makes a snapshot of the given digraph. + /// + Snapshot(SmartDigraph &gr) : _graph(&gr) { node_num=_graph->nodes.size(); arc_num=_graph->arcs.size(); } ///Make a snapshot. - ///Make a snapshot of the digraph. - /// - ///This function can be called more than once. In case of a repeated + ///This function makes a snapshot of the given digraph. + ///It can be called more than once. In case of a repeated ///call, the previous snapshot gets lost. - ///\param graph The digraph we make the snapshot of. - void save(SmartDigraph &graph) - { - _graph=&graph; + void save(SmartDigraph &gr) { + _graph=&gr; node_num=_graph->nodes.size(); arc_num=_graph->arcs.size(); } ///Undo the changes until a snapshot. - ///Undo the changes until a snapshot created by save(). - /// - ///\note After you restored a state, you cannot restore - ///a later state, in other word you cannot add again the arcs deleted - ///by restore(). + ///This function undos the changes until the last snapshot + ///created by save() or Snapshot(SmartDigraph&). void restore() { _graph->restoreSnapshot(*this); @@ -621,29 +610,26 @@ /// /// \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 stack-like) - /// 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 &) {} public: @@ -654,51 +640,52 @@ /// 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(); @@ -742,21 +729,22 @@ public: - ///Class to make a snapshot of the digraph and to restrore to it later. + ///Class to make a snapshot of the graph and to restore it later. - ///Class to make a snapshot of the digraph and to restrore to it later. + ///Class to make a snapshot of the graph and to restore it later. /// - ///The newly added nodes and arcs can be removed using the - ///restore() function. + ///The newly added nodes and edges can be removed using the + ///restore() function. This is the only way for deleting nodes and/or + ///edges from a SmartGraph structure. /// - ///\note After you restore a state, you cannot restore - ///a later state, in other word you cannot add again the arcs deleted - ///by restore() using another one Snapshot instance. + ///\note After a state is restored, you cannot restore a later state, + ///i.e. you cannot add the removed nodes and edges again using + ///another Snapshot instance. /// - ///\warning If you do not use correctly the snapshot that can cause - ///either broken program, invalid state of the digraph, valid but - ///not the restored digraph or no change. Because the runtime performance - ///the validity of the snapshot is not stored. + ///\warning The validity of the snapshot is not stored due to + ///performance reasons. If you do not use the snapshot correctly, + ///it can cause broken program, invalid or not restored state of + ///the graph or no change. class Snapshot { SmartGraph *_graph; @@ -768,36 +756,30 @@ ///Default constructor. ///Default constructor. - ///To actually make a snapshot you must call save(). - /// + ///You have to call save() to actually make a snapshot. Snapshot() : _graph(0) {} ///Constructor that immediately makes a snapshot - ///This constructor immediately makes a snapshot of the digraph. - ///\param graph The digraph we make a snapshot of. - Snapshot(SmartGraph &graph) { - graph.saveSnapshot(*this); + /// This constructor immediately makes a snapshot of the given graph. + /// + Snapshot(SmartGraph &gr) { + gr.saveSnapshot(*this); } ///Make a snapshot. - ///Make a snapshot of the graph. - /// - ///This function can be called more than once. In case of a repeated + ///This function makes a snapshot of the given graph. + ///It can be called more than once. In case of a repeated ///call, the previous snapshot gets lost. - ///\param graph The digraph we make the snapshot of. - void save(SmartGraph &graph) + void save(SmartGraph &gr) { - graph.saveSnapshot(*this); + gr.saveSnapshot(*this); } - ///Undo the changes until a snapshot. + ///Undo the changes until the last snapshot. - ///Undo the changes until a snapshot created by save(). - /// - ///\note After you restored a state, you cannot restore - ///a later state, in other word you cannot add again the arcs deleted - ///by restore(). + ///This function undos the changes until the last snapshot + ///created by save() or Snapshot(SmartGraph&). void restore() { _graph->restoreSnapshot(*this);